The Cryptanalysis reference article from the English Wikipedia on 24-Apr-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Cryptanalysis

Cryptanalysis (from the Greek kryptós and analýein, "to loosen" or "to untie") is the study of the methods for reading encrypted information without knowing the secret key. Sometimes an alternative term, codebreaking, is used instead (though this has a more specialised technical meaning; see code). "Cryptanalysis" is also used to refer to any attempt to circumvent the security of other types of cryptographic algorithms and protocols in general, and not just ciphers.

Cryptanalysis can be performed under a variety of assumptions about the capabilities of the attacker. The following are the most common:

• Ciphertext-only: the cryptanalyst has access only to a collection of ciphertexts or codetexts .
• Known-plaintext: the attacker has a set of ciphertexts to which he knows the corresponding plaintext.
• Chosen-plaintext (chosen-ciphertext): the attacker can obtain the ciphertexts (plaintexts) corresponding to an arbitrary set of plaintexts (ciphertexts) of his own choosing.

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. 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-only attacks or known / chosen plaintext 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:

• Enigma
• DeCSS
• Differential cryptanalysis
• Linear cryptanalysis
• Rubber-hose cryptanalysis
• frequency analysis

See also:

• Cryptography
• Decipherment

This is the "Cryptanalysis" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.