BASICS OF CRYPTOGRAPHY
C = E(P, K
P = D(C, K
Relationship between the plaintext and the ciphertext.
would be transformed into the ciphertext
cryption key tells how to get back from the ciphertext to the plaintext. In this ex-
ample, the decryption key is
in the ciphertext is a
in the plaintext, a
in the ciphertext is an
in the plaintext,
At first glance this might appear to be a safe system because although the
cryptanalyst knows the general system (letter-for-letter substitution), he does not
know which of the 26!
possible keys is in use. Nevertheless, given a sur-
prisingly small amount of ciphertext, the cipher can be broken easily. The basic at-
tack takes advantage of the statistical properties of natural languages.
is the most common letter, followed by
, etc. The most
common two-letter combinations, called
, and so on.
Using this kind of information, breaking the cipher is easy.
Many cryptographic systems, like this one, have the property that given the en-
cryption key it is easy to find the decryption key. Such systems are called
substitution ciphers are completely worthless, other symmetric key algorithms are
known and are relatively secure if the keys are long enough. For serious security,
minimally 256-bit keys should be used, giving a search space of 2
keys. Shorter keys may thwart amateurs, but not major governments.
9.5.2 Public-Key Cryptography
Secret-key systems are efficient because the amount of computation required
to encrypt or decrypt a message is manageable, but they have a big drawback: the
sender and receiver must both be in possession of the shared secret key. They may
even have to get together physically for one to give it to the other.
To get around
is used (Diffie and Hellman, 1976).
system has the property that distinct keys are used for encryption and decryption
and that given a well-chosen encryption key, it is virtually impossible to discover
the corresponding decryption key. Under these circumstances, the encryption key
can be made public and only the private decryption key kept secret.
Just to give a feel for public-key cryptography, consider the following two
Question 1: How much is 314159265358979
Question 2: What is the square root of 3912571506419387090594828508241?
Most sixth graders, if given a pencil, paper, and the promise of a really big ice
cream sundae for the correct answer, could answer question 1 in an hour or two.
Most adults given a pencil, paper, and the promise of a lifetime 50% tax cut could
not solve question 2 at all without using a calculator, computer, or other external
help. Although squaring and square rooting are inverse operations, they differ enor-
mously in their computational complexity. This kind of asymmetry forms the basis
of public-key cryptography. Encryption makes use of the easy operation but de-
cryption without the key requires you to perform the hard operation.
A public-key system called
exploits the fact that multiplying really big
numbers is much easier for a computer to do than factoring really big numbers, es-
pecially when all arithmetic is done using modulo arithmetic and all the numbers
involved have hundreds of digits (Rivest et al., 1978).
This system is widely used
in the cryptographic world. Systems based on discrete logarithms are also used (El
The main problem with public-key cryptography is that it is a thou-
sand times slower than symmetric cryptography.
The way public-key cryptography works is that everyone picks a (public key,
private key) pair and publishes the public key. The public key is the encryption
key; the private key is the decryption key.
Usually, the key generation is auto-
mated, possibly with a user-selected password fed into the algorithm as a seed.
send a secret message to a user, a correspondent encrypts the message with the re-
ceiver’s public key. Since only the receiver has the private key, only the receiver
can decrypt the message.
9.5.3 One-Way Functions
In various situations that we will see later it is desirable to have some function,
, which has the property that given
and its parameter
easy to do, but given only
is computationally infeasible. Such a
function typically mangles the bits in complex ways. It might start out by ini-
Then it could have a loop that iterates as many times as there are 1
, with each iteration permuting the bits of
in an iteration-dependent way,
adding in a different constant on each iteration, and generally mixing the bits up
very thoroughly. Such a function is called a
cryptographic hash function