AUTHENTICATED ENCRYPTION FOR DIGITAL SIGNATURES WITH MESSAGE RECOVERY

• US 20120096274A1
• Filed: 10/11/2011
• Published: 04/19/2012
• Est. Priority Date: 10/15/2010
• Status: Abandoned Application

• Current Assignee: Certicom Corporation (Blackberry Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Campagna, Matthew John, Brown, Daniel Richard L., Zaverucha, Gregory Marc
• Application Number:
  US13/270,970
• Publication Number:
  US 20120096274A1
• Time in Patent Office: Days
• US Class Current: 713/176
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

A framework is proposed for authenticated encryption for digital signatures with message recovery whereby authentication is achieved without a redundancy requirement. The Elliptic Curve Pintsov-Vanstone Signature scheme is modified through the use of authenticated encryption, thereby enabling authentication using a message authentication code. The authenticated encryption may be performed within a single function or as two separate functions. The authenticated encryption may also be applied to associated data in the message to be signed.

Claims

1. A method of applying a signature to an original message [M] to generate a signed message signed by a signer, the original message [M] consisting of a first portion [N] and a second portion [V], the method comprising:

selecting a first integer value [k] and computing a second value [Q] from the first integer value [k] and from a generator [G] of a finite cyclic group such that the second value [Q] is included in the finite cyclic group;

constructing a derived key [k₁] by applying a key derivation function [KDF] to input that comprises the second value [Q];

applying an authenticated encryption function, keyed by the derived key [k₁], to the first portion [N] of the message [M] to obtain an encrypted value [c₁] and a message authentication code [mac];

reversibly combining the encrypted value [c₁] and the message authentication code [mac] to form a first signature component [c];

computing a second signature component [s] using

(i) the first integer value [k];

(ii) a private key [d_A] of the signer; and

(iii) a second integer value dependent on the first signature component [c] and the second portion [V] of the message [M]; and

reversibly combining the first signature component [c], the second signature component [s] and the second portion [V] of the message [M] to form the signed message,

wherein verification of the signed message and recovery of the first portion [N] of the message [M] from the signed message involves a public key [G_A] of the signer,

wherein the finite cyclic group is a subgroup of the group of integers modulo a prime number.

2. The method as claimed in claim 1, the method further comprising:

applying a hash function to a reversible combination of the first signature component [c] and the second portion [V] of the message [M] to obtain a hash result; and

calculating the second integer value equivalent to the hash result.

3. The method as claimed in claim 2, wherein the reversible combination further comprises an identity of the signer.

4. A method of applying a signature to an original message [M] to generate a signed message signed by a signer, the original message [M] consisting of a first portion [N] and a second portion [V], the method comprising:

selecting a first integer value [k] and computing a second value [Q] from the first integer value [k] and from a generator [G] of a finite cyclic group such that the second value [Q] is included in the finite cyclic group;

constructing a first derived key [k₁₁] and a second derived key [k₁₂] by applying a key derivation function [KDF] to input that comprises the second value [Q];

applying a message authentication code ‘

MAC’

function, keyed by the second derived key [k₁₂], to the first portion [N] of the message [M] to obtain a message authentication code [mac];

applying an encryption function, keyed by the first derived key [k₁₁] to a reversible combination of the first portion [N] of the message [M] and the message authentication code [mac] to obtain a first signature component [c];

computing a second signature component [s] using

(i) the first integer value [k];

(ii) a private key [d_A] of the signer; and

(iii) a second integer value dependent on the first signature component [c] and the second portion [V] of the message [M]; and

reversibly combining the first signature component [c], the second signature component [s] and the second portion [V] of the message [M] to form the signed message,

wherein verification of the signed message and recovery of the first portion [N] of the message [M] from the signed message involves a public key [G_A] of the signer that is included in the finite cyclic group and is computable from the private key [d_A] and the generator [G].

5. The method as claimed in claim 4, wherein the finite cyclic group is a subgroup of the group of integers modulo a prime number.

6. The method as claimed in claim 4, wherein the finite cyclic group is a set of points on an elliptic curve and the generator [G] is a base point of the elliptic curve.

7. The method as claimed in claim 4, the method further comprising:

constructing the first derived key [k₁₁] by applying the key derivation function [KDF] to input that comprises the second value [Q] and first auxiliary information; and

constructing the second derived key [k₁₂] by applying the key derivation function [KDF] to input that comprises the second value [Q] and second auxiliary information.

8. The method as claimed in claim 7, wherein the second auxiliary information is different than the first auxiliary information.

9. The method as claimed in claim 4, the method further comprising:

applying the key derivation function [KDF] to input that comprises the second value [Q] to obtain a key;

dividing the key into a first part and a second part; and

constructing the first derived key [k₁₁] from the first part and constructing the second derived key [k₁₂] from the second part.

10. A method of applying a signature to an original message [M] to generate a signed message signed by a signer, the original message [M] consisting of a first portion [N] and a second portion [V], the method comprising:

selecting a first integer value [k] and computing a second value [Q] from the first integer value [k] and from a generator [G] of a finite cyclic group such that the second value [Q] is included in the finite cyclic group;

constructing a first derived key [k₁₁] and a second derived key [k₁₂] by applying a key derivation function [KDF] to input that comprises the second value [Q];

applying an encryption function, keyed by the first derived key [k₁₁] to the first portion [N] of the message [M] to obtain an encrypted value [c₁];

applying a message authentication code ‘

MAC’

function, keyed by the second derived key [k₁₂], to the encrypted value [c₁] to obtain a message authentication code [mac];

reversibly combining the encrypted value [c₁] and the message authentication code [mac] to form a first signature component [c];

computing a second signature component [s] using

(i) the first integer value [k];

(ii) a private key [d_A] of the signer; and

(iii) a second integer value dependent on the first signature component [c] and the second portion [V] of the message [M]; and

reversibly combining the first signature component [c], the second signature component [s] and the second portion [V] of the message [M] to form the signed message,

wherein verification of the signed message and recovery of the first portion [N] of the message [M] from the signed message involves a public key [G_A] of the signer that is included in the finite cyclic group and is computable from the private key [d_A] and the generator [G].

11. A method of applying a signature to an original message [M] to generate a signed message signed by a signer, the original message [M] consisting of a first portion [N] and a second portion [V], the method comprising:

selecting a first integer value [k] and computing a second value [Q] from the first integer value [k] and from a generator [G] of a finite cyclic group such that the second value [Q] is included in the finite cyclic group;

constructing a derived key [k₁] by applying a key derivation function [KDF] to input that comprises the second value [Q];

applying an authenticated-encryption-with-associated-data function, keyed by the derived key [k₁], to the first portion [N] of the message [M] and to the second portion [V] of the message [M] to obtain an encrypted value [c₁] and to obtain a message authentication code [mac];

reversibly combining the encrypted value [c₁] and the message authentication code [mac] to form a first signature component [c];

computing a second signature component [s] using

(i) the first integer value [k];

(ii) a private key [d_A] of the signer; and

(iii) a second integer value equivalent to the message authentication code [mac]; and

reversibly combining the first signature component [c], the second signature component [s] and the second portion [V] of the message [M] to form the signed message,

wherein verification of the signed message and recovery of the first portion [N] of the message [M] from the signed message involves a public key [G_A] of the signer that is included in the finite cyclic group and is computable from the private key [d_A] and the generator [G].

12. A method of verifying a signed message, the signed message having been generated by applying a signature to an original message [M] that consists of a first portion [N] and a second portion [V], the method comprising:

receiving the signed message purported to be signed by a signer, the signed message having been prepared in a reversible manner from a first signature component [c], a second signature component [s], and the second portion [V] of an original message [M];

extracting the first signature component [c], the second signature component [s], and the second portion [V] from the signed message;

extracting a message authentication code [mac′

] and an encrypted value [c₁′

] from the first signature component [c];

receiving a public key [G_A] of the signer that is included in a finite cyclic group and is computable from a private key [d_A] of the signer and a generator [G] of the finite cyclic group;

computing a first value [Q′

] using the second signature component [s], the generator [G], the public key [G_A], and an intermediate value dependent on the first signature component [c] and the second portion [V] of the message [M];

constructing a derived key [k₁′

] by applying a key derivation function [KDF] to input that comprises the first value [Q′

];

applying an authenticated decryption function, keyed by the derived key [k₁′

], to the encrypted value [c₁′

] and to the message authentication code [mac′

] to determine whether the signed message is valid and, where the signed message is valid, to recover the first portion [N] of the original message [M],

wherein the finite cyclic group is a subgroup of the group of integers modulo a prime number.

13. A method of verifying a signed message, the signed message having been generated by applying a signature to an original message [M] that consists of a first portion [N] and a second portion [V], the method comprising:

receiving the signed message purported to be signed by a signer, the signed message having been prepared in a reversible manner from a first signature component [c], a second signature component [s], and the second portion [V] of an original message [M];

extracting the first signature component [c], the second signature component [s], and the second portion [V] from the signed message;

receiving a public key [G_A] of the signer that is included in a finite cyclic group and is computable from a private key [d_A] of the signer and a generator [G] of the finite cyclic group;

computing a first value [Q′

] using the second signature component [s], the generator [G], the public key [G_A], and an intermediate value dependent on the first signature component [c] and the second portion [V] of the message [M];

constructing a first derived key [k₁₁′

] and a second derived key [k₁₂′

] by applying a key derivation function [KDF] to input that comprises the first value [Q′

];

applying a decryption function, keyed by the first derived key [k₁₁′

], to the first signature component [c] to obtain a result;

extracting a recovered value [N′

] and the message authentication code [mac′

] from the result; and

using the second derived key [k₁₂′

] to determine whether the message authentication code [mac′

] is valid for the first portion [N], and, where the message authentication code [mac′

] is valid, recovering the first portion [N] of the original message [M], wherein the recovered value [N′

] is equal to the first portion [N].

14. The method as claimed in claim 13, wherein the finite cyclic group is a subgroup of the group of integers modulo a prime number.

15. The method as claimed in claim 13, wherein the finite cyclic group is a set of points on an elliptic curve and the generator [G] is a base point of the elliptic curve.

16. The method as claimed in claim 13, the method further comprising:

constructing the first derived key [k₁₁′

] by applying the key derivation function [KDF] to input that comprises the first value [Q′

] and first auxiliary information; and

constructing the second derived key [k₁₂′

] by applying the key derivation function [KDF] to input that comprises the first value [Q′

] and second auxiliary information.

17. The method as claimed in claim 16, wherein the second auxiliary information is different than the first auxiliary information.

18. The method as claimed in claim 13, the method further comprising:

applying the key derivation function [KDF] to input that comprises the first value [Q′

] to obtain a key;

dividing the key into a first part and a second part; and

constructing the first derived key [k₁₁′

] from the first part and constructing the second derived key [k₁₂′

] from the second part.

19. A method of verifying a signed message, the signed message having been generated by applying a signature to an original message [M] that consists of a first portion [N] and a second portion [V], the method comprising:

receiving the signed message purported to be signed by a signer, the signed message having been prepared in a reversible manner from a first signature component [c], a second signature component [s], and the second portion [V] of an original message [M];

extracting the first signature component [c], the second signature component [s], and the second portion [V] from the signed message;

extracting a message authentication code [mac′

] and an encrypted value [c₁′

] from the first signature component [c];

receiving a public key [G_A] of the signer that is included in a finite cyclic group and is computable from a private key [d_A] of the signer and a generator [G] of the finite cyclic group;

computing a first value [Q′

] using the second signature component [s], the generator [G], the public key [G_A], and an intermediate value dependent on the first signature component [c] and the second portion [V] of the message [M];

constructing a first derived key [k₁₁′

] and a second derived key [k₁₂′

] by applying a key derivation function [KDF] to input that comprises the first value [Q′

];

using the second derived key [k₁₂′

] to determine whether the message authentication code [mac′

] is valid for the encrypted value [c₁′

], and where the message authentication code [mac′

] is valid, applying a decryption function, keyed by the first derived key [k₁₁′

], to the encrypted value [c₁′

] to recover the first portion [N].

20. A method of verifying a signed message, the signed message having been generated by applying a signature to an original message [M] that consists of a first portion [N] and a second portion [V], the method comprising:

receiving the signed message purported to be signed by a signer, the signed message having been prepared in a reversible manner from a first signature component [c], a second signature component [s], and the second portion [V] of an original message [M];

extracting the first signature component [c], the second signature component [s], and the second portion [V] from the signed message;

extracting a message authentication code [mac′

] and an encrypted value [c₁′

] from the first signature component [c];

receiving a public key [G_A] of the signer that is included in a finite cyclic group and is computable from a private key [d_A] of the signer and a generator [G] of the finite cyclic group;

computing a first value [Q′

] using the second signature component [s], the generator [G], the public key [G_A], and the message authentication code [mac′

];

constructing a derived key [k₁′

] by applying a key derivation function [KDF] to input that comprises the first value [Q′

];

applying an authenticated-decryption-with-associated-data function, keyed by the derived key [k₁′

], to the encrypted value [c₁′

], to the message authentication code [mac′

] and to the second portion [V] to determine whether the signed message is valid and, where the signed message is valid, to recover the first portion [N] of the original message [M].