Accelerated verification of digital signatures and public keys

• US 10,284,370 B2
• Filed: 06/27/2014
• Issued: 05/07/2019
• 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, Antipa, Adrian, Lambert, Robert John
• Primary Examiner(s): Shiferaw, Eleni A
• Assistant Examiner(s): Khan, Sher A
• Application Number:
  US14/318,313
• Publication Number:
  US 20140344579A1
• Time in Patent Office: 1,775 Days
• 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)G+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 performed by a hardware processor of a computing device, comprising:

receiving, by a receiver of the computing device and through a network, an electronic message including a signature, wherein the electronic message omits a public key of a signer, and the signature comprises a signature on the electronic message M;

receiving, by the receiver of the computing device and through the network, a first elliptic curve point associated with a signature component from the signer, wherein the signature component comprises a first signature component r, the signature includes the first signature component r and a second signature component s, and the first elliptic curve point comprises an elliptic curve point R;

recovering, by the hardware processor of the computing device, the omitted public key of the signer based on the received first elliptic curve point and the received signature, wherein the public key comprises a second elliptic curve point in an elliptic curve group different from the first elliptic curve point, wherein the elliptic curve group includes the first and second elliptic curve points, wherein the second elliptic curve point comprises an elliptic curve point Q, wherein recovering the omitted public key of the signer comprises computing Q=r<sup>−

1</sup> (sR−

eG), wherein G comprises a generator of an elliptic curve group that includes the elliptic curve point R and the elliptic curve point Q, and wherein e is a hash value computed from the electronic message M; and

verifying, by the hardware processor of the computing device, the received signature using the recovered public key which provides an accelerated verification of the received signature.

2. The method of claim 1, further comprising verifying that the elliptic curve point Q represents the public key of the signer.

3. The method of claim 1, wherein the elliptic curve point R is generated based on the first signature component r and a cofactor h for an elliptic curve that includes the elliptic curve point R and the elliptic curve point Q.

4. The method of claim 1, wherein the public key of the signer can be used to verify the signature.

5. The method of claim 4, wherein verifying the signature comprises verifying the signature according to an Elliptic Curve Digital Signature Algorithm (ECDSA).

6. A non-transitory computer-readable medium storing instructions that, when executed by one or more hardware processors of a computing device, cause the computing device to perform operations comprising:

receiving, by a receiver of the computing device and through a network, an electronic message including a signature, wherein the electronic message omits a public key of a signer, and the signature comprises a signature on the electronic message M;

receiving, by the receiver of the computing device and through the network, a first elliptic curve point associated with a signature component from the signer, wherein the signature component comprises a first signature component r, the signature includes the first signature component r and a second signature component s, and the first elliptic curve point comprises an elliptic curve point R;

recovering, by the one or more hardware processors of the computing device, the omitted public key of the signer based on the received first elliptic curve point and the received signature, wherein the public key comprises a second elliptic curve point in an elliptic curve group different from the first elliptic curve point, wherein the elliptic curve group includes the first and second elliptic curve points, wherein the second elliptic curve point comprises an elliptic curve point Q, wherein recovering the omitted public key of the signer comprises computing Q=r<sup>−

1</sup> (sR−

eG), wherein G comprises a generator of an elliptic curve group that includes the elliptic curve point R and the elliptic curve point Q, and wherein e is a hash value computed from the electronic message M; and

verifying, by the one or more hardware processors of the computing device, the received signature using the recovered public key which provides an accelerated verification of the received signature.

7. The computer-readable medium of claim 6, the operations further comprising verifying that the elliptic curve point Q represents the public key of the signer.

8. The computer-readable medium of claim 6, wherein the elliptic curve point R is generated based on the first signature component r and a cofactor h for an elliptic curve that includes the elliptic curve point R and the elliptic curve point Q.

9. The computer-readable medium of claim 6, wherein the public key of the signer can be used to verify the signature.

10. A computing device comprising:

a receiver configured to receive an electronic message including a signature, wherein the electronic message omits a public key of a signer, and the signature comprises a signature on the electronic message M;

a memory; and

a hardware processor communicatively coupled with the memory and configured to;

receive, from the receiver, a first elliptic curve point associated with a signature component from the signer, wherein the signature component comprises a first signature component r, the signature includes the first signature component r and a second signature component s, and the first elliptic curve point comprises an elliptic curve point R;

recover, by the hardware processor of the computing device, the omitted public key of the signer based on the received first elliptic curve point and the received signature, wherein the public key comprises a second elliptic curve point in an elliptic curve group different from the first elliptic curve point, wherein the elliptic curve group includes the first and second elliptic curve points, wherein the second elliptic curve point comprises an elliptic curve point Q, wherein recovering the omitted public key of the signer comprises computing Q=r<sup>−

1</sup> (sR−

eG), wherein G comprises a generator of an elliptic curve group that includes the elliptic curve point R and the elliptic curve point Q, and wherein e is a hash value computed from the electronic message M; and

verify, by the hardware processor of the computing device, the received signature using the recovered public key which provides an accelerated verification of the received signature.

11. The computing device of claim 10, wherein the hardware processor is further configured to verify that the elliptic curve point Q represents the public key of the signer.