Skip to content

Instantly share code, notes, and snippets.

@oleganza oleganza/ssss.rb
Last active Oct 9, 2019

Embed
What would you like to do?
128-bit Shamir's Secret Sharing Scheme (SSSS) Implementation in Ruby
#!/usr/bin/env ruby -rubygems
# Shamir's Secret Sharing Scheme with m-of-n rule for 128-bit numbers.
# Author: Oleg Andreev <oleganza@gmail.com>
#
# * Deterministic, extensible algorithm: every combination of secret and threshold produces exactly the same shares on each run. More shares can be generated without invalidating the first ones.
# * This algorithm splits and restores 128-bit secrets with up to 16 shares and up to 16 shares threshold.
# * Secret is a binary 16-byte string below ffffffffffffffffffffffffffffff61.
# * Shares are 17-byte binary strings with first byte indicating threshold and share index (these are necessary for recovery).
#
# See also: https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
require 'digest/sha2'
require 'securerandom'
module SSSS
extend self
Order = 0xffffffffffffffffffffffffffffff61 # Largest prime below 2**128: (2**128 - 159)
def random
be_from_int(SecureRandom.random_number(Order))
end
def prng(seed)
x = Order
s = nil
pad = "".b
while x >= Order
s = Digest::SHA2.digest(Digest::SHA2.digest(seed + pad))[0,16]
x = int_from_be(s)
pad = pad + "\x00".b
end
s
end
# 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
def split(secret, m, n)
prime = Order
secret_num = int_from_be(secret)
if secret_num >= Order
raise "Secret cannot be encoded with 128-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
# Transforms M 17-byte binary strings into original secret 16-byte binary string.
# Each share string must be well-formed.
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
# Returns mmmmxxxx yyyyyyyy yyyyyyyy ... (16 bytes of y)
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
# returns [m, x, y]
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
# 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
def to_nibble(x)
x == 16 ? 0 : x
end
def from_nibble(x)
x == 0 ? 16 : x
end
# 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
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
# Gives the multiplicative inverse of k mod prime. In other words (k * modInverse(k)) % prime = 1 for all prime > k >= 1
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
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
def be_from_int(i, pad = 128)
a = []
while i > 0
a.unshift(i % 256)
i /= 256
end
a.pack("C*").rjust(pad / 8, "\x00")
end
def to_hex(data)
data.unpack("H*").first
end
def from_hex(hex)
[hex].pack("H*")
end
end
if $0 == __FILE__
# Usage
secret = SSSS.random
puts "Secret: #{SSSS.to_hex(secret)}"
shares = SSSS.split(secret, 2, 3)
shares.each do |share|
puts "Share: #{SSSS.to_hex(share)}"
end
restored_secret = SSSS.restore([shares[1], shares[0]])
puts "Recovered secret with shares 2 and 1: #{SSSS.to_hex(restored_secret)}"
restored_secret = SSSS.restore([shares[0], shares[2]])
puts "Recovered secret with shares 1 and 3: #{SSSS.to_hex(restored_secret)}"
restored_secret = SSSS.restore([shares[1], shares[2]])
puts "Recovered secret with shares 2 and 3: #{SSSS.to_hex(restored_secret)}"
# Output:
# Secret: d881c6f74ccac24997bb27040640a8eb
# Share: 2147018841997da8d92211ad7590f85754
# Share: 22b581498be6308f68ac6833e71bb0051e
# Share: 2324010ad632e375f836beba58a667b387
# Recovered secret with shares 2 and 1: d881c6f74ccac24997bb27040640a8eb
# Recovered secret with shares 1 and 3: d881c6f74ccac24997bb27040640a8eb
# Recovered secret with shares 2 and 3: d881c6f74ccac24997bb27040640a8eb
# Test Vectors
test_vectors = [
{
"secret" => "31415926535897932384626433832795",
"1-of-1" => ["1131415926535897932384626433832795"],
"1-of-2" => ["1131415926535897932384626433832795", "1231415926535897932384626433832795"],
"2-of-2" => ["215af384f05d9b45f0e4e348f95b371acd", "2284a5b0ba67ddf44ea6422f8e82eb0e05"],
"1-of-3" => ["1131415926535897932384626433832795", "1231415926535897932384626433832795", "1331415926535897932384626433832795"],
"2-of-3" => ["215af384f05d9b45f0e4e348f95b371acd", "2284a5b0ba67ddf44ea6422f8e82eb0e05", "23ae57dc847220a2ac67a11623aa9f013d"],
"3-of-3" => ["316cb005ab037e85ed9c8befbe72fef75c", "321387c8a1b34863197fae486ca60c1b97", "3325c8a20a62b62f16cceb6c6eccaa93a7"],
"4-of-6" => ["416c4b3a8dc218696f8b1aed23385496eb", "429b14a744ce462bdc71b910b5cf0890ba", "4384d4d7881b01db3881cd0f17457112c8",
"44f0c303944b6b73e265c52a42e9601a3c", "45a61663a602a2f238c80fa43408a7a57b", "466c062ff9e3c8529a531abee5f119b1ac"],
"10-of-16"=>["a1a8b4077b75b0b18aefa63399d0b8d749", "a2e015e817190296d9ebe29f1c8cdc21c7", "a3c65760010c358c9760cece5da815edb4", "a4129891c5efd375a8367c854ab08010d6",
"a53c138386a55b0b35447ca03e44ab4eeb", "a6182993f21038c5d3bf548dac9dee7e20", "a769f010c04a4996b471a82addd4ea05d4", "a88e27a316dda9822f81616b2d48cb5e23",
"a9b0298820dc8c26989b6f8a2e8b00c3c4", "aa98042e1bcdf63b7283503ac4ad364380", "ab27bed0235b651dd92e764fa8cea25ba8", "ac05890d2177c48f4ec6cabd1047d9dbdc",
"adba7838775b82e4022af68f19d9985368", "aeb96045352c20fd24c6de8563cb2446f2", "af4f51af0a774592f9eabb71aaf0348def", "a06f50a680d22280f31b853d941c7eb158"],
},
{
"secret" => "deadbeefcafebabedeadbeefcafebabe",
"1-of-1" => ["11deadbeefcafebabedeadbeefcafebabe"],
"2-of-2" => ["217f21b8a8329e69ea75a518485c8da19d", "221f95b2609a3e19160c9c71a0ee1c887c"],
"2-of-3" => ["217f21b8a8329e69ea75a518485c8da19d", "221f95b2609a3e19160c9c71a0ee1c887c", "23c009ac1901ddc841a393caf97fab6ebc"],
"3-of-3" => ["31d6b7c83a2587dd06be735c2ba5c719c0", "32762d76edcca00dd227bccb825a8daa75", "33bd0ecb0ac0474d211a8a0cf3e9526c3e"],
},
{
"secret" => "ffffffffffffffffffffffffffffff60",
"1-of-1" => ["11ffffffffffffffffffffffffffffff60"],
"2-of-2" => ["21375c71bcaf077f5946f9e901efb9cf70", "226eb8e3795e0efeb28df3d203df739ee1"],
"2-of-3" => ["21375c71bcaf077f5946f9e901efb9cf70", "226eb8e3795e0efeb28df3d203df739ee1", "23a61555360d167e0bd4edbb05cf2d6e52"],
"3-of-3" => ["3112dac40bb910928263e5cf3971c39c8b", "32dec3f6359b1f7671aa60dd821c4969d3", "3363bb967da62cabcdd3712ad9ff916915"],
},
{
"secret" => "00000000000000000000000000000000",
"1-of-1" => ["1100000000000000000000000000000000"],
"2-of-2" => ["2125df3f1da76af07c37689382bc8201a6", "224bbe7e3b4ed5e0f86ed127057904034c"],
"2-of-3" => ["2125df3f1da76af07c37689382bc8201a6", "224bbe7e3b4ed5e0f86ed127057904034c", "23719dbd58f640d174a639ba88358604f2"],
"3-of-3" => ["31651161eeddabb39134be97908f0d7d9e", "32671d1a7e6d7ef24037990a5285a75164", "33062329aeaf79bc0d088f5845e3cd7b52"],
}
]
test_vectors.each do |test|
hexsecret = test.delete("secret")
secret = SSSS.from_hex(hexsecret)
test.each do |rule, defined_shares|
m, n = rule.split("-of-").map{|x|x.to_i}
puts "Testing #{hexsecret} #{rule}:"
shares = SSSS.split(secret, m, n)
hexshares = shares.map{|s| SSSS.to_hex(s)}
failed = false
if hexshares != defined_shares
failed = true
puts "Failed test:"
puts " Expected: #{defined_shares.inspect}"
puts " Generated: #{hexshares.inspect}"
end
subshares = hexshares[0...m] # TODO: iterate over various combinations
restored_secret = SSSS.restore(subshares.map{|s| SSSS.from_hex(s)})
if restored_secret != secret
failed = true
puts "Failed #{hexsecret} #{rule} test: failed to restore secret using #{subshares.inspect}"
end
if !failed
puts "Ok."
end
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.