Class: SecretSharing::Polynomial

Inherits:
Object
  • Object
show all
Defined in:
lib/secret_sharing/polynomial.rb

Overview

The polynomial is used to represent the required random polynomials used in Shamir's Secret Sharing algorithm.

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(coefficients) ⇒ Polynomial

Create a new instance of a Polynomial with n coefficients, when having the polynomial in standard polynomial form.

Example

For the polynomial f(x) = a0 + a1 * x + a2 * x^2 + ... + an * x^n the
coefficients are [a0, a1, a2, ..., an]

Polynomial.new [1, 2, 3]
# => #<SecretSharing::Polynomial:0x0000000 @coefficients=[1, 2, 3]>

Parameters:

  • coefficients (Array)

    an array of integers as the coefficients


21
22
23
24
25
26
27
28
# File 'lib/secret_sharing/polynomial.rb', line 21

def initialize(coefficients)
  coefficients.each do |c|
    not_an_int = 'One or more coefficents are not integers'
    fail ArgumentError, not_an_int unless c.is_a?(Integer)
  end
  @coefficients = coefficients
  @coefficients.freeze
end

Instance Attribute Details

#coefficientsObject (readonly)

Returns the value of attribute coefficients


7
8
9
# File 'lib/secret_sharing/polynomial.rb', line 7

def coefficients
  @coefficients
end

Class Method Details

.egcd(a, b) ⇒ Object

extended Euclidean algorithm


126
127
128
129
130
# File 'lib/secret_sharing/polynomial.rb', line 126

def self.egcd(a, b)
  return [b, 0, 1] if a == 0
  g, y, x = egcd(b % a, a)
  [g, x - b.div(a) * y, y]
end

.lagrange_fraction(points, current, prime) ⇒ Object

part of the lagrange interpolation


107
108
109
110
111
112
113
114
115
116
# File 'lib/secret_sharing/polynomial.rb', line 107

def self.lagrange_fraction(points, current, prime)
  numerator, denominator = 1, 1
  points.each do |point|
    if point != current
      numerator = (numerator * (0 - point.x)) % prime
      denominator = (denominator * (current.x - point.x)) % prime
    end
  end
  [numerator, denominator]
end

.mod_inverse(k, prime) ⇒ Object

inverse modulo


119
120
121
122
123
# File 'lib/secret_sharing/polynomial.rb', line 119

def self.mod_inverse(k, prime)
  k = k % prime
  r = egcd(prime, k.abs).last
  (prime + r) % prime
end

.modular_lagrange_interpolation(points) ⇒ Object

Modular lagrange interpolation


96
97
98
99
100
101
102
103
104
# File 'lib/secret_sharing/polynomial.rb', line 96

def self.modular_lagrange_interpolation(points)
  _, y_values = Point.transpose(points)
  prime = Prime.large_enough_prime(y_values.max)
  points.reduce(0) do |f_x, point|
    numerator, denominator = lagrange_fraction(points, point, prime)
    lagrange_polynomial = numerator * mod_inverse(denominator, prime)
    (prime + f_x + (point.y * lagrange_polynomial)) % prime
  end
end

.points_from_secret(secret_int, point_threshold, num_points) ⇒ Polynomial

Generate points from a secret integer.

Example

SecretSharing::Polynomial.points_from_secret(123, 2, 3)
# => [#<Point: @x=1 @y=109>, #<Point: @x=2 @y=95>, #<Point: @x=3 @y=81>]

Parameters:

  • secret_int (Integer)

    the secret to divide into points

  • point_threshold (Integer)

    number of points to reconstruct

  • num_points (Integer)

    number of points to generate

Returns:


84
85
86
87
88
89
90
91
92
93
# File 'lib/secret_sharing/polynomial.rb', line 84

def self.points_from_secret(secret_int, point_threshold, num_points)
  prime = Prime.large_enough_prime(secret_int)
  fail ArgumentError, 'Threshold must be at least 2' if point_threshold < 2
  fail ArgumentError, 'Threshold must be less than the total number of points' if point_threshold > num_points

  polynomial = random(point_threshold - 1, secret_int, prime)
  polynomial.points(num_points, prime)
rescue Prime::CannotFindLargeEnoughPrime
  raise ArgumentError, 'Secret is too long'
end

.random(degree, intercept, upper_bound) ⇒ Object

Generate a random polynomial with a specific degree, defined x=0 value and an upper limit for the coefficients of the polynomial. All coefficients generated are >= 1.

Example

Polynomial.random(2, 3, 7)
# => #<SecretSharing::Polynomial:0x0000000 @coefficients=[3, 0, 4]>

Parameters:

  • degree (Integer)

    degree of the polynomial to generate

  • intercept (Integer)

    the y value for x=0

  • upper_bound (Integer)

    the highest value of a single coefficient


64
65
66
67
68
69
70
71
# File 'lib/secret_sharing/polynomial.rb', line 64

def self.random(degree, intercept, upper_bound)
  fail ArgumentError, 'Degree must be a non-negative number' if degree < 0

  coefficients = (0...degree).reduce([intercept]) do |accumulator|
    accumulator << SecureRandom.random_number(upper_bound - 1) + 1
  end
  new coefficients
end

Instance Method Details

#points(num_points, prime) ⇒ Array

Generate points on the polynomial, that can be used to reconstruct the polynomial with.

Example

SecretSharing::Polynomial.new([1, 2, 3, 4]).points(3, 7)
# => [#<Point: @x=1 @y=3>, #<Point: @x=2 @y=0>, #<Point: @x=3 @y=2>]

Parameters:

  • num_points (Integer)

    number of points to generate

  • prime (Integer)

    prime for calculation in finite field

Returns:

  • (Array)

    array of calculated points


41
42
43
44
45
46
47
48
49
50
# File 'lib/secret_sharing/polynomial.rb', line 41

def points(num_points, prime)
  intercept = @coefficients[0] # the first coefficient is the intercept
  (1..num_points).map do |x|
    y = intercept
    (1...@coefficients.length).each do |i|
      y = (y + @coefficients[i] * x ** i) % prime
    end
    Point.new(x, y)
  end
end