# US 8,788,827 B2 · Accelerated verification of digital signatures and public keys

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,788,827 B2
- Document ID: US8788827B2
- Status: Granted
- Kind: B2
- Application number: 13/620,206
- Filed: 2012-09-14
- Published: 2013-03-14
- Granted: 2014-07-22
- Earliest claimed: 2005-01-18
- Assignees: Certicom Corp.
- Applicants: Marinus Struik; Daniel R. Brown; Scott A. Vanstone; Robert P. Gallant; Adrian Antipa; Robert J. Lambert
- Inventors: Marinus Struik; Daniel R. Brown; Scott A. Vanstone; Robert P. Gallant; Adrian Antipa; Robert J. Lambert
- Web page: https://patentgrep.com/patent/US8788827B2

## CPC

- H04L 9/3066: {involving algebraic varieties, e.g. elliptic or hyper-elliptic curves}
- G06F 7/725: {over elliptic curves}
- H04L 9/30: Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L 9/3252: {using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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 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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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

### Claim 5 (depends on 4)

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

### Claim 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.

### Claim 7 (depends on 6)

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.

### Claim 8 (depends on 6)

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.

### Claim 9 (depends on 6)

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

### Claim 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.

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 10)

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.

### Claim 13 (depends on 10)

The computing device of claim 10, wherein the public key of the signer can be used to verify the signature.