Status

Draft

Purpose and Origin

Cryptography is an algorithmic process of converting a plain text (or clear text) message to a cipher text (or cipher) message based on an algorithm that both the sender and receiver know, so that the cipher text message can be returned to its original, plain text form. In its cipher form, a message cannot be read by anyone but the intended receiver. The act of converting a plain text message to its cipher text form is called enciphering. Reversing that act (i.e., cipher text form to plain text message) is deciphering. Enciphering and deciphering are more commonly referred to as encryption and decryption, respectively.

There are a number of algorithms for performing encryption and decryption, but comparatively few such algorithms have stood the test of time. The most successful algorithms use a key. A key is simply a parameter to the algorithm that allows the encryption and decryption process to occur. There are many modern key-based cryptographic techniques [Schneier 96]. These are divided into two classes: symmetric and asymmetric (also called public/private) key cryptography. In symmetric key cryptography, the same key is used for both encryption and decryption. In asymmetric key cryptography, one key is used for encryption and another, mathematically related key, is used for decryption.

Symmetric Key Cryptography

The most widely used symmetric key cryptographic method is the Data Encryption Standard (DES) [NIST 93]. Although originally published in 1977 by the National Bureau of Standards (reprinted in [Beker+ 82]), DES has not yet been replaced by any other symmetric-key approach. DES uses a fixed length, 56-bit key and an efficient algorithm to quickly encrypt and decrypt messages. DES can be easily implemented in hardware, making the encryption and decryption process even faster. In general, increasing the key size makes the system more secure. A variation of DES, called Triple-DES or DES-EDE (encrypt-decrypt-encrypt), uses three applications of DES and two independent DES keys to produce an effective key length of 168 bits [ANSI 85].

The International Data Encryption Algorithm (IDEA) was invented by James Massey and Xuejia Lai of ETH Zurich, Switzerland in 1991 and is patented and registered by the Swiss Ascom Tech AG, Solothurn [Lai 92]. IDEA uses a fixed length, 128-bit key (larger than DES but smaller than Triple-DES). It is also faster than Triple-DES. In the early 1990s, Don Rivest of RSA Data Security, Inc., invented the algorithms RC2 and RC4. These use variable length keys and are claimed to be even faster than IDEA. However, implementations may be exported from the U.S. only if they use key lengths of 40 bits or fewer.

Although symmetric key cryptography works, it has a fundamental weak spot-key management. Since the same key is used for encryption and decryption, it must be kept secure. If an adversary knows the key, then the message can be decrypted. At the same time, the key must be available to the sender and the receiver and these two parties may be physically separated. Symmetric key cryptography transforms the problem of transmitting messages securely into that of transmitting keys securely. This is a step forward, because keys are much smaller than messages, and the keys can be generated beforehand. Nevertheless, ensuring that the sender and receiver are using the same key and that potential adversaries do not know this key remains a major stumbling block. This is referred to as the key management problem.

Public/Private Key Cryptography

Asymmetric key cryptography overcomes the key management problem by using different encryption and decryption key pairs. Having knowledge of one key, say the encryption key, is not sufficient enough to determine the other key - the decryption key. Therefore, the encryption key can be made public, provided the decryption key is held only by the party wishing to receive encrypted messages (hence the name public/private key cryptography). Anyone can use the public key to encrypt a message, but only the recipient can decrypt it.

James Ellis, Malcolm Williamson, and Clifford Cocks first investigated public/private key cryptography at the British Government Communications Headquarters (GCHQ) in the early 1970s [Ellis 87]. The first public discussion of public/private key cryptography was by Whitfield Diffie and Martin Hellman in 1976 [Diffie+ 76].

A widely used public/private key algorithm is RSA, named after the initials of its inventors, Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman [RSA 91]. RSA depends on the difficulty of factoring the product of two very large prime numbers. Although used for encrypting whole messages, RSA is much less efficient than symmetric key algorithms such as DES. ElGamal is another public/private key algorithm [El Gamal 85]. It uses a different arithmetic algorithm than RSA, called the discrete logarithm problem. An extensive discussion of public/private key cryptography, including much of the mathematical detail, can be found in the book, Public Key Cryptography [Salomaa 96].

Technical Detail

The mathematical relationship between the public/private key pair permits a general rule: any message encrypted with one key of the pair can be successfully decrypted only with that key's counterpart. To encrypt with the public key means you can decrypt only with the private key. The converse is also true - to encrypt with the private key means you can decrypt only with the public key.

The decision as to which key is kept private and which is made public is not arbitrary. In the case of RSA, the public key uses exponents that are relatively small (in comparison to the private key) making the process of encryption and digital signature verification (discussed later) faster.

Figure 1 illustrates the proper and intended used of public/private key cryptography for sending confidential messages. In the illustration, a user, Bob, has a public/private key pair. The public portion of that key pair is placed in the public domain (for example in a Web server). The private portion is guarded in a private domain, for example, on a digital key card or in a password-protected file.

Figure 1: Proper Use of Public Key Cryptography

For Alice to send a secret message to Bob, the following process needs to be followed:

1. Alice passes the secret message and Bob's public key to the appropriate encryption algorithm to construct the encrypted message.
   
2. Alice transmits the encrypted message (perhaps via e-mail) to Bob.
   
3. Bob decrypts the transmitted, encrypted message with his private key and the appropriate decryption algorithm.

Bob can be assured that Alice's encrypted secret message was not seen by anyone else since only his private key is capable of decrypting the message.

Since we know that a private key can also be used to encrypt messages, Bob could technically respond in secret to Alice's original message by using the same public/private key pair as illustrated in Figure 2.

Figure 2: Improper Use of Public Key Cryptography

In this scenario:

1. Bob passes the secret reply and his private key to the encryption algorithm to construct the encrypted reply.
   
2. Bob transmits the encrypted reply to Alice.
   
3. Alice decrypts the transmitted, encrypted reply with Bob's public key and the decryption algorithm to read this reply.

Unfortunately, Bob's message will not be confidential because anyone with access to the encrypted reply and Bob's public key (which is in the public domain) can decrypt the reply and see the text of the message. However, if Alice had her own public/private key pair, then Bob and Alice could communicate confidentially. In this case, Bob would send messages encrypted with Alice's public key (which only Alice could decrypt by using her private key), and Alice would send messages to Bob encrypted with Bob's public key (which only he could decrypt using his private key).

Usage Considerations

Public key cryptography is especially useful in situations where there is a need for confidentiality, integrity, and non-repudiation. That is, in situations where the messages being passed are intended to only be shared by the sending and receiving parties. Further, public key cryptography is used in situations where the recipient of a message must have confidence that the message received was received as intended by the sender and has not been altered or forged in any manner.

Confidentiality assures that unintended third parties can not view information sent between two communicating parties. Encryption is the most widely used mechanism for providing confidentiality over an insecure medium.

Integrity is knowing that the message you receive was exactly what was sent and it was unaltered or damaged during transmission. Digital signatures are used to seal a message as a means to warn if the integrity of a message has been compromised. Today, Web content that executes on local workstations is commonly downloaded. Knowing that the content has not been surreptitiously modified is critical if you are to trust the content. If the content is from a trusted source and it is unmodified, your confidence in that content is higher - because the content has integrity. If the content is from an unknown source or you cannot tell if it has been modified, the content cannot be trusted. Mechanisms such as digital signatures and certificates help maintain the integrity of exchanged products and services.

Non-repudiation is the inability to disavow an act. In other words, evidence exists that prevents a person from denying an act. For example, you log in to a computer system by presenting a user name and password. Most software applications consider this sufficient evidence to permit access, but could it be proved that it was really you that was logged in? You could argue that someone else obtained your password, possibly using snooping techniques. Now, suppose that a computer system requires a fingerprint or retinal image to gain access. Contesting the fact now becomes more difficult.

Finally, as opposed to symmetric key cryptography, public key cryptography is a useful means of getting around issues dealing with key distribution and management.

Maturity

Public key cryptography has been in use for more than 30 years. Secure Sockets Layer (SSL) defined by Netscape is a popular application of public key cryptography found in Web-enabled applications requiring secure communications and authentication. Pretty Good Privacy (or PGP) is another popular application of public key cryptography used to send confidential electronic mail and digitally signing electronic documents.

Further, a number of commercial companies have become third party providers of public key cryptography software including, but not limited to, RSA Security, Inc, Sun Microsystems, Microsoft, Entrust, Inc., and VeriSign, Inc.

Costs and Limitations

Cost to implement public key cryptography in a system vary according to size and scope. Characteristics that can determine costs include the number of pair-wise keys that need to be created for the purposes of confidentiality and integrity. For example, securing all corporate email will require that employers to issue public keys to all of its employees and enforce the use of those key when communicating corporate ideas and correspondence. Systems are available to support such wide use but come at a cost. A counter-example of this would be a corporate "portal" or web site available to the public from which the public may be asked to place orders. In such a case, the corporation may only be required to acquire public key cryptography for the one or more server(s) that will be used to interact with the public, this is typically a annual cost from security providers such as VeriSign, Inc.

Using this technology may require network management personnel with knowledge of public key cryptography and the use of software that implements public key cryptography and digital signature algorithms especially if an outside provider for public key infrastructures is NOT used. It also requires security personnel and software that can generate, distribute, and control encryption/decryption keys and respond to the loss or compromise of keys.

Index Categories

This technology is classified under the following categories. Select a category for a list of related topics.

Name of technology	Public Key Cryptography
Application category	Information Security (AP.2.4)
Quality measures category	Security (QM.2.1.5)
Computing reviews category	Operating Systems Security & Protection (D.4.6), Security & Protection (K.6.5), Computer-Communications Networks Security and Protection (C.2.0)

References and Information Sources

[Abrams 95]	Abrams, Marshall D.; Jajodia, Sushil; & Podell, Harold J. Information Security An Integrated Collection of Essays. Los Alamitos, CA: IEEE Computer Society Press, 1995.
[Schneier 96]	Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, 2nd editon by , John Wiley & Sons, ISBN 0471128457, 1996.
[NIST 93]	Data Encryption Standard (DES) (FIPS PUB 46-2). Gaithersburg, Md.: National Institute of Standards and Technology, January, 1993. Available WWW: <URL: http://www.nist.gov/itl/div897/pubs/fip46-2.htm>.
[Beker+ 82]	Beker, H. & Piper, F. Cipher Systems. London: Northwood Books, 1982.
[ANSI 85]	ANSI X9.17-1985, American National Standard, Financial Institution Key Management (Wholesale), American Bankers Association, Section 7.2. New York: American National Standards Institute, 1985.
[Lai 92]	Lai, X. ETH Series on Information Processing (J.L. Massey, ed.). Vol. 1, On the Design and Security of Block Ciphers. Konstanz, Switzerland: Hartung-Gorre Verlag, 1992.
[Ellis 87]	Ellis, J.H. ìThe Story of Non-Secret Encryption.î Cheltenham, UK: Communications Electronics Security Group, 1987. Available WWW: <URL: http://www.cesg.gov.uk/about/nsecret/ellis.htm>
[Diffie+ ]	Diffie, W. & Hellman, M.E. ìNew Directions in Cryptography.î IEEE Transactions on Information Theory, IT-22, Vol. 6, pp. 644-654, 1976.
[RSA 91]	PKCS #1: RSA Encryption Standard, Version 1.4. San Mateo, Ca.: RSA Data Security, Inc., 1991.
[El Gamal 85]	El Gamal, T. ìA Public Key Cryptosystem and Signature Scheme Based on Discrete Logarithms.î IEEE Transactions on Information Theory, IT-31, pp. 469-473, 1985.
[Salomaa 96]	Salomaa, A. Public-Key Cryptography, 2nd edition. Berlin: Springer-Verlag, 1996.

Current Author/Maintainer

Scott A. Hissam, SEI

External Reviewers

Modifications

9 Dec 01 (original)