# US 9,003,181 B2 · Incorporating data into cryptographic components of an ECQV certificate

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

- Number: US 9,003,181 B2
- Document ID: US9003181B2
- Status: Granted
- Kind: B2
- Application number: 13/070,178
- Filed: 2011-03-23
- Published: 2012-09-27
- Granted: 2015-04-07
- Earliest claimed: 2011-03-23
- Assignees: Certicom Corp.; BlackBerry Limited
- Applicants: Herbert Anthony Little; Matthew John Campagna; Scott Alexander Vanstone; Daniel Richard L. Brown
- Inventors: Herbert Anthony Little; Matthew John Campagna; Scott Alexander Vanstone; Daniel Richard L. Brown
- Web page: https://patentgrep.com/patent/US9003181B2

## CPC

- H04L 9/0844: {with user authentication or key authentication, e.g. ElGamal, MTI, MQV-Menezes-Qu-Vanstone protocol or Diffie-Hellman protocols using implicitly-certified keys}
- H04L 9/3066: {involving algebraic varieties, e.g. elliptic or hyper-elliptic curves}
- H04L 9/3263: {involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements (network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823)}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

During generation of an implicit certificate for a requestor, a certificate authority incorporates information in the public-key reconstruction data, where the public-key reconstruction data is to be used to compute the public key of the requestor. The information may be related to one or more of the requestor, the certificate authority, and the implicit certificate. The certificate authority reversibly encodes the public-key reconstruction data in the implicit certificate and sends it to the requestor. After receiving the implicit certificate from the certificate authority, the requestor can extract the incorporated information from the public-key reconstruction data. The implicit certificate can be made available to a recipient, and the recipient can also extract the incorporated information.

## Claims

### Claim 1

A method to be performed by a certificate authority as part of an implicit certificate scheme, the method comprising:
receiving a certificate request from a requestor, the certificate request comprising a public value [QA] of the requestor;
selecting particular information [VA] from a finite set;
performing an iterative process of generating a point [BA] on an elliptic curve and applying a known function [F] to the point [BA], wherein the iterative process is repeated until applying the known function [F] to the point [BA] results in the particular information [VA];
encoding an implicit certificate [ICA] using the point [BA] as public-key reconstruction data [BA]; and
calculating an implicit signature [s] that corresponds to the implicit certificate [ICA],
wherein the iterative process comprises:
generating a private value [dCA] of the certificate authority;
multiplying the private value [dCA] of the certificate authority by a base point [G] to obtain a public value [QCA] of the certificate authority;
calculating the public-key reconstruction data [BA] as a sum of the public value [QA] of the requestor and the public value [QCA] of the certificate authority; and
determining whether applying the known function [F] to the public-key reconstruction data [BA] results in the particular information [VA],
wherein the public value [QA] of the requestor, the base point [G], and the public value [QCA] of the certificate authority are on the elliptic curve.

### Claim 2 (depends on 1)

The method as claimed in claim 1, further comprising:
sending the implicit certificate [ICA] and the implicit signature [s] to the requestor for use in calculating a reconstructed private key [kA] which forms a key pair with a public key [KA] that can be reconstructed from the public-key reconstruction data [BA].

### Claim 3 (depends on 1)

The method as claimed in claim 1, further comprising:
making the implicit certificate [ICA] available to a recipient for use in calculating a public key [KA] from the public-key reconstruction data [BA].

### Claim 4 (depends on 1)

The method as claimed in claim 1, wherein the particular information [VA] is related to one or more of the requestor, the implicit certificate [ICA], and a public key [KA] that can be reconstructed from the public-key reconstruction data [BA].

### Claim 5 (depends on 1)

The method as claimed in claim 1, wherein the particular information [VA] comprises a validity period of the implicit certificate [ICA] or a validity date of the implicit certificate [ICA] or both.

### Claim 6 (depends on 1)

The method as claimed in claim 1, wherein in the event that applying the known function [F] to the public-key reconstruction data [BA] does not result in the particular information [VA], the iterative process further comprises:
generating a new private value [new dCA] of the certificate authority;
multiplying the new private value [new dCA] of the certificate authority by the base point [G] to obtain a new public value [new QCA] of the certificate authority;
calculating new public-key reconstruction data [new BA] as a sum of the public value [QA] of the requestor and the new public value [new QCA] of the certificate authority; and
determining whether applying the known function [F] to the new public-key reconstruction data [new BA] results in the particular information [VA],
wherein the new public value [new QCA] of the certificate authority and the new public-key reconstruction data [new BA] are on the elliptic curve.

### Claim 7 (depends on 1)

The method as claimed in claim 1, wherein in the event that applying the known function [F] to the public-key reconstruction data [BA] does not result in the particular information [VA], the iterative process further comprises:
calculating an incremented private value [dCA+c] of the certificate authority as a sum of the private value [dCA] of the certificate authority and a constant integer [c];
calculating incremented public-key reconstruction data [BA +cG] as a sum of the public-key reconstruction data [BA] and a product of the constant integer [c] and the base point [G], wherein the incremented public-key reconstruction data [BA+cG] is on the elliptic curve; and
determining whether applying the known function [F] to the incremented public-key reconstruction data [BA+cG] results in the particular information [VA].

### Claim 8

A method to be performed by a requestor as part of an implicit certificate scheme, the method comprising:
sending a certificate request to a certificate authority;
receiving from the certificate authority an implicit certificate [ICA] from which public-key reconstruction data [BA] is recoverable, wherein the public-key reconstruction data [BA] is on an elliptic curve and can be used to calculate a reconstructed public key [KA];
receiving from the certificate authority an implicit signature [s] that corresponds to the implicit certificate [ICA];
recovering the public-key reconstruction data [BA] from the implicit certificate [ICA]; and
extracting information [VA] from the public-key reconstruction data [BA] by applying a known function [F] to the public-key reconstruction data [BA], the known function [F] having been agreed upon by the requestor and by the certificate authority for use by the certificate authority in incorporating the information [VA] into the public-key reconstruction data [BA].

### Claim 9 (depends on 8)

The method as claimed in claim 8, wherein the extracted information [VA] is related to one or more of the requestor, the reconstructed public key [KA], and the implicit certificate [ICA].

### Claim 10 (depends on 8)

The method as claimed in claim 8, wherein the extracted information [VA] comprises a validity period of the implicit certificate [ICA] or a validity date of the implicit certificate [ICA] or both.

### Claim 11 (depends on 8)

The method as claimed in claim 8, further comprising:
generating a private value [dA] of the requestor; and
calculating a public value [QA] of the requestor as a product of the private value [dA] of the requestor and a base point [G] on the elliptic curve,
wherein the public value [QA] of the requestor is on the elliptic curve, and
wherein sending the certificate request comprises sending the public value [QA] of the requestor.

### Claim 12 (depends on 8)

The method as claimed in claim 8, the method further comprising:
checking whether the extracted information [VA] complies with certificate policy management rules accessible by the requestor.

### Claim 13 (depends on 11)

The method as claimed in claim 11, the method further comprising:
calculating the reconstructed public key [KA] from the implicit certificate [ICA] and from a public key of the CA [KCA], and
calculating a reconstructed private key [kA] from the implicit certificate [ICA], from the implicit signature [s], and from the private value [dA] of the requestor,
wherein the reconstructed private key [kA] forms a key pair with the reconstructed public key [KA].

### Claim 14

A method to be performed by a recipient as part of an implicit certificate scheme, the method comprising:
receiving an implicit certificate [ICA];
recovering public-key reconstruction data [BA] from the implicit certificate [ICA], wherein the public-key reconstruction data [BA] is on an elliptic curve and can be used to calculate a reconstructed public key [KA]; and
extracting information [VA] from the public-key reconstruction data [BA] by applying a known function [F] to the public-key reconstruction data [BA], the known function [F] having been agreed upon by the recipient and by the certificate authority for use by the certificate authority in incorporating the information [VA] into the public-key reconstruction data [BA].

### Claim 15 (depends on 14)

The method as claimed in claim 14, wherein the extracted information [VA] is related to one or more of the implicit certificate [ICA], a requestor of the implicit certificate [ICA], and the reconstructed public key [KA].

### Claim 16 (depends on 14)

The method as claimed in claim 14, wherein the extracted information [VA] comprises a validity period of the implicit certificate [ICA] or a validity date of the implicit certificate [ICA] or both.

### Claim 17 (depends on 14)

The method as claimed in claim 14, the method further comprising:
calculating the reconstructed public key [KA] from the implicit certificate [ICA] and from a public key of a certificate authority [KCA]; and
implicitly authenticating the reconstructed public key [KA] by using the reconstructed public key [KA] during communication with a requestor of the implicit certificate [ICA].

### Claim 18 (depends on 14)

The method as claimed in claim 14, the method further comprising:
checking whether the extracted information [VA] complies with certificate policy management rules accessible by the recipient.

### Claim 19

A certificate authority device for use in an implicit certificate scheme, the device comprising:
a processor;
a communication interface able to receive a certificate request from a requestor device, the certificate request comprising a public value [QA] of the requestor device; and
a memory storing code which, when executed by the processor, results in:
selecting particular information [VA] from a finite set;
performing an iterative process of generating a point [BA] on an elliptic curve and applying a known function [F] to the point [BA], wherein the iterative process is repeated until applying the known function [F] to the point [BA] results in the particular information [VA];
encoding an implicit certificate [ICA] using the point [BA] as public-key reconstruction data [BA]; and
calculating an implicit signature [s] that corresponds to the implicit certificate [ICA],
wherein the iterative process comprises:
generating a private value [dCA] of the certificate authority device;
multiplying the private value [dCA] of the certificate authority device by a base point [G] to obtain a public value [QCA] of the certificate authority device;
calculating the public-key reconstruction data [BA] as a sum of the public value [QA] of the requestor device and the public value [QCA] of the certificate authority device; and
determining whether applying the known function [F] to the public-key reconstruction data [BA] results in the particular information [VA],
wherein the public value [QA] of the requestor device, the base point [G], and the public value [QCA] of the certificate authority device are on the elliptic curve.

### Claim 20 (depends on 19)

The certificate authority device as claimed in claim 19, wherein the code, when executed by the processor, further results in:
sending the implicit certificate [ICA] and the implicit signature [s] to the requestor device via the communication interface so that the requestor device is able to calculate from the implicit certificate [ICA] and from the implicit signature [s] a reconstructed private key [kA] which forms a key pair with a public key [KA] that can be reconstructed from the public-key reconstruction data [BA].

### Claim 21 (depends on 19)

The certificate authority device as claimed in claim 19, wherein the code, when executed by the processor, further results in:
making the implicit certificate [ICA] available to a recipient device for use in calculating a public key [KA] from the public-key reconstruction data [BA].

### Claim 22 (depends on 19)

The certificate authority device as claimed in claim 19, wherein the particular information [VA] is related to one or more of the requestor device, the implicit certificate [ICA], and a public key [KA] that can be reconstructed from public-key reconstruction data [BA].

### Claim 23 (depends on 19)

The certificate authority device as claimed in claim 19, wherein the particular information [VA] comprises a validity period of the implicit certificate [ICA] or a validity date of the implicit certificate [ICA] or both.

### Claim 24 (depends on 19)

The certificate authority device as claimed in claim 19, wherein in the event that applying the known function [F] to the public-key reconstruction data [BA] does not result in the particular information [VA], the iterative process further comprises:
generating a new private value [new dCA] of the certificate authority device;
multiplying the new private value [new dCA] of the certificate authority device by the base point [G] to obtain a new public value [new QCA] of the certificate authority device;
calculating new public-key reconstruction data [new BA] as a sum of the public value [QA] of the requestor device and the new public value [new QCA] of the certificate authority device; and
determining whether applying the known function [F] to the new public-key reconstruction data [new BA] results in the particular information [VA],
wherein the new public value [new QCA] of the certificate authority device and the new public-key reconstruction data [new BA] are on the elliptic curve.

### Claim 25 (depends on 19)

The certificate authority device as claimed in claim 19, wherein in the event that applying the known function [F] to the public-key reconstruction data [BA] does not result in the particular information [VA], the iterative process further comprises:
calculating an incremented private value [dCA+c] of the certificate authority device as a sum of the private value [dCA] of the certificate authority device and a constant integer [c];
calculating incremented public-key reconstruction data [BA+cG] as a sum of the public-key reconstruction data [BA] and a product of the constant integer [c] and the base point [G], wherein the incremented public-key reconstruction data [BA+cG] is on the elliptic curve; and
determining whether applying the known function [F] to the incremented public-key reconstruction data [BA+cG] results in the particular information [VA].

### Claim 26

A system for use in an implicit certificate generation scheme, the system comprising:
a requestor device to generate a certificate request, the certificate request comprising a public value [QA] of the requestor device; and
a certificate authority device to receive the certificate request from the requestor, to select particular information [VA] from a finite set, and, in response to receiving the certificate request, to perform an iterative process of generating a point [BA] on an elliptic curve and applying a known function [F] to the point [BA], wherein the iterative process is repeated until applying the known function [F] to the point [BA] results in the particular information [VA], to encode an implicit certificate [ICA] using the point [BA] as public-key reconstruction data, to calculate an implicit signature [s] that corresponds to the implicit certificate [ICA], and to send the implicit certificate [ICA] and the implicit signature [s] to the requestor device,
wherein the iterative process comprises:
generating a private value [dCA] of the certificate authority device;
multiplying the private value [dCA] of the certificate authority device by a base point [G] to obtain a public value [QCA] of the certificate authority device;
calculating the public-key reconstruction data [BA] as a sum of the public value [QA] of the requestor device and the public value [QCA] of the certificate authority device; and
determining whether applying the known function [F] to the public-key reconstruction data [BA] results in the particular information [VA],
wherein the public value [QA] of the requestor device, the base point [G], and the public value [QCA] of the certificate authority device are on the elliptic curve.

### Claim 27 (depends on 26)

The system as claimed in claim 26, wherein the requestor device, in response to receiving implicit certificate [ICA] and the implicit signature [s] from the CA device, is to recover the public-key reconstruction data [BA] from the implicit certificate [ICA] and is to extract the information [VA] from the public-key reconstruction data [BA] by applying the known function [F] to the public-key reconstruction data [BA].

### Claim 28 (depends on 26)

The system as claimed in claim 26, wherein the particular information [VA] is related to one or more of the requestor device, the implicit certificate [ICA], and a public key [KA] that can be reconstructed from public-key reconstruction data [BA].

### Claim 29 (depends on 26)

The system as claimed in claim 26, wherein the particular information [VA] comprises a validity period of the implicit certificate [ICA] or a validity date of the implicit certificate [ICA] or both.

### Claim 30

A non-transitory computer readable medium storing code which, when executed by a processor of a certificate authority device, results in:
selecting particular information [VA] from a finite set;
performing an iterative process of generating a point [BA] on an elliptic curve and applying a known function [F] to the point [BA], wherein the iterative process is repeated until applying the known function [F] to the point [BA] results in the particular information [VA];
encoding an implicit certificate [ICA] using the point [BA] as public-key reconstruction data [BA]; and
calculating an implicit signature [s] that corresponds to the implicit certificate [ICA],
wherein the iterative process comprises:
generating a private value [dCA] of the certificate authority device;
multiplying the private value [dCA] of the certificate authority device by a base point [G] to obtain a public value [QCA] of the certificate authority device;
calculating the public-key data [BA] as a sum of a public value [QA] of a requestor device and the public value [QCA] of the certificate authority device, the public value [QA] of the requestor device having been received by the certificate authority device in a certificate request from the requestor device; and
determining whether applying the known function [F] to the public-key reconstruction data [BA] results in the particular information [VA],
wherein the public value [QA] of the requestor device, the base point [G], and the public value [QCA] of the certificate authority device are on the elliptic curve.

### Claim 31

A non-transitory computer readable medium storing code which, when executed by a processor of a requestor device that has sent a certificate request to a certificate authority device, results in:
responsive to receiving from the certificate authority device an implicit certificate [ICA] from which public-key reconstruction data [BA] is recoverable, and an implicit signature [s] that corresponds to the implicit certificate [ICA], wherein the public-key reconstruction data [BA] is on an elliptic curve and can be used to calculate a reconstructed public key [KA]:
recovering the public-key reconstruction data [BA] from the implicit certificate [ICA]; and
extracting information [VA] from the public-key reconstruction data [BA] by applying a known function [F] to the public-key reconstruction data [BA], the known function [F] having been agreed upon by the requestor device and by the certificate authority device for use by the certificate authority device in incorporating the information [VA] into the public-key reconstruction data [BA].

### Claim 32

A non-transitory computer readable medium storing code which, when executed by a processor of a recipient device, results in:
responsive to receiving an implicit certificate [ICA]:
recovering public-key reconstruction data [BA] from the implicit certificate [ICA], wherein the public-key reconstruction data [BA] is on an elliptic curve and can be used to calculate a reconstructed public key [KA]; and
extracting information [VA] from the public-key reconstruction data [BA] by applying a known function [F] to the public-key reconstruction data [BA], the known function [F] having been agreed upon by the recipient device and by a certificate authority device for use by the certificate authority device in incorporating the information [VA] into the public-key reconstruction data [BA].