class CloverSplitter
Public Class Methods
divmod(num, den, p)
click to toggle source
# File lib/cloversplitter.rb, line 154 def self.divmod(num, den, p) a, b = egcd(den, p) return num*a end
egcd(a, b)
click to toggle source
# File lib/cloversplitter.rb, line 139 def self.egcd(a, b) # Extended Euclidean algorithm. x, y = 0, 1 last_x, last_y = 1, 0 while b != 0 do quot = a/b a, b = b, a % b x, last_x = last_x-quot*x, x y, last_y = last_y-quot*y, y end return last_x, last_y end
eval_at(poly, x, prime)
click to toggle source
# File lib/cloversplitter.rb, line 29 def self.eval_at(poly, x, prime) # Evaluates polynomial at x (used for share generation). accum = 0 poly.reverse.each do |coeff| accum = ((accum*x)+coeff) % prime end return accum end
int_to_str(a)
click to toggle source
# File lib/cloversplitter.rb, line 65 def self.int_to_str(a) # Turns an integer into a string. # Convert the integer into a string of binary. b = a.to_s(2) # Add zeroes to the start of the string of binary until the length is a multiple of 8. while b.length % 8 != 0 do b = "0"+b end # Convert the string of binary into a list of character values. c = [] c_a = b.chars.each_slice(8).to_a c_a.each do |i| s = String.new() i.each do |j| s << j end c << s.to_i(2) end # Convert the list of character values back into a string. d = String.new() c.each do |i| d << i.chr end # Ignore the first byte (which will always be \x80). d = d[1, d.length-1] return d end
lagrange_interpolate(x, x_s, y_s, p)
click to toggle source
# File lib/cloversplitter.rb, line 182 def self.lagrange_interpolate(x, x_s, y_s, p) k = x_s.length if k != x_s.uniq.length raise("An error occured during lagrange interpolation.") end nums = [] dens = [] (0..k-1).each do |i| others = Array.new(x_s) cur = others.delete_at(i) nums_a = Array.new() dens_a = Array.new() others.each do |o| nums_a << x-o dens_a << cur-o end nums << prod(nums_a) dens << prod(dens_a) end den = prod(dens) num_a = Array.new() (0..(k-1)).each do |i| num_a << divmod(nums[i]*den*y_s[i] % p, dens[i], p) end num = sum(num_a) return (divmod(num, den, p)+p) % p end
prod(vals)
click to toggle source
# File lib/cloversplitter.rb, line 160 def self.prod(vals) # Calculate the product of a list of values. accum = 1 vals.each do |v| accum *= v end return accum end
recover_secret(shares, prime=((2**3217)-1))
click to toggle source
# File lib/cloversplitter.rb, line 215 def self.recover_secret(shares, prime=((2**3217)-1)) # This function takes a list of shares and attempts to recover the secret string from those shares. If the number of shares is below the minimum number of shares required for recovery, the resulting string will be nonsensical and may scramble/gargle the console if printed. On a *nix system, the console can usually be reset with the "reset" command. # shares: A list containing two or more shares. # prime: The prime number that was used for share generation. if shares.length < 2 raise("At least two shares are required in order to attempt secret recovery.") end x_s, y_s = shares.transpose recovered_data = lagrange_interpolate(0, x_s, y_s, prime) return self.int_to_str(recovered_data) end
str_to_int(a)
click to toggle source
# File lib/cloversplitter.rb, line 40 def self.str_to_int(a) # Turns an ASCII-8BIT string into an integer. # Prepend \x80 to the string to prevent information loss occuring for strings that start with \x00. a = "\x80".force_encoding("ASCII-8BIT")+a # Decode string into a list of integers (with one integer representing each character). b = a.each_byte.to_a # Initialise c_b; this will be used to hold bytes (expressed in binary) for each character. c_b = String.new() # Loop through each value in b, appending the corresponding binary sequence for each character to c_b. b.each do |i| n = i.to_s(2) while n.length < 8 do n = "0"+n end c_b += n end # Convert c_b into an integer. c_b.to_i(2) end
sum(vals)
click to toggle source
# File lib/cloversplitter.rb, line 171 def self.sum(vals) # Calculate the sum of a list of values. accum = 0 vals.each do |v| accum += v end return accum end