Accelerated verification of digital signatures and public keys
First Claim
Patent Images
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−
1 (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.
7 Assignments
0 Petitions
Accused Products
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.
-
Citations
11 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−
1 (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; andverifying, 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. - View Dependent Claims (2, 3, 4, 5)
-
-
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−
1 (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; andverifying, 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. - View Dependent Claims (7, 8, 9)
-
-
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−
1 (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; andverify, 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. - View Dependent Claims (11)
-
Specification