Generating digital signatures

• US 9,503,267 B2
• Filed: 12/28/2011
• Issued: 11/22/2016
• Est. Priority Date: 12/28/2011
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Brown, Daniel Richard L., Antipa, Adrian
• Primary Examiner(s): Shiferaw, Eleni
• Assistant Examiner(s): WADE, SHAQUEAL D
• Application Number:
  US14/368,737
• Publication Number:
  US 20140365779A1
• Time in Patent Office: 1,791 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 21/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 Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 21/72 in cryptographic circuits
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

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.

Claims

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.