Cryptography

During recent years the increase in the amount of studies concerning cryptography has been really explosive, and there are two main reasons for this. In the first place, the seminal idea of public key cryptography, apart from being of extraordinary interest on its own right, has created entirely new types of applications, some of which are rather contra-intuitive with respect to the common sense notions concerning communication between different parties. In the second place, the need for cryptography has increased tremendously due to various aspects of data security. This can be expressed briefly by saying that there are now really many "positive" applications of cryptography, whereas the earlier applications were mainly "negative" , i.e., secret communication during wars, criminal activities, etc. Besides, it seems that the range of applications will become larger and larger with the expansion of electronic mail and similar systems.

Consider messages sent via an insecure channel (cf. Communication channel). (The channel might be a telephone line subject to wiretapping by an eavesdropper, or it might be some data storage device in an information system.) Such messages will be referred to as plaintext. To increase security, the sender encrypts the plaintext and sends the resulting cryptotext via the channel. The receiver then decrypts the cryptotext back to the plaintext. (Instead of plaintext and cryptotext, the terms cleartext and ciphertext are often used.)

The encryption and decryption are usually carried out in terms of a specific cryptosystem. Essentially, a cryptosystem specifies several (often infinitely many) keys. Each key $ K $ determines an encryption function $ e _ {K} $ and a decryption function $ d _ {K} $. Cryptotext $ c $ is obtained from plaintext $ w $ using $ e _ {K} $:

$$ e _ {K} ( w) = c. $$

Conversely,

$$ d _ {K} ( c) = w. $$

Thus,

$$ d _ {K} ( e _ {K} ( w)) = w. $$

More specifically, a cryptosystem $ CS $ consists of a plaintext space, a cryptotext space and a key space. All three items are at most countable. Typically, a plaintext space could be $ \Sigma ^ {*} $, for some alphabet $ \Sigma $, or the set of all meaningful sentences in a natural language such as English. Similarly, the cryptotext space could be $ \Delta ^ {*} $, for some alphabet $ \Delta $. Each key $ K $ determines mappings $ e _ {K} $ and $ d _ {K} $ in the sense discussed above. For instance, if the plaintext and cryptotext spaces are $ \Sigma ^ {*} $ and $ \Delta ^ {*} $, then $ e _ {K} $ will be a translation of $ \Sigma ^ {*} $ into $ \Delta ^ {*} $( cf. Translation).

"Legal" communication activities may be intercepted by an eavesdropper or cryptanalyst. In a good cryptosystem cryptanalysis will be very difficult. No satisfactory formalization of these notions has been found so far: formalizations do not capture the essential issues from the point of view of applications.

Perhaps the oldest and best known among all cryptosystems is called Caesar cipher or briefly CAESAR. Both the plaintext space and the cryptotext space consist in this case of all words over the English alphabet $ \Sigma = \{ A \dots Z \} $( cf. Word). The key space is $ \{ 0 \dots 25 \} $. If $ K $ is an element of the key space, then $ e _ {K} $ is the morphism mapping each letter $ K $ letters ahead in the alphabet. (The ordering of $ \Sigma $ is the natural alphabetic one, and the end of the alphabet is continued cyclically to the beginning, cf. Lexicographic order.) For instance,

$$ e _ {25} ( IBM) = HAL,\ \ e _ {6} ( MUPID) = SAVOJ, $$

$$ e _ {3} ( HELP) = KHOS,\ e _ {0} ( CRYPTO) = CRYPTO. $$

The decryption function $ d _ {K} $ corresponding to the key $ K $ is defined by

$$ d _ {K} = \ e _ {26 - K } . $$

Thus,

$$ d _ {6} ( SAVOJ) = \ e _ {20} ( SAVOJ) = \ MUPID. $$

Clearly, in this case all functions $ e _ {K} $ and $ d _ {K} $ are bijections of $ \Sigma ^ {*} $ onto $ \Sigma ^ {*} $( cf. Bijection).

The cardinality of the key space of CAESAR is very small. No cryptosystem with this property can be good in the sense described above: cryptanalysis can be carried out simply by trying all possible keys. This is particularly easy if the plaintext is in some natural language. Then, for reasonably long cryptotexts (say with length $ \geq 10 $), in general only one decryption key produces a meaningful plaintext. This redundancy of natural languages constitutes the foundation for the cryptanalysis of many cryptosystems; knowledge of the statistical distribution of individual letters, pairs of consecutive letters and triples of consecutive letters uncovers the correspondence between plaintext and cryptotext letters.

CAESAR is the oldest widely used cryptosystem. A great variety of other cryptosystems has been developed. A property shared by all of these classical cryptosystems is that, whenever one knows the encryption key $ e _ {K} $, one also knows the decryption key $ d _ {K} $. More explicitly, $ d _ {K} $ is either immediately implied by $ e _ {K} $ or else can be computed from $ e _ {K} $ without too much difficulty. Thus, if one is dealing with any of the classical cryptosystems, the encryption key $ e _ {K} $ must be kept secret: once it is publicized, the decryption key $ d _ {K} $ is given away.

The seminal idea of public key cryptosystems (as opposed to what has been called above "classical" systems) is due to W. Diffie and M. Hellman, [a3]: the knowledge of $ e _ {K} $ does not necessarily give away $ d _ {K} $. More specifically, the computation of $ d _ {K} $ from $ e _ {K} $ may be intractable, at least for almost-all keys $ K $.

The idea of public key cryptosystems is very simple — why was it presented so late in the history of cryptography? One apparent reason is that some theory of computational complexity had to be ready before the realization of the idea of public key cryptography (cf. Complexity theory).

The system RSA due to R. Rivest, A. Shamir and L. Adleman [a4], is by now the most tested one among the public key systems. At the time of writing (1988), nothing serious has come up against RSA.

RSA is based on the fact that it is almost impossible to recover two large prime numbers $ p $ and $ q $ from their product $ n = pq $— at least according to the presently known factorization algorithms. On the other hand, large random prime numbers can be generated fast. The public key encryption is based on $ n $, whereas decryption requires that one knows $ p $ and $ q $. Details are presented below.

Let $ p $ and $ q $ be two large random primes (typically, having at least 100 digits in their decimal representation). Denote

$$ n = pq \ \ \textrm{ and } \ \ \phi ( n) = \ ( p - 1) ( q - 1). $$

(Here $ \phi $ is the Euler function.) Choose a number $ e > 1 $ relatively prime to $ \phi ( n) $ and a number $ d $ satisfying the congruence

$$ ed \equiv 1 ( \mathop{\rm mod} \phi ( n)). $$

(Since $ e $ and $ \phi ( n) $ are relatively prime, the congruence has a solution. It can be found rapidly by the Euclidean algorithm.)

The numbers $ n $ and $ e $, referred to as the modulus and the encryption exponent, respectively, constitute the public encryption key. The cryptotext $ c $ will be the least positive remainder of $ w ^ {e} $ $ ( \mathop{\rm mod} n) $, where $ w $ is the plaintext word over the alphabet $ \{ 0 \dots 9 \} $. One assumes that the length $ i $ of $ w $ satisfies the inequalities $ 10 ^ {i - 1 } < n < 10 ^ {i} $. This is to make sure that the modular calculations do not cause any ambiguities and that, on the other hand, the plaintext blocks are not too short.

It can be shown by straightforward elementary number theory that $ c ^ {d} \equiv w $ $ ( \mathop{\rm mod} n) $. Thus, the trapdoor $ d $ enables one to decrypt.

For example, choose $ p = 47 $ and $ q = 59 $, yielding $ n = 2773 $ and $ \phi ( n) = 2668 $. Choose further $ e = 17 $, yielding $ d = 157 $. Since $ 10 ^ {3} < n < 10 ^ {4} $, the plaintext blocks should consist of four decimal digits. For instance, $ 1920 ^ {17} \equiv 2109 $ $ ( \mathop{\rm mod} 2773 ) $. For decryption, $ 2109 ^ {157} \equiv 1920 $ $ ( \mathop{\rm mod} 2773) $.

It is rather easy to factorize 2773 and, hence, to find the decryption exponent $ d = 157 $. However, one might still want to consider the case where $ p $ and $ q $ are so large that they cannot be recovered from their product $ n $. How could cryptanalysis be carried out in this case?

For instance, assume that one is able to compute $ \phi ( n) $ without actually factorizing $ n $. Then $ p + q $ is immediately obtainable from $ \phi ( n) = n - ( p + q) + 1 $ and the public information $ n $. On the other hand, $ p - q $ is the square root of $ ( p + q) ^ {2} - 4n $ and, thus, also immediately obtainable. Now $ p $ and $ q $ can be immediately computed from $ p + q $ and $ p - q $. This means that an algorithm for computing $ \phi ( n) $ yields an algorithm of essentially the same complexity for factorizing $ n $.

Public key cryptosystems are especially suitable for authentication and electronic signatures.

Consider two parties $ A $ and $ B $ with conflicting interests, e.g. a bank and a customer or two superpowers. When $ A $ sends a message to $ B $, it should be signed and the signature should give the parties the following two kinds of protection.

i) Both $ A $ and $ B $ should be protected against messages addressed to $ B $, fed in the information system by a third party $ C $ who pretends to be $ A $.

ii) $ A $ should be protected against messages forged by $ B $ who claims to have received them from $ A $, properly signed.

If a classical cryptosystem is used, then the requirement i) can be satisfied in a reasonable fashion: $ A $ and $ B $ agree upon a secret encryption key known only to them. On the other hand, the requirement ii) is apparently more difficult to satisfy because $ B $ should know something about the way $ A $ generates the signature, and yet it should be impossible for $ B $ to generate $ A $' s signature. Observe also that if one is dealing with a big network of communicating parties (say, a network of mail users) then it is impractical to use a distinct secret method of signing for every pair of users.

If a public key cryptosystem is used, both i) and ii) can be satisfied, at least in principle. $ A $ sends the message $ w $ to $ B $ in the form $ e _ {B} ( d _ {A} ( w)) $. $ B $ can first recover $ d _ {A} ( w) $ by the secret decryption key $ d _ {B} $. From $ d _ {A} ( w) $, $ B $ can recover $ w $ by the publicly known $ e _ {A} $. (Recall that $ e _ {A} $ and $ d _ {A} $ are inverses.) Now both i) and ii) are satisfied because only $ A $ knows $ d _ {A} $. Hence, neither $ C $ nor $ B $ forge $ A $' s signature. Also $ A $ cannot later deny sending the message to $ B $.

References

[a1]	H. Beker, F. Piper, "Cipher systems" , Northwood Books (1982)
[a2]	D.E. Denning, "Cryptography and data security" , Addison-Wesley (1982)
[a3]	W. Diffie, M. Hellman, "New directions in cryptography" IEEE Trans. Information Theory , IT-22 (1976) pp. 644–654
[a4]	R. Rivest, A. Shamir, L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems" Comm. ACM , 21 (1978) pp. 120–126
[a5]	A. Salomaa, "Computation and automata" , Cambridge Univ. Press (1985)