Cryptography

Cryptology is the science concerned with data communication and storage in secure and usually secret form, and it encompasses both cryptography and cryptanalysis. Cryptanalysis, from the Greek kryptós and analýein, is the science and art of recovering or forging cryptographically secured information without knowledge of the key. Cryptology is often mistakenly considered a synonym for cryptography, but specialists in the field have adopted the convention that cryptology is the more inclusive term.

The earliest device used to conceal a written message was the scytale, a tapered baton around which a strip of parchment or leather was wound and on which the text was inscribed. The Spartans employed it for secret communication between military commanders from as early as 400 BCE, making it the first recorded use of cryptography for correspondence. When the strip was unwrapped, the letters were left disarranged, and the message could be recovered only by winding the parchment around a rod of the same diameter. The scytale thus performed a transposition cipher, in which the order of the letters rather than their identity was altered. According to Plutarch, the Spartan ephors made two round pieces of wood exactly alike, keeping one and giving the other to the envoy, so that a message wound on one rod could be read only on its match.

The origins of the device are less certain than its use. From indirect evidence the scytale was first mentioned by the Greek poet Archilochus in the 7th century BC, while a clear indication of its employment as a cryptographic instrument appears only with Apollonius of Rhodes in the middle of the 3rd century BC.

The Romans practised a different principle, monoalphabetic substitution with a simple cyclic displacement of the alphabet. Julius Caesar employed a shift of three positions, so that plaintext A was encrypted as D, while Augustus Caesar used a shift of one position, so that A became B. In Suetonius's account, Caesar wrote confidential letters in cipher by changing the order of the letters of the alphabet so that no word could be made out, and to read them one substitutes the fourth letter, D, for A.

The first people to understand clearly the principles of cryptography and to elucidate the beginnings of cryptanalysis were the Arabs, who devised and used both substitution and transposition ciphers and discovered letter frequency distributions and probable plaintext.

801–873), an Arab polymath of ninth-century Baghdad, composed what is widely regarded as the earliest known treatise on cryptanalysis, the Risalah fi Istikhraj al-Mu'amma, written around 850 AD. To his people al-Kindi became known as the philosopher of the Arabs; he was the only notable philosopher of pure Arabian blood and the first one in Islam.

Al-Kindi's method was to take a sample of ordinary writing in the language long enough to fill one sheet, count the occurrences of each letter, and then match the most frequent ciphertext symbols to the most frequent letters of the sample.

For roughly a thousand years, from the medieval Arab world through Renaissance Europe and into the early modern period, frequency analysis remained the primary tool of the codebreaker. By about 1412 the encyclopedist al-Kalka-shandī could include a respectable treatment of several cryptographic systems in his encyclopedia and give explicit instructions on how to cryptanalyze ciphertext using letter frequency counts.

The Vigenère cipher was first described by Giovan Battista Bellaso in 1553. It is easy to understand and implement, yet it resisted all attempts to break it until 1863. That long resistance earned it the description le chiffrage indéchiffrable, the indecipherable cipher.

The scheme acquired Vigenère's name through misattribution in the 19th century. The cipher now known under his name is based on one described earlier by Bellaso.

The mechanization of cryptography began shortly after World War I, drawing on telephone and telegraph technology and on calculating machines. That convergence produced the rotor machines that would be used by all participants in World War II.

The Enigma machine was invented by the German engineer Arthur Scherbius shortly after World War I. It was adopted by the German armed forces between 1926 and 1935.

The machine contained a series of interchangeable rotors, which rotated every time a key was pressed so that the cipher changed continuously. A plugboard on the front of the machine transposed pairs of letters.

The military Enigma had 158,962,555,217,826,360,000 different settings — nearly 159 quintillion, about 67 bits.

Its strength lay in the number of ways it could be set: combining three rotors from a set of five, each rotor with 26 positions, and a plugboard with ten pairs of letters connected.

In December 1932 the plugboard Enigma was broken by the mathematician Marian Rejewski at the Polish General Staff's Cipher Bureau, using permutation group theory and French-supplied intelligence from German spy Hans-Thilo Schmidt. By 1938 Rejewski had invented a device called the cryptologic bomb, and Henryk Zygalski had devised his sheets, to mechanize the search for Enigma settings.

Bletchley Park was the wartime home of the Government Code and Cypher School, Britain's signals intelligence agency, later renamed GCHQ. Nearly 10,000 people worked in the wider Bletchley Park organisation during the Second World War. The scale of that organisation reflected the difficulty of the problem it faced: the German plugboard-equipped Enigma had become the principal crypto-system of the German Reich and later of other Axis powers.

The British bombe was an electromechanical device designed by Alan Turing soon after he arrived at Bletchley Park in September 1939. Harold Keen of the British Tabulating Machine Company turned his ideas into a working machine under the codename CANTAB. The first bombe was delivered to Bletchley Park on 18 March 1940 and was named Victory. Before the Second World War Turing was already working part-time for the British Government's Code and Cypher School, and in 1939 he took up a full-time role at Bletchley Park in Buckinghamshire.

Enigma devices typically changed settings every 24 hours and offered 103 sextillion possible combinations, so staff at Bletchley Park worked around the clock to break the settings by hand.

Of the two great wartime cryptanalytic efforts, the cryptanalysis of the Japanese ciphers is the more impressive, because it was a tour de force of cryptanalysis against ciphertext alone. In 1939 the Japanese introduced a new cipher machine, code-named Purple by U.S. cryptanalysts, in which rotors were replaced by telephone stepping switches.

Among the greatest triumphs in the history of cryptanalysis were the Polish and British solution of the German Enigma ciphers and of two teleprinter ciphers whose output was code-named Ultra, and the American cryptanalysis of the Japanese Red, Orange and Purple ciphers, code-named Magic. In 1930 the Japanese Foreign Office put its first rotor machine into service, code-named Red by U. cryptanalysts, and in 1935–36 the U. Army Signal Intelligence Service team led by William F. Friedman succeeded in cryptanalyzing Red ciphers.

Shannon published A Mathematical Theory of Communication in the Bell System Technical Journal in 1948, a paper that founded the subject of information theory. Its central insight was that pictures, words and sounds could be transmitted by sending a stream of 1s and 0s down a wire, rather than requiring electromagnetic waves on a wire. Shannon framed the fundamental problem of communication as reproducing at one point either exactly or approximately a message selected at another point.

To measure information Shannon proposed the use of logarithms; with base 2 the resulting units are called binary digits, or more briefly bits, a word suggested by J. Quantities of the form H = pi log pi play a central role in information theory as measures of information, choice and uncertainty, and Shannon called H the entropy of the set of probabilities.

Shannon's treatment of secrecy assumed that the enemy knows the system being used, including the family of transformations and the probabilities of choosing various keys. He distinguished concealment systems, in which the existence of the message is hidden, from privacy systems such as speech inversion, in which special equipment is required to recover the message. He measured the work characteristic of a system as the average amount of work, say in man hours, needed to determine the key for a cryptogram of N letters, and noted that complete trial and error is totally impractical except when the key is absurdly small, since a key of 26! possibilities can be written on a small slip of paper.

The Data Encryption Standard entered the public record as Federal Information Processing Standards Publication 46, bearing a publication date of January 15, 1977. Its adoption followed a period of public evaluation, and the standard was issued by the National Bureau of Standards. The algorithm itself descended from IBM's Lucifer, and its key size was shortened from 112 bits to 56 bits after secret consultations between the National Bureau of Standards and the National Security Agency. DES was mandated for use in unclassified U.S. government applications protecting binary-coded data during transmission and storage, and on a case-by-case basis for classified information.

The key described in the original standard consists of 64 binary digits, of which 56 bits are used directly by the algorithm and 8 bits are used for error detection. In the later formulation, the 56 bits are randomly generated and used directly by the algorithm, while the remaining 8 bits may be used for error detection. Because the fixed 56-bit key was overrun by improvements in computing, later NIST specifications called for an algorithm capable of increasing the key length if necessary. A way was devised that effectively gave the aging DES a 112-bit key: triple DES, which uses two normal DES keys in an encrypt-decrypt-encrypt operation, and banking standards adopted the scheme for security. Equipment with triple DES could be interoperable with equipment that only implemented the older single DES.

FIPS 46-1 superseded and reaffirmed the standard in January 1988. FIPS 46-3 was reaffirmed in October 1999 and withdrawn on May 19, 2005, and NIST now provides it only for historical purposes. The withdrawal closed the standard's official life, though the work of replacing it had begun years earlier. Beginning in 1997 NIST worked with industry and the cryptographic community to develop an Advanced Encryption Standard, with the goal of protecting sensitive government information well into the 21st century.

Public-key cryptography entered the published record with New Directions in Cryptography, which appeared in the November 1976 issue of IEEE Transactions on Information Theory. The paper examined two kinds of contemporary developments in cryptography, observing that widening applications of teleprocessing had created a need for new types of cryptographic systems that minimize the need for secure key distribution channels and supply the equivalent of a written signature. It proposed two approaches to transmitting keying information over public, insecure channels without compromising the security of the system.

The RSA system is the public-key method of Rivest, Shamir and Adleman, and its security rests on the difficulty of factoring the public modulus. The scheme was presented as an encryption method with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. Its authors drew two consequences: couriers are not needed to transmit keys, since messages can be enciphered with a publicly revealed key, and a message can be signed using a privately held decryption key whose signature anyone can verify.

In 1970 James H. Ellis, a British cryptographer at the UK Government Communications Headquarters, conceived of the possibility of non-secret encryption, now called public key cryptography, but could see no way to implement it. In 1973 Ellis's colleague Clifford Cocks implemented what has become known as the RSA encryption algorithm, and in 1974 Malcolm J. Williamson developed what is now known as Diffie-Hellman key exchange. The British discoveries were not publicly acknowledged until the research was declassified in 1997 by the British government.

The Advanced Encryption Standard was published as FIPS 197 on November 26, 2001, and it is based on the Rijndael family of algorithms. The standard specifies three members of that family — AES-128, AES-192 and AES-256 — distinguished by the length of the key each employs.

AES accepts keys of 128, 192 or 256 bits, and it encrypts and decrypts data in blocks of 128 bits.

The Secure Hash Standard defines a family of secure hash algorithms ranging from SHA-1 up to SHA-512 and its truncated variants, with message digests ranging in length from 160 to 512 bits depending on the algorithm. Message digests are used to detect whether messages have been changed since the digests were generated.

NIST announced the initiation of the AES development effort on 2 January 1997 and made a formal call for algorithms on 12 September 1997, stipulating that the AES be unclassified, publicly disclosed and available royalty-free worldwide. The competition received 15 viable submissions from 12 countries, and in October 2000 NIST announced that Rijndael, created by the Belgian cryptographers Joan Daemen and Vincent Rijmen, had been accepted as the new standard.

Cryptography on the web rests on a small number of widely deployed protocols and standards. According to W3Techs surveys, the default protocol HTTPS is used by 90.2% of all websites.

The standards landscape shifted with the arrival of post-quantum tools. FIPS 203, 204 and 205 were finalized on August 13, 2024.

Offering HTTPS requires getting a certificate from a certificate authority; since 2016 the certificate authority Let's Encrypt has offered free certificates to the public using an API that enables easy automation.

NIST announced in 2022 its selection of four algorithms — CRYSTALS-Kyber, CRYSTALS-Dilithium, Sphincs+ and FALCON — slated for standardization, and in 2023 released draft versions of three of the standards. The post-quantum standard FIPS 203 is based on the CRYSTALS-Kyber algorithm, which has been renamed ML-KEM, short for Module-Lattice-Based Key-Encapsulation Mechanism, while FIPS 204 is intended as the primary standard for protecting digital signatures, using the CRYSTALS-Dilithium algorithm, renamed ML-DSA, short for Module-Lattice-Based Digital Signature Algorithm. NIST published FIPS 203 on 13 August 2024 as the Module-Lattice-Based Key-Encapsulation Mechanism Standard.

• c. 400 BCE
  The Spartan scytale
  The Spartans employed the scytale, a cipher device consisting of a tapered baton wrapped with parchment, for secret communication between military commanders.
• c. 850
  Al-Kindi's treatise on cryptanalysis
  In ninth-century Baghdad the Arab polymath al-Kindi composed the Risalah fi Istikhraj al-Mu'amma, the earliest known treatise on cryptanalysis, setting out frequency analysis.
• 1470
  Alberti's cipher disk
  Leon Battista Alberti published Trattati in cifra, describing the first cipher disk and prescribing that its setting be changed after enciphering three or four words.
• 1553
  First description of the Vigenère cipher
  Giovan Battista Bellaso described the polyalphabetic cipher that would later be misattributed to Blaise de Vigenère.
• 1586
  Vigenère's autokey cipher
  Blaise de Vigenère published an autokey polyalphabetic cipher before the court of Henry III of France.
• 1863
  Kasiski breaks the Vigenère cipher
  Friedrich Kasiski published the first general method of deciphering Vigenère ciphers, three centuries after the cipher was described.
• 1918
  Scherbius patents the Enigma
  The firm Scherbius & Ritter patented ideas for a cipher machine in 1918 and began marketing the finished product as Enigma in 1923, initially for commercial markets.
• December 1932
  Enigma broken by Rejewski
  Marian Rejewski of the Polish General Staff's Cipher Bureau broke the plugboard Enigma using permutation group theory and French-supplied intelligence.
• 1939
  Turing joins Bletchley Park
  Alan Turing took up a full-time role at Bletchley Park, where he designed the British bombe soon after arriving in September.
• 18 March 1940
  First Bombe delivered
  The first bombe, named Victory, was delivered to Bletchley Park on 18 March 1940.
• 1948
  Shannon's information theory paper
  Claude Shannon published A Mathematical Theory of Communication in the Bell System Technical Journal, founding information theory.
• 1949
  Communication Theory of Secrecy Systems
  Shannon's follow-up paper applied information theory to cryptography and defined perfect secrecy.
• November 1976
  Public-key cryptography published
  Diffie and Hellman's New Directions in Cryptography appeared in IEEE Transactions on Information Theory, proposing public key cryptosystems.
• 15 January 1977
  DES becomes a federal standard
  The Data Encryption Standard was issued as Federal Information Processing Standards Publication 46.
• 26 November 2001
  AES published as FIPS 197
  The Advanced Encryption Standard, based on the Rijndael algorithm selected in 2000, was published as FIPS 197.
• August 2018
  TLS 1.3 specified
  RFC 8446 specified Transport Layer Security version 1.3, superseding previous versions including TLS 1.2.
• 13 August 2024
  Post-quantum standards finalized
  NIST released the first three finalized post-quantum encryption standards, FIPS 203, 204 and 205, to secure data against quantum computers.