Class: Rcrypto::SSS

Inherits:
Object
  • Object
show all
Defined in:
lib/rcrypto/sss.rb

Constant Summary collapse

@@prime =

The largest PRIME 256-bit big.Int primes.utm.edu/lists/2small/200bit.html PRIME = 2^n - k = 2^256 - 189

115792089237316195423570985008687907853269984665640564039457584007913129639747

Instance Method Summary collapse

Instance Method Details

#combine(shares, is_base64 = false) ⇒ Object

Takes a string array of shares encoded in Base64 or Hex created via Shamir’s Algorithm

Note: the polynomial will converge if the specified minimum number of shares
      or more are passed to this function. Passing thus does not affect it
      Passing fewer however, simply means that the returned secret is wrong.



398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
 
# File 'lib/rcrypto/sss.rb', line 398

def combine(shares, is_base64 = false)
  raise Exception('shares is NULL or empty') if shares.empty?

  # Recreate the original object of x, y points, based upon number of shares
  # and size of each share (number of parts in the secret).
  #
  # points[shares][parts][2]
  points = if is_base64
             decode_share_base64(shares)
           else
             decode_share_hex(shares)
           end
  # puts points

  # Use Lagrange Polynomial Interpolation (LPI) to reconstruct the secrets.
  # For each part of the secrets (clearest to iterate over)...
  secrets = []
  for j in 0...(points[0]).length
    secrets.append(0)
    # and every share...
    for i in 0...shares.length  # LPI sum loop
      # remember the current x and y values.
      ax = points[i][j][0]  # ax
      ay = points[i][j][1]  # ay
      numerator = 1  # LPI numerator
      denominator = 1  # LPI denominator
      # and for every other point...
      for k in 0...shares.length  # LPI product loop
        if k != i
          # combine them via half products.
          # x=0 ==> [(0-bx)/(ax-bx)] * ...
          bx = points[k][j][0]  # bx
          numerator = (numerator * -bx) % @@prime  # (0 - bx) * ...
          denominator = (denominator * (ax - bx)) % @@prime  # (ax - bx) * ...
        end
      end
      # LPI product: x=0, y = ay * [(x-bx)/(ax-bx)] * ...
      # multiply together the points (ay)(numerator)(denominator)^-1 ...
      fx = ay
      fx = (fx * numerator) % @@prime
      fx = (fx * modinv(denominator, @@prime)) % @@prime

      # LPI sum: s = fx + fx + ...
      secrets[j] = (secrets[j] + fx) % @@prime
    end
  end
  rs = merge_int_to_string(secrets)
  rs
end

#create(minimum, shares, secret, is_base64 = false) ⇒ Object

Returns a new array of secret shares (encoding x,y pairs as Base64 or Hex strings) created by Shamir’s Secret Sharing Algorithm requiring a minimum number of share to recreate, of length shares, from the input secret raw as a string.



317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
 
# File 'lib/rcrypto/sss.rb', line 317

def create(minimum, shares, secret, is_base64 = false)
  result = []

  # Verify minimum isn't greater than shares; there is no way to recreate
  # the original polynomial in our current setup, therefore it doesn't make
  # sense to generate fewer shares than are needed to reconstruct the secrets.
  if minimum <= 0 || shares <= 0
    raise Exception('minimum or shares is invalid')
  end
  if minimum > shares
    raise Exception('cannot require more shares then existing')
  end
  raise Exception('secret is NULL or empty') if secret.empty?

  # Convert the secrets to its respective 256-bit Int representation.
  secrets = split_secret_to_int(secret)

  # List of currently used numbers in the polynomial
  numbers = [0]

  # Create the polynomial of degree (minimum - 1); that is, the highest
  # order term is (minimum-1), though as there is a constant term with
  # order 0, there are (minimum) number of coefficients.
  #
  # However, the polynomial object is a 2d array, because we are constructing
  # a different polynomial for each part of the secrets.
  #
  # polynomial[parts][minimum]
  polynomial = []
  for i in 0...secrets.length
    sub_poly = []
    sub_poly.push(secrets[i])
    j = 1
    while j < minimum
      # Each coefficient should be unique
      x = random_number()
      while in_numbers(numbers, x)
        x = random_number()
      end

      numbers.append(x)
      sub_poly.push(x)
      j += 1
    end
    polynomial.push(sub_poly)
  end

  # Create the points object; this holds the (x, y) points of each share.
  # Again, because secrets is an array, each share could have multiple parts
  # over which we are computing Shamir's Algorithm. The last dimension is
  # always two, as it is storing an x, y pair of points.
  #
  # Note: this array is technically unnecessary due to creating result
  # in the inner loop. Can disappear later if desired.
  for i in 0...shares
    s = ''
    for j in 0...secrets.length
      # generate a new x-coordinate.
      x = random_number()
      while in_numbers(numbers, x)
        x = random_number()
      end
      numbers.append(x)
      y = evaluate_polynomial(polynomial, j, x)
      if is_base64
        s += to_base64(x)
        s += to_base64(y)
      else
        s += to_hex(x)
        s += to_hex(y)
      end
    end
    result.push(s)
  end
  result
end

#decode_share_base64(shares) ⇒ Object

Takes a string array of shares encoded in Base64Url created via Shamir’s Algorithm; each string must be of equal length of a multiple of 88 characters as a single 88 character share is a pair of 256-bit numbers (x, y).



203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
 
# File 'lib/rcrypto/sss.rb', line 203

def decode_share_base64(shares)
  # Recreate the original object of x, y points, based upon number of shares
  # and size of each share (number of parts in the secret).
  secrets = []

  # For each share...
  for i in 0...shares.length
    # ensure that it is valid.
    unless is_valid_share_base64(shares[i])
      raise Exception('one of the shares is invalid')
    end

    # find the number of parts it represents.
    share = shares[i]
    count = share.length / 88
    arr_sh = []
    # and for each part, find the x,y pair...
    for j in 0...count
      pair = share[j * 88...(j + 1) * 88]
      arr_xy = []
      # decoding from Base64.
      x = from_base64(pair[0...44])
      y = from_base64(pair[44...88])
      arr_xy.push(x)
      arr_xy.push(y)
      arr_sh.push(arr_xy)
    end
    secrets.push(arr_sh)
  end
  secrets
end

#decode_share_hex(shares) ⇒ Object

Takes a string array of shares encoded in Hex created via Shamir’s Algorithm; each string must be of equal length of a multiple of 128 characters as a single 128 character share is a pair of 256-bit numbers (x, y).



260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
 
# File 'lib/rcrypto/sss.rb', line 260

def decode_share_hex(shares)
  # Recreate the original object of x, y points, based upon number of shares
  # and size of each share (number of parts in the secret).
  secrets = []

  # For each share...
  for i in 0...shares.length
    # ensure that it is valid.
    unless is_valid_share_hex(shares[i])
      raise Exception('one of the shares is invalid')
    end

    # find the number of parts it represents.
    share = shares[i]
    count = share.length / 128
    arr_sh = []
    # and for each part, find the x,y pair...
    for j in 0...count
      pair = share[j * 128...(j + 1) * 128]
      arr_xy = []
      # decoding from Hex.
      x = from_hex(pair[0...64])
      y = from_hex(pair[64...128])
      arr_xy.push(x)
      arr_xy.push(y)
      arr_sh.push(arr_xy)
    end
    secrets.push(arr_sh)
  end
  secrets
end

#egcd(a, b) ⇒ Object

extended gcd



16
17
18
19
20
21
22
23
 
# File 'lib/rcrypto/sss.rb', line 16

def egcd(a, b)
  if a == 0
    return b, 0, 1
  else
    g, y, x = egcd(b % a, a)
    return g, x - (b / a) * y, y
  end
end

#evaluate_polynomial(polynomial, part, value) ⇒ Object

Evaluates a polynomial with coefficients specified in reverse order:

evaluatePolynomial([a, b, c, d], x):
    return a + bx + cx^2 + dx^3
Horner's method: ((dx + c)x + b)x + a



123
124
125
126
127
128
129
130
131
132
 
# File 'lib/rcrypto/sss.rb', line 123

def evaluate_polynomial(polynomial, part, value)
  last = polynomial[part].length - 1
  result = polynomial[part][last]
  s = last - 1
  while s >= 0
    result = (result * value + polynomial[part][s]) % @@prime
    s -= 1
  end
  result
end

#from_base64(number) ⇒ Object

Returns the number base64 in base 10 Int representation; note: this is not coming from a string representation; the base64 input is exactly 256 bits long, and the output is an arbitrary size base 10 integer.



90
91
92
93
94
95
 
# File 'lib/rcrypto/sss.rb', line 90

def from_base64(number)
  u8b = Base64.urlsafe_decode64(number)
  hex_data = u8b_to_hex(u8b)
  rs = hex_data.to_i(16)
  rs
end

#from_hex(number) ⇒ Object

Returns the number Hex in base 10 Int representation; note: this is not coming from a string representation; the Hex input is exactly 256 bits long, and the output is an arbitrary size base 10 integer.



114
115
116
117
 
# File 'lib/rcrypto/sss.rb', line 114

def from_hex(number)
  rs = number.to_i(16)
  rs
end

#hex_to_u8b(hex) ⇒ Object

Return Uint8Array binary representation of hex string.



47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
# File 'lib/rcrypto/sss.rb', line 47

def hex_to_u8b(hex)
  u8 = []
  hex = '0' + hex if hex.length.odd?
  len = hex.length / 2
  i = 0
  j = 0
  while i < len
    u8.append((hex[j...j + 2]).to_i(16))
    j += 2
    i += 1
  end
  # uint8_t
  u8b = u8.pack('C*')
  u8b
end

#hexlify(s) ⇒ Object

Convert string to hex.



36
37
38
39
 
# File 'lib/rcrypto/sss.rb', line 36

def hexlify(s)
  a = s.encode("UTF-8").bytes.map { |b| b.to_s(16) }
  a.join.downcase
end

#in_numbers(numbers, value) ⇒ Object

in_numbers(numbers, value) returns boolean whether or not value is in array



193
194
195
196
197
198
 
# File 'lib/rcrypto/sss.rb', line 193

def in_numbers(numbers, value)
  for n in numbers
    return true if n == value
  end
  false
end

#is_valid_share_base64(candidate) ⇒ Object

Takes in a given string to check if it is a valid secret

Requirements:

  Length multiple of 88

Can decode each 44 character block as Bas64Url

Returns only success/failure (bool)



242
243
244
245
246
247
248
249
250
251
252
253
254
255
 
# File 'lib/rcrypto/sss.rb', line 242

def is_valid_share_base64(candidate)
  return false if candidate.length == 0 || candidate.length % 88 != 0

  count = candidate.length / 44
  j = 0
  while j < count
    part = candidate[j * 44...(j + 1) * 44]
    decode = from_base64(part)
    return false if decode <= 0 || decode >= @@prime

    j += 1
  end
  true
end

#is_valid_share_hex(candidate) ⇒ Object

Takes in a given string to check if it is a valid secret

Requirements:

  Length multiple of 128

Can decode each 64 character block as Hex

Returns only success/failure (bool)



299
300
301
302
303
304
305
306
307
308
309
310
311
312
 
# File 'lib/rcrypto/sss.rb', line 299

def is_valid_share_hex(candidate)
  return false if candidate.length == 0 || candidate.length % 128 != 0

  count = candidate.length / 64
  j = 0
  while j < count
    part = candidate[j * 64...(j + 1) * 64]
    decode = from_hex(part)
    return false if decode <= 0 || decode >= @@prime

    j += 1
  end
  return true
end

#merge_int_to_string(secrets) ⇒ Object

Converts an array of Ints to the original byte array, removing any least significant nulls.



182
183
184
185
186
187
188
189
190
 
# File 'lib/rcrypto/sss.rb', line 182

def merge_int_to_string(secrets)
  hex_data = ''
  for s in secrets
    tmp = to_hex(s)
    hex_data += tmp
  end
  hex_data = unhexlify(trim_right_doubled_zero(hex_data))
  hex_data
end

#modinv(a, m) ⇒ Object

Computes the multiplicative inverse of the number on the field PRIME.



26
27
28
29
30
31
32
33
 
# File 'lib/rcrypto/sss.rb', line 26

def modinv(a, m)
  g, x, y = egcd(a, m)
  if g != 1
    raise Exception('modular inverse does not exist')
  else
    return x % m
  end
end

#random_number ⇒ Object

Returns a random number from the range (0, PRIME-1) inclusive



11
12
13
 
# File 'lib/rcrypto/sss.rb', line 11

def random_number
  rand(1...@@prime)
end

#split_secret_to_int(secret) ⇒ Object

Converts a byte array into an a 256-bit Int, array based upon size of the input byte; all values are right-padded to length 256, even if the most significant bit is zero.



137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
 
# File 'lib/rcrypto/sss.rb', line 137

def split_secret_to_int(secret)
  result = []
  hex_data = hexlify(secret)
  count = (hex_data.length / 64.0).ceil
  i = 0
  while i < count
    if (i + 1) * 64 < hex_data.length
      subs = hex_data[i * 64...(i + 1) * 64]
      result.append(subs.to_i(16))
    else
      last = hex_data[i * 64...hex_data.length]
      n = 64 - last.length
      j = 0
      while j < n
        last += '0'
        j += 1
      end
      result.append(last.to_i(16))
    end
    i += 1
  end
  result
end

#to_base64(number) ⇒ Object

Returns the Int number base10 in base64 representation; note: this is not a string representation; the base64 output is exactly 256 bits long.



74
75
76
77
78
79
80
81
82
83
84
85
 
# File 'lib/rcrypto/sss.rb', line 74

def to_base64(number)
  hex_data = number.to_s(16)
  n = 64 - hex_data.length
  i = 0
  while i < n
    hex_data = '0' + hex_data
    i += 1
  end
  u8b = hex_to_u8b(hex_data)
  b64_data = Base64.urlsafe_encode64(u8b)
  b64_data
end

#to_hex(number) ⇒ Object

Returns the Int number base10 in Hex representation; note: this is not a string representation; the Hex output is exactly 256 bits long.



99
100
101
102
103
104
105
106
107
108
109
 
# File 'lib/rcrypto/sss.rb', line 99

def to_hex(number)
  hex_data = number.to_s(16)
  # puts hex_data
  n = 64 - hex_data.length
  i = 0
  while i < n
    hex_data = '0' + hex_data
    i += 1
  end
  hex_data
end

#trim_right_doubled_zero(s) ⇒ Object

Remove right doubled characters ‘0’ (zero byte in hex)



162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
 
# File 'lib/rcrypto/sss.rb', line 162

def trim_right_doubled_zero(s)
  last = s.length
  i = s.length - 1
  while i > 2
    if s[i] == '0' && s[i - 1] == '0'
      last = i - 1
    else
      break
    end
    i -= 2
  end
  if last == s.length
    s
  else
    s[0..(last-1)]
  end
end

#u8b_to_hex(u8b) ⇒ Object

Return hex string representation of Uint8Array binary.



64
65
66
67
68
69
70
 
# File 'lib/rcrypto/sss.rb', line 64

def u8b_to_hex(u8b)
  u8 = u8b.unpack('C*')
  hex = u8.map do |v|
    v.to_s(16).rjust(2, '0')
  end.join
  hex
end

#unhexlify(s) ⇒ Object

Convert hex to string.



42
43
44
 
# File 'lib/rcrypto/sss.rb', line 42

def unhexlify(s)
  s.split.pack('H*').force_encoding("UTF-8")
end