http://www.ieeeghn.org/wiki/index.php/Cryptography
Cryptography
From GHN
Cryptography Background
The word cryptography comes from the Greek words kryptos meaning hidden and graphein meaning writing. Cryptography is the study of hidden writing, or the science of encrypting and decrypting text and messages.
Origins
It is believed that the oldest known text to contain one of the essential components of cryptography, a modification of the text, occurred some 4000 years ago in the Egyptian town of Menet Khufu where the hieroglyphic inscriptions on the tomb of the nobleman KHNUMHOTEP II were written with a number of unusual symbols to confuse or obscure the meaning of the inscriptions.
In 5BC the Spartans, a warrior society famed for their austere lifestyle, bravery, and skill in battle, developed a cryptographic device to send and receive secret messages. This device, a cylinder called a Scytale, was in the possession of both the sender and the recipient of the message. To prepare the message, a narrow strip of parchment or leather, much like a modern-day paper streamer, was wound around the Scytale and the message was written across it. Once unwound, for transport to the receiver, the tape displayed only a sequence of meaningless letters until it was re-wound onto a Scytale of exactly the same diameter. The code, produced by unwinding the tape, was a TRANSPOSITION cipher, that is, one where the letters remain the same but the order is changed. This is still the basis for many popular modern-day techniques.
The other major ingredient of these modern techniques is the ADDITIVE/SUBSTITUTION cipher. Although the Greek writer Polyibus described a substitution technique, its first recorded use was by Julius Caesar. Messages were encoded by substituting the letter in the text by one that is three positions to the right. A became D, V became Y etc. The reason why a substitution of three letters, and not four, two or six, was chosen has never been explained.
In an essay written in 1466, an Italian Leon Battista Alberti who is often called the ‘father of western cryptography’, described the construction of a cypher disk, founding the concept of POLY ALPHABETIC ciphers. Although he had made the most important advance in cryptography in at least five hundred years, he did not develop his concept. It was left for others, the best known being the French cryptographer Blaise de Vigenere to devise a practical poly alphabetic system which bears his name, the VIGENERE SQUARE. At the time, and for a considerable time afterwards this technique was believed to be unbreakable (Le Chiffre Indechiffrable). There was however a weakness in this cipher waiting to be exploited because the cyphertext produced by this method was vulnerable to the yet undiscovered statistical attack.
Classical cryptography
The earliest known use of cryptography is found in non-standard hieroglyphs carved into monuments from Egypt's Old Kingdom (ca 4500+ years ago). These are not thought to be serious attempts at secret communications, however, but rather to have been attempts at mystery, intrigue, or even amusement for literate onlookers. These are examples of still other uses of cryptography, or of something that looks (impressively if misleadingly) like it. Some clay tablets from Mesopotamia, somewhat later are clearly meant to protect information — they encrypt recipes, presumably commercially valuable. Later still, Hebrew scholars made use of simple monoalphabetic substitution ciphers (such as the Atbash cipher) beginning perhaps around 500 to 600 BC.
Cryptography has a long tradition in religious writing likely to offend the dominant culture or political authorities. Perhaps the most famous is the 'Number of the Beast' from the Book of Revelation in the Christian New Testament. '666' might be a cryptographic (i.e., encrypted) way of concealing a dangerous reference; many scholars believe it's a concealed reference to the Roman Empire, or more likely to the Emperor Nero himself, (and so to Roman persecution policies) that would have been understood by the initiated (who 'had the key to understanding'), and yet be safe or at least deniable (and so 'less' dangerous) if it came to the attention of the authorities. At least for orthodox Christian writing, most of the need for such concealment ended with Constantine's conversion and the adoption of Christianity as the official religion of the Empire.
A Scytale, an early device for encryption. The Greeks of Classical times are said to have known of ciphers (e.g., the scytale transposition cipher claimed to have been used by the Spartan military). Herodotus tells us of secret messages physically concealed beneath wax on wooden tablets or as a tattoo on a slave's head concealed by regrown hair, though these are not properly examples of cryptography per se as the message, once known, is directly readable; this is known as steganography. Another Greek method was developed by Polybius (now called the "Polybius Square").[1] The Romans certainly did know something of cryptography (e.g., the Caesar cipher and its variations). There is ancient mention of a book about Roman military cryptography (especially Julius Caesar's); it has been, unfortunately, lost.
In India, cryptography was also well known. It is recommended in the Kama Sutra as a technique by which lovers can communicate without being discovered.
Medieval cryptography
The first page of al-Kindi's manuscript On Deciphering Cryptographic Messages, containing the first descriptions of cryptanalysis and frequency analysis. See also: Voynich Manuscript
It was probably religiously motivated textual analysis of the Qur'an which led to the invention of the frequency analysis technique for breaking monoalphabetic substitution ciphers by al-Kindi sometime around AD 800 (Ibrahim Al-Kadi -1992). It was the most fundamental cryptanalytic advance until WWII.
Essentially all ciphers remained vulnerable to this cryptanalytic technique until the development of the polyalphabetic cipher by Leone Battista Alberti (ca 1465), and many remained so thereafter. Alberti is often called the "Father of Western Cryptology". Johannes Trithemius, in his work Poligraphia, invented the tabula recta, a critical component of the Vigenère cipher. The French cryptographer Blaise de Vigenere devised a practical poly alphabetic system which bears his name, the Vigenère cipher.[2]
Although Leone Battista Alberti is usually considered the father of polyalphabetic cipher, Prof. Al-Kadi's 1990 paper (ref- 3), reviewing Arabic contributions to cryptography reported knowledge of polyalphabetic ciphers 500 years before Alberti, based on a recently discovered manuscript by al-Kindi.[citation needed]
The Arab mathematician, Al-Kindi, wrote a book on cryptography entitled Risalah fi Istikhraj al-Mu'amma (Manuscript for the Deciphering Cryptographic Messages), circa AD 800. He described the first cryptanalysis techniques, including some for polyalphabetic ciphers, cipher classification, Arabic Phonetics and Syntax, and, most importantly, described the use of several techniques for cryptanalysis, and gave the first descriptions on frequency analysis.[3] He also covered methods of encipherments, cryptanalysis of certain encipherments, and statistical analysis of letters and letter combinations in Arabic.[4]
Ahmad al-Qalqashandi (1355-1418) wrote the Subh al-a 'sha, a 14-volume encyclopaedia which included a section on cryptology. This information was attributed to Taj ad-Din Ali ibn ad-Duraihim ben Muhammad ath-Tha 'alibi al-Mausili who lived from 1312 to 1361, but whose writings on cryptography have been lost. The list of ciphers in this work included both substitution and transposition, and for the first time, a cipher with multiple substitutions for each plaintext letter. Also traced to Ibn al-Duraihim is an exposition on and worked example of cryptanalysis, including the use of tables of letter frequencies and sets of letters which can not occur together in one word.
In Europe, cryptography became (secretly) more important as a consequence of political competition and religious revolution. For instance, in Europe during and after the Renaissance, citizens of the various Italian states — the Papal States and the Roman Catholic Church included — were responsible for rapid proliferation of cryptographic techniques, few of which reflect understanding (or even knowledge) of Alberti's polyalphabetic advance. 'Advanced ciphers', even after Alberti, weren't as advanced as their inventors / developers / users claimed (and probably even themselves believed). They were regularly broken. This over-optimism may be inherent in cryptography for it was then, and remains today, fundamentally difficult to accurately know how vulnerable your system actually is. In the absence of knowledge, guesses and hopes, as may be expected, are common.
Cryptography, cryptanalysis, and secret agent/courier betrayal featured in the Babington plot during the reign of Queen Elizabeth I which led to the execution of Mary, Queen of Scots. An encrypted message from the time of the Man in the Iron Mask (decrypted just prior to 1900 by Étienne Bazeries) has shed some, regrettably non-definitive, light on the identity of that real, if legendary and unfortunate, prisoner. Cryptography, and its misuse, were involved in the plotting which led to the execution of Mata Hari and in the conniving which led to the travesty of Dreyfus' conviction and imprisonment, both in the early 20th century. Fortunately, cryptographers were also involved in exposing the machinations which had led to Dreyfus' problems; Mata Hari, in contrast, was shot.
Outside of Europe, after the end of the Muslim Golden Age at the hand of the Mongols, cryptography remained comparatively undeveloped. Cryptography in Japan seems not to have been used until about 1510, and advanced techniques were not known until after the opening of the country to the West beginning in the 1860s. During the 1920s, it was Polish naval officers who assisted the Japanese military with code and cipher development.
Cryptography from 1800 to World War II
It wasn't until the 19th century that cryptographers developed anything more than ad-hoc approaches to either encryption or cryptoanalysis. Examples include Charles Babbage's Crimean War era work on the mathematical cryptanalysis of polyalphabetic ciphers, redeveloped and published somewhat later by the Prussian Friedrich Kasiski. The understanding of cryptography at this time typically consisted of hard-won rules of thumb; eg, Auguste Kerckhoffs' cryptographic writings in the latter 19th century. Edgar Allan Poe used systematic methods to solve ciphers in the 1840s. In particular he placed a notice of his abilities in the Philadelphia paper Alexander's Weekly Express Messenger, inviting submissions of ciphers, of which he proceeded to solve almost all. His successes created a public stir lasting several months. He later wrote an essay on methods of cryptography which proved useful as an introduction for the novice Room 40 British cryptanalysts attempting to break German codes and ciphers during World War I, and in a famous story, "The Gold Bug", in which cryptoanalysis featured prominently.
Around 1854, Charles Babbage, developed the method of statistical analysis by which he successfully decrypted messages encrypted by the Vigenere square. Unfortunately, due to his habit of not completing ‘the paperwork’, or possibly to protect the fact that because of his work Britain could decrypt Vigenere messages sent in the Crimea, this fact was not discovered until the twentieth century. The honour of developing the statistical attack technique and cracking Vigenere was to go to the Prussian Kasiski in 1863, this technique having since been termed the "Kasiski Test".
In 1917, Gilbert Vernam proposed a teletype cipher where a previously-prepared key, kept on a paper tape, is combined character by character with the plaintext message to produce the output ciphertext. This led to the development of the one time pad and to the use of electromechanical devices known as cipher machines.
Mathematical crypto methods proliferated in the period prior to World War II, notably in William F. Friedman's application of statistical techniques to cryptanalysis and cipher development and in Marian Rejewski's initial break into the German Army's version of the Enigma system in 1932.
Both cryptography and cryptoanalysis have become far more mathematical since WWII. Even so, it has taken the wide availability of computers and the Internet as a communications medium, to bring effective cryptography into common use by anyone other than national governments or similarly large enterprises.
World War II cryptography
The Enigma machine was widely used by Nazi Germany; its cryptanalysis by the Allies provided vital Ultra intelligence. By World War II, mechanical and electromechanical cipher machines were in wide use, although — where such machines were impractical — manual systems continued in use. Great advances were made in both cipher design and cryptanalysis, all in secrecy. Information about this period has begun to be declassified as the official British 50-year secrecy period has come to an end, as U.S. archives have slowly opened, and as assorted memoirs and articles have appeared.
The Germans made heavy use, in several variants, of an electromechanical rotor machine known as Enigma. Mathematician Marian Rejewski, at Poland's Cipher Bureau, in December 1932 deduced the detailed structure of the German Army Enigma, using mathematics and limited documentation supplied by Captain Gustave Bertrand of French military intelligence. This was the greatest breakthrough in cryptanalysis in a thousand years and more, according to historian David Kahn. Rejewski and his mathematical Cipher Bureau colleagues, Jerzy Różycki and Henryk Zygalski, continued reading Enigma and keeping pace with the evolution of the German Army machine's components and encipherment procedures. As the Poles' resources became strained by the changes being introduced by the Germans, and as war loomed, the Cipher Bureau, on the Polish General Staff's instructions, on July 25, 1939, at Warsaw, initiated French and British intelligence representatives into the secrets of Enigma decryption.
Soon after World War II broke out on 1 September 1939, key Cipher Bureau personnel were evacuated on September 17, as the Soviet Union entered eastern Poland, they crossed into Romania. From there they reached Paris, France; at PC Bruno, near Paris, they continued breaking Enigma, collaborating with British cryptologists at Bletchley Park as the British got up to speed on breaking Enigma. In due course, the British cryptographers — whose ranks included many chess masters and mathematics dons such as Gordon Welchman, Max Newman, and Alan Turing the conceptual founder of modern computing — substantially advanced the scale and technology of Enigma decryption.
At the end of the War, on 19 April 1945, Britain's top military officers were told that they could never reveal that the German Enigma cipher had been broken because it would give the defeated enemy the chance to say they "were not well and fairly beaten". [1]
US Navy cryptographers, with cooperation from British and Dutch cryptographers broke into several Japanese Navy crypto systems after 1940. The break into one of these, JN-25, famously led to the US victory in the Battle of Midway; and to the publication of that fact in the Chicago Tribune shortly after the battle, though the Japanese seem not to have noticed for they kept using the JN-25 system. A US Army group, the SIS, managed to break the highest security Japanese diplomatic cipher system (an electromechanical 'stepping switch' machine called Purple by the Americans) even before WWII began. The Americans referred to the intelligence resulting from cryptanalysis, perhaps especially that from the Purple machine, as 'Magic'. The British eventually settled on 'Ultra' for intelligence resulting from cryptanalysis, particularly that from message traffic protected by the various Enigmas. An earlier British term for Ultra had been 'Boniface' in an attempt to suggest, if betrayed, that it might have an individual agent as a source.
The German military also deployed several mechanical attempts at a one-time pad. Bletchley Park called them the Fish ciphers, and Max Newman and colleagues designed and deployed the Heath Robinson, and then the world's first programmable digital electronic computer, the Colossus, to help with their cryptanalysis. The German Foreign Office began to use the one-time pad in 1919; some of this traffic was read in WWII partly as the result of recovery of some key material in South America that was discarded without sufficient care by a German courier.
The Japanese Foreign Office used a locally developed electrical stepping switch based system, named Purple by the US, and also had used several similar machines for attaches in some Japanese embassies. One of these was called the 'M-machine' by the US, another was referred to as 'Red'. All these systems were broken, to one degree or another, by the Allies.
SIGABA is described in U.S. Patent 6,175,625 , filed in 1944 but not issued until 2001.Allied cipher machines used in WWII included the British TypeX and the American SIGABA; both were electromechanical rotor designs similar in spirit to the Enigma, albeit with major improvements. Neither is known to have been broken by anyone during the War. The Poles used the Lacida machine, but its security was found to be less than intended (by Polish Army cryptographers in the UK), and its use was discontinued. US troops in the field used the M-209 and the still less secure M-94 family machines. British SOE agents initially used 'poem ciphers' (memorized poems were the encryption/decryption keys), but later in the War, they began to switch to one-time pads.
The VIC cipher (used at least until 1957 in connection with Rudolf Abel's NY spy ring) was a very complex hand cipher, and is claimed to be the most complicated known to have been used by the Soviets, according to David Kahn in Kahn on Codes. For the decrypting of Soviet ciphers (particularly when one-time pads were reused), see the Venona project.
Modern cryptography
Until the 1970s, secure cryptography was largely the preserve of governments. Two events have since brought it squarely into the public domain:
- The creation of a public encryption standard (DES); and
- The invention of public-key cryptography.
Shannon
The era of modern cryptography really begins with Claude Shannon, arguably the father of mathematical cryptography, with the work he did during WWII on communications security. In 1949 he published Communication Theory of Secrecy Systems in the Bell System Technical Journal and a little later the book, Mathematical Theory of Communication, with Warren Weaver. Both included results from his WWII work. These, in addition to his other works on information and communication theory established a solid theoretical basis for cryptography and also for much of cryptanalysis. And with that, cryptography more or less disappeared into secret government communications organizations such as NSA, GCHQ, and their equivalents elsewhere. Very little work was again made public until the mid '70s, when everything changed.
An encryption standard
The mid-1970s saw two major public i.e., non-secret; advances. First was the publication of the draft Data Encryption Standard in the U.S. Federal Register on 17 March 1975. The proposed DES cipher was submitted by a research group at IBM, at the invitation of the National Bureau of Standards (now NIST), in an effort to develop secure electronic communication facilities for businesses such as banks and other large financial organizations. After 'advice' and modification by NSA, acting behind the scenes, it was adopted and published as a Federal Information Processing Standard Publication in 1977 (currently at FIPS 46-3). DES was the first publicly accessible cipher to be 'blessed' by a national agency such as NSA. The release of its specification by NBS stimulated an explosion of public and academic interest in cryptography.
The aging DES was officially replaced by the Advanced Encryption Standard (AES) in 2001 when NIST announced FIPS 197. After an open competition, NIST selected Rijndael, submitted by two Belgian cryptographers, to be the AES. DES, and more secure variants of it (such as Triple DES; see FIPS 46-3), are still used today, having been incorporated into many national and organizational standards. However, its 56-bit key-size has been shown to be insufficient to guard against brute force attacks. One such attack, undertaken by the cyber civil-rights group Electronic Frontier Foundation in 1997, succeeded in 56 hours — the story is in Cracking DES, published by O'Reilly and Associates. As a result, use of straight DES encryption is now without doubt insecure for use in new cryptosystem designs, and messages protected by older cryptosystems using DES, and indeed all messages sent since 1976 using DES, are also at risk. Regardless of DES' inherent quality, the DES key size (56-bits) was thought to be too small by some even in 1976, perhaps most publicly by Whitfield Diffie. There was suspicion that government organizations even then had sufficient computing power to break DES messages; clearly others have achieved this capability.
Public Key Systems
The second development, in 1976, was perhaps even more important, for it fundamentally changed the way cryptosystems might work. This was the publication of the paper “New Directions in Cryptography” by Whitfield Diffie and Martin Hellman. It introduced a radically new method of distributing cryptographic keys, which went far toward solving one of the fundamental problems of cryptography, key distribution, and has become known as the Diffie-Hellman key exchange. The article also stimulated the almost immediate public development of a new class of enciphering algorithms, the asymmetric key algorithms.
Prior to that time, all useful modern encryption algorithms had been symmetric key algorithms, in which the same cryptographic key is used with the underlying algorithm by both the sender and the recipient, who must both keep it secret. All of the electromechanical machines used in WWII were of this logical class, as were the Caesar and Atbash ciphers and essentially all cipher systems throughout history. The 'key' for a code is the codebook, which must likewise be distributed and kept secret, and so shares most of the same problems in practice.
Of necessity, the key in every such system had to be exchanged between the communicating parties in some secure way prior to any use of the system (the term usually used is 'via a secure channel') such as a trustworthy courier with a briefcase handcuffed to a wrist, or face-to-face contact, or a loyal carrier pigeon. This key management requirement is never trivial and very rapidly becomes unmanageable as the number of participants increases, or when secure channels aren't available for key exchange, or when, as is sensible cryptographic practice, keys are frequently changed. In particular, if messages are meant to be secure from other users, a separate key is required for each possible pair of users. A system of this kind is known as a secret key, or symmetric key cryptosystem. D-H key exchange (and succeeding improvements and variants) made operation of these systems much easier, and more secure, than had ever been possible before in all of history.
In contrast, asymmetric key encryption uses a pair of mathematically related keys, each of which decrypts the encryption performed using the other. Some, but not all, of these algorithms have the additional property that one of the paired keys cannot be deduced from the other by any known method other than trial and error. An algorithm of this kind is known as a public key or asymmetric key system. Using such an algorithm, only one key pair is needed per user. By designating one key of the pair as private (always secret), and the other as public (often widely available), no secure channel is needed for key exchange. So long as the private key stays secret, the public key can be widely known for a very long time without compromising security, making it safe to reuse the same key pair indefinitely.
For two users of an asymmetric key algorithm to communicate securely over an insecure channel, each user will need to know their own public and private keys as well as the other user's public key. Take this basic scenario: Alice and Bob each have a pair of keys they've been using for years with many other users. At the start of their message, they exchange public keys, unencrypted over an insecure line. Alice then encrypts a message using her private key, and then re-encrypts that result using Bob's public key. The double-encrypted message is then sent as digital data over a wire from Alice to Bob. Bob receives the bit stream and decrypts it using his own private key, and then decrypts that bit stream using Alice's public key. If the final result is recognizable as a message, Bob can be confident that the message actually came from someone who knows Alice's private key (presumably actually her if she's been careful with her private key), and that anyone eavesdropping on the channel will need Bob's private key in order to understand the message.
Asymmetric algorithms rely for their effectiveness on a class of problems in mathematics called one-way functions, which require relatively little computational power to execute, but vast amounts of power to reverse, if reversal is possible at all. A classic example of a one-way function is multiplication of very large prime numbers. It's fairly quick to multiply two large primes, but very difficult to find the factors of the product of two large primes. Because of the mathematics of one-way functions, most possible keys are bad choices as cryptographic keys; only a small fraction of the possible keys of a given length are suitable, and so asymmetric algorithms require very long keys to reach the same level of security provided by relatively shorter symmetric keys. The need to both generate the key pairs, and perform the encryption/decryption operations make asymmetric algorithms computationally expensive, compared to most symmetric algorithms. Since symmetric algorithms can often use any sequence of (random, or at least unpredictable) bits as a key, a disposable session key can be quickly generated for short-term use. Consequently, it is common practice to use a long asymmetric key to exchange a disposable, much shorter (but just as strong) symmetric key. The slower asymmetric algorithm securely sends a symmetric session key, and the faster symmetric algorithm takes over for the remainder of the message.
Asymmetric key cryptography, Diffie-Hellman key exchange, and the best known of the public key / private key algorithms (i.e., what is usually called the RSA algorithm), all seem to have been independently developed at a UK intelligence agency before the public announcement by Diffie and Hellman in 1976. GCHQ has released documents claiming they had developed public key cryptography before the publication of Diffie and Hellman's paper. Various classified papers were written at GCHQ during the 1960s and 1970s which eventually led to schemes essentially identical to RSA encryption and to Diffie-Hellman key exchange in 1973 and 1974. Some of these have now been published, and the inventors (James H. Ellis, Clifford Cocks, and Malcolm Williamson) have made public select parts of their work.
Cryptography Politics (Wars)
The public developments of the 1970s broke the near monopoly on high quality cryptography held by government organizations, refer to S Levy's Crypto for a journalistic account of some of the policy controversy of the time in the US. For the first time ever, those outside government organizations had access to cryptography not readily breakable by anyone, including governments. Considerable controversy, and conflict, both public and private, began more or less immediately. It has not yet subsided. In many countries, for example, export of cryptography is subject to restrictions. Until 1996 export from the U.S. of cryptography using keys longer than 40 bits, ie too small to be very secure against a knowledgeable attacker, was sharply limited. As recently as 2004, former FBI Director Louis Freeh, testifying before the 9/11 Commission, called for new laws against public use of encryption.
One of the most significant people favouring strong encryption for public use was Phil Zimmermann. He wrote and then in 1991 released PGP (Pretty Good Privacy), a very high quality crypto system. He distributed a freeware version of PGP when he felt threatened by legislation then under consideration by the US Government that would require backdoors to be included in all cryptographic products developed within the US. His system was released worldwide shortly after he released it in the US, and that began a long criminal investigation of him by the US Government Justice Department for the alleged violation of export restrictions. The Justice Department eventually dropped its case against Zimmermann, and the freeware distribution of PGP has continued around the world. PGP even eventually became an open Internet standard, RFC 2440 or OpenPGP.
Modern Cryptoanalysis
The development of cryptography has been paralleled by near equal developments in cryptoanalysis — of the "breaking" of codes and ciphers. The early discovery and application of frequency analysis to the reading of encrypted communications has on occasion altered the course of history. Thus the Zimmermann Telegram triggered the United States' entry into World War I; and Allied reading of Nazi Germany's ciphers shortened World War II, in some evaluations by as much as two years.
Modern cryptoanalysts sometimes harness large numbers of integrated circuits. This board is part of the EFF DES cracker, which contained over 1800 custom chips and could brute force a DES key in a matter of days. While modern ciphers like AES and the higher quality asymmetric ciphers are widely considered unbreakable, poor designs and implementations are still sometimes adopted and there have been important cryptanalytic breaks of deployed crypto systems in recent years.
Notable examples of broken crypto designs include DES, the first Wi-Fi encryption scheme WEP, the Content Scrambling System used for encrypting and controlling DVD use, the A5/1 and A5/2 ciphers used in GSM cell phones, and the CRYPTO1 cipher used in the widely deployed MIFARE Classic smart cards from NXP Semiconductors, a spun off division of Philips Electronics. All of these are symmetric ciphers. Thus far, not one of the mathematical ideas underlying public key cryptography has been proven to be 'unbreakable', and so some future mathematical analysis advance might render systems relying on them insecure. While few informed observers foresee such a breakthrough, the key size recommended for security as best practice keeps increasing as increased computing power required for breaking codes becomes cheaper and more available.
More recent developments utilising quantum computing is the NTRUEncrypt lattice based systems first proposed in 1996. It was standardised in 2008 by the IEEE Std 1363.1. This currently appears to be the leading candidate when RSA and elliptic curve cryptography eventually need to be withdrawn. The parallels, and an idea for quantum encryption techniques are based on the massive computational intensive thermodynamics modelling in the book by George G Szpiro.
Applications
- Ancient Languages; Modern cryptanalysis has been used by archaeologists to identify ancient languages and codes.
- Radio Communications; Early radio communications used baseband inversion (analogue systems) and then multi-band vocoders, eg the NEC C1 radiotelephone radios circa 1982. This only made casual eavesdropping difficult and was very easily cracked – even without additional equipment!
GSM communications
• Authentication
The COMP128 algorithm as the implementation of the A3 algorithm is most popular. The A3 task is to generate the 32-bit Signed Response utilizing the 128-bit random challenge generated by the Home Location Register and the 128-bit Individual Subscriber Authentication Key from the Subscribers SIM card or the Home Location Register. This encryption has been broken in under a minute.
• Voice Encryption
This uses a stream cipher known as the A5 algorithm. Multiple versions of the A5 algorithm exist which implement various levels of encryption. This encryption has been broken in under a second using ciphertext-only attack. Attack methods for A5/1 and A5/3 are also published.
A5/0 utilizes no encryption.
A5/1 is the original A5 algorithm used in Europe.
A5/2 is a weaker encryption algorithm created for export and used in the United States.
A5/3 is a strong encryption algorithm created as part of the 3rd Generation Partnership Project (3GPP).
Motorola build voice/data crypto radios, XTS3000, XTS5000 etc. These have DES-XL, DVI-XL, DVP-XL (noting DVP is an early first generation Securenet product).
DVP is a Motorola developed Digital Voice Privacy algorithm made in the mid-1970's using 32bit key length.
DES is Motorola encryption algorithm that meets US Government encryption guidelines, using a 56bit DES key.
DVP-XL is Motorola proprietary encryption algorithm using 32bit key encryption.
DVI-XL is an export grade variant of DVP-XL for export outside of the US.
DES-XL is a Motorola variant of the US Government DES algorithm.
DVP and DES are self-synchronizing modes of operation, coverage range is slightly degraded due to data errors due to Rayleigh fading on radio channel.
DVP-XL, DVI-XL, DES-XL use a sync header and periodic sync updates. For operation on fading radio channels, this provides encryption coverage range similar to analog FM voice coverage.
DVP-XL, DVI-XL, and DES-XL should provide similar coverage on conventional or trunked systems. Since current generation of trunking control channels are not encrypted, someone could monitor which talkgroups are active and the general level of activity, even though they could not monitor the talkgroup conversations on the traffic channels.
DES-OFB used output feedback for error correction.
ADP is a 40bit key length software based encryption method, simple, but restricts hardware updates.
AES-256, these algorithms that use a 256 bit key length.
Microsoft messed up the Windows 3.1 and Windows 95 password file (.PWL) encryption key processing, providing a maximum of 32 bits of keyspace. A dictionary attack could recover most password in a few seconds. Frank Stevenson extended this attack by taking advantage of the fact that the RC4 cipher that Microsoft used was a pure keystream generator, allowing all information protected with it to be recovered in a fraction of a second, even with more recent upgrades to 128bit keys.
The idea of self encrypting polymorphic viruses gained popularity in the early 1990’s and brought to life generators of polymorphic code - in early 1992 the famous "Dedicated" virus appears, based on the first known polymorphic generator MtE and the first in a series of MtE-viruses; shortly after that there appears the polymorphic generator itself.
Cryptography is featured heavily in the 1998 film “Mercury Rising” with Bruce Willis, Alec Baldwin and Miko Hughes.
The 1992 film “Sneakers” touches on crypro techniques, and the 1988 Vietnam war film “Bat 21” shows a crypto style graphical map key used to rescue a general.
Further Reading
“Breaking the Maya Code”. Michael D. Coe, 1992, 304 pp. London and New York: Thames and Hudson. The work of the Russian linguist Yuri Knorozov is the basis for reading Mayan hieroglyphics phonetically.
“The secret life of numbers”, George G Szpiro, 210 pp. Joseph Henry Press 2006, Chapter 47.
CRYPTANALYSIS: A STUDY OF CIPHERS AND THEIR SOLUTION by Helen Fouche Gaines, Dover Publications, 1956 edition.
“The Codebreakers”, David Kahn, Macmillian, 1967.
"The Sectret War", Francis Russell & the Editors of TIME-LIFE Books, Time-Life Books, 1981.
"The Puzzle Palace", James Bamford, Houghton-Mifflin, 1982.
“The Code Book”, Simon Singh, Doubleday, 1998.
CRYPTOGRAPHY DECRYPTED by H.X. Mel and Doris Baker, Addison-Wesley, 2001.
"Quantum Cryptography" by Charles Bennett, Gilles Brassard, & Artur K. Ekert, SCIENTIFIC AMERICAN, July 1992.
"They're Listening To Your Calls" by Otis Port with Inka Resch, BUSINESS WEEK, 31 May 1999, 110:111.
"Handbook of Applied Cryptography", A. Menezes, P. van Oorschot, and S. Vanstone, CRC Press, 1996.
Encryption Wars Article - Spectrum Magazine May 2000
Exhaustive Cryptoanalysis of the NBS Data Encryption Standard
