Explanation of the Three Types of Cryptosystems - GIAC Research in the Common Body of Knowledge

Explanation of the Three Types of Cryptosystems: Category: Cryptography
Author: Eric Conrad
Date Added: February 6th, 2007

Introduction

This paper discusses the three types of cryptosystems: Symmetric key, Asymmetric key and Hash Functions. Symmetric key encryption uses one key to encrypt and decrypt. Asymmetric key encryption uses two keys; when one key is used to encrypt, the other is used to decrypt. Hash functions create a message digest via an algorithm and use no key.

Symmetric Key Encryption

Symmetric key (also called private key or secret key) cryptography uses the same key to encrypt and decrypt. The name "private key" derives from the need to keep the key private. A major challenge associated with symmetric key cryptosystems is the secure distribution of keys.

Common symmetric key encryption algorithms include DES (the Data Encryption Standard) and AES (the Advanced Encryption Standard).

The following diagram illustrates an exchange of messages using a symmetric key. Alice must first transmit the symmetric key "XYZZY" to Bob via a secure channel. After the key is received, Alice can then encrypt the plaintext with the same key and transmit the ciphertext to Bob, who can then decrypt the ciphertext using the same key.

The security of the exchange relies on the security of the symmetric key. If an attacker intercepts the symmetric key, the attacker can read the ciphertext and he can create new ciphertext.

Asymmetric Key Encryption

Asymmetric key encryption (also called public key encryption) uses two keys: a public and a private key. Data encrypted with one key can be decrypted only with the other key.

Whitfield Diffie and Martin Hellman first publicly described this approach in November 1976 in New Directions in Cryptography, where they announced: We stand today on the brink of a revolution in cryptography.¹ The paper described trapdoor functions (sometimes called one-way functions), which are simple to calculate in one direction but difficult to calculate in reverse (without access to trapdoor information). Diffie and Hellman's paper described using the computation of large logarithms as a trapdoor function.

A logarithm is the reverse of exponentiation. Calculating 7 to the 13^th power (96,889,010,407) is computationally simple. Calculating the logarithm of 96,889,010,407 into 7 to the 13^th power is much more difficult.

In this example, the integers 7 and 13 are trap door information, which allows the key owner to efficiently calculate the trapdoor function. As Diffie and Hellman explained:

The situation is precisely analogous to a combination lock. Anyone who knows the combination can do in seconds what even a skilled locksmith would require hours to accomplish. And yet, if he forgets the combination, he has no advantage.²

Other one-way functions used for asymmetric cryptography include factoring large numbers and elliptic curves.

The factoring method relies on the fact that calculating a large number from the product of three primes³ is relatively easy, but calculating the original three primes from a large number is much harder. For example, calculating 7349 * 2731 * 6899 = 138,463,750,981 can be done in less than a second on any modern calculator. However, factoring 138,463,750,981 into the original three primes is much more difficult.

Elliptic Curve Cryptography (ECC) uses calculation of points on an elliptic curve as the basis for encryption. Multiplying points on an elliptic curve is analogous to exponentiation, and ECC is similar to (but more difficult than) computing logarithms. Because reversing the function is more difficult, ECC is thought to be more secure⁴ than other asymmetric algorithms using the same key size; this allows for smaller keys.

Asymmetric cryptography solves the challenge of secure distribution of secret keys. User Alice wants to email Bob( a student at MIT) securely. She goes to MIT's public key server, http://pgp.mit.edu/⁵, looks up his email address (bob@mit.edu), and finds his public key.

Alice can then use a program, such as Pretty Good Privacy (PGP),⁶ to encrypt a message using Bob's public key. After encrypted, only Bob's private key (held securely by Bob) can decrypt the message. Bob can then respond securely by using Alice's public key⁷ to encrypt his reply.

Asymmetric key encryption also provides authentication. Only Alice has access to her secret key, so if Bob is able to decrypt a message with Alice's public key, he has assurance that Alice is the author.

Diffie-Hellman Key Exchange

Asymmetric algorithms are more complex than their symmetric counterparts and require more processing power. The Diffie-Hellman key exchange was designed to leverage the strengths of each type of encryption, and it uses asymmetric encryption to securely exchange a symmetric session key. That symmetric key is then used as a session key for encryption (typically using an algorithm such as DES or AES), and it can be changed at regular intervals.

The name Diffie-Hellman is typically used, but a more appropriate name is "Diffie-Hellman-Merkle key exchange," based on Ralph Merkle's contributions.⁸

Hash Functions

Hash functions are also called one-way encryption. A hash function transforms plaintext into a fixed length string which is called a message digest (or simply a hash). It is called one-way encryption because there is no way to convert the message digest back into plaintext.⁹

The most popular hash functions are MD5 (Message Digest 5), which uses 128 bits and SHA1 (Secure Hash Algorithm 1)¹⁰, which uses 160 bits.

Here is an example of the MD5 hash function:

Regardless of input length, the MD5 hash function generates a 128-bit hash (shown in hex here). A change of a single character in the phrase should result in a different MD5 hash. Due to this quality, hashes are often used for data integrity; if a hash of a file has changed, the file contents have changed.

Hashes are not unique. For example, Alice generates a 128-bit (or 16-byte) MD5 hash of the ls program on her Unix system (typically around 300K). The universe of unique 300 kilobyte strings is larger than the universe of unique 16-byte strings. Therefore, there will be collisions, where two different strings (or Unix programs) can generate the same MD5 hash. Attackers can attempt to alter data and generate a collision to hide the alteration.

A good hash function should produce message digests that are impossible to brute force (systematically search for a collision) in a reasonable amount of time. The hash function should also have statistically evenly distributed collisions. This is called strong collision resistance.

Passwords

Hashes are used for password storage on modern operating systems to avoid storing users' unencrypted passwords on the system. Many Linux distributions use MD5 hashes.

A user attempts to log onto a system by typing his password. The system then takes that password and generates a hash using MD5 and compares the generated hash with the stored hash¹¹. If they match, the user is authenticated.

Digital Signatures

Hash functions are also used with asymmetric encryption to provide digital signatures. As the name implies, a digital signature is the electronic counterpart to a written signature.

User Alice wishes to sign an email she sends to Bob. She generates a 160-bit SHA1 hash of her email body text, and then she encrypts the hash with her private key. This creates a digital signature. She then sends Bob the email with the digital signature attached.

Bob receives the email and generates a 160-bit SHA1 signature of the email body text. He then decrypts the digital signature with Alice's public key.¹² This produces the original 160-bit SHA1 hash that Alice created. Bob then compares the two hashes. If they match, he has a high assurance of integrity that the email has not been altered.

In addition to integrity, digital signatures provide non-repudiation. Not only does Bob know that Alice's email has not been altered, he also knows that Alice (or someone holding Alice's secret key) signed it. Thus, Alice cannot later deny (repudiate) signing the email.

Summary

In summary, Symmetric key and Asymmetric key encryption provide confidentiality, which ensures the privacy of data. They can also be used to provide authentication (where knowledge of a key serves as proof of identity). Hash functions can be used to provide integrity, which ensures that data has not been altered. Additionally, Asymmetric key encryption (often combined with hashes) can be used for non-repudiation (proving a user performed a specific action).

¹ Diffie, Whitfield and Martin Hellman. "New Directions in Cryptography" IEEE Transactions on Information Theory. Nov. 1976. URL: http://crypto.csail.mit.edu/classes/6.857/papers/diffie-hellman.pdf.

² New Directions in Cryptography, page 9.

³ A prime number is evenly divisible only by 1 and itself.

⁴ ECC is fairly new, as it was independently discovered by Neal Koblitz and Victor S. Miller in 1985. Newer cryptographic algorithms are at higher risk for undiscovered attacks.

⁵ Lists of public key servers are available online; http://www.rossde.com/PGP/pgp_keyserv.html is one example.

⁶ Commercial version: http://www.pgp.com/; free version: http://www.gnupg.org/.

⁷ Alice can send her public key to Bob, or Bob can use a public key server to find it.

⁸ Hellman, Martin E. "An Overview of Public Key Cryptography.": IEEE Communications Magazine, 16(6):24-32, November 1978. URL: http://www.comsoc.org/livepubs/ci1/public/anniv/pdfs/hellman.pdf.

⁹ Attackers might attempt to discover the original plaintext by hashing many plaintexts via a dictionary or brute force attack, attempting to discover an identical resulting hash.

¹⁰ Additional versions of SHA (named after their bit length) are SHA-224, SHA-256, SHA-384, and SHA-512. These are collectively known as SHA2.

¹¹ This is simplified for clarity; salts are also typically used in combination with hashes for password authentication.

¹² Public keys are not used solely for encryption: as mentioned previously. When one asymmetric key is used to encrypt, the other is used to decrypt. Because Alice used her private key to encrypt, her public key is used to decrypt.

^ Top

Domain 5: Cryptography