Class: SecretSharing::Shamir

Inherits:
Object
  • Object
show all
Defined in:
lib/secretsharing/shamir.rb

Overview

The SecretSharing::Shamir class can be used to share random secrets between n people, so that k < n people can recover the secret, but k-1 people learn nothing (in an information-theoretical sense) about the secret.

For a theoretical background, see www.cs.tau.ac.il/~bchor/Shamir.html or en.wikipedia.org/wiki/Secret_sharing#Shamir.27s_scheme

To share a secret, create a new SecretSharing::Shamir object and then call the create_random_secret() method. The secret is now in the secret attribute and the shares are an array in the shares attribute.

Alternatively, you can call the set_fixed_secret() method with an OpenSSL::BN object (or something that can be passed to OpenSSL::BN.new) to set your own secret.

To recover a secret, create a SecretSharing::Shamir object and add the necessary shares to it using the ‘<<’ method. Once enough shares have been added, the secret can be recovered in the secret attribute.

Defined Under Namespace

Classes: Share

Constant Summary collapse

DEFAULT_SECRET_BITLENGTH = 
256

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(n, k = n) ⇒ Shamir

To create a new SecretSharing::Shamir object, you can pass either just n, or k and n.

For example:

s = SecretSharing::Shamir.new(5, 3)

to create an object for 3 out of 5 secret sharing.

or

s = SecretSharing::Shamir.new(3)

for 3 out of 3 secret sharing.



42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
# File 'lib/secretsharing/shamir.rb', line 42

def initialize(n, k=n)
  if k > n then
    raise ArgumentError, 'k must be smaller or equal than n'
  end  
  if k < 2 then
    raise ArgumentError, 'k must be greater or equal to two'
  end
  if n > 255 then
    raise ArgumentError, 'n must be smaller than 256'
  end
  @n = n
  @k = k
  @secret = nil
  @shares = []
  @received_shares = []
end

Instance Attribute Details

#k ⇒ Object (readonly)

Returns the value of attribute k.



28
29
30
 
# File 'lib/secretsharing/shamir.rb', line 28

def k
  @k
end

#n ⇒ Object (readonly)

Returns the value of attribute n.



28
29
30
 
# File 'lib/secretsharing/shamir.rb', line 28

def n
  @n
end

#secret ⇒ Object (readonly)

Returns the value of attribute secret.



28
29
30
 
# File 'lib/secretsharing/shamir.rb', line 28

def secret
  @secret
end

#secret_bitlength ⇒ Object (readonly)

Returns the value of attribute secret_bitlength.



28
29
30
 
# File 'lib/secretsharing/shamir.rb', line 28

def secret_bitlength
  @secret_bitlength
end

#shares ⇒ Object (readonly)

Returns the value of attribute shares.



28
29
30
 
# File 'lib/secretsharing/shamir.rb', line 28

def shares
  @shares
end

Class Method Details

.smallest_prime_of_bitlength(bitlength) ⇒ Object

Computes the smallest prime of a given bitlength. Uses prime_fasttest from the OpenSSL library with 20 attempts to be compatible to openssl prime, which is used in the OpenXPKI::Crypto::Secret::Split library.



130
131
132
133
134
135
136
137
138
139
140
141
142
 
# File 'lib/secretsharing/shamir.rb', line 130

def self.smallest_prime_of_bitlength(bitlength)
  # start with 2^bit_length + 1
  test_prime = OpenSSL::BN.new((2**bitlength + 1).to_s)  
  prime_found = false
  while (! prime_found) do
    # prime_fasttest? 20 do be compatible to
    # openssl prime, which is used in
    # OpenXPKI::Crypto::Secret::Split
    prime_found = test_prime.prime_fasttest? 20
    test_prime += 2
  end
  test_prime
end

Instance Method Details

#<<(share) ⇒ Object

Add a secret share to the object. Accepts either a SecretSharing::Shamir::Share instance or a string representing one. Returns true if enough shares have been added to recover the secret, false otherweise.



103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
# File 'lib/secretsharing/shamir.rb', line 103

def <<(share)
  # convert from string if needed
  if share.class != SecretSharing::Shamir::Share then
    if share.class == String then
      share = SecretSharing::Shamir::Share.from_string(share)
    else
      raise ArgumentError 'SecretSharing::Shamir::Share ' \
                        + 'or String needed'
    end
  end
  if @received_shares.include? share then
    raise 'share has already been added'
  end
  if @received_shares.length == @k then
    raise 'we already have enough shares, no need to add more'
  end
  @received_shares << share
  if @received_shares.length == @k then
    recover_secret
    return true
  end
  false
end

#create_random_secret(bitlength = DEFAULT_SECRET_BITLENGTH) ⇒ Object

Create a random secret of a certain bitlength. Returns the secret and stores it in the ‘secret’ attribute.



66
67
68
69
70
71
72
73
 
# File 'lib/secretsharing/shamir.rb', line 66

def create_random_secret(bitlength = DEFAULT_SECRET_BITLENGTH)
  raise 'secret already set' if secret_set?
  raise 'max bitlength is 1024' if bitlength > 1024
  @secret = get_random_number(bitlength)
  @secret_bitlength = bitlength
  create_shares
  @secret
end

#secret_password ⇒ Object

The secret in a password representation (Base64-encoded)



92
93
94
95
96
97
 
# File 'lib/secretsharing/shamir.rb', line 92

def secret_password
  if ! secret_set? then
    raise "Secret not (yet) set."
  end
  Base64.encode64([@secret.to_s(16)].pack('h*')).split("\n").join
end

#secret_set? ⇒ Boolean

Check whether the secret is set.

Returns:

  • (Boolean) 


60
61
62
 
# File 'lib/secretsharing/shamir.rb', line 60

def secret_set?
  ! @secret.nil?
end

#set_fixed_secret(secret) ⇒ Object

Set the secret to a fixed OpenSSL::BN value. Stores it in the ‘secret’ attribute, creates the corresponding shares and returns the secret



78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/secretsharing/shamir.rb', line 78

def set_fixed_secret(secret)
  raise 'secret already set' if secret_set?
  if secret.class != OpenSSL::BN then
    # create OpenSSL bignum
    secret = OpenSSL::BN.new(secret)
  end
  raise 'max bitlength is 1024' if secret.num_bits > 1024
  @secret = secret
  @secret_bitlength = secret.num_bits
  create_shares
  @secret
end