# 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

Returns the value of attribute coefficients.

## Class Method Summary collapse

• extended Euclidean algorithm.

• part of the lagrange interpolation.

• inverse modulo.

• Modular lagrange interpolation.

• Generate points from a secret integer.

• Generate a random polynomial with a specific degree, defined x=0 value and an upper limit for the coefficients of the polynomial.

## Instance Method Summary collapse

• constructor

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

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

## 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

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:

• the generated polynomial

 ``` 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 # 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```