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
Constants
- VERSION
Public Class Methods
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
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
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
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
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
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
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
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
# 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