Information Security Management Handbook, Sixth Edition (2012)
DOMAIN 5: CRYPTOGRAPHY
Cryptographic Concepts, Methodologies, and Practices
Chapter 20. Elliptic Curve Cryptosystems
Jeff Stapleton
Cryptography Overview
Cryptography, from the Greek words “kryptos” and “graphin” for hidden and secret writing, has a broader meaning for protecting electronic information during transmission and in storage. The birth of writing, depending on one’s perspectives of ideographs, mnemonic symbols, or phonetic writing, seems to be somewhere between 8000 and 6000 years old. Cryptography, by comparison, is a 4000-year-old technology attributed to an Egyptian scribe using unusual hieroglyphics carved about 1900 BC in the main tomb chamber of the nobleman Khnumhotep II. One of the more well-known ancient methods is the Caesar Cipher based on the Grecian writer Polybius’ signaling system used by Julius Cesar during the Gallic Wars. Another well-known historical method is the Jefferson Wheel based on the French Vigenére cipher used by the U.S. Army in World War I.1World War II ushered in the modern cryptography era, notably with the declassification and publication of Claude Shannon’s paper “The Communication Theory of Secrecy Systems,” published in the Bell System Technical Journal in 1949.2
Information security afforded by modern cryptography includes data confidentiality, integrity, authenticity, nonrepudiation, and reliability.3 Modern cryptography is based on mathematically “hard” problems translated into algorithms or schemes. Algorithms are the basic building blocks with a precise set of rules having specific inputs and outputs. Schemes are more general in nature, characteristically using one or more algorithms in an orderly fashion to achieve a particular information security goal such as data encryption, digital signature, or establishing cryptographic keys. Protocols are implementations of a particular scheme incorporating algorithms, configuration parameters, inputs, and outputs.
For example, one such “hard” problem is factorization for the RSA public key schemes introduced by its inventors, Rivest et al. in 1978.4 The RSA modulus is the product of two random prime numbers, which is difficult to factor for very large numbers. Another difficult problem is discrete logarithms (DLs), which are group theory analogs of ordinary logarithms. Recall that the log of a number is the power to which a base number must be raised to produce that number, e.g., the log of 343 is 3 for base 7 because 73=343. The first DL scheme was the key agreement protocol proposed by Diffie and Hellman in 1976.5 ElGamal described another DL scheme for digital signature in 1984. Another DL scheme is the Digital Signature Algorithm (DSA) proposed by the National Institute of Standards and Technology (NIST) in 1991 and published as FIPS PUB 186 in 1994. All of these DL schemes can be described in the abstract setting of a finite cyclic group, including elliptic curve groups, which provide the foundation for elliptic curve cryptosystems (ECCs).6
Elliptic Curve Cryptography
The study of elliptic curves (which is not an ellipse) by algebraists and number theorists dates back to the mid-nineteenth century. Hence, elliptic curves have a rich history, having been studied by mathematicians for over 100 years with an extensive literature describing their elegant properties. They have been used to solve a diverse range of problems, such as Lenstra’s elliptic curve factorization method (ECM) and including proving Fermat’s Last Theorem.6
An elliptic curve is a set of points specified by two coefficients a and b, which are elements of a finite field Fq of the size prime number q, e.g., an equation of the form y2=x3+ax+b.7
Elliptic curve systems as applied to ElGamal protocols were first proposed in 1985 independently by Koblitz8 from the University of Washington, and Miller9 then at IBM. The security of the cryptosystems using elliptic curves hinges on the intractability of the DL problem in the algebraic system (another “hard” problem). Unlike the case of the DL problem in finite fields, or the problem of factoring integers, there is no subexponential-time algorithm known for the elliptic curve DL problem. The best algorithm known to date takes fully exponential time.
ECC Schemes
Digital Signatures
Digital signatures in lieu of written signatures are computed using a set of rule and parameters that allow the identity of the signatory and the integrity of the signed data to be verified by a relying party. A cryptographic private key is to generate a digital signature, the digital signature is provided to the relying party along with the signed data, and the corresponding cryptographic public key (not the same as the private key) is used to verify the digital signature. Public keys may be known and used by anyone; however, only the signer posses the associated private key. Anyone can verify the signature by employing the signatory’s public key. Only the user that possesses the private key can perform signature generation. Digital signatures may be used for stored or transmitted data.10
Federal Information Processing Standards Publication (FIPS PUB) 186-3 defines three approved methods for digital signature generation and verification. (1) DSA is specified in FIPS PUB 186-3, which includes criteria for the generation of domain parameters, for the generation of public and private key pairs, and for the generation and verification of digital signatures. (2) The RSA DSA is specified in American National Standard X9.31 and Public Key Cryptography Standard (PKCS) #1. FIPS 186-3 approves the use of implementations of either or both of these standards, but specifies additional requirements. (3) The Elliptic Curve Digital Signature Algorithm (ECDSA) is specified in ANS X9.62. FIPS 186-3 approves the use of ECDSA, but specifies additional requirements.10
The ECDSA X9.62 standard provides methods and criteria for the generation of public and private keys that are required by the ECDSA and the procedural controls required for the secure use of the algorithm with these keys. ECDSA is the elliptic curve analog of the DSA defined in FIPS PUB 186.10 The ECDSA standard also provides methods and criteria for the generation of elliptic curve domain parameters that are required by the ECDSA and the procedural controls required for the secure use of the algorithm with these domain parameters.7
Key Establishment
Key establishment schemes are cryptographic methods that establish keying data suitable for subsequent cryptographic use by cryptographic schemes to its legitimate users. Key agreement schemes and key transport schemes are types of key establishment schemes. A key transport scheme is a key establishment scheme in which the keying data established is determined entirely by one entity. A key agreement scheme is a key establishment scheme in which the keying data established is a function of contributions provided by both entities in such a way that neither party can predetermine the value of the keying data.11
X9.63 specifies asymmetric key establishment schemes. The operation of each of the schemes employs arithmetic operations in the group of points on an elliptic curve defined over a finite field. The standard defines both key agreement schemes and key transport schemes. Common to all schemes, the elliptic curve domain parameters are previously known by each participating entity. The public key of at least one entity is exchanged with the other, although sometimes both entities exchange public keys. As an additional security precaution, some of the schemes use ephemeral keys, which are short-lived asymmetric keys whose lifetime is limited to the actual key establishment process. Hence, the standard distinguishes between “static” longtime keys where the public key is typically encapsulated in an X.509 certificate and ephemeral keys. The standard also offers the elliptical curve analog of the Diffie–Hellman key agreement method.
The eleven (11) key agreement schemes provided in X9.62 include the following:
Ephemeral Unified Model Scheme
1-Pass Diffie–Hellman Scheme
Static Unified Model Scheme
Combined Unified Model with Key Confirmation Scheme
1-Pass Unified Model Scheme
Full Unified Model Scheme
Full Unified Model with Key Confirmation Scheme
Station-to-Station Scheme
1-Pass MQV Scheme
Full MQV Scheme
Full MQV with Key Confirmation Scheme
The Menezes–Qu–Vanstone (MQV) schemes incorporate both static and ephemeral asymmetric keys.
The two (2) key transport schemes provided in X9.62 include the following:
1-Pass Transport Scheme
3-Pass Transport Scheme
Each scheme has slightly different characteristics that can be applied depending on the application requirements and environmental restrictions such as data size considerations, the number of messages exchanges, and computational restrictions. The standard also provides background on finite fields, elliptic curve and point compression, data conversion, cryptographic primitives common to the various key establishment schemes including number-theory algorithms, security considerations, and examples.
Identity-Based Encryption
Identity-based cryptography is an asymmetric method of employing a relatively unique yet publicly available data element such as an electronic mail (e-mail) address or an Internet Protocol (IP) address as the public key and securely deriving the corresponding private key. Although the concept had been theorized as early as 1984 by Adi Shamir, one of the first practical implementations for identity-based encryption (IBE) was finally devised by Boneh and Franklin in 2001.12,13
IBE is based on bilinear maps, which is a relationship between three groups such that any two elements, one from the first group and another from the second group, map to a third group. This allows a public key generator to determine a private key for a chosen public key such that a message encrypted with the public key can only be decrypted using the derived private key. The chosen public key must be an assigned identifier unique to the key pair owner.
RFC 5409 defines the way to use the Boneh–Franklin and Boneh–Boyen IBE public-key algorithms in the Cryptographic Message Syntax (CMS). IBE is a public-key technology for encrypting content-encryption keys (CEK) implemented within the framework of the CMS using the recipient’s e-mail address. The sender can use the recipient’s public “email” key to encrypt a message, a trusted intermediary party can generate the private key for the public “email” key, and the recipient can decrypt the message using the derived private key.
IBE can avoid the complexity of requesting, distributing, verifying, and revoking public key certificates by using publicly managed information such as e-mail or IP addresses.
Implicit Certificates
An implicit certificate scheme differs from a traditional certificate scheme by removing the explicit inclusion of a public key and a trusted third-party signature on that key and associated identity with the notion just a public-key reconstruction value. Traditional public key certificates are created by a trusted third-party certificate authority (CA). The CA signature on the certificate binds the subject’s identity to the subject’s public key. X.509 certificates range in size from 1100 bytes for a 160-bit ECC public key to 1650 bytes for a 2048-bit RSA public key.14
An ECC implicit certificate consists of two elements, the subject’s identity value and public key reconstruction data, issued from a CA. The subject’s public key can be reconstructed by a relying party based on the subject’s identity value, the reconstruction data, and the CA public key. The subject proves its identity with a relying party by engaging in an action that requires the action of the subject’s private key. The benefit is that the implicit certificate is a third of an X.509 certificate. Thus, an 1100 byte X.509 certificate for a 160-bit ECC public key is reduced to a 376 byte implicit certificate.
Summary
Cryptography is a 4000-year-old technology that has recently been enriched in the past 25 years by elliptic curve cryptography (ECC) based on 100 years of mathematical research. ECC offers digital signature, key management schemes, IBE, and implicit certificates. Its relative cryptography strength for smaller key sizes makes it ideal for less powerful systems, narrower bandwidth, and storage constraints. Moore’s law of doubling the number of transistors on an integrated circuit every 2 years has continued to increase computing power and consequently pushed the need for stronger and larger cryptographic keys. Even the National Security Agency (NSA) has recognized its importance as its Suite B cryptography includes ECDSA, Ephemeral Unified Model Scheme, and 1-Pass Diffie–Hellman Scheme (ECHD).
References
1. Kahn, D. The Code Breakers: The Story of Secret Writing. Macmillan Publishing Company, New York, ISBN 0-02-560460-0, 1967.
2. Schneier, B. Applied Cryptography, Second Edition: Protocols, Algorithms, and Source Code in C. Wiley, New York, ISBN 0-471-12845-7, 1995.
3. Tipton, H. F. and Nozaki, M. K. Information Security Management Handbook, Sixth Edition, vol. 4. Auerbach, New York, ISBN 978-1-4398-1902-9, 2010.
4. Rivest, R., Shamir, A., and Adleman, L. A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM 21(2): 120–126, 1978.
5. Diffie, W. and Hellman, M. E. New directions in cryptography. IEEE Transactions on Information Theory 22(6): 644–654, 1976.
6. Hankerson, D., Menezes, A., and Vanstone, S. Guide to Elliptic Curve Cryptography. Springer, New York, ISBN 0-387-95273-X, 2004.
7. American National Standard X9.62-2005, Public key cryptography for the financial services industry—The elliptic curve digital signature algorithm (ECDSA).
8. Koblitz, N. Elliptic curve cryptosystems. Mathematics of Computation 48: 203–209, 1987.
9. Miller, V. Use of elliptic curves in cryptography, Advances in Cryptology—CRYPTO 85 (Santa Barbara, CA), LNCS 218, 417–426, 1985.
10. Federal Information Processing Standards Publication (FIPS PUB) 186-3, Digital signature standard (DSS), National Institute of Standards and Technology, Information Technology Laboratory, June 2009.
11. American National Standard X9.63-2001, Public key cryptography for the financial services industry—Key agreement and key transport using elliptic curve cryptography.
12. Shamir, A. Identity-based cryptosystems and signature schemes. Advances in Cryptology: Proceedings of CRYPTO 84. LNCS 7: 47–53, 1984.
13. Dan, B. and Matt, F. Identity-based encryption from the Weil pairing. In Advances in Cryptology—CRYPTO 2001, LNCS 2139/2001. Springer, pp. 213–229, 2001.
14. American National Standard X9.123-draft, Elliptic curve Qu-Vanstone implicit certificates.
15. Menezes, A. J., Qu, M., and Vanstone, S. A. Some new key agreement [MQV] protocols providing implicit authentication. Workshop record. 2nd Workshop on Selected Areas in Cryptography (SAC ’95), Ottawa, ON, May 18–19, 1995.
16. Law, L., Menezes, A., Qu, M., Solinas, J., and Vanstone, S. An efficient protocol for authenticated key agreement [MQV]. Technical report CORR 98-05, Department of Combinatorics & Optimization, University of Waterloo, March 1998.
17. Internet Engineering Task Force (IETF). Using the Boneh–Franklin and Boneh–Boyen Identity-Based Encryption Algorithms with the Cryptographic Message Syntax (CMS). RFC 5409, 2009.