Cryptanalysis

Cryptanalysis (from the Greek krypt�s and analy�ein, "to loosen" or "to untie"), strictly, includes methods and techniques of recovering information from encrypted material (produced by ciphers or codes) without knowledge of the key, or codebook. Someone who performs cryptanalysis is called a cryptanalyst. In reality, cryptanalysis includes any method which can do so, and the most successful attacks on well implemented modern crypto systems are almost certainly not strictly cryptanalytic ones.

There are three basic types of strict cryptanalysis characterised by what the cryptanalyst knows:

encrypted text (ciphertext or codetext) only;
known ciphertext/plaintext pairs; or
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 an encrypted letter beginning with "Dear Sir" or a computer session starting with "LOGIN:". The last category (chosen plaintext or ciphertext) 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. For single-key (secret key) cryptography there is no significant difference between chosen plaintext and chosen ciphertext if the key is known, but in two-key cryptography it is possible for one of the encryption or decryption functions to be secure against chosen input (either plain or encrypted) while the other is vulnerable.

Because of its reliance on "hard" mathematical problems as a basis for crypto algorithms and because one of the keys is publicly exposed, two-key cryptography has led to a new type of cryptanalysis, which is nearly indistinguishable from research in other areas of computational mathematics. Unlike ciphertext attacks or ciphertext/plaintext pair 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 underlying connection between the two keys. 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 (Diffie_Hellman key exchange) depends 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 of IBM found a computationally feasible way to find 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 encryption algorithm is no more secure 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 (ie, 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. And 1,000,000,000,000 operations could be performed very much faster, too. Computer speeds may be confidently expected to continue to increase. Factoring techniques may continue do so as well, but will most likely depend on mathematical insight and creativity, neither of which has ever been successfully predictable.

The security of two-key cryptography depends on mathematical questions in a way that single-key cryptography generally did not, and conversely equates cryptanalysis to mathematical research in a new way. 150-digit numbers of the kind once used in RSA have been factored. The effort was greater than above, but was not unreasonable on fast modern computers. By the start of the 21st century, 150-digit numbers were no longer considered enough for RSA keys. Numbers of several hundred digits are still considered too hard to factor in 2004, though methods will probably continue to improve over time, requiring algorithms to keep pace.

Famous attacks: