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 determines an encryption function and a decryption function . Cryptotext is obtained from plaintext using :

Conversely,

Thus,

More specifically, a cryptosystem 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 , for some alphabet , or the set of all meaningful sentences in a natural language such as English. Similarly, the cryptotext space could be , for some alphabet . Each key determines mappings and in the sense discussed above. For instance, if the plaintext and cryptotext spaces are and , then will be a translation of into (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 (cf. Word). The key space is . If is an element of the key space, then is the morphism mapping each letter letters ahead in the alphabet. (The ordering of is the natural alphabetic one, and the end of the alphabet is continued cyclically to the beginning, cf. Lexicographic order.) For instance,

The decryption function corresponding to the key is defined by

Thus,

Clearly, in this case all functions and are bijections of onto (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 ), 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 , one also knows the decryption key . More explicitly, is either immediately implied by or else can be computed from without too much difficulty. Thus, if one is dealing with any of the classical cryptosystems, the encryption key must be kept secret: once it is publicized, the decryption key 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 does not necessarily give away . More specifically, the computation of from may be intractable, at least for almost-all keys .

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 and from their product — 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 , whereas decryption requires that one knows and . Details are presented below.

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

(Here is the Euler function.) Choose a number relatively prime to and a number satisfying the congruence

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

The numbers and , referred to as the modulus and the encryption exponent, respectively, constitute the public encryption key. The cryptotext will be the least positive remainder of , where is the plaintext word over the alphabet . One assumes that the length of satisfies the inequalities . 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 . Thus, the trapdoor enables one to decrypt.

For example, choose and , yielding and . Choose further , yielding . Since , the plaintext blocks should consist of four decimal digits. For instance, . For decryption, .

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

For instance, assume that one is able to compute without actually factorizing . Then is immediately obtainable from and the public information . On the other hand, is the square root of and, thus, also immediately obtainable. Now and can be immediately computed from and . This means that an algorithm for computing yields an algorithm of essentially the same complexity for factorizing .

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

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

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

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

If a classical cryptosystem is used, then the requirement i) can be satisfied in a reasonable fashion: and agree upon a secret encryption key known only to them. On the other hand, the requirement ii) is apparently more difficult to satisfy because should know something about the way generates the signature, and yet it should be impossible for to generate '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. sends the message to in the form . can first recover by the secret decryption key . From , can recover by the publicly known . (Recall that and are inverses.) Now both i) and ii) are satisfied because only knows . Hence, neither nor forge 's signature. Also cannot later deny sending the message to .

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)