Generating digital signatures

Patent metadata

Field	Value
Publication number	US-9503267-B2
Application number	US-201114368737-A
Country	US
Kind code	B2
Filing date	Dec 28, 2011
Priority date	Dec 28, 2011
Publication date	Nov 22, 2016
Grant date	Nov 22, 2016

Abstract

Methods, systems, and computer programs for generating a digital signature are disclosed. In some aspects, a symmetric key is accessed. The symmetric key is based on an ephemeral public key. The ephemeral public key is associated with an ephemeral private key. A ciphertext is generated based on the symmetric key and a message. An input value is obtained based on the ciphertext independent of a hash function. A digital signature is generated from the ephemeral private key, the input value, and a long term private key.

First claim

What is claimed is:

1. A method for generating a digital signature, the method comprising:
accessing a symmetric key, wherein the symmetric key is based on an ephemeral public key, and the ephemeral public key is associated with an ephemeral private key;
generating, by a hardware processor on a computing device, a ciphertext based on the symmetric key and a first portion of a message;
obtaining an input value independent of a hash function and based on the ciphertext, wherein obtaining the input value comprises:
producing a concatenation of the ciphertext and a second portion of the message; and
applying at least one of a truncation function or a reduction function on the concatenation;

generating, by the hardware processor on the computing device, a digital signature value from the ephemeral private key, the input value, and a long term private key; and
transmitting the digital signature value, the ciphertext, and the second portion of the message from the computing device to another computing device.

2. The method of claim 1 , wherein obtaining the input value includes:
if the reduction function is applied on the concatenation, reducing the concatenation of the ciphertext and the second portion of the message modulo an integer n; or if the truncation function is applied on the concatenation, truncating the concatenation of the ciphertext and the second portion of the message to a specified length.

3. The method of claim 2 , wherein the integer n represents an order of a generator point G, the ephemeral private key is an integer k, and the ephemeral public key is an elliptic curve point R=kG.

4. The method of claim 1 , wherein generating the digital signature value includes computing s=k−de mod n, where s represents the digital signature value, k represents the ephemeral private key, d represents the long term private key associated with the entity, e represents the input value, and n represents an integer.

5. The method of claim 4 , wherein the ephemeral public key is a first elliptic curve point R=kG, and G is a generator point of order n.

6. The method of claim 1 , further comprising generating the symmetric key by evaluating a key derivation function based on the ephemeral public key.

7. A computing device comprising data processing apparatus operable to:
access a symmetric key, wherein the symmetric key is based on an ephemeral public key, and the ephemeral public key is associated with an ephemeral private key;
generate a ciphertext based on the symmetric key and a first portion of a message;
obtain an input value independent of a hash function and based on the ciphertext by:
producing a concatenation of the ciphertext and a second portion of the message; and
applying at least one of a truncation function or a reduction function on the concatenation;

generate a digital signature value from the ephemeral private key, the input value, and a long term private key; and
transmit the digital signature value, the ciphertext, and the second portion of the message from the computing device to another computing device.

8. The computing device of claim 7 , wherein obtaining the input value includes:
if the reduction function is applied on the concatenation, reducing the concatenation of the ciphertext and the second portion of the message modulo an integer n; or if the truncation function is applied on the concatenation, truncating the concatenation of the ciphertext and the second portion of the message to a specified length.

9. The computing device of claim 8 , wherein the integer n represents an order of a generator point G, the ephemeral private key is an integer k, and the ephemeral public key is an elliptic curve point R=kG.

10. A non-transitory computer-readable medium storing instructions that are operable when executed by data processing apparatus to perform operations for generating a digital signature, the operations comprising:
accessing a symmetric key, wherein the symmetric key is based on an ephemeral public key, and the ephemeral public key is associated with an ephemeral private key;
generating a ciphertext based on the symmetric key and a first portion of a message;
obtaining an input value independent of a hash function and based on the ciphertext, wherein obtaining the input value comprises:
producing a concatenation of the ciphertext and a second portion of the message; and
applying at least one of a truncation function or a reduction function on the concatenation;

generating, at a computing device, a digital signature value from the ephemeral private key, the input value, and a long term private key; and
transmitting the digital signature value, the ciphertext, and the second portion of the message from the computing device to another computing device.

11. The non-transitory computer-readable medium of claim 10 , wherein obtaining the input value includes:
if the reduction function is applied on the concatenation, reducing the concatenation of the ciphertext and the second portion of the message modulo an integer n; or if the truncation function is applied on the concatenation, truncating the concatenation of the ciphertext and the second portion of the message to a specified length.

12. The non-transitory computer-readable medium of claim 11 , wherein the integer n represents an order of a generator point G, the ephemeral private key is an integer k, and the ephemeral public key is an elliptic curve point R=kG.

13. The non-transitory computer-readable medium of claim 10 , wherein generating the digital signature value includes computing s=k−de mod n, where s represents the digital signature value, k represents the ephemeral private key, d represents the long term private key associated with the entity, e represents the input value, and n represents an integer.

14. The non-transitory computer-readable medium of claim 13 , wherein the ephemeral public key is a first elliptic curve point R=kG, and G is a generator point of order n.

15. The non-transitory computer-readable medium of claim 10 , wherein the operations comprise generating the symmetric key by evaluating a key derivation function based on the ephemeral public key.

Assignees

• Brown Daniel Richard L
• Antipa Adrian
• Certicom Corp

Inventors

• Brown Daniel Richard L
• Antipa Adrian

Classifications

• G06F21/10

  Protecting distributed programs or content, e.g. vending or licensing of copyrighted material (protection in video systems or pay television H04N7/16) {; Digital rights management [DRM]} · CPC title

• H04L9/3281

  Electricity · mapped topic

• G06F21/72

  in cryptographic circuits · CPC title

• H04L9/3066

  involving algebraic varieties, e.g. elliptic or hyper-elliptic curves · CPC title

• G06F21/64

  Protecting data integrity, e.g. using checksums, certificates or signatures · CPC title