class Rcrypto::SSS
Public Instance Methods
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.
# File lib/rcrypto/sss.rb, line 393 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 negbx = -bx # (0 - bx) axbx = ax - bx # (ax - bx) numerator = (numerator * negbx) % @@prime # (0 - bx) * ... denominator = (denominator * axbx) % @@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
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.
# File lib/rcrypto/sss.rb, line 313 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 subpoly = [] subpoly.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) subpoly.push(x) j += 1 end polynomial.push(subpoly) 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 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
extended gcd
# 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
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
# File lib/rcrypto/sss.rb, line 128 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
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.
# File lib/rcrypto/sss.rb, line 95 def from_base64(number) u8b = Base64.urlsafe_decode64(number) hexdata = u8b_to_hex(u8b) rs = hexdata.to_i(16) rs end
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.
# File lib/rcrypto/sss.rb, line 119 def from_hex(number) rs = number.to_i(16) rs end
Return Uint8Array binary representation of hex string.
# File lib/rcrypto/sss.rb, line 52 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
Convert string to hex.
# File lib/rcrypto/sss.rb, line 36 def hexlify(s) a = [] if s.respond_to? :each_byte s.each_byte { |b| a << sprintf('%02X', b) } else s.each { |b| a << sprintf('%02X', b) } end a.join.downcase end
in_numbers
(numbers, value) returns boolean whether or not value is in array
# File lib/rcrypto/sss.rb, line 189 def in_numbers(numbers, value) for n in numbers return true if n == value end false end
Converts an array of Ints to the original byte array, removing any least significant nulls.
# File lib/rcrypto/sss.rb, line 178 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(hex_data)) hex_data end
Computes the multiplicative inverse of the number on the field PRIME.
# 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
Returns a random number from the range (0, PRIME-1) inclusive
# File lib/rcrypto/sss.rb, line 11 def random_number rand(1...@@prime) end
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.
# File lib/rcrypto/sss.rb, line 142 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
Returns the Int number base10 in base64 representation; note: this is not a string representation; the base64 output is exactly 256 bits long.
# File lib/rcrypto/sss.rb, line 79 def to_base64(number) hexdata = number.to_s(16) n = 64 - hexdata.length i = 0 while i < n hexdata = '0' + hexdata i += 1 end u8b = hex_to_u8b(hexdata) b64data = Base64.urlsafe_encode64(u8b) b64data end
Returns the Int number base10 in Hex representation; note: this is not a string representation; the Hex output is exactly 256 bits long.
# File lib/rcrypto/sss.rb, line 104 def to_hex(number) hexdata = number.to_s(16) # puts hexdata n = 64 - hexdata.length i = 0 while i < n hexdata = '0' + hexdata i += 1 end hexdata end
Remove right character '0'
# File lib/rcrypto/sss.rb, line 167 def trim_right(s) i = s.length - 1 while i >= 0 && s[i] == '0' i -= 1 end rs = s[0..i] rs end
Return hex string representation of Uint8Array binary.
# File lib/rcrypto/sss.rb, line 69 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
Convert hex to string.
# File lib/rcrypto/sss.rb, line 47 def unhexlify(s) s.split.pack('H*') end