Accelerated verification of digital signatures and public keys
View Patent ↗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 so 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.
1. A computer-implemented method comprising:
receiving, from a signer, a signature on a message M, wherein the signature includes a first signature component r and a second signature component s;
obtaining an elliptic curve point associated with the first signature component r; and
generating, by operation of a cryptographic module comprising one or more processors, a public key of the signer based on the elliptic curve point and a hash value e computed from the message M;
wherein the elliptic curve point comprises a first elliptic curve point R, the public key of the signer comprises a second elliptic curve point Q, generating the public key of the signer comprises computing Q=r −1 (sR−eG), and G comprises a generator of an elliptic curve group that includes the first elliptic curve point R and the second elliptic curve point Q.
2. The method of claim 1 , further comprising verifying that the second elliptic curve point Q represents the public key of the signer.
3. The method of claim 1 , wherein the first elliptic curve point R is generated based on the first signature component r and a cofactor h for an elliptic curve that includes the first elliptic curve point R and the second 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 processors, perform operations comprising:
receiving, from a signer, a signature on a message M, wherein the signature includes a first signature component r and a second signature component s;
obtaining an elliptic curve point associated with the first signature component r; and
generating a public key of the signer based on the elliptic curve point and a hash value e computed from the message M;
wherein the elliptic curve point comprises a first elliptic curve point R, the public key of the signer comprises a second elliptic curve point Q, generating the public key of the signer comprises computing Q=r −1 (sR−eG), and G comprises a generator of an elliptic curve group that includes the first elliptic curve point R and the second elliptic curve point Q.
7. The computer-readable medium of claim 6 , the operations further comprising verifying that the second elliptic curve point Q represents the public key of the signer.
8. The computer-readable medium of claim 6 , wherein the first elliptic curve point R is generated based on the first signature component r and a cofactor h for an elliptic curve that includes the first elliptic curve point R and the second 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 cryptographic module operable to:
receive, from a signer, a signature on a message M, wherein the signature includes a first signature component r and a second signature component s;
obtain an elliptic curve point associated with the first signature component r; and
generate a public key of the signer based on the elliptic curve point and a hash value e computed from the message M;
wherein the elliptic curve point comprises a first elliptic curve point R, the public key of the signer comprises a second elliptic curve point Q, generating the public key of the signer comprises computing Q=r −1 (sR−eG), and G comprises a generator of an elliptic curve group that includes the first elliptic curve point R and the second elliptic curve point Q.
11. The computing device of claim 10 , wherein the cryptographic module is further operable to verify that the second elliptic curve point Q represents the public key of the signer.
12. The computing device of claim 10 , wherein the first elliptic curve point R is generated based on the first signature component r and a cofactor h for an elliptic curve that includes the first elliptic curve point R and the second elliptic curve point Q.
13. The computing device of claim 10 , wherein the public key of the signer can be used to verify the signature.