module ECDSA

The top-level module for the ECDSA gem.

TODO: we keep using this abstraction called the ‘point_field’ all over the place. Figure out what it is really called and make it come from a method on Group.

Source: csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf

Source: csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf

Source: csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf

Source: csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf

Source: “Curve P-256” from csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.doc

Source: www.secg.org/collateral/sec2_final.pdf

Source: www.secg.org/collateral/sec2_final.pdf

Source: www.secg.org/collateral/sec2_final.pdf

Source: www.secg.org/collateral/sec2_final.pdf

Source: www.secg.org/collateral/sec2_final.pdf

Source: www.secg.org/collateral/sec2_final.pdf

Source: www.secg.org/collateral/sec2_final.pdf

Source: www.secg.org/collateral/sec2_final.pdf

Source: www.secg.org/collateral/sec2_final.pdf

Source: www.secg.org/collateral/sec2_final.pdf

Source: www.secg.org/collateral/sec2_final.pdf

Source: www.secg.org/collateral/sec2_final.pdf

Source: www.secg.org/collateral/sec2_final.pdf

Source: www.secg.org/collateral/sec2_final.pdf

Source: www.secg.org/collateral/sec2_final.pdf

Constants

VERSION

Public Class Methods

bit_length(integer) click to toggle source

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

# File lib/ecdsa.rb, line 22
def self.bit_length(integer)
  length = 0
  while integer > 0
    length += 1
    integer >>= 1
  end
  length
end
byte_length(integer) click to toggle source

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

# File lib/ecdsa.rb, line 12
def self.byte_length(integer)
  length = 0
  while integer > 0
    length += 1
    integer >>= 8
  end
  length
end
check_signature!(public_key, digest, signature) click to toggle source

Verifies the given {Signature} and raises an {InvalidSignatureError} if it is invalid.

This algorithm comes from Section 4.1.4 of [SEC1](www.secg.org/collateral/sec1_final.pdf).

@param public_key (Point) @param digest (String or Integer) @param signature (Signature) @return true

# File lib/ecdsa/verify.rb, line 29
def self.check_signature!(public_key, digest, signature)
  group = public_key.group
  field = group.field

  # Step 1: r and s must be in the field and non-zero
  raise InvalidSignatureError, 'Invalid signature: r is not in the field.' if !field.include?(signature.r)
  raise InvalidSignatureError, 'Invalid signature: s is not in the field.' if !field.include?(signature.s)
  raise InvalidSignatureError, 'Invalid signature: r is zero.' if signature.r.zero?
  raise InvalidSignatureError, 'Invalid signature: s is zero.' if signature.s.zero?

  # Step 2 was already performed when the digest of the message was computed.

  # Step 3: Convert octet string to number and take leftmost bits.
  e = normalize_digest(digest, group.bit_length)

  # Step 4
  point_field = PrimeField.new(group.order)
  s_inverted = point_field.inverse(signature.s)
  u1 = point_field.mod(e * s_inverted)
  u2 = point_field.mod(signature.r * s_inverted)

  # Step 5
  r = group.generator.multiply_by_scalar(u1).add_to_point public_key.multiply_by_scalar(u2)
  raise InvalidSignatureError, 'Invalid signature: r is infinity in step 5.' if r.infinity?

  # Steps 6 and 7
  v = point_field.mod r.x

  # Step 8
  raise InvalidSignatureError, 'Invalid signature: v does not equal r.' if v != signature.r

  true
end
normalize_digest(digest, bit_length) click to toggle source

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

# File lib/ecdsa.rb, line 32
def self.normalize_digest(digest, bit_length)
  if digest.is_a?(String)
    digest = digest.dup.force_encoding('BINARY')
    digest_bit_length = digest.size * 8
    num = Format::IntegerOctetString.decode(digest)

    if digest_bit_length <= bit_length
      num
    else
      num >> (digest_bit_length - bit_length)
    end
  elsif digest.is_a?(Integer)
    digest
  else
    raise ArgumentError, 'Digest must be a string or integer.'
  end
end
recover_public_key(group, digest, signature) { |calculate_public_key(group, digest, signature, point)| ... } click to toggle source

Recovers the set of possible public keys from a {Signature} and the digest that it signs.

If you do not pass a block to ‘recover_public_key` then it returns an Enumerator that will lazily find more public keys when needed. If you are going to iterate through the enumerator more than once, you should probably convert it to an array first with `to_a` to save CPU time.

If you pass a block, it will yield the public keys to the block one at a time as it finds them.

This is better than just returning an array of all possibilities, because it allows the caller to stop the algorithm when the desired public key has been found, saving CPU time.

This algorithm comes from Section 4.1.6 of [SEC1 2.0](www.secg.org/download/aid-780/sec1-v2.pdf)

@param group (Group) @param digest (String or Integer) @param signature (Signature)

# File lib/ecdsa/recover_public_key.rb, line 22
def self.recover_public_key(group, digest, signature)
  return enum_for(:recover_public_key, group, digest, signature) if !block_given?

  digest = normalize_digest(digest, group.bit_length)

  each_possible_temporary_public_key(group, digest, signature) do |point|
    yield calculate_public_key(group, digest, signature, point)
  end

  nil
end
sign(group, private_key, digest, temporary_key) click to toggle source

Produces an ECDSA signature.

This algorithm comes from section 4.1.3 of [SEC1](www.secg.org/collateral/sec1_final.pdf).

@param group (Group) The curve that is being used. @param private_key (Integer) The private key. (The number of times to add

the generator point to itself to get the public key.)

@param digest (String or Integer)

A digest of the message to be signed, usually generated with a hashing algorithm
like SHA2.  The same algorithm must be used when verifying the signature.

@param temporary_key (Integer)

A temporary private key.
This is also known as "k" in some documents.
Warning: Never use the same `temporary_key` value twice for two different messages
or else it will be easy for someone to calculate your private key.
The `temporary_key` should be generated with a secure random number generator.

@return (Signature or nil) Usually this method returns a {Signature}, but

there is a very small chance that the calculated "s" value for the
signature will be 0, in which case the method returns nil.  If that happens,
you should generate a new temporary key and try again.
# File lib/ecdsa/sign.rb, line 25
def self.sign(group, private_key, digest, temporary_key)
  # Second part of step 1: Select ephemeral elliptic curve key pair
  # temporary_key was already selected for us by the caller
  r_point = group.new_point temporary_key

  # Steps 2 and 3
  point_field = PrimeField.new(group.order)
  r = point_field.mod(r_point.x)
  return nil if r.zero?

  # Step 4, calculating the hash, was already performed by the caller.

  # Step 5
  e = normalize_digest(digest, group.bit_length)

  # Step 6
  s = point_field.mod(point_field.inverse(temporary_key) * (e + r * private_key))
  return nil if s.zero?

  Signature.new r, s
end
valid_signature?(public_key, digest, signature) click to toggle source

Verifies the given {Signature} and returns true if it is valid.

This algorithm comes from Section 4.1.4 of [SEC1](www.secg.org/collateral/sec1_final.pdf).

@param public_key (Point) @param digest (String or Integer) @param signature (Signature) @return true if the ECDSA signature if valid, returns false otherwise.

# File lib/ecdsa/verify.rb, line 14
def self.valid_signature?(public_key, digest, signature)
  check_signature! public_key, digest, signature
rescue InvalidSignatureError
  false
end

Private Class Methods

calculate_public_key(group, digest, signature, temporary_public_key) click to toggle source

Assuming that we know the public key corresponding to the (random) temporary private key used during signing, this method tells us what the actual public key was.

# File lib/ecdsa/recover_public_key.rb, line 51
def self.calculate_public_key(group, digest, signature, temporary_public_key)
  point_field = PrimeField.new(group.order)

  # public key = (tempPubKey * s - G * e) / r
  rs = temporary_public_key.multiply_by_scalar(signature.s)
  ge = group.generator.multiply_by_scalar(digest)
  r_inv = point_field.inverse(signature.r)

  rs.add_to_point(ge.negate).multiply_by_scalar(r_inv)
end
each_possible_temporary_public_key(group, digest, signature) { |point| ... } click to toggle source
# File lib/ecdsa/recover_public_key.rb, line 36
def self.each_possible_temporary_public_key(group, digest, signature)
  # Instead of using the cofactor as the iteration limit as specified in SEC1,
  # we just iterate until x is too large to fit in the underlying field.
  # That way we don't have to know the cofactor of the group.
  signature.r.step(group.field.prime - 1, group.order) do |x|
    group.solve_for_y(x).each do |y|
      point = group.new_point [x, y]
      yield point if point.multiply_by_scalar(group.order).infinity?
    end
  end
end