Accelerated Verification of Digital Signatures and Public Keys

• US 20140344579A1
• Filed: 06/27/2014
• Published: 11/20/2014
• Est. Priority Date: 01/18/2005
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: STRUIK, Marinus, BROWN, Daniel Richard L., VANSTONE, Scott Alexander, GALLANT, Robert Philip, LAMBERT, Robert John, ANTIPA, Adrian
• Granted Patent: US 10,284,370 B2
• Time in Patent Office: Days
• US Class Current: 713/171
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

Abstract

Accelerated computation of combinations of group operations in a finite field is provided by arranging for at least one of the operands to have a relatively small bit length. In a elliptic curve group, verification that a value representative of a point R corresponds the sum of two other points uG and vG is obtained by deriving integers w,z of reduced bit length and that v=w/z. The verification equality R=uG+vQ may then be computed as −zR+(uz mod n)+wQ=O with z and w of reduced bit length This is beneficial in digital signature verification where increased verification can be attained.

Claims

1. A method of verifying the equality of a relationship between the sum of scalar multiples of a pair of points on an elliptic curve and a third point on said curve comprising the steps of

i) obtaining a pair of integers of bit length less than one of said scalars and whose ratio corresponds to said scalar,

ii) substituting said integers for said scalars in said relationship to obtain an equivalent relationship in which at least one of said terms is a scalar multiple of one of said points with reduced bit length, and

iii) computing said equivalent relationship to verify said equality.

2. A method according to claim 1 wherein a pair of said terms have reduced bit length.

3. A method according to claim 2 wherein the other of said integers modifies said third point to provide a scalar multiple of reduced bit length

4. A method according to claim 3 wherein a further term of said equivalent relationship is separated in to a pair of points, each represented by a bit string of reduced length, one of which has a fixed value and the other of which is variable.

5. A method according to claim 4 wherein said one of said points of fixed value is pre-computed and stored for repeated use.

6. A method according to claim 3 wherein said integers have equal bit length.

7. A method according to claim 3 wherein said integers have different bit lengths.

8. A method according to claim 3 wherein said equality is verified by equating the sum of said points to a group identity and performing simultaneous addition on at least a pair of said points.

9. A method according to claim 8 wherein computation of the addition of at least said pair of points is performed using a simultaneous double and add algorithm.

10. A method according to claim 3 wherein said points are used in a system in which one of said points is fixed and the other of said points vary, said variable points being associated with said integers of reduced bit length.

11. A method according to claim 10 wherein at least a portion of the scalar multiple of said fixed point is precomputed.

12. A method according to claim 11 wherein said scalar multiple of said fixed point is split in to a pair of points and one of said points is precomputed.

13. A method according to claim 12 wherein scalar multiples of each of said points are summed and the result compared to the group identity for verification of the equality.

14. A method according to claim I wherein said integers are obtained using an iterative algorithm that is interrupted when integers of required bit length are obtained.

15. A method according to claim 14 wherein said algorithm is extended Euclidean algorithm.

16. A method of verifying a digital signature of a message performed by a cryptographic operation in a group of a finite field having elements represented by bit strings of defined maximum bit length, said signature comprising a pair of components, one of which is derived from an ephemeral public key of a signer and the other of which combines said message, said first component and said ephemeral public key and a long term public key of said signer, said method comprising the steps of recovering said ephemeral public key from said first component, establishing a verification equality as a combination of group operations on said ephemeral public key, said long term public key and a generator of said group with at least one of said group operations involving an operand represented by bit strings having a reduced bit length less than said defined maximum bit length, computing said combination and accepting said signature if said equality holds and rejecting said signature if said equality fails.

17. A method according to claim 16 wherein said group operation of reduced bit length is performed on said ephemeral public key.

18. a method according to claim 17 wherein group operations on said ephemeral public key and said long term public key each involve an operand of reduced bit length.

19. A method according to claim 16 wherein said group is an elliptic curve group and said combination of group operations is a sum of scalar multiples of points on said curve.

20. A method according to claim 19 wherein said verification equality is of the form −

zR=(zu mod n) G+wQ where

R is the ephemeral public key;

G is the generator of the group;

Q is the long term public key;

n is the order of the group respective;

z, w are integers having bit lengths t<

n, and

u is an integer derived from said signature components

O is the group identity.

21-38. -38. (canceled)