AUTHENTICATED ENCRYPTION FOR DIGITAL SIGNATURES WITH MESSAGE RECOVERY
First Claim
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 [k1] 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 [k1], to the first portion [N] of the message [M] to obtain an encrypted value [c1] and a message authentication code [mac];
reversibly combining the encrypted value [c1] 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 [dA] 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 [GA] of the signer,wherein the finite cyclic group is a subgroup of the group of integers modulo a prime number.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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 [k1] 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 [k1], to the first portion [N] of the message [M] to obtain an encrypted value [c1] and a message authentication code [mac]; reversibly combining the encrypted value [c1] 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 [dA] 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 [GA] of the signer, wherein the finite cyclic group is a subgroup of the group of integers modulo a prime number. - View Dependent Claims (2, 3)
-
-
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 [k11] and a second derived key [k12] 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 [k12], 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 [k11] 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 [dA] 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 [GA] of the signer that is included in the finite cyclic group and is computable from the private key [dA] and the generator [G]. - View Dependent Claims (5, 6, 7, 8, 9)
-
-
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 [k11] and a second derived key [k12] 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 [k11] to the first portion [N] of the message [M] to obtain an encrypted value [c1]; applying a message authentication code ‘
MAC’
function, keyed by the second derived key [k12], to the encrypted value [c1] to obtain a message authentication code [mac];reversibly combining the encrypted value [c1] 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 [dA] 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 [GA] of the signer that is included in the finite cyclic group and is computable from the private key [dA] 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 [k1] 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 [k1], to the first portion [N] of the message [M] and to the second portion [V] of the message [M] to obtain an encrypted value [c1] and to obtain a message authentication code [mac]; reversibly combining the encrypted value [c1] 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 [dA] 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 [GA] of the signer that is included in the finite cyclic group and is computable from the private key [dA] 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 [c1′
] from the first signature component [c];receiving a public key [GA] of the signer that is included in a finite cyclic group and is computable from a private key [dA] 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 [GA], and an intermediate value dependent on the first signature component [c] and the second portion [V] of the message [M];constructing a derived key [k1′
] 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 [k1′
], to the encrypted value [c1′
] 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 [GA] of the signer that is included in a finite cyclic group and is computable from a private key [dA] 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 [GA], 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 [k11′
] and a second derived key [k12′
] 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 [k11′
], to the first signature component [c] to obtain a result;extracting a recovered value [N′
] and the message authentication code [mac′
] from the result; andusing the second derived key [k12′
] 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]. - View Dependent Claims (14, 15, 16, 17, 18)
-
-
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 [c1′
] from the first signature component [c];receiving a public key [GA] of the signer that is included in a finite cyclic group and is computable from a private key [dA] 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 [GA], 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 [k11′
] and a second derived key [k12′
] by applying a key derivation function [KDF] to input that comprises the first value [Q′
];using the second derived key [k12′
] to determine whether the message authentication code [mac′
] is valid for the encrypted value [c1′
], and where the message authentication code [mac′
] is valid, applying a decryption function, keyed by the first derived key [k11′
], to the encrypted value [c1′
] 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 [c1′
] from the first signature component [c];receiving a public key [GA] of the signer that is included in a finite cyclic group and is computable from a private key [dA] 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 [GA], and the message authentication code [mac′
];constructing a derived key [k1′
] 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 [k1′
], to the encrypted value [c1′
], 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].
-
Specification