Class: ECDSA::PrimeField

Inherits:
Object
  • Object
show all
Defined in:
lib/ecdsa/prime_field.rb

Overview

Instances of this class represent a field where the elements are non-negative integers less than a prime p.

To add two elements of the field:

“‘ruby sum = field.mod(a + b) “`

To multiply two elements of the field:

“‘ruby product = field.mod(a * b) “`

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(prime) ⇒ PrimeField

Returns a new instance of PrimeField.

Raises:

  • (ArgumentError) 


20
21
22
23
 
# File 'lib/ecdsa/prime_field.rb', line 20

def initialize(prime)
  raise ArgumentError, "Invalid prime #{prime.inspect}" if !prime.is_a?(Integer)
  @prime = prime
end

Instance Attribute Details

#prime ⇒ Integer (readonly)

Returns the prime number that the field is based on.

Returns:

  • (Integer) —

    the prime number that the field is based on.



18
19
20
 
# File 'lib/ecdsa/prime_field.rb', line 18

def prime
  @prime
end

Class Method Details

.factor_out_twos(x) ⇒ Object

This method is NOT part of the public API of the ECDSA gem.



105
106
107
108
109
110
111
112
 
# File 'lib/ecdsa/prime_field.rb', line 105

def self.factor_out_twos(x)
  e = 0
  while x.even?
    x /= 2
    e += 1
  end
  [e, x]
end

.jacobi(n, p) ⇒ Object

This method is NOT part of the public API of the ECDSA gem.

Algorithm algorithm 2.149 from cacr.uwaterloo.ca/hac/



117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
 
# File 'lib/ecdsa/prime_field.rb', line 117

def self.jacobi(n, p)
  raise 'Jacobi symbol is not defined for primes less than 3.' if p < 3

  n = n % p

  return 0 if n == 0  # Step 1
  return 1 if n == 1  # Step 2

  e, n1 = factor_out_twos n                         # Step 3
  s = (e.even? || [1, 7].include?(p % 8)) ? 1 : -1  # Step 4
  s = -s if (p % 4) == 3 && (n1 % 4) == 3           # Step 5

  # Step 6 and 7
  return s if n1 == 1
  s * jacobi(p, n1)
end

Instance Method Details

#include?(e) ⇒ true or false

Returns true if the given object is an integer and a member of the field.

Parameters:

  • e (Object)

Returns:

  • (true or false) 


28
29
30
 
# File 'lib/ecdsa/prime_field.rb', line 28

def include?(e)
  e.is_a?(Integer) && e >= 0 && e < prime
end

#inverse(n) ⇒ Integer

Computes the multiplicative inverse of a field element using the [Extended Euclidean Algorithm](en.wikipedia.org/wiki/Extended_Euclidean_algorithm).

Parameters:

  • n (Integer)

Returns:

  • (Integer) —

    integer ‘inv` such that `(inv * num) % prime` is one.

Raises:

  • (ArgumentError) 


44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/ecdsa/prime_field.rb', line 44

def inverse(n)
  raise ArgumentError, '0 has no multiplicative inverse.' if n.zero?

  # For every i, we make sure that num * s[i] + prime * t[i] = r[i].
  # Eventually r[i] will equal 1 because gcd(num, prime) is always 1.
  # At that point, s[i] is the multiplicative inverse of num in the field.

  remainders = [n, prime]
  s = [1, 0]
  t = [0, 1]
  arrays = [remainders, s, t]
  while remainders.last > 0
    quotient = remainders[-2] / remainders[-1]
    arrays.each do |array|
      array << array[-2] - quotient * array[-1]
    end
  end

  raise 'Inversion bug: remainder is not 1.' if remainders[-2] != 1
  mod s[-2]
end

#mod(n) ⇒ Integer

Calculates the remainder of ‘n` after being divided by the field’s prime.

Parameters:

  • n (Integer)

Returns:

  • (Integer) 


35
36
37
 
# File 'lib/ecdsa/prime_field.rb', line 35

def mod(n)
  n % prime
end

#power(n, m) ⇒ Integer

Computes ‘n` raised to the power `m`. This algorithm uses the same idea as ECDSA::Point#multiply_by_scalar.

Parameters:

  • n (Integer) —

    the base

  • m (Integer) —

    the exponent

Returns:

  • (Integer) 


72
73
74
75
76
77
78
79
80
81
 
# File 'lib/ecdsa/prime_field.rb', line 72

def power(n, m)
  result = 1
  v = n
  while m > 0
    result = mod result * v if m.odd?
    v = square v
    m >>= 1
  end
  result
end

#square(n) ⇒ Integer

Computes ‘n` multiplied by itself.

Parameters:

  • n (Integer)

Returns:

  • (Integer) 


86
87
88
 
# File 'lib/ecdsa/prime_field.rb', line 86

def square(n)
  mod n * n
end

#square_roots(n) ⇒ Array

Finds all possible square roots of the given field element.

Parameters:

  • n (Integer)

Returns:

  • (Array) —

    A sorted array of numbers whose square is equal to ‘n`.

Raises:

  • (ArgumentError) 


94
95
96
97
98
99
100
101
102
 
# File 'lib/ecdsa/prime_field.rb', line 94

def square_roots(n)
  raise ArgumentError, "Not a member of the field: #{n}." if !include?(n)
  case
  when prime == 2 then [n]
  when (prime % 4) == 3 then square_roots_for_p_3_mod_4(n)
  when (prime % 8) == 5 then square_roots_for_p_5_mod_8(n)
  else square_roots_default(n)
  end
end