Cryptography in Information Security
From Computing and Software Wiki
Contents |
Introduction
The word cryptography comes from two Greek words meaning "secret writing" and is the art and science of concealing meaning. Cryptanalysis is the breaking of codes. The basic component of cryptography is a
cryptosystem.
Quintuple (E, D, M, K, C):
- M set of plaintexts
- K set of keys
- C set of ciphertexts
- E set of encryption functions
- D set of decryption functions
The goal of cryptography is to keep enciphered information secret. An adversary wishes to break a ciphertext. Standard cryptographic practice is to assume that one knows the algorithm used to encipher the plaintext, but not the specific cryptographic key (in other words, she knows D and E). One may use three types of attacks.
Classical Cryptosystems
Classical cryptosystems (also called single-key or symmetric cryptosystems) are cryptosystems that use the same key for encipherment and decipherment. So the sender, receiver share common key. Keys may be the same, or trivial to derive from one another. The are sometime called symmetric cryptography.
Vigènere cipher
A longer key might obscure the statistics. The Vigenère cipher chooses a sequence of keys, represented by a string. The key letters are applied to successive plaintext characters, and when the end of the key is reached, the key starts over. The length of the key is called the period of the cipher. Because this requires several different key letters, this type of cipher is called polyalphabetic.
- EXAMPLE: The first line of a limerick is enciphered using the key "BENCH," as follows.
Key B ENCHBENC HBENC HBENCH BENCHBENCH Plaintext A LIMERICK PACKS LAUGHS ANATOMICAL Ciphertext B PVOLSMPM WBGXU SBYTJZ BRNVVNMPCS
For many years, the Vigenère cipher was considered unbreakable. Then a Prussian cavalry officer named Kasiski noticed that repetitions occur when characters of the key appear over the same characters in the ciphertext. The number of characters between the repetitions is a multiple of the period.
One Time Pad The one-time pad is a variant of the Vigenère cipher. The technique is the same. The key string is chosen at random, and is at least as long as the message, so it does not repeat.
Data Encryption Standard
The Data Encryption Standard (DES) was designed to encipher sensitive but nonclassified data. It is bit-oriented, unlike the other ciphers we have seen. It uses both transposition and substitution and for that reason is sometimes referred to as a product cipher. Its input, output, and key are each 64 bits long. The sets of 64 bits are referred to as blocks
Public Key Cryptography
Diffie-Hellman
In 1976, Diffie and Hellman proposed a new type of cryptography that distinguished between encipherment and decipherment keys.
One of the keys would be publicly known; the other would be kept private by its owner. Classical cryptography requires the sender and recipient to share a common key. Public key cryptography does not. If the encipherment key is public, to send a secret message simply encipher the message with the recipient's public key. Then send it. The recipient can decipher it using his private key.
- EXAMPLE: Alice and Bob have chosen p = 53 and g = 17. They choose their private keys to be kAlice = 5 and kBob = 7. Their public keys are
-KAlice = 175 mod 53 = 40 and -KBob = 177 mod 53 = 6.
Suppose Bob wishes to send Alice a message. He computes a shared secret key by enciphering Alice's public key using his private key: SBob,Alice = KAlice kBob mod p = 407 mod 53 = 38 and enciphers his message using this key (and any desired secret key cryptosystem). When Alice gets the message, she computes the key she shares with Bob as SAlice,Bob = KBob kAlice mod p = 65 mod 53 = 38 The mathematical properties of modular exponentiation ensure that for any two users A and B, SA,B = SB,A
RSA
is an exponentiation cipher. Choose two large prime numbers p and q, and let n = pq. The totient (n) of n is the number of numbers less than n with no factors in common with n.
- EXAMPLE: Let n = 10. The numbers that are less than 10 and are relatively prime to (have no factors in common with) n are 1, 3, 7, and 9. Hence, totient(10) = 4. Similarly, if n = 21, the numbers that are relatively prime to n are 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, and 20. So totient(21) = 12
Cryptographic Checksums
HMAC
Alice wants to send Bob a message of n bits. She wants Bob to be able to verify that the message he receives is the same one that was sent. So she applies a mathematical function, called a checksum function, to generate a smaller set of k bits from the original n bits. This smaller set is called the checksum or message digest. Alice then sends Bob both the message and the checksum. When Bob gets the message, he recomputes the checksum and compares it with the one Alice sent. If they match, he assumes that the message has not been changed.
- EXAMPLE: The parity bit in the ASCII representation is often used as a single-bit checksum. If
odd parity is used, the sum of the 1-bits in the ASCII representation of the character, and the parity bit, is odd. Assume that Alice sends Bob the letter "A." In ASCII, the representation of "A" using odd parity is p0111101 in binary, where p represents the parity bit. Because five bits are set, the parity bit is 0 for odd parity. When Bob gets the message 00111101, he counts the 1-bits in the message. Because this number is odd, Bob knows that the message has arrived unchanged.
HMAC is a generic term for an algorithm that uses a keyless hash function and a cryptographic key to produce a keyed hash function [594]. This mechanism enables Alice to validate that data Bob sent to her is unchanged in transit. Without the key, anyone could change the data and recompute the message authentication code, and Alice would be none the wiser. The need for HMAC arose because keyed hash functions are derived from cryptographic algorithms. Many countries restrict the import and export of software that implements such algorithms. They do not restrict software implementing keyless hash functions, because such functions cannot be used to conceal information. Hence, HMAC builds on a keyless hash function using a cryptographic key to create a keyed hash function.
Summary
For our purposes, three aspects of cryptography require study. Classical cryptography uses a single key shared by all involved. Public key cryptography uses two keys, one shared and the other private. Both types of cryptosystems can provide secrecy and origin authentication (although classical cryptography requires a trusted third party to provide both). Cryptographic hash functions may or may not use a secret key and provide data authentication. All cryptosystems are based on substitution (of some quantity for another) and permutation (scrambling of some quantity). Cryptanalysis, the breaking of ciphers, uses statistical approaches (such as the Kasiski method and differential cryptanalysis) and mathematical approaches (such as attacks on the RSA method). As techniques of cryptanalysis improve, our understanding of encipherment methods also improves and ciphers become harder to break. The same holds for cryptographic checksum functions. However, as computing power increases, key length must also increase. A 56-bit key was deemed secure by many in 1976; it is clearly not secure now.
Research Issues
Cryptography is an exciting area of research, and all aspects of it are being studied. New secret key ciphers incorporate techniques for defeating differential and linear cryptanalysis. New public key ciphers use simple instances of NP-hard problems as their bases, and they cast those instances into the more general framework of the NP-hard problem. Other public key ciphers revisit well-studied, difficult classical problems (such as factoring) and use them so that mathematically breaking the cipher is equivalent to solving the hard problem. Still others are built on the notion of randomness (in the sense of unpredictability). Cryptanalytic techniques are also improving. From the development of differential cryptanalysis came linear cryptanalysis. The use of NP-hard problems leads to an analysis of the problem underlying the cipher to reduce it to the simpler, solvable case. The use of classical mathematical problems leads to the application of advanced technology to make the specific problem computable; for example, advances in technology have increased the sizes of numbers that can be factored, which in turn lead to the use of larger primes as the basis for ciphers such as RSA. Advances in both cryptography and cryptanalysis lead to a notion of "provable security." The issue is to prove under what conditions a cipher is unbreakable. Then, if the conditions are met, perfect secrecy is obtained. Similar issues arise with cryptographic protocols (some of which the next chapters will explore). This leads to the area of assurance and serves as an excellent test base for many assurance techniques
References
1. Onion Routing for Anonymous Communications. [1]
[2]
[3]
[4]
[5]
[6]
