Close-up of the rotors in a Fialka cipher machine

Cryptanalysis (from the Greek kryptós, "hidden", and analýein, "to loosen" or "to untie") is the study of methods for obtaining the meaning of encrypted information, without access to the secret information which is normally required to do so. In Cryptography, Fialka (M-125 is the name of a Cold War -era Soviet cipher machine Greek (el ελληνική γλώσσα or simply el ελληνικά — "Hellenic" is an Indo-European language, spoken today by 15-22 million people mainly Typically, this involves finding a secret key. In Cryptography, a key is a piece of information (a Parameter) that determines the functional output of a cryptographic algorithm In non-technical language, this is the practice of codebreaking or cracking the code, although these phrases also have a specialised technical meaning (see code). In Cryptography, a code is a method used to transform a Message into an obscured form preventing those who do not possess special information or key

"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 encryption. Cryptography (or cryptology; from Greek grc κρυπτός kryptos, "hidden secret" and grc γράφω gráphō, "I write" In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation A security protocol ( cryptographic protocol or encryption protocol) is an abstract or concrete protocol that performs a security -related function However, cryptanalysis usually excludes methods of attack that do not primarily target weaknesses in the actual cryptography, such as bribery, physical coercion, burglary, keystroke logging, and social engineering, although these types of attack are an important concern and are often more effective than traditional cryptanalysis. Cryptography (or cryptology; from Greek grc κρυπτός kryptos, "hidden secret" and grc γράφω gráphō, "I write" Bribery, a form of pecuniary corruption is an act usually implying money or gift given that alters the behaviour of the recipient in ways not consistent with the duties of that person In Cryptography, rubber-hose cryptanalysis is a Euphemism for the extraction of cryptographic secrets (e Keystroke logging (often called keylogging) is a method of capturing and recording user keystrokes

Even though the goal has been the same, the methods and techniques of cryptanalysis have changed drastically through the history of cryptography, adapting to increasing cryptographic complexity, ranging from the pen-and-paper methods of the past, through machines like Enigma in World War II, to the computer-based schemes of the present. The Enigma machine is any one of a family of related electro-mechanical Rotor machines used to generate Ciphers for the Encryption and decryption of World War II, or the Second World War, (often abbreviated WWII) was a global military conflict which involved a majority of the world's nations, including The results of cryptanalysis have also changed — it is no longer possible to have unlimited success in codebreaking, and there is a hierarchical classification of what constitutes a rare practical attack. In the mid-1970s, a new class of cryptography was introduced: asymmetric cryptography. Public-key cryptography, also known as asymmetric cryptography, is a form of Cryptography in which the key used to encrypt a message differs from the key Methods for breaking these cryptosystems are typically radically different from before, and usually involve solving carefully-constructed problems in pure mathematics, the best-known being integer factorization. There are two different meanings of the word cryptosystem. One is used by the cryptographic community while the other is the meaning understood by the public Broadly speaking pure mathematics is Mathematics motivated entirely for reasons other than application

## History of cryptanalysis

Cryptanalysis has coevolved together with cryptography, and the contest can be traced through the history of cryptography—new ciphers being designed to replace old broken designs, and new cryptanalytic techniques invented to crack the improved schemes . The history of Cryptography begins thousands of years ago Until recent decades it has been the story of what might be called classic cryptography — that is of In a broad sense biological co-evolution is "the change of a biological object triggered by the change of a related object" The history of Cryptography begins thousands of years ago Until recent decades it has been the story of what might be called classic cryptography — that is of In Cryptography, a cipher (or cypher) is an Algorithm for performing Encryption and Decryption &mdash a series of well-defined steps In practice, they are viewed as two sides of the same coin: in order to create secure cryptography, you have to design against possible cryptanalysis.

### Classical cryptanalysis

First page of Al-Kindi's 9th century Manuscript on Deciphering Cryptographic Messages

Although the actual word "cryptanalysis" is relatively recent (it was coined by William Friedman in 1920), methods for breaking codes and ciphers are much older. ( أبو يوسف يعقوب إبن إسحاق الكندي) (c William Frederick Friedman ( September 24, 1891 &ndash November 12, 1969) was a US Army cryptologist. In Cryptography, a code is a method used to transform a Message into an obscured form preventing those who do not possess special information or key In Cryptography, a cipher (or cypher) is an Algorithm for performing Encryption and Decryption &mdash a series of well-defined steps The first known recorded explanation of cryptanalysis was given by 9th century Arabian polymath Abu Yusuf Yaqub ibn Ishaq al-Sabbah Al-Kindi in A Manuscript on Deciphering Cryptographic Messages. The 9th century is the period from 801 to 900 in accordance with the Julian calendar in the Christian / Common Era. The araB gene Promoter is a bacterial promoter activated by e L-arabinose binding A polymath ( Greek polymathēs, πολυμαθής "having learned much" is a person whose knowledge is not restricted to one subject area ( أبو يوسف يعقوب إبن إسحاق الكندي) (c This treatise includes a description of the method of frequency analysis (Ibrahim Al-Kadi, 1992- ref-3). In Cryptanalysis, frequency analysis is the study of the frequency of letters or groups of letters in a Ciphertext. Ibrahim A Al-Kadi PhD (born March 6, 1954) is a Saudi Electrical engineer, known especially for his work on Cryptology history

Frequency analysis is the basic tool for breaking most classical ciphers. In Cryptanalysis, frequency analysis is the study of the frequency of letters or groups of letters in a Ciphertext. In Cryptography, a classical cipher is a type of Cipher used historically but which now have fallen for the most part into disuse In natural languages, certain letters of the alphabet appear more frequently than others; in English, "E" is likely to be the most common letter in any sample of plaintext. An alphabet is a standardized set of letters basic written symbols each of which roughly represents a Phoneme, a Spoken language, either English is a West Germanic language originating in England and is the First language for most people in the United Kingdom, the United States E is the fifth letter in the Latin alphabet. Its name in English is spelled e (iː plural es or ees (also written E's E In Cryptography, plaintext is the information which the sender wishes to transmit to the receiver(s Similarly, the digraph "TH" is the most likely pair of letters in English, and so on. A digraph, bigraph, or digram is a pair of characters used to write one Phoneme (distinct sound or a sequence of phonemes that does not correspond Frequency analysis relies on a cipher failing to hide these statistics. Statistics is a mathematical science pertaining to the collection analysis interpretation or explanation and presentation of Data. For example, in a simple substitution cipher (where each letter is simply replaced with another), the most frequent letter in the ciphertext would be a likely candidate for "E". In Cryptography, a substitution cipher is a method of Encryption by which units of plaintext are substituted with Ciphertext according to a regular system

In practice, frequency analysis relies as much on linguistic knowledge as it does on statistics, but as ciphers became more complex, mathematics became more important in cryptanalysis. Linguistics is the scientific study of Language, encompassing a number of sub-fields Statistics is a mathematical science pertaining to the collection analysis interpretation or explanation and presentation of Data. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and This change was particularly evident during World War II, where efforts to crack Axis ciphers required new levels of mathematical sophistication. World War II, or the Second World War, (often abbreviated WWII) was a global military conflict which involved a majority of the world's nations, including The Axis powers also known as the Axis alliance Axis nations Axis countries or sometimes just the Axis were those Countries Moreover, automation was first applied to cryptanalysis in that era with the Polish Bomba device, use of punched card equipment, and in the Colossus — one of the earliest computers (arguably the first programmable electronic digital computer). The Bomba, or Bomba kryptologiczna ( Polish for " Bomb " or " Cryptologic bomb " was a special-purpose The Colossus machines were electronic Computing devices used by British codebreakers to read Encrypted German messages during

### Modern cryptanalysis

Replica of a Bombe device

Even though computation was used to great effect in cryptanalysis in World War II, it also made possible new methods of cryptography orders of magnitude more complex than ever before. In the History of cryptography, the Bombe was an electromechanical device used by British Cryptologists to help break German Enigma An order of magnitude is the class of scale or magnitude of any amount where each class contains values of a fixed ratio to the class preceding it Taken as a whole, modern cryptography has become much more impervious to cryptanalysis than the pen-and-paper systems of the past, and now seems to have the upper hand against pure cryptanalysis. The historian David Kahn notes, "Many are the cryptosystems offered by the hundreds of commercial vendors today that cannot be broken by any known methods of cryptanalysis. David Kahn (b February 7, 1930) is a US Historian, Journalist and Writer. Indeed, in such systems even a chosen plaintext attack, in which a selected plaintext is matched against its ciphertext, cannot yield the key that unlock other messages. In a sense, then, cryptanalysis is dead. But that is not the end of the story. Cryptanalysis may be dead, but there is - to mix my metaphors - more than one way to skin a cat. ". [1] Kahn goes on to mention increased opportunities for interception, bugging, side channel attacks and quantum computers as replacements for the traditional means of cryptanalysis. A covert listening device, more commonly known as a bug, is usually a combination of a Miniature Radio transmitter with a Microphone. In Cryptography, a side channel attack is any attack based on information gained from the physical Implementation of a Cryptosystem, rather than brute Quantum cryptography, or quantum key distribution (QKD uses Quantum mechanics to guarantee secure communication

Kahn may have been premature in his cryptanalysis postmortem; weak ciphers are not yet extinct, and cryptanalytic methods employed by intelligence agencies remain unpublished. In academia, new designs are regularly presented, and are also frequently broken: the 1984 block cipher Madryga was found to be susceptible to ciphertext-only attacks in 1998; FEAL-4, proposed as a replacement for the DES standard encryption algorithm, was demolished by a spate of attacks from the academic community, many of which are entirely practical. In Cryptography, a block cipher is a symmetric key Cipher which operates on fixed-length groups of Bits termed blocks, with an In Cryptography, Madryga is a Block cipher created in 1984 by W In Cryptography, a ciphertext-only attack (COA or known ciphertext attack is an Attack model for Cryptanalysis where the attacker is assumed In Cryptography, FEAL (the Fast Data Encipherment Algorithm) is a Block cipher proposed as an alternative to the Data Encryption Standard The Data Encryption Standard ( DES) is a Cipher (a method for Encrypting information selected by NBS as an official Federal Information In industry, too, ciphers are not free from flaws: for example, the A5/1, A5/2 and CMEA algorithms, used in mobile phone technology, can all be broken in hours, minutes or even in real-time using widely-available computing equipment. For other uses of this term see Industry (disambiguation An industry (from Latin industrius, "diligent industrious" A5/1 is a Stream cipher used to provide over-the-air communication Privacy in the GSM cellular telephone standard A5/2 is a Stream cipher used to provide voice privacy in the GSM cellular telephone protocol In Cryptography, the Cellular Message Encryption Algorithm ( CMEA) is a Block cipher which was used for securing Mobile phones in the United In 2001, Wired Equivalent Privacy (WEP), a protocol used to secure Wi-Fi wireless networks, was shown to be susceptible to a practical related-key attack. Wired Equivalent Privacy ( WEP) is a deprecated Algorithm to secure IEEE 802 Wi-Fi (ˈwaɪfaɪ is the trade name for the popular wireless technology used Wireless network refers to any type of Computer network that is Wireless, and is commonly associated with a Telecommunications network whose interconnections In Cryptography, a related-key attack is any form of Cryptanalysis where the attacker can observe the operation of a Cipher under several different

### The results of cryptanalysis

The decrypted Zimmermann Telegram. The Zimmermann Telegram (or Zimmermann Note; German: Zimmermann-Depesche; Spanish: Telegrama Zimmermann) was a coded

Successful cryptanalysis has undoubtedly influenced history; the ability to read the presumed-secret thoughts and plans of others can be a decisive advantage, and never more so than during wartime. For example, in World War I, the breaking of the Zimmermann Telegram was instrumental in bringing the United States into the war. World War I (abbreviated WWI; also known as the First World War, the Great War, and the War to End All The Zimmermann Telegram (or Zimmermann Note; German: Zimmermann-Depesche; Spanish: Telegrama Zimmermann) was a coded In World War II, the cryptanalysis of the German ciphers — including the Enigma machine and the Lorenz cipher — has been credited with everything between shortening the end of the European war by a few months to determining the eventual result (see ULTRA). World War II, or the Second World War, (often abbreviated WWII) was a global military conflict which involved a majority of the world's nations, including The Enigma machine is any one of a family of related electro-mechanical Rotor machines used to generate Ciphers for the Encryption and decryption of "Tunny" redirects here For the fish see Tuna. The Lorenz SZ 40 and SZ 42 ( Schlüsselzusatz, meaning ULTra ("Urban Light Transport" is a Personal rapid transit system from Advanced Transport Systems Ltd a company based in Cardiff, Wales. The United States also benefited from the cryptanalysis of the Japanese PURPLE code (see MAGIC). The United States of America —commonly referred to as the This article is about the Japanese cipher Purple also known as AN-1 (citation for AN-1 nomenclature for Purple? In World War II, Magic was the United States Codename for intelligence derived from the Cryptanalysis of PURPLE, a Japanese foreign

Governments have long recognised the potential benefits of cryptanalysis for intelligence, both military and diplomatic, and established dedicated organisations devoted to breaking the codes and ciphers of other nations, for example, GCHQ and the NSA, organisations which are still very active today. Military intelligence (abbreviated MI int Commonwealth, or intel The Government Communications Headquarters (GCHQ is a British Intelligence agency responsible for providing Signals intelligence (SIGINT and Information The National Security Agency/ Central Security Service ( NSA/CSS) is a cryptologic intelligence agency of the United States government In 2004, it was reported that the United States had broken Iranian ciphers. For a topic outline on this subject see List of basic Iran topics. (It is unknown, however, whether this was pure cryptanalysis, or whether other factors were involved: [1]).

## Characterising attacks

Cryptanalytic attacks vary in potency and how much of a threat they pose to real-world cryptosystems. There are two different meanings of the word cryptosystem. One is used by the cryptographic community while the other is the meaning understood by the public A certificational weakness is a theoretical attack that is unlikely to be applicable in any real-world situation; the majority of results found in modern cryptanalytic research are of this type. Essentially, the practical importance of an attack is dependent on the answers to the following three questions:

1. What knowledge and capabilities are needed as a prerequisite?
2. How much additional secret information is deduced?
3. How much effort is required? (What is the computational complexity?)

### Prior knowledge: scenarios for cryptanalysis

Cryptanalysis can be performed under a number of assumptions about how much can be observed or found out about the system under attack. Knowledge is defined ( Oxford English Dictionary) variously as (i expertise and skills acquired by a person through experience or education the theoretical or practical understanding Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources As a basic starting point it is normally assumed that, for the purposes of analysis, the general algorithm is known; this is Kerckhoffs' principle of "the enemy knows the system". In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation In Cryptography, Kerckhoffs' principle (also called Kerckhoffs' assumption, axiom or law) was stated by Auguste Kerckhoffs in This is a reasonable assumption in practice — throughout history, there are countless examples of secret algorithms falling into wider knowledge, variously through espionage, betrayal and reverse engineering. Betrayal, a form of Deception or dismissal of prior presumptions is the breaking or violation of a presumptive Social contract ( trust, or Confidence Reverse engineering (RE is the process of discovering the technological principles of a device object or system through analysis of its structure function and operation (On occasion, ciphers have been reconstructed through pure deduction; for example, the German Lorenz cipher and the Japanese Purple code, and a variety of classical schemes). "Tunny" redirects here For the fish see Tuna. The Lorenz SZ 40 and SZ 42 ( Schlüsselzusatz, meaning This article is about the Japanese cipher Purple also known as AN-1 (citation for AN-1 nomenclature for Purple?

Other assumptions include:

• Ciphertext-only: the cryptanalyst has access only to a collection of ciphertexts or codetexts. In Cryptography, a ciphertext-only attack (COA or known ciphertext attack is an Attack model for Cryptanalysis where the attacker is assumed In Cryptography, a code is a method used to transform a Message into an obscured form preventing those who do not possess special information or key
• Known-plaintext: the attacker has a set of ciphertexts to which he knows the corresponding plaintext. The known-plaintext attack (KPA is an Attack model for Cryptanalysis where the attacker has samples of both the Plaintext and its encrypted In Cryptography, plaintext is the information which the sender wishes to transmit to the receiver(s
• Chosen-plaintext (chosen-ciphertext): the attacker can obtain the ciphertexts (plaintexts) corresponding to an arbitrary set of plaintexts (ciphertexts) of his own choosing. A chosen-plaintext attack (CPA is an Attack model for Cryptanalysis which presumes that the attacker has the capability to choose arbitrary Plaintexts A chosen-ciphertext attack (CCA is an Attack model for Cryptanalysis in which the cryptanalyst gathers information at least in part by choosing a Ciphertext
• Adaptive chosen-plaintext: like a chosen-plaintext attack, except the attacker can choose subsequent plaintexts based on information learned from previous encryptions. A chosen-plaintext attack (CPA is an Attack model for Cryptanalysis which presumes that the attacker has the capability to choose arbitrary Plaintexts Similarly Adaptive chosen ciphertext attack. An adaptive chosen-ciphertext attack (abbreviated as CCA2) is an interactive form of Chosen-ciphertext attack in which an attacker sends a number of ciphertexts to
• Related-key attack: Like a chosen-plaintext attack, except the attacker can obtain ciphertexts encrypted under two different keys. In Cryptography, a related-key attack is any form of Cryptanalysis where the attacker can observe the operation of a Cipher under several different The keys are unknown, but the relationship between them is known; for example, two keys that differ in the one bit.

These types of attack clearly differ in how plausible they would be to mount in practice. Although some are more likely than others, cryptographers will often take a conservative approach to security and assume the worst-case when designing algorithms, reasoning that if a scheme is secure even against unrealistic threats, then it should also resist real-world cryptanalysis as well.

The assumptions are often more realistic than they might seem upon first glance. For a known-plaintext attack, the cryptanalyst might well know or be able to guess at a likely part of the plaintext, such as an encrypted letter beginning with "Dear Sir", or a computer session starting with "LOGIN:". A chosen-plaintext attack is less likely, but it is sometimes plausible: for example, you could convince someone to forward a message you have given them, but in encrypted form. Related-key attacks are mostly theoretical, although they can be realistic in certain situations, for example, when constructing cryptographic hash functions using a block cipher. A cryptographic Hash function is a transformation that takes an input (or 'message' and returns a fixed-size string which is called the hash value (sometimes In Cryptography, a block cipher is a symmetric key Cipher which operates on fixed-length groups of Bits termed blocks, with an

### Classifying success in cryptanalysis

The results of cryptanalysis can also vary in usefulness. For example, cryptographer Lars Knudsen (1998) classified various types of attack on block ciphers according to the amount and quality of secret information that was discovered:

• Total break — the attacker deduces the secret key. Lars Ramkilde Knudsen (born February 21, 1962) is a Danish researcher in Cryptography, particularly interested in the design and analysis In Cryptography, a block cipher is a symmetric key Cipher which operates on fixed-length groups of Bits termed blocks, with an In Cryptography, a key is a piece of information (a Parameter) that determines the functional output of a cryptographic algorithm
• Global deduction — the attacker discovers a functionally equivalent algorithm for encryption and decryption, but without learning the key. In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation
• Instance (local) deduction — the attacker discovers additional plaintexts (or ciphertexts) not previously known.
• Information deduction — the attacker gains some Shannon information about plaintexts (or ciphertexts) not previously known.
• Distinguishing algorithm — the attacker can distinguish the cipher from a random permutation. In several fields of Mathematics the term permutation is used with different but closely related meanings

Similar considerations apply to attacks on other types of cryptographic algorithm.

### Complexity

Attacks can also be characterised by the amount of resources they require. This can be in the form of:

• Time — the number of "primitive operations" which must be performed. This is quite loose; primitive operations could be basic computer instructions, such as addition, XOR, shift, and so forth, or entire encryption methods.
• Memory — the amount of storage required to perform the attack.
• Data — the quantity of plaintexts and ciphertexts required.

In academic cryptography, a weakness or a break in a scheme is usually defined quite conservatively. Bruce Schneier sums up this approach: "Breaking a cipher simply means finding a weakness in the cipher that can be exploited with a complexity less than brute force. Never mind that brute-force might require 2128 encryptions; an attack requiring 2110 encryptions would be considered a break. . . simply put, a break can just be a certificational weakness: evidence that the cipher does not perform as advertised. " (Schneier, 2000).

## Cryptanalysis of asymmetric cryptography

Asymmetric cryptography (or public key cryptography) is cryptography that relies on using two keys; one private, and one public. Public-key cryptography, also known as asymmetric cryptography, is a form of Cryptography in which the key used to encrypt a message differs from the key Public-key cryptography, also known as asymmetric cryptography, is a form of Cryptography in which the key used to encrypt a message differs from the key Such ciphers invariably rely on "hard" mathematical problems as the basis of their security, so an obvious point of attack is to develop methods for solving the problem. A mathematical problem is a problem that is amenable to being analyzed and possibly solved with the methods of Mathematics. The security of two-key cryptography depends on mathematical questions in a way that single-key cryptography generally does not, and conversely links cryptanalysis to wider mathematical research in a new way.

Asymmetric schemes are designed around the (conjectured) difficulty of solving various mathematical problems. In Mathematics, a conjecture is a Mathematical statement which appears resourceful but has not been formally proven to be true under the rules of If an improved algorithm can be found to solve the problem, then the system is weakened. For example, the security of the Diffie-Hellman key exchange scheme depends on the difficulty of calculating the discrete logarithm. Diffie-Hellman key exchange ( D-H) is a Cryptographic protocol that allows two parties that have no prior knowledge of each other to jointly establish a shared secret In Mathematics, specifically in Abstract algebra and its applications discrete logarithms are group-theoretic analogues of ordinary Logarithms In 1983, Don Coppersmith found a faster way to find discrete logarithms (in certain groups), and thereby requiring cryptographers to use larger groups (or different types of groups). Don Coppersmith is a Cryptographer and Mathematician. He was involved in the design of the Data Encryption Standard Block cipher at IBM RSA's security depends (in part) upon the difficulty of integer factorization — a breakthrough in factoring would impact the security of RSA.

In 1980, one could factor a difficult 50-digit number at an expense of 1012 elementary computer operations. By 1984 the state of the art in factoring algorithms had advanced to a point where a 75-digit number could be factored in 1012 operations. Advances in computing technology also meant that the operations could be performed much faster, too. Moore's law predicts that computer speeds will continue to increase. Moore's law describes an important trend in the History of computer hardware. 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. 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 a large enough key size for RSA. In Cryptography, key size or key length is the size (usually measured in bits or bytes of the key used in a cryptographic algorithm (such as a Cipher Numbers with several hundred digits are still considered too hard to factor in 2005, though methods will probably continue to improve over time, requiring key size to keep pace or new algorithms to be used. In Cryptography, key size or key length is the size (usually measured in bits or bytes of the key used in a cryptographic algorithm (such as a Cipher

Another distinguishing feature of asymmetric schemes is that, unlike attacks on symmetric cryptosystems, any cryptanalysis has the opportunity to make use of knowledge gained from the public key. Public-key cryptography, also known as asymmetric cryptography, is a form of Cryptography in which the key used to encrypt a message differs from the key

## Quantum computing applications for cryptanalysis

Quantum computers, which are still in the early phases of development, have potential use in cryptanalysis. A quantum computer is a device for Computation that makes direct use of distinctively Quantum mechanical Phenomena, such as superposition For example, Shor's Algorithm could factor large numbers in polynomial time, in effect breaking some commonly used forms of public-key encryption. Shor's algorithm, first introduced by mathematician Peter Shor, is a quantum Algorithm for Integer factorization.

By using Grover's algorithm on a quantum computer, brute-force key search can be made quadratically faster. Grover's algorithm is a Quantum algorithm for searching an unsorted Database with N entries in O(N1/2 time and using However, this could be countered by increasing the key length.