AUTHENTICATED ENCRYPTION FOR DIGITAL SIGNATURES WITH MESSAGE RECOVERY

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
47Forward
Citations 
0
Petitions 
3
Assignments
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 [k_{1}] 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_{1}], to the first portion [N] of the message [M] to obtain an encrypted value [c_{1}] and a message authentication code [mac];
reversibly combining the encrypted value [c_{1}] 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.
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 PintsovVanstone 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.
49 Citations
View as Search Results
SYSTEM AND METHOD FOR DIGITAL USER AUTHENTICATION  
Patent #
US 20120198228A1
Filed 12/20/2011

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

Keyed PV Signatures  
Patent #
US 20120239930A1
Filed 03/16/2012

Current Assignee
Blackberry Limited

Sponsoring Entity
Blackberry Limited

CENTRALIZED KERNAL MODULE LOADING  
Patent #
US 20120311341A1
Filed 05/31/2011

Current Assignee
Red Hat Inc.

Sponsoring Entity
Red Hat Inc.

EFFICIENT AUTHENTICATION FOR MOBILE AND PERVASIVE COMPUTING  
Patent #
US 20130145169A1
Filed 12/04/2012

Current Assignee
University of Washington

Sponsoring Entity
University of Washington

METHODS AND SYSTEMS FOR AUTHENTICATING ELECTRONIC MESSAGES USING CLIENTGENERATED ENCRYPTION KEYS  
Patent #
US 20130166914A1
Filed 12/22/2011

Current Assignee
Xerox Corporation

Sponsoring Entity
Xerox Corporation

Method and System Making it Possible to Test a Cryptographic Integrity of an Error Tolerant Data Item  
Patent #
US 20140052987A1
Filed 12/22/2011

Current Assignee
Thales SA

Sponsoring Entity
Thales SA

System and method for verifying status of an authentication device through a biometric profile  
Patent #
US 9,053,310 B2
Filed 08/08/2014

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

Methods and systems for authenticating electronic messages using clientgenerated encryption keys  
Patent #
US 9,065,842 B2
Filed 12/22/2011

Current Assignee
Xerox Corporation

Sponsoring Entity
Xerox Corporation

Keyed PV signatures  
Patent #
US 9,088,419 B2
Filed 03/16/2012

Current Assignee
Blackberry Limited

Sponsoring Entity
Blackberry Limited

System and method for determining component version compatibility across a device ecosystem  
Patent #
US 9,092,302 B2
Filed 09/10/2014

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

Centralized kernel module loading  
Patent #
US 9,111,099 B2
Filed 05/31/2011

Current Assignee
Red Hat Inc.

Sponsoring Entity
Red Hat Inc.

Passive pressure regulation mechanism  
Patent #
US 9,121,401 B2
Filed 09/06/2013

Current Assignee
Aperio Technologies Incorporated

Sponsoring Entity
Aperio Technologies Incorporated

Efficient authentication for mobile and pervasive computing  
Patent #
US 9,166,793 B2
Filed 12/04/2012

Current Assignee
University of Washington

Sponsoring Entity
University of Washington

System and method for digital user authentication  
Patent #
US 9,282,085 B2
Filed 12/20/2011

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for integrating twofactor authentication in a device  
Patent #
US 9,338,156 B2
Filed 02/24/2014

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for enforcing a policy for an authenticator device  
Patent #
US 9,361,451 B2
Filed 05/06/2014

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for verifying status of an authentication device  
Patent #
US 9,443,073 B2
Filed 08/08/2014

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for determining component version compatibility across a device ecosystem  
Patent #
US 9,454,365 B2
Filed 06/18/2015

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for verifying status of an authentication device through a biometric profile  
Patent #
US 9,454,656 B2
Filed 05/04/2015

Current Assignee
DUOS Security Incorporated

Sponsoring Entity
DUOS Security Incorporated

System and method for verifying status of an authentication device  
Patent #
US 9,455,988 B2
Filed 04/11/2016

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for assessing vulnerability of a mobile device  
Patent #
US 9,467,463 B2
Filed 08/31/2012

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for proxying federated authentication protocols  
Patent #
US 9,491,175 B2
Filed 10/17/2014

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for enforcing a policy for an authenticator device  
Patent #
US 9,524,388 B2
Filed 01/06/2015

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method of notifying mobile devices to complete transactions after additional agent verification  
Patent #
US 9,532,222 B2
Filed 05/04/2016

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method of notifying mobile devices to complete transactions  
Patent #
US 9,544,143 B2
Filed 03/02/2011

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for patching a device through exploitation  
Patent #
US 9,607,156 B2
Filed 02/24/2014

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for centralized key distribution  
Patent #
US 9,608,814 B2
Filed 09/10/2014

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

SIGNED ENVELOPE ENCRYPTION  
Patent #
US 20170171219A1
Filed 12/11/2015

Current Assignee
Amazon Technologies

Sponsoring Entity
Amazon Technologies

Method and system making it possible to test a cryptographic integrity of an error tolerant data item  
Patent #
US 9,705,675 B2
Filed 12/22/2011

Current Assignee
Thales SA

Sponsoring Entity
Thales SA

System and method for an integrity focused authentication service  
Patent #
US 9,762,590 B2
Filed 04/16/2015

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

Method for key rotation  
Patent #
US 9,774,579 B2
Filed 06/27/2016

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for converting onetime passcodes to appbased authentication  
Patent #
US 9,979,719 B2
Filed 12/08/2015

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method of notifying mobile devices to complete transactions  
Patent #
US 9,992,194 B2
Filed 11/29/2016

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for determining component version compatibility across a device ecosystem  
Patent #
US 9,996,343 B2
Filed 05/12/2016

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for integrating twofactor authentication in a device  
Patent #
US 10,013,548 B2
Filed 04/07/2016

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for an integrity focused authentication service  
Patent #
US 10,021,113 B2
Filed 07/27/2017

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

Method for key rotation  
Patent #
US 10,063,531 B2
Filed 08/24/2017

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method of notifying mobile devices to complete transactions  
Patent #
US 10,129,250 B2
Filed 05/04/2018

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for proxying federated authentication protocols  
Patent #
US 10,200,368 B2
Filed 10/06/2016

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for integrating twofactor authentication in a device  
Patent #
US 10,223,520 B2
Filed 06/04/2018

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for determining component version compatibility across a device ecosystem  
Patent #
US 10,248,414 B2
Filed 05/10/2018

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method for assessing vulnerability of a mobile device  
Patent #
US 10,348,756 B2
Filed 09/08/2016

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

Signed envelope encryption  
Patent #
US 10,412,098 B2
Filed 12/11/2015

Current Assignee
Amazon Technologies

Sponsoring Entity
Amazon Technologies

Systems and methods for intelligently configuring computer security  
Patent #
US 10,412,113 B2
Filed 12/10/2018

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

System and method of notifying mobile devices to complete transactions after additional agent verification  
Patent #
US 10,445,732 B2
Filed 11/18/2016

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

Key exchange through partially trusted third party  
Patent #
US 10,447,674 B2
Filed 07/06/2017

Current Assignee
Amazon Technologies

Sponsoring Entity
Amazon Technologies

System and method of notifying mobile devices to complete transactions after additional agent verification  
Patent #
US 10,706,421 B2
Filed 09/12/2019

Current Assignee
Duo Security Incorporated

Sponsoring Entity
Duo Security Incorporated

MESSAGE TRANSMISSION METHOD, PREFERABLY FOR AN ENERGY DISTRIBUTION NETWORK  
Patent #
US 20100158250A1
Filed 10/13/2009

Current Assignee
Stmicroelectronics SRL

Sponsoring Entity
Stmicroelectronics SRL

System and method for controlling features on a device  
Patent #
US 20090292926A1
Filed 12/12/2008

Current Assignee
Blackberry Limited

Sponsoring Entity
Certicom Corporation

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 [k_{1}] 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_{1}], to the first portion [N] of the message [M] to obtain an encrypted value [c_{1}] and a message authentication code [mac]; reversibly combining the encrypted value [c_{1}] 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.  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 [k_{11}] and a second derived key [k_{12}] 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_{12}], 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_{11}] 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].  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 [k_{11}] and a second derived key [k_{12}] 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_{11}] to the first portion [N] of the message [M] to obtain an encrypted value [c_{1}]; applying a message authentication code ‘
MAC’
function, keyed by the second derived key [k_{12}], to the encrypted value [c_{1}] to obtain a message authentication code [mac];reversibly combining the encrypted value [c_{1}] 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_{1}] by applying a key derivation function [KDF] to input that comprises the second value [Q]; applying an authenticatedencryptionwithassociateddata function, keyed by the derived key [k_{1}], 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_{1}] and to obtain a message authentication code [mac]; reversibly combining the encrypted value [c_{1}] 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_{1}′
] 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_{1}′
] 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_{1}′
], to the encrypted value [c_{1}′
] 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_{11}′
] and a second derived key [k_{12}′
] 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_{11}′
], 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 [k_{12}′
] 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 [c_{1}′
] 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_{11}′
] and a second derived key [k_{12}′
] by applying a key derivation function [KDF] to input that comprises the first value [Q′
];using the second derived key [k_{12}′
] to determine whether the message authentication code [mac′
] is valid for the encrypted value [c_{1}′
], and where the message authentication code [mac′
] is valid, applying a decryption function, keyed by the first derived key [k_{11}′
], to the encrypted value [c_{1}′
] 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_{1}′
] 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_{1}′
] by applying a key derivation function [KDF] to input that comprises the first value [Q′
];applying an authenticateddecryptionwithassociateddata function, keyed by the derived key [k_{1}′
], to the encrypted value [c_{1}′
], 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].
1 Specification
This application claims priority under 35 §U.S.C. 119(e) from U.S. Provisional Patent Application No. 61/393,730, filed Oct. 15, 2010, and which is incorporated by reference herein.
The technology described herein relates generally to cryptographic signatures, and particularly to the generation and use of cryptographic signatures with message recovery.
Traditional cryptographic signature schemes can be used to provide (1) assurance of the identity of the signer, and (2) assurance that a received message has not been altered during transmission. Typically, a signer generates an unforgeable signature on a message, such that a recipient may subsequently verify the signature for authentication of the signer'"'"'s identity and the origin of the message.
In general, smallersized cryptographic values are desirable because they may reduce storage and transmission requirements. Signature schemes which are based on the intractability of the elliptic curve discrete logarithm problem, such as the Elliptic Curve Digital Signature Algorithm (ECDSA), for example as described in “American National Standard for Financial Services ANS X9.622005: Public Key Cryptography for the Financial Services Industry—The Elliptic Curve Digital Signature Algorithm (ECDSA)”, Accredited Standards Committee X9, Inc., 2005, may enable the use of smaller signatures than those of other cryptography schemes, such as the Rivest Shamir Adleman (RSA) algorithm, for example as described in “PKCS #1 v2.1: RSA Cryptography Standards”, RSA Laboratories, 2002, while still offering the same level of security. Digital signatures with partial message recovery, for example as described by Nyberg et al. in “Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem”, Advances in Cryptology—Eurocrypt '"'"'94, Springer Verlag, New York, 1994, may also reduce transmission requirements of the [message, signature] pair by embedding a portion of the message (the hidden portion) within the signature value, while not increasing the size of the signature. For example, the portion of the message that is embedded might include the address of the sender, or a confirmation of the recipient'"'"'s address. The Elliptic Curve PintsovVanstone Signature (ECPVS) scheme is an example of a digital signature scheme with partial message recovery. The ECPVS scheme is described in more detail, for example in “American National Standard for Financial Services Draft X9.9220070221: Public Key Cryptography for the Financial Services Industry, Digital Signature Algorithms Giving Partial Message Recovery Part 1: Elliptic Curve PintsovVanstone Signatures (ECPVS)”, Accredited Standards Committee X9, Inc., 2007, as well as by Vanstone et al. in U.S. Pat. No. 7,249,259. In ECPVS, all or part of the message to be signed can be embedded or “hidden” in and recovered from the signature. This scheme can also be used to provide a level of confidentiality by adding the restriction that the public key of the signer be kept secret, such that only parties who possess the public key may verify the signature, and hence only they may compute the hidden portion of the message.
In order for an ECPVS signature to be verified, the hidden portion of the message to be signed has a predefined characteristic that is chosen by the signer and agreed on by the verifier. For example, the hidden portion may contain a certain level of redundancy, which is checked by the verifier in order to verify the signature. The redundancy allows the hidden portion of the message to be identified as belonging to a set of valid plaintexts. Given sufficient redundancy, it should be infeasible for a forger to produce a signature which satisfies all criteria. The more redundancy there is in the hidden portion of the message, the higher the level of security, and the longer the signed message to be transmitted.
The figures of the accompanying drawings are intended to illustrate by way of example and not limitation. Like reference numbers in the figures indicate corresponding, analogous or similar elements.
While the signature schemes described herein are instantiated using a group of points on an elliptic curve, they could alternatively be instantiated using any finite cyclic group, for example, a subgroup of p, the group of integers modulo a prime number p. In this case, the group order may be p−1 and a generator G generates a subgroup of order n, where n divides p−1. Traditionally, arithmetic in subgroups of p is written multiplicatively, where the product of two elements P and Q is PQ, and the analogue of scalar multiplication in elliptic curve groups by an integer k is exponentiation, that is, P^{k}.
Protocols based on elliptic curve cryptography (ECC) rely on the intractability of the elliptic curve discrete logarithm problem. Given publiclyknown points G and Q on an elliptic curve E, where point Q is equal to a product of a scalar multiplying factor d and point G, that is Q=dG, it is conjecturally very difficult to determine scalar multiplying factor d. With known algorithms, the computational difficulty of solving this problem increases exponentially with the size of the subgroup generated by G.
To implement an ECCbased protocol, all participants agree on the domain parameters of the elliptic curve. An elliptic curve E defined over a prime finite field _{p}, that is _{p}), is defined by elliptic curve domain parameters D=(p, a, b, G, n, h), where p is an odd prime number that represents the number of elements in the field, integers a and b are elements of prime finite field _{p }that satisfy for example 4a^{3}+27b^{2}≠0 (mod p), (however curves specified by another equation may be suitable), G is a base point or generator on elliptic curve E(_{p}) that has order n, and cofactor h is a relatively small integer that is defined as a ratio of the number of points #E(_{p}) on elliptic curve E(_{p}) over n. Arithmetic in subgroups of E(_{p}) may be written additively, where the sum of two points P and Q is P+Q, and scalar multiplication by an integer k is kP. Further details of existing ECCbased protocols are described in “Standards for Efficient Cryptography SEC1: Elliptic Curve Cryptography”, Certicom Research, Certicom Corp., 2000, and “Standards for Efficient Cryptography SEC2: Recommended Elliptic Curve Domain Parameters version 2.0”, Certicom Research, Certicom Corp., 2000. Elliptic curves can also be defined over the finite field F_{2}m, which is a binary representation with 2^{m }elements, rather than over a prime finite field _{p}, and the techniques described in this document can be modified to suit elliptic curves defined over the finite field F_{2}m.
The Elliptic Curve PintsovVanstone Signature (ECPVS) scheme provides a digital signature scheme with partial message recovery. The ECPVS scheme has been used to provide a level of confidentiality by enabling a portion of the message being signed to be embedded or “hidden” within one of the resultant signature components. ECPVS can be used by a signer to generate a digital signature on data and by a verifier to verify the authenticity of the signature and to recover the portion of the message hidden within the signature. A private key of the signer is used in the signature generation process, and the corresponding public key is used in the signature verification process. In order for the hidden portion of the message to remain confidential, the public key of the signer needs to be kept secret.
The term “signer” as used herein refers to any computerized device able to generate a digital signature on data. The term “verifier” as used herein refers to any computerized device able to verify the authenticity of a digital signature.
One aspect of the ECPVS scheme is the selection by the signer of message redundancy criteria for a hidden portion of a message to be signed, where the redundancy criteria are known by the verifier in order to verify the signed message. Examples of redundancy criteria include that the message is an ASCII file, that the message is in a specific format, that the message contains certain key words, or that each paragraph ends with a period. The amount of total redundancy is a scalable security parameter which is chosen to achieve security objectives. Given sufficient redundancy, it should be infeasible for a forger to produce a valid signature on a message which satisfies the redundancy criteria. The more redundancy there is in the hidden portion of the message to be signed, the higher the level of security, and the longer the signed message to be transmitted. Consequently, selection of an appropriate cryptographic signature may involve a tradeoff between security requirements and storage/transmission requirements.
A framework for using authenticated encryption in digital signatures with message recovery is herein proposed whereby the ECPVS scheme is modified to remove the redundancy criteria on the hidden portion of a message to be signed. The proposed framework can be applied to signature generation and signature verification.
In one example, an Authenticated EncryptionPintsov Vanstone (AEPV) scheme uses an authenticated encryption (AE) function to encrypt a hidden portion of a message to be signed while creating a message authentication code (MAC) on the hidden portion that shall be used by a verifier to verify the signed message.
In another example, a MACthenEncryptPintsov Vanstone (MEPV) scheme uses a MAC function to obtain a MAC on the hidden portion of the message to be signed, followed by an encryption function to encrypt a combination of the hidden portion and the MAC, such that the MAC may be used by the verifier to verify the signed message. In a variation, an EncryptthenMACPintsov Vanstone (EMPV) scheme uses the encryption function to encrypt the hidden portion of the signed message first, followed by the MAC function to obtain a MAC on the encryption result.
In yet another example, an Authenticated Encryption with Associated DataPintsov Vanstone (AEADPV) scheme uses an authenticated encryption with associated data (AEAD) function to encrypt the hidden portion of the message and to create a MAC on both the hidden portion and on nonencrypted associated data in the message, thereby allowing for authentication of both the hidden portion and the associated data.
The framework proposed herein may also be applied to keyed ECPVS and other signcryption techniques.
In the following examples, it may be assumed, unless otherwise stated, that a signer and a verifier in a signature scheme have agreed on suitable domain parameters. For example, for a signature scheme instantiated using a group of points on an elliptic curve, the signer and the verifier agree on the corresponding elliptic curve domain parameters, including a base point G.
As previously described, while the PintsovVanstone (PV) signature schemes described herein are instantiated using a group of points on an elliptic curve, the schemes may be instantiated using any finite cyclic group. In this case, the signer and the verifier would have to agree on domain parameters associated with that group, including a generator G.
The signer and the verifier using a particular signature scheme agree on the functions and parameters associated with that scheme. For example, with an Authenticated EncryptionPintsov Vanstone (AEPV) scheme, the signer and the verifier agree on an authenticated encryption (AE) function keyed by an integer k_{1 }that is able to take a message M as input and output an encrypted value c_{1 }and a message authentication code (MAC) mac, that is AE_{k1}(M)=(c_{1}, mac). The signer and the verifier also agree on an authenticated decryption (AD) function which is a reverse transformation of AE that is keyed by an integer k_{1 }and that takes an encrypted value c_{1}′ and a MAC mac′ as inputs and outputs either the message M and an indication of validity, or null and an indication of invalidity, that is AD_{k1}(c_{1}′, mac′)=(M, VALID) or AD_{k1 }(c_{1}′, mac′)=(NULL, INVALID). The signer and the verifier also agree on the bit length of key k_{1 }and on the bit length of MAC mac.
The signer and the verifier agree on a suitable key derivation function (KDF). For example, with the (AEPV) scheme, the KDF is able to be used to construct a key suitable for use with authenticated encryption function AE_{k1 }and authenticated decryption function AD_{k1}. Any ANSIX9approved key derivation function may be used, for example, the KDFs described in “NIST SP 800108 Recommendation for Key Derivation Using Pseudorandom Functions”, National Institute of Standards and Technology, 2009.
In examples where a hash function is to be used as part of a signature scheme, the signer and the verifier agree on a cryptographic hash function which maps arbitrary length inputs to fixedlength outputs. Example hash functions include the SHA2 family as described in “FIPS PUB 1803 Federal Information Processing Standards Publication: Secure Hash Standard (SHS)”, National Institute of Standards and Technology, 2008.
The signer and the verifier agree on encoding methods to communicate values, including integers and group elements. An example encoding method is ASN.1 described by Dubuisson in “ASN.1 Communication Between Heterogeneous Systems”, Morgan Kaufmann, 2000. The signer and the verifier also agree on a common encoding of lists of values as bitstrings prior to hashing them. For example, they may agree (1) to convert all values to octet strings, and then (2) to hash a concatenation of the octet strings. As with hashing, an encoding may be performed before deriving keys. With both the KDF and hash function, encoding may incorporate additional information, for example, date, time, name of signer, name of verifier, or contact information related to the message being signed.
For security of a signature scheme, the domain parameters should be chosen carefully. Further details of parameter choices for Pintsov Vanstone signature schemes may be found in “IEEE P1363a/D2, Standard Specifications for Public Key Cryptography: Pinstov Vanstone Signatures with Message Recovery”, Institute of Electrical and Electronics Engineers, 2000. It should also be noted that, for security, a signer may comprise a secure random or pseudorandom number generator for generating keys and signed messages.
As described previously, a public key of the signer that corresponds to a private key that was used in the signature generation process is known to the verifier for verification of a signed message. Furthermore, for those implementations where the hidden portion of the message is to remain confidential, the public key of the signer should not be disclosed to other entities.
Q=k·G. (1)
In some implementations, the pair (k, Q) is ephemeral. That is, a new pair (k, Q) is generated for each message M to which a signature is to be applied.
At 204, the signer constructs a derived key k_{1 }from second value Q. For example, derived key k_{1 }may be constructed by applying a key derivation function KDF to second value Q, according to equation 2:
k_{1}=KDF(Q). (2)
At 206, the signer applies an AE function keyed by derived key k_{1}, that is AE_{k1}, to hidden portion N of message M 104 to obtain an encrypted value c_{1 }and a Message Authentication Code (MAC) mac of a prerequisite length L, where length L is a parameter of authenticated encryption function AE. This is shown in equation 3:
(c_{1}, mac)=AE_{k1}(N). (3)
The AE function is used to encrypt hidden portion N of message M 104 and to create a MAC mac that can be used by a verifier for subsequent verification of signed message 106. An adversary who does not know derived key k_{1}, but observes a number of [encrypted value, MAC] pairs output by authenticated encryption function AE_{k1 }should not be able to output a new [encrypted value, MAC] pair that could be used by the verifier to successfully verify signed message 106 and recover hidden portion N of message M 104. Authenticated decryption is described in more detail with respect to
One possible AE function that may be used is the Advanced Encryption Standard (AES) with Counter Mode Encryption (CME) and Cipher Block Chaining (CBC), also known as AESCCM, which is described in “NIST SP 80038C Recommendation for Block Cipher Modes of Operation: The CCM Mode for Authentication and Confidentiality”, National Institute of Standards and Technology, 2007. Another possible AE function that may be used is AES with Galois Counter Mode (AESGCM), which is described in “NIST SP 80038D Recommendation for Block Cipher Modes of Operation: The Galois/Counter Mode (GCM) and GMAC”, National Institute of Standards and Technology, 2007. Details of the AES are described in “FIPS PUB 197 Advanced Encryption Standard (AES)”, Federal Information Processing Standards, 2001, and Section 7.2.2 of “Handbook of Applied Cryptography”, CRC Press, ISBN 0849385237. Yet another possible AE function that may be used is AES Key Wrap, which is described in “AES Key Wrap Specification”, National Institute of Standards and Technology, November 2001, and variants thereof. The Accredited Standards Committee, X9, Inc. (ASC X9) has defined four algorithms in its draft standard published November 2004. Any of those four algorithms is a suitable AE function that may be used: AESKW (a variant of the AES Key Wrap Specification), TDKW (similar to AESKW, but using Triple DES as the underlying block cipher instead of AES), AKW1 (essentially the algorithm proposed in the Internet Engineering Task Force Request For Comment 3217), and AKW2 (the algorithm that is implicitly defined in a “key block” specification that has been developed for use in constrained legacy systems in the financial services industry). It is also contemplated to use an AE function that does not explicitly output a MAC value upon encryption but still provides authentication. For example, such an AE function, when applied to an input I, outputs an encrypted value AE_{k1}(I) but does not output any MAC, and its associated authenticated decryption function AD, when applied to an input I′, outputs either that I′ is not valid, or I and an indication that I is valid.
Returning to
c=c_{1}∥mac (4)
Alternatively, first signature component c may be a concatenation of MAC mac and encrypted value c_{1}, that is, c=mac∥c_{1}. More generally, first signature component c may be a result of applying any reversible function f to encrypted value c_{1 }and MAC mac, that is, c=f (c_{1}, mac), where f is agreed on by the signer and the verifier. It will also be understood by a person of ordinary skill in the art that certain nonreversible functions may be used. For example, a function f that takes three elements x, y, and z as input, and outputs a concatenation of x and y, that is f(x,y,z)=x∥y, is not reversible because the output contains no information about element z. However, this function could still be used.
At 210, the signer computes a second signature component s, according to equation 5:
s=Hash(c∥V)·d_{A}+k (mod n), (5)
where Hash is a cryptographic hash function as described previously, and d_{A }is a private key of the signer, with a corresponding public key G_{A }having been computed as a product of private key d_{A }and base point G, that is G_{A}=d_{A}·G.
While not explicitly shown in the figures, other methods of calculating second signature component s are contemplated. For example, second signature component s could be calculated by switching the positions of private key d_{A }and first value k in equation 5, that is s=Hash(c∥V)·k+d_{A }(mod n). Alternatively, either of the terms in either one of these equations could be negated. If second signature component s is calculated using such a modification of equation 5, the verification procedure is changed accordingly.
Although not explicitly shown, Hash(c∥V) is converted to an integer for use in equation 5 or any of the alternatives to equation 5.
The expression c∥V denotes a concatenation of first signature component c and visible portion V of message M 104. Alternatively, visible portion V may be concatenated with first signature component c, that is, V∥c. More generally, first signature component c may be combined with visible portion V using any reversible function g, that is, g (c, V), where g is agreed on by the signer and the verifier. As described previously with respect to equation 4, certain nonreversible functions may also be used.
At 212, the signer prepares signed message 106, the signed message 106 comprising first signature component c, second signature component s, and visible portion V of message M 104. While first signature component c and visible portion V are shown as separate elements of signed message 106, it is contemplated that they may also be combined using reversible function g as was done during the computation of second signature component s at 210. For example, if first signature component c and visible portion V were concatenated as shown in equation 5, signed message 106 may comprise the same concatenation that is c∥V.
At 301, the verifier extracts first signature component c′, second signature component s′, and visible portion V′ of message M 104 from signed message 106. The apostrophe is used to indicate a value that has not yet been verified. As described previously, if first signature component c and visible portion V have been combined using reversible function g, the inverse of function g, that is, g^{−1}, will be necessary to extract first signature component c′ and visible portion V′ from signed message 106.
At 302, the verifier extracts encrypted value c_{1}′ and MAC mac′ from first signature component c′ using prerequisite length L associated with authenticated encryption function AE, which has been agreed on by the signer and the verifier. For example, if first signature component c was defined as the concatenation of encrypted value c_{1 }and MAC mac as shown in equation 4, the verifier can determine encrypted value c_{1}′ by defining the last L bits of first signature component c′ as MAC mac′, such that the remaining bits at the beginning of first signature component c′ correspond to encrypted value c_{1}′.
If encrypted value c_{1 }and MAC mac have been combined using some other reversible function f as described previously, the inverse of function f, that is f^{−1}, will be necessary to extract encrypted value c_{1}′ and MAC mac′ from first signature component c′.
It should be noted that the extraction described at 302 could be performed at any time prior to applying the authenticated decryption function at 308, as described in more detail below.
At 304, the verifier computes a value Q′, according to equation 6:
Q′=s′·G−Hash(c′∥V′)·G_{A}, (6)
where Hash is the same cryptographic hash function used by the signer to compute second signature component s at 210 as shown in equation 5. As previously described, if second signature component s has been calculated using a modification of equation 5, equation 6 will need to be modified accordingly. As in equation 5, Hash(c∥V) is converted to an integer for use in equation 6. Public key G_{A }110 may be received directly from signer or may be received from a trusted entity, such as a certificate authority. As previously described, other combinations of first signature component c′ and visible portion V′ are contemplated in place of the concatenation c′∥V′ shown in equation 6, provided the combination used in equation 6 corresponds to that used in computing second signature component s in equation 5.
At 306, the verifier constructs a derived key k_{1}′ from value Q′ using the same method used by the signer to construct derived key k_{1 }at 204. For example, if the signer has used key derivation function KDF to construct derived key k_{1 }as shown in equation 2, the verifier is to construct derived key k_{1}′ according to equation 7:
k_{1}′=KDF(Q′). (7)
At 308, the verifier applies an AD function that is a reverse transformation of the AE function that was used by the signer at 206. The AD function, which is keyed by derived key k_{1}′ and denoted AD_{k1′}, may be used to verify signed message 106 and recover hidden portion N of message 104. Result 108 of the AD function depends on whether the verifier is able to verify signed message 106. If the verifier determines that signed message 106 is valid, result 108 comprises recovered hidden portion N of message M 104 and an indication of validity. If the verifier determines that signed message 106 is invalid, result 108 comprises only an indication of invalidity, without hidden portion N.
Instead of jointly creating encrypted value c_{1 }and MAC mac using an AE function as described in equation 3 and shown at 206, the encryption and creation of a MAC can be performed as two separate steps. There are at least two variants of this which will be referred to as: (1) MACthenEncrypt (ME), and (2) EncryptthenMAC (EM). (There is also an EncryptandMAC variant. However, given that the EncryptandMAC variant is only secure for specific choices of encryption function and MAC function, the EncryptandMAC variant is not explicitly described.)
Both the encryption function and the MAC function may be secure functions. Examples of secure encryption functions include AES with Cipher Block Chaining (AESCBC) and AES Counter Mode (AESCTR) as described in “NIST SP 80038A Recommendation for Block Cipher Modes of Operation”, National Institute of Standards and Technology, 2001. Examples of secure MAC functions include AES Cipher Block Chaining Message Authentication Code (AESCBCMAC) as described in “ISO/IEC 9797 Data Cryptographic Techniques—Data integrity mechanism using a cryptographic check function employing a block cipher algorithm”, International Organization for Standardization, 1989, and AES Cipherbased MAC (AESCMAC) as described in “NIST SP 80038B Recommendation for Block Cipher Modes of Operation: The CMAC Mode for Authentication”, National Institute of Standards and Technology, 2005. The encryption function and MAC function are agreed on by the signer and the verifier.
(k_{1}, k_{2})=KDF(Q), (8)
where the output of KDF is longer than the output of the KDF used in equation 2, such that the output may be divided into first derived key k_{11 }and second derived k_{12}. Alternatively, first derived key k_{11 }and second derived k_{12 }could be constructed by applying a KDF to second value Q twice, using different auxiliary information for each application. While it is possible to apply a KDF to second value Q twice without using different auxiliary information for each application, this may not be advisable for security reasons.
At 405, the signer applies a MAC function T keyed by second derived key k_{12}, that is T_{k12}, to hidden portion N of message M 104 to obtain a MAC mac, according to equation 9:
mac=T_{k12}(N), (9)
where MAC mac has a prerequisite length L which is a parameter of MAC function T.
At 406, the signer applies an encryption function E keyed by first derived key K_{11}, that is E_{k11}, to a combination of hidden portion N and MAC mac to obtain a first signature component c, according to equation 10:
c=E_{k11}(N∥mac). (10)
The expression NlImac denotes a concatenation of hidden portion N and MAC mac. Alternatively, MAC mac may be concatenated with hidden portion N, that is mac∥N. More generally, hidden portion N may be combined with MAC mac using any reversible function j, that is j(N, mac), where j is agreed on by the signer and the verifier. As described previously with respect to equation 4, certain nonreversible functions may also be used.
Upon obtaining first signature component c at 406, the method proceeds as described with respect to
To decrypt first signature component c′, the verifier applies a decryption function D to first signature component c′ at 508, where decryption function D is a reverse transformation of encryption function E that was used by the signer at 406. The decryption function is keyed by first derived key k_{11}′ and is denoted D_{k11′}. This is shown in equation 11:
N′∥mac′=D_{k11′}(c), (11)
where N′∥mac′ denotes a concatenation of a hidden portion N′ of signed message 106 and a MAC mac′. The verifier is able to extract hidden portion N′ and MAC mac′ from the concatenation N′∥mac′ using prerequisite length L associated with MAC function T agreed on by the signer and the verifier. If hidden portion N and MAC mac were combined at 406 using some other reversible function j as described previously, the inverse of function j, that is j^{−1}, will be necessary to obtain hidden portion N′ and MAC mac′.
At 510, the verifier uses second derived key k_{12}′ to verify that MAC mac′ is a valid MAC of hidden portion N′ of signed message 106, and accordingly determines whether signed message 106 is valid. As described previously with respect to
It is also contemplated that an EncryptthenMAC/VerifythenDecrypt variant could be used as an alternative to the MACthenEncrypt/DecryptthenVerify variant.
At 606, the signer applies an encryption function E keyed by first derived key k_{11}, that is E_{k11}, to hidden portion N to obtain an encrypted value c_{1}, according to equation 12:
c_{1}=E_{k11}(N) (12)
At 607, the signer applies a MAC function T keyed by second derived key k_{12}, that is T_{k12}, to encrypted value c_{1 }to obtain a MAC mac, according to equation 13:
mac=T_{k12}(c_{1}), (13)
where MAC mac has a prerequisite length L which is a parameter of MAC function T.
Upon obtaining MAC mac at 607, the method proceeds as described with respect to
At 708, the verifier uses second derived key k_{12}′ to verify that MAC mac′ is a valid MAC of encrypted value c_{1}′, and accordingly determines whether signed message 106 is valid.
If the verifier determines that MAC mac′ is a valid MAC of encrypted value c_{1}′, the verifier proceeds to apply a decryption function D to encrypted value c_{1}′ at 710, where the decryption function is a reverse transformation of encryption function E that was used by the signer at 606. The decryption function is keyed by first derived key k_{11}′ and is denoted D_{k11′}. This is shown in equation 14:
N=D_{k11′}(c_{1}′). (14)
Because the verifier has already determined at 708 that MAC mac′ is a valid MAC of encrypted value c_{1}′, and consequently that signed message 106 is valid, result 108 comprises recovered hidden portion N of message M 104 and an indication of validity.
If the verifier determines at 708 that MAC mac′ is not a valid MAC of encrypted value c_{1}′, the verifier does not apply decryption function D at 710, and result 108 comprises only an indication of invalidity, without hidden portion N.
In another example, Authenticated Encryption with Associated Data (AEAD) can be used as part of a PintsovVanstone signature scheme with message recovery. For example, the AE function could be replaced by an AEAD function. AEAD is described in more detail by Rogaway in “Authenticated encryption with associated data”, Proceedings of ACM CCS'"'"'02: 98107, ACM, New York, 2002.
Similarly to the AEPV, MEPV, and EMPV schemes, an AEADPintsov Vanstone (AEADPV) scheme can be used to encrypt a hidden portion N of a message M that is to be embedded or hidden in the signature and to provide authenticity and confidentiality to that portion of the message. The AEADPV scheme uses the AEAD function to guarantee the authenticity of a visible portion V of the message (and thus may avoid use of a hash function). In many settings there are data associated with an encrypted value that is public to allow processing or routing of a message by intermediate parties who are not in possession of the encryption key. Using an AEAD function in place of an AE function in the previously described signature scheme has an advantage that a hash function is not involved.
The AEADPV scheme includes that the signer and the verifier agree on an AEAD function keyed by an integer k_{1 }that is able to take a hidden portion N and a visible portion V as inputs and to output an encrypted value c_{1 }and a MAC mac, that is AEAD_{k}(N, V)=(c_{1}, mac). The signer and the verifier also agree on an Authenticated Decryption with Associated Data (ADAD) function which is a reverse transformation of AEAD that is keyed by an integer k_{1}′ and that takes an encrypted value c_{1}′ and a MAC mac′ as inputs and outputs either the hidden portion N and an indication of validity, or null and an indication of invalidity, that is ADAD_{k1′}, (c_{1}′, mac′, V)=(N, VALID) or ADAD_{k1′} (c_{1}′, mac′, V)=(NULL, INVALID). The signer and the verifier also agree on the bit length of key k_{1 }and on the bit length of MAC mac. An example AEAD scheme suitable for use in the proposed framework is described by Kohno et al. in “CWC: A HighPerformance Conventional Authenticated Encryption Mode”, Proceedings of Fast Software Encryption 2004 (FSE'"'"'04), LNCS 3017: 408426, 2004.
At 806, the signer applies an AEAD function keyed by derived key k_{1}, that is AEAD_{k1}, to hidden portion N of message M 104 and visible portion V of message M 104 to obtain an encrypted value c_{1 }and a MAC mac of a prerequisite length L, where length L is a parameter associated with AEAD which has been agreed on by the signer and the verifier. This is shown in equation 15:
(c_{1}, mac)=AEAD_{k1}(N, V). (15)
The AEAD function is used to encrypt hidden portion N of message M 104 and to create a MAC that can be used by a verifier for subsequent verification of signed message 106. In particular, application of the AEAD function may be used to guarantee the authenticity of visible portion V, without involving a hash function, as described in more detail below.
After obtaining encrypted value c_{1 }and MAC mac at 806, the signer proceeds as described with respect to
At 810, the signer computes a second signature component s, according to equation 16:
s=mac·d_{A}+k(mod n), (16)
where MAC mac has been converted to an integer for use in equation 16. A comparison of equation 16 to equation 5 reveals that the hash function of the AEPV, MEPV, and EMPV authenticated encryption methods is not involved in AEADPV encryption.
While not explicitly shown in
Following computation of second signature component s at 208, the signer proceeds as described with respect to
At 904, the verifier computes a value Q′ using public key G_{A }110, according to equation 17:
Q′=s′·G−mac′·G_{A}, (17)
where MAC mac′ has been converted to an integer prior to use in equation 17. A comparison of equation 17 to equation 6 reveals that the hash function of the AEPV, MEPV, and EMPV authenticated decryption methods is not involved in AEADPV decryption.
As previously described, if second signature component s has been calculated using a modification of equation 16, equation 17 will need to be modified accordingly.
At 306, the verifier constructs a derived key k_{1}′ from value Q′ using the same method used by the signer to construct derived key k_{1 }at 204.
At 908, the verifier applies an ADAD function to encrypted value c_{1}′, MAC mac′ and visible portion V′, where the ADAD function is a reverse transformation of the AEAD function that was used by the signer at 806. The ADAD function, which is keyed by derived key k_{1}′ and denoted ADAD_{k1′}, may be used to verify signed message 106 and recover hidden portion N of message M 104. Result 108 of the ADAD function depends on whether the verifier is able to verify signed message 106. If the verifier determines that signed message 106 is valid, result 108 comprises recovered hidden portion N of message M 104 and an indication of validity. If the verifier determines that signed message 106 is invalid, result 108 comprises only an indication of invalidity, without hidden portion N.
As discussed previously, the proposed framework may also be applied to keyed ECPVS and other signcryption techniques. Signcryption provides the functionality of both a public key signature and encryption. The signer uses the verifier'"'"'s public key when creating the signcryption message. Only the verifier can decrypt the message and verify that it was signed by the signer using the verifier'"'"'s secret key and the signer'"'"'s public key. This differs from keeping the signer'"'"'s public key secret as in ECPVS, since the confidentiality is provided by the secrecy of the verifier'"'"'s secret key, and the signer'"'"'s public key may be public.
It will be appreciated that for very short messages M=N∥V, visible portion V may be null. The AEPV scheme can handle the case when visible portion V is null without modification. If hidden portion N is null, then hidden portion N should be replaced in the AEPV scheme by the zero byte or any other public constant. The AEADPV scheme may be able to handle null messages. If not, a null message or null portion of a message can be replaced by a public constant.
Signer device 1000 is able to perform one or more of the example methods illustrated in
Verifier device 1040 is able to perform one or more of the example methods illustrated in
Processors 1002 and 1042 may comprise any combination of processing units, digital signal processors, hardware accelerators, and the like. All or part of memory 1004 may be embedded in processor 1002. All or part of memory 1044 may be embedded in processor 1042.
Communication interfaces 1006 and 1046 may be wired communication interfaces or wireless communication interfaces or optical communication interfaces. For example, communication interfaces 1006 and 1046 may be Universal Serial Bus (USB) interfaces, Ethernet interfaces, Integrated Services Digital Network (ISDN) interfaces, Digital Subscriber Line (DSL) interfaces, Local Area Network (LAN) interfaces, HighDefinition Multimedia (HDMI) interfaces, Digital Visual Interfaces (DVIs), or Institute of Electrical and Electronics Engineers (IEEE) 1394 interfaces such as i.LINK™, Lynx^{SM} or Firewire®. In another example, communication interfaces 1006 and 1046 may be Wireless Local Area Network (WLAN) interfaces, shortrange wireless communication interfaces such as Wireless Personal Area Network (WPAN) interfaces, near field communication interfaces, wireless metropolitan area network (WMAN) interfaces, or Wireless Wide Area Network (WWAN) interfaces.
The functionality of one or more of the example methods illustrated in
Each of memories 1004 and 1044 is able to store parameters 1010 that have been agreed on by signer device 1000 and verifier device 1040. Examples of agreed on parameters 1010 are elliptic curve domain parameters D, one or more key derivation functions, one or more hash functions, one or more functions associated with a signature scheme to be implemented (for example, one or more of an AE function, a MAC function, an encryption function, and an AEAD function), as well as parameters associated with the signature scheme, such as a prerequisite length L of a message authentication code.
Memory 1004 is able to store a private key d_{A }1012 of signer device 1000 that corresponds to public key G_{A }1014 of signer device 1000. Memory 1004 is also able to store a first value k 1016 and a second value Q 1018 as computed at 202, except for those implementations where the pair (k, Q) is ephemeral and thus not stored in memory. Memory 1004 is able to store a hidden portion N 1020 and a visible portion V 1022 of a message to be signed. In addition, memory 1004 is able to store one or more derived keys 1024 as constructed at 204 or 404, encrypted value c_{1 }1026 as computed at 206, 606, or 806 and message authentication code mac 1028 as determined at 206, 405, 607, or 806. Memory 1004 is able to store a first signature component c 1030 as determined at 208 or 406, and a second signature component s 1032 as determined 210 or 810. Memory 1004 may store additional elements which are not explicitly shown in
As denoted by an arrow 1034, a signed message 1036 comprising visible portion V 1022, first signature component c 1030, and second signature component s 1032 is able to be sent, directly or via one or more intermediaries, from signer device 1000 to verifier device 1040, where it may be stored in memory 1044 of verifier device 1040. While not explicitly shown, signed message 1036 may be sent from signer device 1000 via communication interface 1006 and may be received by verifier device 1040 via communication interface 1046.
The functionality of one or more of the example methods illustrated in
Memory 1044 is able to store public key G_{A }1014 of signer device 1000, which it may have received directly from signer device 1000 or from a trusted device (not shown), possibly via communication interface 1046 and possibly by other means. For example, public key G_{A }1014 of signer device 1000 may be included in software installed on verifier device 1040. Memory 1044 is also able to store a value Q′ 1050 as determined at 304 or 904, one or more derived keys 1052 as constructed at 306 or 506, encrypted value c_{1}′ 1054 as extracted at 302 and message authentication code mac′ 1056 as determined at 302 or 508, and recovered hidden portion N 1020. Memory 1044 may store additional elements which are not explicitly shown in
Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims.