Wikipedia 10K Redux by Reagle from Starling archive. Bugs abound!!!

<-- Previous | Newer --> | Current: 980962902 WojPob at Wed, 31 Jan 2001 17:41:42 +0000.

CryptanalysiS

CryptanalysiS (from the GreeK kryptós and analýein, "to loosen" or "to untie") is the science (and art) of recovering information from ciphers without knowledge of the key. CryptologY is often--and mistakenly--considered a synonym for CryptographY and occasionally for CryptanalysiS, as in the popular solution of CryptograM's or CipheR's, but specialists in the field have for years adopted the convention that CryptologY is the more inclusive term encompassing both CryptographY and CryptanalysiS.


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.