# Cryptanalysis

From Wikipedia

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

Cryptanalysis (from the Greek kryptós and analy´ein, "to loosen" or "to untie") is the science (and art) of recovering information from ciphers without knowledge of the key.

There are three generic types of cryptanalysis characterised by what the cryptanalyst knows: (1) ciphertext only; (2) known ciphertext/plaintext pairs; and (3) chosen plaintext or chosen ciphertext.

Often the cryptanalyst either will know some of the plaintext or will be able to guess at, and exploit, a likely element of the text, such as a letter beginning with "Dear Sir" or a computer session starting with "LOG IN." The last category represents the most favourable situation for the CryptanalysT in which he can cause either the transmitter to encrypt a plaintext of his choice or the receiver to decrypt a ciphertext that he chose. Of course, for single-key Cryptography there is no distinction between chosen plaintext and chosen ciphertext, but in two-key Cryptography it is possible for one of the encryption or decryption functions to be secure against chosen input while the other is vulnerable.

Because of its reliance on "hard" mathematical problems as a basis for cryptoalgorithms and because one of the keys is publicly exposed, two-key cryptography has led to a new type of cryptanalysis that is virtually indistinguishable from research in any other area of computational mathematics. Unlike the ciphertext attacks or ciphertext/plaintext pairs attacks in single-key cryptosystems, this sort of cryptanalysis is aimed at breaking the cryptosystem by analysis that can be carried out based only on a knowledge of the system itself. Obviously there is no counterpart to this kind of cryptanalytic attack in single-key systems. One of the most attractive schemes for exchanging session keys in a hybrid cryptosystem depended on the ease with which a number (primitive root) could be raised to a power (in a finite field), as opposed to the difficulty of calculating the discrete logarithm. A special-purpose chip to implement this algorithm was produced by a U.S. company, and several others designed secure electronic mail and computer-networking schemes based on the algorithm. In 1983 Donald Coppersmith found a computationally feasible way to take discrete logarithms in precisely those finite fields that had been of greatest cryptographic interest and thereby gave to the cryptanalyst a tool with which to break those cryptosystems. Similarly, the RSA cryptoalgorithm is no securer than the modulus is difficult to factor, so that a breakthrough in factoring would also be a cryptanalytic breakthrough.

In 1980 one could factor a difficult 50-digit number at an expense of 1,000,000,000,000 elementary computer operations (add, subtract, shift, and so forth). By 1984 the state of the art in factoring algorithms had advanced to a point where a 75-digit number could be factored in 1,000,000,000,000 operations.

If a mathematical advance made it feasible to factor 150 or more digit numbers in the same number of operations, this would make it possible for the cryptanalyst to break several commercial RSA schemes. In other words, the security of two-key cryptography depends on well-defined mathematical questions in a way that single-key cryptography generally did not and conversely equates cryptanalysis to mathematical research in an atypical way.

(The specifics of this are somewhat out of date. 150 digit numbers of the kind used in RSA have been factored. The effort was greater than above, but not unreasonable on fast modern computers. 150 digit numbers are no longer considered enough for RSA. 300 digits is still considered too hard to factor in 2001, though methods will probably continue to improve over time.)

Famous attacks: