class ECDSA::PrimeField

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) “`

Attributes

prime[R]

@return (Integer) the prime number that the field is based on.

Public Class Methods

factor_out_twos(x) click to toggle source

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

# 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) click to toggle source

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

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

# 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
new(prime) click to toggle source
# 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

Public Instance Methods

include?(e) click to toggle source

Returns true if the given object is an integer and a member of the field. @param e (Object) @return (true or false)

# File lib/ecdsa/prime_field.rb, line 28
def include?(e)
  e.is_a?(Integer) && e >= 0 && e < prime
end
inverse(n) click to toggle source

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

@param n (Integer) @return (Integer) integer ‘inv` such that `(inv * num) % prime` is one.

# 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) click to toggle source

Calculates the remainder of ‘n` after being divided by the field’s prime. @param n (Integer) @return (Integer)

# File lib/ecdsa/prime_field.rb, line 35
def mod(n)
  n % prime
end
power(n, m) click to toggle source

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

@param n (Integer) the base @param m (Integer) the exponent @return (Integer)

# 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) click to toggle source

Computes ‘n` multiplied by itself. @param n (Integer) @return (Integer)

# File lib/ecdsa/prime_field.rb, line 86
def square(n)
  mod n * n
end
square_roots(n) click to toggle source

Finds all possible square roots of the given field element.

@param n (Integer) @return (Array) A sorted array of numbers whose square is equal to ‘n`.

# 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

Private Instance Methods

jacobi(n) click to toggle source
# File lib/ecdsa/prime_field.rb, line 136
def jacobi(n)
  self.class.send(:jacobi, n, prime)
end
square_roots_default(n) click to toggle source

This is Algorithm 3.34 from cacr.uwaterloo.ca/hac/ It has no limitations except prime must be at least three, so we could remove all the other square root algorithms if we wanted to.

# File lib/ecdsa/prime_field.rb, line 167
def square_roots_default(n)
  return [0] if n == 0
  return [] if jacobi(n) == -1   # Step 1

  # Step 2, except we don't want to use randomness.
  b = (1...prime).find { |i| jacobi(i) == -1 }

  s, t = self.class.factor_out_twos(prime - 1)  # Step 3
  n_inv = inverse(n)  # Step 4

  # Step 5
  c = power b, t
  r = power n, (t + 1) / 2

  # Step 6
  (1...s).each do |i|
    d = power r * r * n_inv, 1 << (s - i - 1)
    r = mod r * c if d == prime - 1
    c = square c
  end

  square_roots_given_candidate n, r
end
square_roots_for_p_3_mod_4(n) click to toggle source

This is Algorithm 1 from math.stanford.edu/~jbooher/expos/sqr_qnr.pdf It is also Algorithm 3.36 from cacr.uwaterloo.ca/hac/ The algorithm assumes that its input actually does have a square root. To get around that, we double check the answer after running the algorithm to make sure it works.

# File lib/ecdsa/prime_field.rb, line 145
def square_roots_for_p_3_mod_4(n)
  candidate = power n, (prime + 1) / 4
  square_roots_given_candidate n, candidate
end
square_roots_for_p_5_mod_8(n) click to toggle source

This is Algorithm 3.37 from cacr.uwaterloo.ca/hac/

# File lib/ecdsa/prime_field.rb, line 151
def square_roots_for_p_5_mod_8(n)
  case power n, (prime - 1) / 4
  when 1
    candidate = power n, (prime + 3) / 8
  when prime - 1
    candidate = mod 2 * n * power(4 * n, (prime - 5) / 8)
  else
    # I think this can happen because we are not checking the Jacobi.
    return []
  end
  square_roots_given_candidate n, candidate
end
square_roots_given_candidate(n, candidate) click to toggle source
# File lib/ecdsa/prime_field.rb, line 191
def square_roots_given_candidate(n, candidate)
  return [] if square(candidate) != n
  [candidate, mod(-candidate)].uniq.sort
end