Consider two computers A and B communicating messages via a network that is also accessible to an intruder computer I. The following are some of the security violations that can occur:
Passive Wiretapping: I reads a message.
Modification: I modifies a message.
Site Impersonation: I sends messages to A pretending it is B.
Cryptography is the only known solution to prevent security violations of this kind. It also has other applications, as we shall study later.
The basic concepts in cryptography are encryption and decryption. Encryption refers to the transformation of intelligible information into an unintelligible form for the express purpose of rendering it useless to an intruder. This transformation process is represented by a mathematical function (enciphering algorithm) C = E(P, K)
where P is plaintext (or cleartext) to be encrypted, K is an encryption key, and C is the resulting cyphertext. Decryption is represented by a matching decryption function (decryption algorithm) P = D(C, K)
where K is the decryption key.
In a cryptosystem a sender uses K to encrypts messages, which the receiver decrypts using K. An intruder's role in such a system is to guess K given the cyphertext, the encryption and decryption algorithms, and possibly some side information.
The strength of a cryptosystem is measured by its resistance to attack, that is, how difficult it is to determine K. Based on increasing amounts and types of available side information, attacks can be classified, in order of increasing intensity, as follows:
Cyphertext only: The intruder has intercepted the cyphertext material and has general knowledge of an opponent's messages and statistical properties of the language (e.g., frequency of letters or words).
Known plaintext: The intruder has, in addition, substantial amounts of plaintext and corresponding cyphertext.
Chosen plaintext: The intruder can see, in addition, cyphertext for any plaintext.
The requirement of most present-day commercial and government agencies is that the cryptosystem be able to withstand a chosen plaintext attack.
Unfortunately, all current encryption methods have problems. The only known provably secure method, called the `one-time pad', involves the use of a random key that has the same length as the plaintext to be encrypted. The key is exclusive-or'd with the message to produce the cyphertext. Given the key and the cyphertext, the receiver uses the same method to reproduce the plaintext. After that the same key is never used again. The intruder is then faced with the possibility of inspecting 2messages, a great number of which will be valid.
This method also has its problems.
on the key, it must be transmitted as well, a procedure that is just as difficult as the original problem of secure transmission. One solution to this problem is to use computer-generated pseudo random numbers. These numbers, however, are too easy to guess.
A currently popular encryption method, developed by the National Bureau of Standards, is called DES, for `Data Encryption Standard'. The algorithm (encryption or decryption) can be performed efficiently with a special-purpose chip, but far less efficiently with a program. The key is 56 bit (or bytes) long; critics argue that this length is too short and an exhaustive search will soon be possible using commercially available general-purpose computers.
The one-time pad and DES are considered conventional; they share the property that the same key is used for encryption and decryption. A non-conventional approach called public-key cryptography uses different keys for encryption and decryption, and is used as follows: Every user U has a pair of keys, one for encryption U and one for decryption U. It is impossible to guess U from U or vice versa. Cyphertext encrypted with U is decrypted with U. Everyone's E key is made public; it is saved in a public place where anyone may access it. Let's say A and B are two parties that want to send secure messages to each other. A encrypts messages for B using B's public key B. B can decrypt the messages using his private key B, but no one else can do so since no one else knows B. Similarly, B encrypts messages for A using A's public key A. These messages are secret. However, B cannot be sure that A has sent the messages because anyone could have used B, B's public key. Thus messages are not authenticated.
For authentication we need to assume that a user's decryption key can be used to encrypt cleartext that can be decrypted by his encryption key. Thus both of the following need to be true: D(E(P, U), U) = P E(D(P, U), U) = P
Now let A encrypt its messages to B using A's secret key A. B can decrypt the messages by using A's public key A. Now we have authentication: B is sure that A sent the message because only A knows A. However, we do not have secrecy: anyone else who gets this message can also apply A's public key A and decrypt it!
These two ideas can be combined to create messages that are both secret and authenticated: A sends the following to B: C = E(D(P, A), B)
which only B can read by computing: E(D(C, B), A)
B is now sure that A has sent the message,
Thus we have both secrecy and authentication. (Would we have both if A sent instead the message D(E(P, B), A)?)
Encryption and decryption algorithms that can be used in
public-key systems are too complex to be discussed here.
Typically,
a public-key system is based on a mathematical problem
with the following two properties:
1) it is hard to find a solution to the problem, and
2) it is easy to recognize a solution to the problem.
The encryption and decryption algorithms are such that
the difficulty of finding a key is equal to solving the problem
and the difficulty of encryption and decryption is equivalent to
recognizing a solution to the problem.
An example of such a problem is factoring the product of two very large prime
numbers.
A popular method called RSA (for Rivest-Shamir-Adleman)
is based on
this problem.
One important class of such problems is the set of
NP complete problems,
which have
the interesting property that solutions to them are recognizable
in polynomial time whereas the best known methods for finding
these solutions take exponential time,
and a polynomial time solution to one of these problems
would lead to polynomial time solutions to all of them (including,
as it turns out the factoring problem even though this problem has not
been shown to be NP-complete).
An example of an NP complete problem is the knapsack problem: Given a set of
items a... a,
with sizes s... s
with values v... v,
is there a set of these items such sum of the sizes is <= B (the capacity
of the knapsack) and the sum of the values >= K (the total value
required).