Class: BTC::SecretSharing

Inherits:
Object
  • Object
show all
Defined in:
lib/btcruby/ssss.rb

Constant Summary collapse

Order96 =

Largest prime below 2**96: (2**96 - 17)

0xffffffffffffffffffffffef
Order104 =

Largest prime below 2**104: (2**104 - 17)

0xffffffffffffffffffffffffef
Order128 =

Largest prime below 2**128: (2**128 - 159)

0xffffffffffffffffffffffffffffff61

Instance Method Summary collapse

Constructor Details

#initialize(bitlength = 128) ⇒ SecretSharing

Returns a new instance of SecretSharing.



19
20
21
22
23
24
25
26
27
28
29
30
 
# File 'lib/btcruby/ssss.rb', line 19

def initialize(bitlength = 128)
  if bitlength == 128
    @order = Order128
  elsif bitlength == 104
    @order = Order104
  elsif bitlength == 96
    @order = Order96
  else
    raise ArgumentError, "Unsupported bit length #{bitlength}"
  end
  @bitlength = bitlength
end

Instance Method Details

#be_from_int(i, pad = @bitlength) ⇒ Object 



172
173
174
175
176
177
178
179
 
# File 'lib/btcruby/ssss.rb', line 172

def be_from_int(i, pad = @bitlength)
  a = []
  while i > 0
    a.unshift(i % 256)
    i /= 256
  end
  a.pack("C*").rjust(pad / 8, "\x00")
end

#from_nibble(x) ⇒ Object 



139
140
141
 
# File 'lib/btcruby/ssss.rb', line 139

def from_nibble(x)
  x == 0 ? 16 : x
end

#gcd_decomposition(a, b) ⇒ Object

Gives the decomposition of the gcd of a and b. Returns [x,y,z] such that x = gcd(a,b) and y*a + z*b = x



144
145
146
147
148
149
150
151
152
153
 
# File 'lib/btcruby/ssss.rb', line 144

def gcd_decomposition(a,b)
  if b == 0
    [a, 1, 0]
  else
    n = a/b
    c = a % b
    r = gcd_decomposition(b,c)
    [r[0], r[2], r[1]-r[2]*n]
  end
end

#int_from_be(data) ⇒ Object 



162
163
164
165
166
167
168
169
170
 
# File 'lib/btcruby/ssss.rb', line 162

def int_from_be(data)
  r = data.unpack("C*").reverse.inject({pos:0, total:0}) do |ctx, c|
    c = c << ctx[:pos]
    ctx[:pos] += 8
    ctx[:total] += c
    ctx
  end
  r[:total]
end

#modinv(k, prime) ⇒ Object

Gives the multiplicative inverse of k mod prime. In other words (k * modInverse(k)) % prime = 1 for all prime > k >= 1



156
157
158
159
160
 
# File 'lib/btcruby/ssss.rb', line 156

def modinv(k, prime)
  k = k % prime
  r = (k < 0) ? -gcd_decomposition(prime,-k)[2] : gcd_decomposition(prime,k)[2]
  return (prime + r) % prime
end

#point_from_string(s) ⇒ Object

returns [m, x, y]



125
126
127
128
129
130
131
 
# File 'lib/btcruby/ssss.rb', line 125

def point_from_string(s)
  byte = s.bytes.first
  m = from_nibble(byte >> 4)
  x = from_nibble(byte & 0x0f)
  y = int_from_be(s[1..-1])
  [m, x, y]
end

#prng(seed) ⇒ Object 



104
105
106
107
108
109
110
111
112
113
114
 
# File 'lib/btcruby/ssss.rb', line 104

def prng(seed)
  x = @order
  s = nil
  pad = "".b
  while x >= @order
    s = Digest::SHA2.digest(Digest::SHA2.digest(seed + pad))[0,@bitlength/8]
    x = int_from_be(s)
    pad = pad + "\x00".b
  end
  s
end

#random ⇒ Object 



32
33
34
 
# File 'lib/btcruby/ssss.rb', line 32

def random
  be_from_int(SecureRandom.random_number(@order))
end

#restore(shares) ⇒ Object

Transforms M 17-byte binary strings into original secret 16-byte binary string. Each share string must be well-formed.



73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/btcruby/ssss.rb', line 73

def restore(shares)
  prime = @order
  shares = shares.dup.uniq
  raise "No shares provided" if shares.size == 0
  points = shares.map{|s| point_from_string(s) } # [[m,x,y],...]
  ms = points.map{|p| p[0]}.uniq
  xs = points.map{|p| p[1]}.uniq
  raise "Shares do not use the same M value" if ms.size > 1
  m = ms.first
  raise "All shares must have unique X values" if xs.size != points.size
  raise "Number of shares should be M or more" if points.size < m
  points = points[0, m] # make sure we have exactly M points
  y = 0
  points.size.times do |formula| # 0..(m-1)
    # Multiply the numerator across the top and denominators across the bottom to do Lagrange's interpolation
    numerator = 1
    denominator = 1
    points.size.times do |count| # 0..(m-1)
      if formula != count # skip element with i == j
        startposition = points[formula][1]
        nextposition = points[count][1]
        numerator = (numerator * -nextposition) % prime
        denominator = (denominator * (startposition - nextposition)) % prime
      end
    end
    value = points[formula][2]
    y = (prime + y + (value * numerator * modinv(denominator, prime))) % prime
  end
  return be_from_int(y)
end

#split(secret, m, n) ⇒ Object

Returns N strings, any M of them are enough to retrieve a secret. Each string encodes X and Y coordinates and also M. X & M takes one byte, Y takes 16 bytes: MMMMXXXX YYYYYYYY YYYYYYYY YYYYYYYY YYYYYYYY YYYYYYYY YYYYYYYY YYYYYYYY YYYYYYYY YYYYYYYY YYYYYYYY YYYYYYYY YYYYYYYY YYYYYYYY YYYYYYYY YYYYYYYY YYYYYYYY



39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/btcruby/ssss.rb', line 39

def split(secret, m, n)
  prime = @order
  secret_num = int_from_be(secret)
  if secret_num >= @order
    raise "Secret cannot be encoded with #{@bitlength}-bit SSSS"
  end
  if !(n >= 1 && n <= 16)
    raise "N must be between 1 and 16"
  end
  if !(m >= 1 && m <= n)
    raise "M must be between 1 and N"
  end
  shares = []
  coef = [secret_num] # polynomial coefficients
  (m - 1).times do |i|
    # Generate unpredictable yet deterministic coefficients for each secret and M.
    coef << int_from_be(prng(secret + m.chr + i.chr))
  end
  n.times do |i|
    x = i + 1
    exp = 1
    y = coef[0]
    while exp < m
      y = (y + (coef[exp] * ((x**exp) % prime) % prime)) % prime
      exp += 1
    end
    # Encode share
    shares << string_from_point(m, x, y)
  end
  shares
end

#string_from_point(m, x, y) ⇒ Object

Returns mmmmxxxx yyyyyyyy yyyyyyyy … (16 bytes of y)



117
118
119
120
121
122
 
# File 'lib/btcruby/ssss.rb', line 117

def string_from_point(m, x, y)
  m = to_nibble(m)
  x = to_nibble(x)
  byte = [(m << 4) + x].pack("C")
  byte + be_from_int(y)
end

#to_nibble(x) ⇒ Object

Encodes values in range 1..16 to one nibble where all values are encoded as-is, except for 16 which becomes 0. This is to make strings look friendly for common cases when M,N < 16



135
136
137
 
# File 'lib/btcruby/ssss.rb', line 135

def to_nibble(x)
  x == 16 ? 0 : x
end