Be able to define the term cyber security and be able to describe the main purposes of cyber security.
|Students should know that cyber security consists of the processes, practices and technologies designed to protect networks, computers, programs and data from attack, damage or unauthorised access.|
The Four Fundamentals of Cybersecurity
- By Brad Deflin
- Published: 7/27/2015
The innovation in IT security technology is driving ease-of-use and efficacy, and represents great value. And, true to the nature of technology, these attributes will increase with time. Treasury departments should engage staff with this technology in a fashion that is relevant to their daily activities in their personal lives, which will dramatically increase awareness and compliance at the workplace.
“The Four Fundamentals of Personal Cybersecurity” is an approach relevant to individuals, yet has direct application to employees in the workplace.
1. Protect the device. Smartphones, laptops, pads, tablets, and about anything that connects online should be protected using state-of-the-science device protection solutions. Fortunately, recent innovations have brought high-quality and effective protection systems that once were available only to large, server-centric networks, and made them available to individuals and their devices to function securely in all environments and over any networks.
- Device protection should include remote management features that eliminate the need for user-input or behavioral modifications.
- Real-time antivirus, browser and application protections, and the host of defenses standard with most high-quality solutions, are essential.
- Lock and Erase functions are optional.
- Password management applications should work seamlessly across mobile device platforms, and the enterprise should sponsor software purchases and training for all employees.
- Automatic updating and patching of operating system software and other, vulnerable third-party applications such as Adobe and Java.
- Increasingly, collaborative threat intelligence resources are coming to bear for actionable, real-time, preemptive defenses.
- Algorithms will increase in effectiveness and application to predict and defend from future threats as they morph and evolve.
These automated and remotely managed functions will dramatically mitigate the risk of attacks to individuals and their devices, regardless of location.
2. Protect the connection. Once the individual device connects online, more defenses are required to protect the information transmitted over the Internet.
- In addition to device protection, each individual device should have a VPN, or Virtual Private Network, for automatic encryption of Internet traffic. A good VPN will protect the user’s identity, location, browsing, shopping, banking, and all information transacted online, including over public WiFi networks.
- Consumer level or “retail” VPN services have to-date been clunky to use and unpredictable in their operation. Recent innovation and new distribution models are providing much better performance and experience, and the improvements are expected to continue to improve over the near future.
3. Protect email communication. In many cases, email is the “barn-door” for personal information. Unfortunately, especially in the U.S., email is expected by many consumers to be “free” and has distracted us from some of the basic notions to the value of privacy today.
- Use a service that automatically strips IP location and metadata information from individual emails as they travel the Internet.
- Use services that employ open-source software for ultimate security, portability, and compatibility across technology architecture and platforms.
- Private email accounts can act as multi-generational digital domains for your employees and families, and provide a cyber-safe-room for decades to come.
- Private email as an employee benefit communicates full engagement of the enterprise and its leadership to every individual, inside and out of the organization.
4. Protect and back up electronic documents and files. Remote backup services are easy and cheap, and the convenience of the cloud is great, but critical documents deserve a digital vault.
- Critical documents include scanned passports, social security cards, birth certificates, wills, trusts, tax returns, and the other documents that are core to our personal lives.
- Easy-to-use but highly secure digital vaults act as a safety-deposit-box for sensitive documents.
Subsidizing the protection of these four fundamentals in your staff’s personal lives will drive increased cybersecurity awareness, compliance and effectiveness across the enterprise. All of these solutions are highly affordable, do not invade anyone’s privacy, and will provide an ROI that pays by reducing risk and increasing productivity for many years to come. Additionally, this approach to cybersecurity strategy positions the enterprise for optimal benefit from the forthcoming acceleration of disruptive innovation in the IT security industry.
Protecting your cyber assets and critical data
Cyber security has never been simple and because attacks evolve every day as attackers become more inventive, it is critical to properly define cyber security and identify what constitutes good cyber security.
Why is this so important? Because year over year, the worldwide spend for cyber security continues to grow: 71.1 billion in 2014 (7.9% over 2013), and 75 billion in 2015 (4.7% from 2014) and expected to reach 101 billion by 2018. Organizations are starting to understand that malware is a publically available commodity that makes it easy for anyone to become a cyber attacker, and even more companies offer security solutions that do little to defend against attacks. Cyber security demands focus and dedication.
Cyber security protects the data and integrity of computing assets belonging to or connecting to an organization’s network. Its purpose is to defend those assets against all threat actors throughout the entire life cycle of a cyber attack.
Kill chains, zero-day attacks, ransomware, alert fatigue and budgetary constraints are just a few of the challenges that cyber security professionals face. Cyber security experts need a stronger understanding of these topics and many others, to be able to confront those challenges more effectively.
The following articles each cover a specific cyber security topic to provide insights into the modern security environment, the cyber threat landscape and attacker mentality, including how attackers work, what tools they use, what vulnerabilities they target and what they’re really after.
Protecting your cyber assets and critical data
Cyber security has never been simple and because attacks evolve every day as attackers become more inventive, it is critical to properly define cyber security and identify what constitutes good cyber security.
RSA encryption is one method of encypting data that is to be transitted over an insecure medium such as the Internet.
In 1978, Ron Rivest, Adi Shamir, and Leonard Adleman introduced a cryptographic algorithm, which was essentially to replace the less secure National Bureau of Standards (NBS) algorithm. Most importantly, RSA implements a public-key cryptosystem, as well as digital signatures. RSA is motivated by the published works of Diffie and Hellman from several years before, who described the idea of such an algorithm, but never truly developed it. Introduced at the time when the era of electronic email was expected to soon arise, RSA implemented two important ideas:
- Public-key encryption. This idea omits the need for a “courier” to deliver keys to recipients over another secure channel before transmitting the originally-intended message. In RSA, encryption keys are public, while the decryption keys are not, so only the person with the correct decryption key can decipher an encrypted message. Everyone has their own encryption and decryption keys. The keys must be made in such a way that the decryption key may not be easily deduced from the public encryption key.
- Digital signatures. The receiver may need to verify that a transmitted message actually originated from the sender (signature), and didn’t just come from there (authentication). This is done using the sender’s decryption key, and the signature can later be verified by anyone, using the corresponding public encryption key. Signatures therefore cannot be forged. Also, no signer can later deny having signed the message.
This is not only useful for electronic mail, but for other electronic transactions and transmissions, such as fund transfers. The security of the RSA algorithm has so far been validated, since no known attempts to break it have yet been successful, mostly due to the difficulty of factoring large numbers n = pq, where p and q are large prime numbers.
How secure is RSA?
The RSA algorithm is indeed among the strongest, but can it withstand anything? Certainly nothing can withstand the test of time. In fact, no encryption technique is even perfectly secure from an attack by a realistic cryptanalyst. Methods such as brute-force are simple but lengthy and may crack a message, but not likely an entire encryption scheme. We must also consider a probabilistic approach, meaning there’s always a chance some one may get the “one key out of a million”. So far, we don’t know how to prove whether an encryption scheme is unbreakable. If we cannot prove it, we will at least see if someone can break the code. This is how the NBS standard and RSA were essentially certified. Despite years of attempts, no one has been known to crack either algorithm. Such a resistance to attack makes RSA secure in practice.
Breaking RSA is at least as hard as factoring n. Factoring large numbers is not provably hard, but no algorithms exists today to factor a 200-digit number in a reasonable amount of time. Fermat and Legendre have both contributed to this field by developing factoring algorithms, though factoring is still an age-old math problem. This is precisely what has partially “certified” RSA as secure.
To show that RSA is secure, we will consider how a cryptanalyst may try to obtain the decryption key from the public encryption key, and not how an intruder may attempt to “steal” the decryption key. This should be taken care of as one would protect their money, through physical security methods. The authors of RSA provide an example: the encryption device (which could be, say, a set of integrated chips within a computer), would be separate from the rest of the system. It would generate encryption and decryption keys, but would not print out the decryption key, even for its owner. It would, in fact, erase the decryption key if it sensed an attempted intrusion.
RSA is a strong encryption algorithm that has stood a partial test of time. RSA implements a public-key cryptosystem that allows secure communications and “digital signatures”, and its security rests in part on the difficulty of factoring large numbers. The authors (RSA) urged anyone to attempt to break their code, whether by factorization techniques or otherwise, and nobody to date seems to have succeeded. This has in effect certified RSA, and will continue to assure its security for as long as it stands the test of time against such break-ins.
At the time (1978), the RSA encryption function seemed to be the only known candidate for a trap-door one-way permutation, but now, others certainly exist, such as The Diffie-Hellman key agreement protocol or Digital Signature Algorithm (DSA) from the US goivernment's capstone project, or The ElGamal system ( a public-key cryptosystem based on the discrete logarithm problem), or The Merkle-Hellman knapsack cryptosystem (interestingly broken by Shamir) or The McEliece cryptosystem which is a public-key encryption algorithm based on algebraic coding theory.
The average size of n must increase with time as more efficient factoring algorithms are made and as computers are getting faster. In 1978, the authors of RSA suggested 200-digit long values for n. “As of 2008, the largest (known) number factored by a general-purpose factoring algorithm was [200 digits (663 bits)] long” . Currently, RSA keys are typically between 1024 and 2048 bits long, which experts predict may be breakable in the near future. So far, no one sees 4096-bit keys to be broken anytime soon. Today, an n no longer than 300 bits can be factored on a PC in several hours, thus keys are typically 4-7 times longer today.
RSA is slower than certain other symmetric cryptosystems. RSA is, in fact, commonly used to securely transmit the keys for another less secure, but faster algorithm. Several issues in fact exist that could potentially damage RSA’s security, such as timing attacks and problems with key distribution. I will not go into detail about these issues here. They are described succinctly in . In fact, these issues have solutions; the only downside is that any device implementing RSA would have to have much more hardware and software to counter certain types of attacks or attempts at eavesdropping.
A very major threat to RSA would be a solution to the Riemann hypothesis. Thus a solution has neither been proven to exist nor to not exist. Development on the Riemann hypothesis is currently relatively stagnant. However, if a solution were found, prime numbers would be too easy to find, and RSA would fall apart. Undoubtedly, much more sophisticated algorithms than RSA will continue to be developed as mathematicians discover more in the fields of number theory and cryptanalysis.
See which encryption method uses digital signatures, symmetric key exchanges, bulk encryption and much more in this Diffie-Hellman vs. RSA showdown from expert Michael Cobb.
Do you know of any algorithms that merge or combine the RSA and Diffie-Hellman algorithms? Would there be any benefit in doing so? If this is not possible, is one better than the other?
Let me answer this question by first explaining Diffie-Hellman vs. RSA algorithms. Diffie-Hellman is a key exchange algorithm and allows two parties to establish, over an insecure communications channel, a shared secret key that only the two parties know, even without having shared anything beforehand.
The shared key is an asymmetric key, but, like all asymmetric key systems, it is inherently slow and impractical for bulk encryption. The key is used instead to securely exchange a symmetric key, such as AES (Advanced Encryption Standard) used to encrypt subsequent communications. Unlike Diffie-Hellman, the RSA algorithm can be used for signing digital signatures as well as symmetric key exchange, but it does require the exchange of a public key beforehand.
RSA and Diffie-Hellman are both based on supposedly intractable problems, the difficulty of factoring large numbers and exponentiation and modular arithmetic respectively, and with key lengths of 1,024 bits, give comparable levels of security. Both have been subjected to scrutiny by mathematicians and cryptographers, but given correct implementation, neither is significantly less secure than the other.
The nature of the Diffie-Hellman key exchange does make it susceptible to man-in-the-middle attacks since it doesn't authenticate either party involved in the exchange. This is why Diffie-Hellman is used in combination with an additional authentication method, generally digital signatures. When using RSA, a 1,024-bit key is considered suitable both for generating digital signatures and for key exchange when used with bulk encryption, while a 2048-bit key is recommended when a digital signature must be kept secure for an extended period of time, such as a certificate authority’s key.
Getting back to the question at hand, you can’t really merge the two algorithms because of the unique attributes and complexity that each one has. Most encryption systems offer a choice between them rather than combining them. SSL 3.0 supports a choice of key exchange algorithms, including the RSA key exchange when certificates are used, and Diffie-Hellman key exchange for exchanging keys without certificates and without prior communication between client and server.
What’s the difference between Diffie-Hellman and RSA
Posted on 30 April 2015 by Carine Benji
RSA encryption is an asymmetric cryptography algorithm, widely used in electronic commerce and more generally to exchange confidential data on the Internet. Ron Rivest, Adi Shamir, and Leonard Adleman developed RSA, and it is named from the first letters of their last names (RSA). This algorithm was described in 1977 and has been patented by the Massachusetts Institute of Technology (MIT) in 1983 in the United States. The patent expired on 21 September 2000: This description responds to the fifth question our list of ” 300 infoSec Questions”:Question 5 What does RSA stand for ?
I do not know about you, but I thought in my head: they are still alive? when I sawAdi Shamir, Ronald Rivest, Whitfield Diffie, in the cryptographers’ Panel at the RSA Conference 2015. Not that I wish they are no longer of this world, but instead, it’s just that when you have learned from books inventions and scope, subconsciously you think that inventors are certainly no longer alive, I do not know why but there is the impression we have. So I wish long life to these Gents !
Going back to our definition ; RSA is a cryptosystem for public-key encryption , and it is widely used on the internet and elsewhere due to its strong security . Asymmetric encryption methods use RSA : For example, e-mail applications often use RSA to privately share a symmetric key between two systems. The application uses the recipient’s public key to encrypt a symmetric key, and the recipient’s private key decrypts it.
Diffie–Hellman (Whitfield Diffie – Martin Hellman ) key exchange is based on the premise that two correspondents, Alice and Bob, wish to communicate a secret number, but must do so on an insecure channel. An unauthorized user, Eve, is trying to intercept the message over the unsafe channel. If Eve obtains the message containing the key, all integrity and confidentiality is lost. This issue is resolved by masking the key using modular arithmetic. Diffie – Hellman is used to generate a shared secret in public for later symmetric(“private-key”) encryption.
RSA is an asymmetric algorithm used to encrypt data and digitally sign transmissions.. RSA is widely used to protect Internet traffic, including e-mail. RSA relies on the mathematical properties of prime numbers when creating public and private keys.These keys are commonly used with asymmetric encryption to privately share a symmetric key .Diffie-Hellman addresses key management and provides another method to privately share a symmetric key between two parties.
(Those who knows Insanity Workout with Shaun T. knows what’s Dig deeper mean …so instead to dig deep in our body’s resources we have to Dig deep in our brain !!! )
RSA uses the mathematical properties of prime numbers to generate secure public and private keys. Specifically, RSA relies on the fact that the product of two large prime numbers can’t be easily factored. The strength of the RSA depends on the difficulty of the prime number factorization. For applications with high-level security, the number of the decryption key bits should be greater than 512 bits. The math is complex and intriguing to mathematicians, but you don’t have to understand the math to understand that RSA is secure.
For example, researchers published a paper in 2010 identifying how long it took to factor a 232-digit number (768 bits). They wrote that it took them about two and a half years using hundreds of systems. They estimated that if a single 2.2 GHz computer was used, it would take fifteen hundred years to complete. RSA is used on the Internet as one of the protections for credit card transactions. It’s safe to say that today’s credit card information won’t be of much value in fifteen hundred years.
RSA uses at least 1024-bit keys today. RSA Security (a company that frequently tests the security of RSA) recommends using key sizes of at least 2048 bits long, and 3072-bit keys are on the horizon.
RSA is used to come up with a public/private key pair for asymmetric (“public-key”) encryption:
- Used to perform “true” public-key cryptography
- Key identity: (me)d = m (mod n) (lets you recover the encrypted message)
- n = prime1 × prime2 (n is publicly used for encryption)
- φ = (prime1 – 1) × (prime2 – 1) (Euler’s totient function)
- e is such that 1 < e < φ, and (e, φ) are coprime (e is publicly used for encryption)
- d × e = 1 (mod φ) (the modular inverse d is privately used for decryption)
Diffie-Hellman is a key exchange algorithm used to privately share a symmetric key between two parties. Once the two parties know the symmetric key, they use symmetric encryption to encrypt the data.
The Diffie–Hellman key exchange is based on the premise that two correspondents, Alice and Bob, wish to communicate a secret number, but must do so on an insecure channel. An unauthorized user, Eve, is trying to intercept the message over the unsafe channel. If Eve obtains the message containing the key, all integrity and confidentiality is lost. This issue is resolved by masking the key using modular arithmetic. Alice and Bob achieve secrecy by agreeing on a large prime number, p, and a base number, n. Alice will choose a personal, private value, a, which remains unknown to Bob.
Bob will generate a secret value only known to himself, b. It is important that a and b are less than p. Alice and Bob’s respective secret keys should be relatively prime to n, meaning that neither shares common factors with n. Alice’s public value is na mod p and Bob’s is nb mod p. The two correspondents exchange their public values, so that both parties now know both. Alice will compute nab = (nb)a mod p. Bob will compute nba = (na)b mod p. Once both algorithms are computed, each party will have the same number. Alice and Bob are now able to privately communicate on the insecure network.
Diffie-Hellman is used to generate a shared secret in public for later symmetric (“private-key”) encryption:
- Creates a shared secret between two (or more) parties, for subsequent symmetric encryption
- Key identity: (gens1)s2 = (gens2)s1 = shared secret (mod prime)
- gen is an integer whose powers generate all integer in [1, prime) (mod prime)
- s1 and s2 are the individuals’ “secrets”, only used to generate the symmetric key
RSA is used to come up with a public/private key pair for asymmetric (“public-key”) encryption.Diffie-Hellman is used to generate a shared secret in public for later symmetric (“private-key”) encryption.
From David Kahn's ``The Codebreakers'' (Macmillan, 1967):
``It must be that as soon as a culture has reached a certain level, probably measured largely by its literacy, cryptography appears spontaneously -- as its parents, language and writing, probably also did. The multiple human needs and desires that demand privacy among two or more people in the midst of social life must inevitably lead to cryptology wherever men thrive and wherever they write. Cultural diffusion seems a less likely explanation for its occurrence in so many areas, many of them distant and isolated.'' [p. 84]
The invention of cryptography is not limited to either civilians or the government. Wherever the need for secrecy is felt, the invention occurs. However, over time the quality of the best available system continues to improve and those best systems were often invented by civilians. Again, from David Kahn:
``It was the amateurs of cryptology who created the species. The professionals, who almost certainly surpassed them in cryptanalytic expertise, concentrated on down-to-earth problems of the systems that were then in use but are now outdated. The amateurs, unfettered to those realities, soared into the empyrean of theory.'' [pp. 125-6]
In the table to follow, each description starts with (date; civ or govt; source). Sources are identified in full at the end. [Thanks to Ben Brockert of Mediapolis Iowa for making this into a table.]
|Date||C or G||Source||Info|
|about 1900 BC||civ||Kahn p.71||An Egyptian scribe used non-standard hieroglyphs in an inscription. Kahn lists this as the first documented example of written cryptography.|
|1500 BC||civ||Kahn p.75||A Mesopotamian tablet contains an enciphered formula for the making of glazes for pottery.|
|500-600 BC||civ||Kahn p.77||Hebrew scribes writing down the book of Jeremiah used a reversed-alphabet simple substitution cipher known as ATBASH. (Jeremiah started dictating to Baruch in 605 BC but the chapters containing these bits of cipher are attributed to a source labeled ``C'' (believed not to be Baruch) which could be an editor writing after the Babylonian exile in 587 BC, someone contemporaneous with Baruch or even Jeremiah himself.) ATBASH was one of a few Hebrew ciphers of the time.|
|487 BC||govt||Kahn p.82||The Greeks used a device called the ``skytale'' -- a staff around which a long, thin strip of leather was wrapped and written on. The leather was taken off and worn as a belt. Presumably, the recipient would have a matching staff and the encrypting staff would be left home.
[Note: an article in the July 1998 issue of Cryptologia entitled ``The Myth of the Skytale'' makes the case that the cryptographic use of the skytale was a myth.]
|50-60 BC||govt||Kahn p.83||Julius Caesar (100-44 BC) used a simple substitution with the normal alphabet (just shifting the letters a fixed amount) in government communciations. This cipher was less strong than ATBASH, by a small amount, but in a day when few people read in the first place, it was good enough. He also used tansliteration of Latin into Greek letters and a number of other simple ciphers.|
|0-400?||civ||Burton||The Kama Sutra of Vatsayana lists cryptography as the 44th and 45th of 64 arts (yogas) men and women should know and practice. The date of this work is unclear but is believed to be between the first and fourth centuries, AD. [Another expert, John W. Spellman, will commit only to the range between the 4th century BC and the 5th century AD.] Vatsayana says that his Kama Sutra is a compilation of much earlier works, making the dating of the cryptography references even more uncertain.
Part I, Chapter III lists the 64 arts and opens with: ``Man should study the Kama Sutra and the arts and sciences subordinate thereto [....] Even young maids should study this Kama Sutra, along with its arts and sciences, before marriage, and after it they should continue to do so with the consent of their husbands.'' These arts are clearly not the province of a government or even of academics, but rather are practices of laymen.
In this list of arts, the 44th and 45th read:
|200's||civ||Kahn p.91||``The so-called Leiden papyrus [...] employs cipher to conceal the crucial portions of important [magic] recipes''.|
|725-790?||govt/(civ)||Kahn p.97||Abu `Abd al-Rahman al-Khalil ibn Ahmad ibn `Amr ibn Tammam al Farahidi al-Zadi al Yahmadi wrote a (now lost) book on cryptography, inspired by his solution of a cryptogram in Greek for the Byzantine emperor. His solution was based on known (correctly guessed) plaintext at the message start -- a standard cryptanalytic method, used even in WW-II against Enigma messages.|
|855||civ||Kahn p.93||Abu Bakr Ahmad ben `Ali ben Wahshiyya an-Nabati published several cipher alphabets which were traditionally used for magic.|
|---||govt||Kahn p.94||``A few documents with ciphertext survive from the Ghaznavid government of conquered Persia, and one chronicler reports that high officials were supplied with a personal cipher before setting out for new posts. But the general lack of continuity of Islamic states and the consequent failure to develop a permanent civil service and to set up permanent embassies in other countries militated against cryptography's more widespread use.''|
|1226||govt||Kahn p.106||``As early as 1226, a faint political cryptography appeared in the archives of Venice, where dots or crosses replaced the vowels in a few scattered words.''|
|about 1250||civ||Kahn p.90||Roger Bacon not only described several ciphers but wrote: ``A man is crazy who writes a secret in any other way than one which will conceal it from the vulgar.''|
|1379||govt/civ||Kahn p.107||Gabrieli di Lavinde at the request of Clement VII, compiled a combination substitution alphabet and small code -- the first example of the nomenclator Kahn has found. This class of code/cipher was to remain in general use among diplomats and some civilians for the next 450 years, in spite of the fact that there were stronger ciphers being invented in the meantime, possibly because of its relative convenience.|
|1300's||govt||Kahn p.94||`Abd al-Rahman Ibn Khaldun wrote "The Muqaddimah", a substantial survey of history which cites the use of ``names of perfumes, fruits, birds, or flowers to indicate the letters, or [...] of forms different from the accepted forms of the letters'' as a cipher among tax and army bureaus. He also includes a reference to cryptanalysis, noting ``Well-known writings on the subject are in the possession of the people.'' [p.97]|
|1392||civ||Price p.182-7||"The Equatorie of the Planetis", possibly written by Geoffrey Chaucer, contains passages in cipher. The cipher is a simple substitution with a cipher alphabet consisting of letters, digits and symbols.|
|1412||civ||Kahn p.95-6||Shihab al-Din abu `l-`Abbas Ahmad ben `Ali ben Ahmad `Abd Allah al-Qalqashandi wrote "Subh al-a `sha", a 14-volume Arabic encyclopedia 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 cryptology 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.|
|1466-7||civ||Kahn p.127||Leon Battista Alberti (a friend of Leonardo Dato, a potifical secretary who might have instructed Alberti in the state of the art in cryptology) invented and published the first polyalphabetic cipher, designing a cipher disk (known to us as the Captain Midnight Decoder Badge) to simplify the process. This class of cipher was apparently not broken until the 1800's. Alberti also wrote extensively on the state of the art in ciphers, besides his own invention. Alberti also used his disk for enciphered code. These systems were much stronger than the nomenclator in use by the diplomats of the day and for centuries to come.|
|1473-1490||civ||Kahn p.91||``A manuscript [...] by Arnaldus de Bruxella uses five lines of cipher to conceal the crucial part of the operation of making a philosopher's stone.''|
|1518||civ||Kahn p.130-6||Johannes Trithemius wrote the first printed book on cryptology. He invented a steganographic cipher in which each letter was represented as a word taken from a succession of columns. The resulting series of words would be a legitimate prayer. He also described polyalphabetic ciphers in the now-standard form of rectangular substitution tables. He introduced the notion of changing alphabets with each letter.|
|1553||civ||Kahn p.137||Giovan Batista Belaso introduced the notion of using a passphrase as the key for a repeated polyalphabetic cipher. (This is the standard polyalphabetic cipher operation mis-named ``Vigenère'' by most writers to this day.)|
|1563||civ||Kahn p.138||Giovanni Battista Porta wrote a text on ciphers, introducing the digraphic cipher. He classified ciphers as transposition, substitution and symbol substitution (use of a strange alphabet). He suggested use of synonyms and misspellings to confuse the cryptanalyst. He apparently introduced the notion of a mixed alphabet in a polyalphabetic tableau.|
|1564||civ||Kahn p.144(footnote)||Bellaso published an autokey cipher improving on the work of Cardano who appears to have invented the idea.|
|1585||civ||Kahn p.146||Blaise de Vigenère wrote a book on ciphers, including the first authentic plaintext and ciphertext autokey systems (in which previous plaintext or ciphertext letters are used for the current letter's key). [Kahn p.147: both of these were forgotten and re-invented late in the 19th century.] [The autokey idea survives today in the DES CBC and CFB modes.]|
|1623||civ||Bacon||Sir Francis Bacon described a cipher which now bears his name -- a biliteral cipher, known today as a 5-bit binary encoding. He advanced it as a steganographic device -- by using variation in type face to carry each bit of the encoding.|
|1790's||civ/govt||Kahn p.192, Cryptologia v.5 No.4 pp.193-208||Thomas Jefferson, possibly aided by Dr. Robert Patterson (a mathematician at U. Penn.), invented his wheel cipher. This was re-invented in several forms later and used in WW-II by the US Navy as the Strip Cipher, M-138-A.|
|1817||govt||Kahn p.195||Colonel Decius Wadsworth produced a geared cipher disk with a different number of letters in the plain and cipher alphabets -- resulting in a progressive cipher in which alphabets are used irregularly, depending on the plaintext used.|
|1854||civ||Kahn p.198||Charles Wheatstone invented what has become known as the Playfair cipher, having been publicized by his friend Lyon Playfair. This cipher uses a keyed array of letters to make a digraphic cipher which is easy to use in the field. He also re-invented the Wadsworth device and is known for that one.|
|1857||civ||Kahn p.202||Admiral Sir Francis Beaufort's cipher (a variant of what's called ``Vigenère'') was published by his brother, after the admiral's death in the form of a 4x5 inch card.|
|1859||civ||Kahn p.203||Pliny Earle Chase published the first description of a fractionating (tomographic) cipher.|
|1854||civ||Cryptologia v.5 No.4 pp.193-208||Charles Babbage seems to have re-invented the wheel cipher.|
``A study of United States patents from the issuance of the first cryptographic patent in 1861 through 1980 identified 1,769 patents which are primarily related to cryptography.'' [p.1]
|1861||civ/(govt)||Kahn p.207||Friedrich W. Kasiski published a book giving the first general solution of a polyalphabetic cipher with repeating passphrase, thus marking the end of several hundred years of strength for the polyalphabetic cipher.|
|1861-5||govt||Kahn p.215||During the Civil War, possibly among other ciphers, the Union used substitution of select words followed by word columnar-transposition while the Confederacy used Vigenère (the solution of which had just been published by Kasiski).|
|1891||govt/(civ)||Cryptologia v.5 No.4 pp.193-208||Major Etienne Bazeries did his version of the wheel cipher and published the design in 1901 after the French Army rejected it. [Even though he was a military cryptologist, the fact that he published it leads me to rate this as (civ) as well as govt.]|
|1913||govt||Cryptologia v.5 No.4 pp.193-208||Captain Parket Hitt reinvented the wheel cipher, in strip form, leading to the M-138-A of WW-II.|
|1916||govt||Cryptologia v.5 No.4 pp.193-208||Major Joseph O. Mauborgne put Hitt's strip cipher back in wheel form, strengthened the alphabet construction and produced what led to the M-94 cipher device.|
|1917||civ||Kahn p.371||William Frederick Friedman, later to be honored as the father of US cryptanalysis (and the man who coined that term), was employed as a civilian cryptanalyst (along with his wife Elizebeth) at Riverbank Laboratories and performed cryptanalysis for the US Government, which had no cryptanalytic expertise of its own. WFF went on to start a school for military cryptanalysts at Riverbank -- later taking that work to Washington and leaving Riverbank.|
|1917||civ||Kahn p.401||Gilbert S. Vernam, working for AT&T, invented a practical polyalphabetic cipher machine capable of using a key which is totally random and never repeats -- a one-time-tape. This is the only provably secure cipher, as far as we know. This machine was offered to the Government for use in WW-I but it was rejected. It was put on the commercial market in 1920.|
|1918||govt||Kahn p.340-5||The ADFGVX system was put into service by the Germans near the end of WW-I. This was a cipher which performed a substitution (through a keyed array), fractionation and then transposition of the letter fractions. It was broken by the French cryptanalyst, Lieutenant Georges Painvin.|
|1919||civ||Kahn p.420||Hugo Alexander Koch filed a patent in the Netherlands on a rotor based cipher machine. He assigned these patent rights in 1927 to Arthur Scherbius who invented and had been marketing the Enigma machine since about 1923.|
|1919||civ||Kahn p.422||Arvid Gerhard Damm applied for a patent in Sweden for a mechanical rotor cipher machine. This machine grew into a family of cipher machines under the direction of Boris Caesar Wilhelm Hagelin who took over the business and was the only one of the commercial cryptographers of this period to make a thriving business. After the war, a Swedish law which enabled the government to appropriate inventions it felt important to defense caused Hagelin to move the company to Zug Switzerland where it was incorporated as Crypto AG. The company is still in operation, although facing controversy for having allegedly weakened a cipher product for sale to Iran.|
|1921||civ||Kahn p.415||Edward Hugh Hebern incorporated ``Hebern Electric Code'', a company making electro-mechanical cipher machines based on rotors which turn, odometer style, with each character enciphered.|
|1923||civ||Kahn p.421||Arthur Scherbius incorporated ``Chiffriermaschinen Aktiengesellschaft'' to make and sell his Enigma machine.|
|1924||civ||Deavours p.151||Alexander von Kryha produced his ``coding machine'' which was used, even by the German Diplomatic Corps, into the 1950s. However, it was cryptographically weak -- having a small period. A test cryptogram of 1135 characters was solved by the US cryptanalysts Friedman, Kullback, Rowlett and Sinkov in 2 hours and 41 minutes. Nevertheless, the machine continued to be sold and used -- a triumph of salesmanship and a lesson to consumers of cryptographic devices.|
|1927-33||civ||Kahn p.802ff||Users of cryptography weren't limited to legitimate bankers, lovers, experimenters, etc. There were also a handful of criminals. ``The greatest era of international smuggling -- Prohibition -- created the greatest era of criminal cryptology.'' [p.817] To this day, the FBI runs a cryptanalytic office to deal with criminal cryptography. [As of Kahn's writing in 1967, that office was located at 215 Pennsylvania Avenue SE, Washington DC.]
``A retired lieutenant commander of the Royal Navy devised the systems for Consolidated Exporters' Pacific operation, though its Gulf and Atlantic groups made up their own as needed.
|1929||civ||Kahn p.404||Lester S. Hill published ``Cryptography in an Algebraic Alphabet'' in which a block of plaintext is enciphered by a matrix operation.|
|1933-45||govt||Kahn p.422 (and many others)||The Enigma machine was not a commercial success but it was taken over and improved upon to become the cryptographic workhorse of Nazi Germany. [It was broken by the Polish mathematician, Marian Rejewski, based only on captured ciphertext and one list of three months worth of daily keys obtained through a spy. Continued breaks were based on developments during the war by Alan Turing, Gordon Welchman and others at Bletchley Park in England.]|
|1937||govt||Kahn p.18ff.||The Japanese Purple machine was invented in response to revelations by Herbert O. Yardley and broken by a team headed by William Frederick Friedman. The Purple machine used telephone stepping relays instead of rotors and thus had a totally different permutation at each step rather than the related permutations of one rotor in different positions.|
|1930's||govt||Kahn p.510ff., Deavours p.10,89-91||Kahn attributes the American SIGABA (M-134-C) to William F. Friedman while Deavours attributes it to an idea of Frank Rowlett, one of Friedman's first hires. It improved on the rotor inventions of Hebern and Scherbius by using pseudo-random stepping of multiple rotors on each enciphering step rather than have uniform, odometer-like stepping of rotors as in Enigma. It also used 15 rotors (10 for character transformation, 5 probably for controlling stepping) rather than the Enigma's 3 or 4.|
|1930's||govt||Deavours p.144||The British TYPEX machine was an offshoot of the commercial Enigma purchased by the British for study in the 1920's. It was a 5-rotor machine with the two initial rotors being stators, serving the purpose of the German Enigma's plugboard.|
|1970||civ||Feistel||Dr. Horst Feistel led a research project at the IBM Watson Research Lab in the 1960's which developed the Lucifer cipher. This later inspired the US DES (below) and other product ciphers, creating a family labeled ``Feistel ciphers''.|
|1976||civ/govt||FIPS PUB-46||A design by IBM, based on the Lucifer cipher and with changes (including both S-box improvements and reduction of key size) by the US NSA, was chosen to be the U.S. Data Encryption Standard. It has since found worldwide acceptance, largely because it has shown itself strong against 20 years of attacks. Even some who believe it is past its useful life use it as a component -- e.g., of 3-key triple-DES.|
|1976||civ||Diffie||Whitfield Diffie and Martin Hellman published ``New Directions in Cryptography'', introducing the idea of public key cryptography. They also put forth the idea of authentication by powers of a one way function, now used in the S/Key challenge/response utility. They closed their paper with an observation for which this timeline web page gives detailed evidence: ``Skill in production cryptanalysis has always been heavily on the side of the professionals, but innovation, particularly in the design of new types of cryptographic systems, has come primarily from amateurs.''|
|April 1977||civ||Shamir||Inspired by the Diffie-Hellman paper and acting as complete novices in cryptography, Ronald L. Rivest, Adi Shamir and Leonard M. Adleman had been discussing how to make a practical public key system. One night in April, Ron Rivest was laid up with a massive headache and the RSA algorithm came to him. He wrote it up for Shamir and Adleman and sent it to them the next morning. It was a practical public-key cipher for both confidentiality and digital signatures, based on the difficulty of factoring large numbers. They submitted this to Martin Gardner on April 4 for publication in Scientific American. It appeared in the September, 1977 issue. The Scientific American article included an offer to send the full technical report to anyone submitting a self-addressed, stamped envelope. There were thousands of such requests, from all over the world.
Someone at NSA objected to the distribution of this report to foreign nationals and for a while, RS&A suspended mailings -- but when NSA failed to respond to inquiries asking for the legal basis of their request, RS&A resumed mailings. Adi Shamir believes this is the origin of the current policy [as of August 1995] that technical reports or papers can be freely distributed. [Note: two international journals, ``Cryptologia'' and ``The Journal of Cryptology'' were founded shortly after this attempt by NSA to restrain publication.]
Contrary to rumor, RS&A apparently had no knowledge of ITAR or patent secrecy orders. They did not publish before applying for international patents because they wanted to avoid such restraints on free expression but rather because they were not thinking about patents for the algorithm. They just wanted to get the idea out.
|1978||civ||RSA||The RSA algorithm was published in the Communications of the ACM.|
|1982 or earlier||civ||ROT13||The rot13 cipher was introduced into USENET News software to permit the encryption of postings in order to prevent innocent eyes from being assaulted by objectionable text. This is the first example I know of in which a cipher with a key everyone knows actually was effective for something. Here is an early reference to it. [Thanks for Arthur Bernard Byrne for that reference.]|
|1990||civ||IACR90||Xuejia Lai and James Massey in Switzerland published ``A Proposal for a New Block Encryption Standard'', a proposed International Data Encryption Algorithm (IDEA) -- to replace DES. IDEA uses a 128-bit key and employs operations which are convenient for general purpose computers, therefore making software implementations more efficient.|
|1990||civ||IACR90||Charles H. Bennett, Gilles Brassard et al. published their experimental results on Quantum Cryptography, which uses single photons to communicate a stream of key bits for some later Vernam encipherment of a message (or other uses). Assuming the laws of quantum mechanics hold, Quantum Cryptography provides not only secrecy but a positive indication of eavesdropping and a measurement of the maximum number of bits an eavesdropper might have captured. On the downside, QC currently requires a fiber-optic cable between the two parties.|
|1991||civ||Garfinkel||Phil Zimmermann released his first version of PGP (Pretty Good Privacy) in response to the threat by the FBI to demand access to the cleartext of the communications of citizens. PGP offered high security to the general citizen and as such could have been seen as a competitor to commercial products like Mailsafe from RSADSI. However, PGP is especially notable because it was released as freeware and has become a worldwide standard as a result while its competitors of the time remain effectively unknown.|
|1994||civ||Rivest||Professor Ron Rivest, author of the earlier RC2 and RC4 algorithms included in RSADSI's BSAFE cryptographic library, published a proposed algorithm, RC5, on the Internet. This algorithm uses data-dependent rotation as its non-linear operation and is parameterized so that the user can vary the block size, number of rounds and key length. It is still too new to have been analyzed enough to enable one to know what parameters to use for a desired strength -- although an analysis by RSA Labs, reported at CRYPTO'95, suggests that w=32, r=12 gives strength superior to DES. It should be remembered, however, that this is just a first analysis.|
- Bacon: Sir Francis Bacon, ``De Augmentis Scientarum'', Book 6, Chapter i. [as quoted in C. Stopes, ``Bacon-Shakspere Question'', 1889]
- Burton: Sir Richard F. Burton trans., ``The Kama Sutra of Vatsayana'', Arkana/Penguin, 1991.
- Deavours: Cipher A. Deavours and Louis Kruh, ``Machine Cryptography and Modern Cryptanalysis'', Artech House, 1985.
- Diffie: Whitfield Diffie and Martin Hellman, ``New Directions in Cryptography'', IEEE Transactions on Information Theory, Nov 1976.
- Feistel: Horst Feistel, ``Cryptographic Coding for Data-Bank Privacy'', IBM Research Report RC2827.
- Garfinkel: Simson Garfinkel, ``PGP: Pretty Good Privacy'', O'Reilly & Associates, Inc., 1995.
- IACR90: Proceedings, EUROCRYPT '90; Springer Verlag.
- Kahn: David Kahn, ``The Codebreakers'', Macmillan, 1967.
- Price: Derek J. Price, ``The Equatorie of the Planetis'', edited from Peterhouse MS 75.I, Cambridge University Press, 1955.
- Rivest: Ronald L. Rivest, ``The RC5 Encryption Algorithm'', document made available by FTP and World Wide Web, 1994.
- ROT13: Steve Bellovin and Marcus Ranum, individual personal communications, July 1995.
- RSA: Rivest, Shamir and Adleman, ``A method for obtaining digital signatures and public key cryptosystems'', Communications of the ACM, Feb. 1978, pp. 120-126.
- Shamir: Adi Shamir, ``Myths and Realities'', invited talk at CRYPTO '95, Santa Barbara, CA; August 1995.
Public key cryptography – the breakthrough that revolutionized email and ecommerce – was first discovered by American geeks. Right? Wrong.
The story of the invention of public key cryptography is a cypherpunk sacred text: In 1976, an iconoclastic young hacker named Whitfield Diffie hooked up with Stanford professor Martin Hellman, and together they devised what experts hailed as the most important development in crypto since the invention of polyalphabetic ciphers during the Renaissance. The duo produced a system that allowed an unlimited number of people to communicate with total privacy.
A year later, three MIT mathematicians implemented the Diffie-Hellman theory, developing the landmark RSA algorithm, the mathematical formula that made public key feasible. Published in a landmark MIT paper and hailed by Scientific American, these capabilities would turn out to be a vital step in making network communications secure, and became a bulwark for personal privacy as the Internet grew.
Like a lot of mythic accounts, this one turns out to be well off the mark. The problem lies not in its veracity, but in what the story leaves out. In fact, the situation is a little like a Hollywood remake of a foreign cult film. In this case, though, no one knew the earlier version existed – that the plot had been changed and characters replaced – because it was never released and the negatives were buried. The truth has emerged only because the surviving stars recently got permission from their "studio" to talk.
So roll back the time frame to a few years before the Diffie-Hellman/RSA saga. Change the setting from MIT and Stanford, places where you can nearly get sunburned from the heat of new ideas, to a cloistered British intelligence agency in the sleepy Cotswolds city of Cheltenham, about 100 miles from London. Instead of the famil- iar cast – a dashing hacker, his academic collaborator, a tight-knit team of mathematics researchers – imagine three nearly anonymous British civil servants laboring in the kind of obscurity possible only in the intelligence community's shadow world.
One of the three – an engineer, not a mathematician – has been given what looks like a sidetrack assignment to solve a problem no one thinks can be solved. Mulling it over while in his pajamas one night, he has a startling insight, but he's not sure his math skills are strong enough to unravel its implications. Enter two Cambridge University math grads who have quit advanced-degree programs and come to work in the world of spooks because – well, because they need a job. Friendly rivals since they were schoolboys, they're fellow lodgers who, ruminating in their off hours, separately happen upon algorithms that would make the engineer's idea fly (the same algorithms published to astonishment and acclaim by the Americans a few years later). Then, after their agency tries and fails to knock down their work, it decides to sit on the findings and stay on the sidelines – even when the American discovery of public key touches off a cryptographic and commercial revolution.
During the late '60s, intelligence agencies were giving much thought to the fast-breaking developments in computers and wireless technologies, and to ways to protect government data that traveled over these channels. While encryption hardware was evolving, one crucial part of the process hadn't changed since World War I: the need to distribute and use digital keys to scramble and unscramble messages. The process was a bottleneck. To ensure security, a unique key had to be generated for every pair of people who needed to conduct secret conversations; then those keys had to be delivered securely. Thousands of people were in the classified loop, and that meant generating millions of keys that needed to be protected. Managing the system was, to put it in a very un-British way, a bitch.
At the UK's Government Communications Headquarters – a government spy bureau that is the rough equivalent of the US National Security Agency – senior scientist James Ellis was working on the problem. Ellis, an orphan who had been raised by his grandparents in London's East End, had joined the GCHQ in the '50s, then left for a time to work (presumably on security issues) at the post office. By 1969, in his 40s, Ellis was back at the GCHQ and, as part of its Communications-Electronics Security Group, was hunting for a way past the seemingly intractable conundrum of key management. It is difficult to peer into the office politics of his world, and doubly so at a distance of 30 years. Still, it's clear that this assignment placed him neither at the white-hot center of international intrigue nor at the forefront of research. "I think he was sort of sidetracked," a colleague says.
Ellis had his doubts about finding a solution to the problem. "It was obvious to everyone, including me," he later wrote, "that no secure communication was possible without a secret key, some other secret knowledge, or at least some way in which the recipient was in a different position from an interceptor. After all, if they were in identical situations, how could one possibly be able to receive what the other could not? Thus there was no incentive to look for something so clearly impossible."
But then Ellis came across a paper buried in the GCHQ's mountain of secret material. Written by an anonymous author, it described a project conceived by Bell Telephone toward the end of World War II. The scheme, labeled Project C43, was an ingenious method of analog voice scrambling that worked by the use of distortion.
To conceptualize it, imagine you want to send a message over the phone line and you suspect someone is listening. How can you keep the message secure? The Bell scientist suggested that the person receiving the message simply add noise to the line. When the message arrives, message and noise are intermingled and eavesdroppers will hear only garbage. The recipient, knowing precisely how the noise was added, can subtract it from the transmission and wind up with the original, unscrambled message.
For modern cryptography, Project C43 was useless. For one thing, it was an analog model, and by the late '60s the world was going digital. But Ellis found it exciting nevertheless: The sender of a message didn't have to worry about an enemy listening in, even if the foe knew how the system worked. What made this possible was that, in contrast to conventional cryptography, the recipient is a collaborator in the encryption. "Secure communication," Ellis wrote, "was, at least, theoretically possible if the recipient took part in the encipherment."
That raised a tantalizing question for Ellis: Could a secure, digitally encrypted message be sent without keys being exchanged in advance? This heretical idea popped into his head one night after he had gone to bed. Sitting in the dark in his Cheltenham bedroom, he decided it could, and he came up with an existence proof for the question. His name for it would embody the contradiction: nonsecret encryption.
It worked by taking the digitized, nonsecret exchange between two parties – call them Alice and Bob – and submitting it to a series of three mathematical alterations. Let's say, for instance, that Bob wants to send a message to Alice. The problem is Eve, an unwelcome snoop who is familiar with the way this particular scrambling system works, down to the mathematical formulas themselves – since these rules are, in this scenario, public knowledge.
Alice gets the ball rolling by generating a large number chosen at random. This, in effect, is a secret key that only she holds. Now comes a crucial act suggested to Ellis by Project C43: Alice, who is the intended recipient, actually initiates the scrambling process by executing a mathematical operation to transform the key to a new number. She sends the new number to Bob.
The new number is analogous to what we know as a public key. Since an important property of the mathematical operation Alice uses is that it cannot be calculated in reverse, even by an outside observer who has this second, nonsecret number, and also knows what function produced it, cannot do an inverse calculation to retrieve the first, secret number. This is something that will remain known only to the recipient, Alice.
Now that Bob has this nonsecret number, he uses a second operation to scramble the private message he has for Alice, which he then sends. With a third mathematical function, Alice uses her original, secret key to essentially strip the encryption from the message. She can now read the plain text, and Eve can do nothing but gnash her teeth as she watches a very public exchange of what, to her, will remain gibberish.
The nonsecret key acts like the line noise in Project C43. Since such keys wouldn't have to be protected, it would be possible to have secure communications without all the prior arrangements necessary in conventional crypto, opening the way for protected communications on a vast scale.
Ellis hadn't been assigned to unleash a revolution in cryptography, but the possibility that he had done so had to be dealt with. The very basis of the idea – its "nonsecret" element – seemed so heretical that, to some at the GCHQ, disproving his thesis would be striking a blow for the natural order of things. In July 1969, a draft of Ellis's paper – which, naturally, was classified – was sent to the GCHQ's chief mathematician, Shaun Wylie. Just before Christmas, he delivered his judgment: "Unfortunately, I can't see anything wrong with this."
However, the mathematician noted, Ellis had presented only a proof that such a system could exist. The unknown remained: Was there really a way of generating a nonsecret key from the original private key?
To make it work, you needed to be certain that the Eves of the world could not reverse the first mathematical process and get their hands on the key. Ellis had conjectured a set of lookup tables that would perform the various scrambling and descrambling calculations but had not developed the specific functions. Until they were formulated, nonsecret encryption would be nothing more than a theoretical curiosity. Ellis did not hide this state of affairs when he formally wrote up his idea in a January 1970 internal paper called "The Possibility of Secure Non-Secret Digital Encryption."
"It is necessary to distinguish carefully between fact and opinion, i.e., between that which has actually been proved and that which seems likely," he wrote. "It is particularly difficult to do this in this case because we have established something which, to most people, seems inherently impossible."
The remaining step in the creation of a secure, nonsecret key was not trivial. Even as he set about the search for the nonreversible functions that would make his scheme work, Ellis, an engineer by training, was concerned that his mathematics skills were not up to the task. And despite the possible importance of a nonsecret system, the GCHQ did not assign much brainpower to aid him in the quest. At times over the next few years, some Communications-Electronics Security Group cryptographers would read Ellis's paper and work for a while on potential solutions, and in 1971 a new chief scientist took an interest and assigned some people to the problem. But while those looking for the mystery functions developed ideas about what the characteristics of such things might be, they had no luck in actually finding one that worked.
Then Clifford Cocks came along.
In 1973, Cocks was a recent arrival in the electronics-security group. He had come to intelligence work from Kings College, Cambridge, where he earned an undergraduate degree in math, and Oxford, where he did graduate work in number theory before deciding to move on. Although Cocks didn't know much about the GCHQ and really hadn't thought about cryptography as a focus of his work, he knew the agency needed mathematicians. Also, a childhood friend, Malcolm Williamson, was already there. In September of that year, at age 22, Cocks went to work in Cheltenham.
When people arrived at the GCHQ, they were assigned a mentor "to teach you the ropes and tell you what you needed to know," Cocks recalled in a recent lecture. His was Nick Patterson, another Cambridge alumnus. One day at teatime, about two months after Cocks's arrival, Patterson mentioned Ellis's idea to his protégé.
"Nick explained it to me very mathematically, in terms of wanting a nonreversible function, with a property where you could encrypt and decrypt with the input of this function," Cocks said during his lecture, adding that not reading Ellis's paper before the conversation was an advantage. That allowed him to consider the problem without preconceptions. Since he had done his research the previous year in number theory – working with large primes and multiplication – it made sense to him to use that knowledge. "I suppose it was actually also helpful that I wasn't doing anything that evening," Cocks added blithely.
After work he walked back to the modest house he rented in Cheltenham with Williamson, ate dinner, and sat down to think. Because of the secrecy imposed by the GCHQ, he had certain limitations: He could not bring anything home from his office, and if he pondered a work-related problem "in digs," he was not permitted to write anything down. The only medium he had was his brain. "Happily," he said, "the first idea seemed to work just fine."
His idea was more than fine – it was elegant. "If you wanted a function that couldn't be inverted," he now says, "it seemed very natural to me to think of the concept of multiplying quite large prime numbers together."
Cocks is pointing to a basic mathematical truth: The product of two large prime numbers is extremely difficult to factor – that is, to reverse to obtain the original primes. He figured that the secret key in his implementation would be two huge primes, generated by a message recipient. The primes would be multiplied, and the product would be the nonsecret key, the number given openly to a sender (who could, if need be, also get the number from a public directory). Cocks then figured out a simple mathematical formula that would allow the sender to encrypt a message in such a way that it could be decrypted only by someone who knows the original primes. "This is very interesting," Cocks remembers thinking. After mapping it out in his head, he went to sleep. "I went back to work the next morning and wrote it down," he recalls.
Cocks, in one evening, had achieved a breakthrough that several years later would be repeated – in the form of the revolutionary RSA algorithm – after months of intensive trial and error by MIT researchers Ron Rivest, Adi Shamir, and Len Adleman.
Word got around the electronics-security group that someone had found a way to implement James Ellis's idea. Cocks mentioned to his friend Malcolm Williamson that he had an internal paper coming out. This was a one-up move; it was unusual for a recruit to circulate a paper so soon. Cocks's announcement got Williamson's attention; he listened closely as Cocks explained the problem and his solution.
Williamson had known Cocks since they were both 12 – they had attended the same grammar school in Manchester, and they had both gone to Cambridge. Williamson had done graduate work at Liverpool University, then one day saw an ad, posted by the GCHQ, calling for mathematicians. Without knowing much about the agency, he had applied – and soon found himself working on cryptographic problems.
Williamson had not heard of the Ellis problem before, but it struck him as rather unreasonable. How could you do cryptography when you passed the key in the open? So he set about to shoot down the concept, but he couldn't. "I didn't manage to prove that there were any flaws in what he had," he recalls.
But in the process, Williamson began considering ways that two collaborating parties could pass numbers back and forth to build a shared key that would be secure even if an eavesdropper was monitoring every bit of the exchange. It was very late when he got it – 8 or 12 hours after he sat down to think. His scheme involved a complex set of exchanges in which each party picks a random number, performs a calculation on it by a difficult-to-reverse formula, and arrives at a shared key.
It's indicative of the project's relative unimportance at the GCHQ that Williamson didn't write up his work for a couple of months. Not long after he did, and after some conversations with Ellis, he came up with an idea that streamlined his concept. It was precisely the same formulation for what would later be known as the Diffie-Hellman algorithm. As far as Williamson is concerned, though, it was pretty much a consequence of his first paper, so obvious that he felt in no hurry to circulate it. "It really didn't feel like such a big step," he says.
Now the GCHQ had two means of implementing Ellis's heresy. But just as the agency had been suspicious of the initial idea, it moved ultracautiously with Cocks's and Williamson's schemes. Ironically, one factor weighing against accepting the solutions was their sheer straightforwardness. "There's a basic principle that neat and tidy problems have neat and tidy solutions and messy problems don't have neat and tidy solutions," says Williamson. "Most of cipher design is essentially messy; it's not neat and tidy and mathematical. So we're pretty comfortable that people are not going to be able to break those things, because even if you hack away at it, you're not going to suddenly find a little magic screw there that, if you unscrew it, everything falls to pieces. But in all this stuff with public key, there absolutely may be a magic screw. Some graduate-student mathematician could really cause a disaster."
So concerned was the GCHQ with this possibility that it not only looked at the schemes internally – finding no inherent flaws – but also took the unusual step in 1974 of going to a renowned outsider, Professor R. F. Churchhouse of the University of Wales, presenting him with the mathematical foundation of Cocks's idea, and asking whether it was secure. Churchhouse concluded that as long as no one figured out a fast way of factoring huge primes – something that no mathematician had ever come close to – the scheme was sound.
The agency ultimately determined that between the two methods, Williamson's was preferable because its functions were easier to work with than the huge numbers Cocks's scheme required. Even so, the system was judged to be impractical. "The machines that would be used were expensive and very slow," explains Cocks. "It took minutes to generate a key. We looked at the circumstances under which you would find it useful to have a machine that took that long to produce keys and immediately thought the applications were too limited to make it worth floating."
So the GCHQ's thinking had advanced from judging nonsecret encryption to be impossible to finding it overly cumbersome. Many people in the agency also remained concerned that such a radically new kind of cryptography might have weaknesses too subtle to detect, weaknesses that an enemy might use to crack the system.
Even Williamson believed that the whole venture was too risky. When he finally wrote up a revised version of his key scheme, he cited these reservations as the reason for the two-year delay. "I find myself in an embarrassing position," he wrote. "I have come to doubt the whole theory of nonsecret encryption. The trouble is that I have no proof that the method … is genuinely secure." He conceded he could not find anything wrong with the system, though, "and would be grateful if anyone else can." No one did. But by then the GCHQ had tacitly concluded it wasn't worth the effort to implement a public key crypto system.
In 1976, of course, Diffie and Hellman presented their findings in two papers, which were followed in 1977 by a famous paper about RSA publicized by Scientific American. These developments made a huge splash; the news even found its way into the popular press, and the public key discoverers were widely heralded. One can only imagine how weird this all must have been for Ellis, Cocks, and Williamson, who could never, outside the walls of the GCHQ, even hint at what they knew about nonsecret encryption.
Cocks says that when Ellis read Diffie and Hellman's first paper, which outlined the public key idea but suggested no implementation, he said simply, "They're where I was in 1969." The Stanford team's second paper did suggest a means of implementation – identical to the Williamson solution. Cocks had temporarily left the GCHQ for a stint at the Ministry of Defense and first learned of the Americans' work in Martin Gardiner's Scientific American column in mid-1977 – the one describing the RSA algorithm Cocks had first discovered three years earlier. He says, with some understatement, "I was surprised."
In 1977, the British cryptographers were upset to learn that both Stanford University and MIT were planning to patent, respectively, the Diffie-Hellman and RSA algorithms. "I tried to get them to block the US patent," Williamson says. "We could have done that, but in fact the people higher up didn't want to. Patents are complicated." Specifically, there was a question as to whether one could obtain a patent under British law for what was essentially a mathematical algorithm. "The advice we received was, 'Don't bother,'" says Cocks.
That stance apparently condemned the intelligence establishment – in the UK, at least – to the role of bystander during the cryptographic revolution Diffie and Hellman had sparked. The GCHQ and the NSA would eventually come to take public key seriously, but they no longer held their crypto monopoly. A new community of cryptographers, not bound by government constraints or prejudices, quickly began a process of furious innovation that would transform cryptography from a tool of secrecy to a technology of privacy.
Chief among the developments that grew out of public key cryptography was the ability to authenticate message senders with digital signatures. There followed ideas for digital cash, including a system that preserved a spender's anonymity, just as with actual money. There were schemes for "secret sharing," in which information is divided among several people in such a way that it can be recovered only by consent of a given percentage of the keyholders. There were digital-certificate systems that allowed identities to be verified online or through smartcards. There were systems for digital time-stamping, electronic receipts, and all sorts of ecommerce activities. As a result of these efforts, public key is now ubiquitous, on every copy of Netscape and Lotus Notes – and may one day wind up in everyone's wallet as smartcards.
It's easy to fault the intelligence community for not pursuing the development of nonsecret encryption, but from a national-security standpoint, its cautious approach was understandable. Using an untried technique to protect government secrets posed a risk. One of nonsecret crypto's inventors still makes this point. "The government has to be very cautious," says Williamson. "It's much more important to secure some of this stuff than, say, banking transactions or Internet communications, or what the next-model Ford is going to look like. If I were on the top of the pyramid then, would I have dared to implement it? What was the chance that somebody would find that magic screw that unlocks everything?"
In the final reckoning, nonsecret encryption was too much a departure from what was known. "You've got to remember," says Williamson, "this is the civil service. I mean, this is something new and different. 'Let's ignore it. Let's sweep it under the carpet.'"
A quarter of a century after they did their big work, the British trio insist that they didn't feel shortchanged when they saw others get all the credit for ideas they had come up with themselves. "Ellis got internal recognition," says Cocks, who himself is perfectly comfortable with his anonymity. "You accept that. Internal recognition is all you get."
Of the three, only Ellis took steps to bring his work to public attention. In 1987, he wrote a paper directed to outsiders outlining how he had hit on the idea of nonsecret encryption. For anyone thick enough to have missed his point, he closed the paper by noting it was "some time after the basic work had been done" that Diffie and Hellman made what he called the "rediscovery of the NSE techniques." But the GCHQ classified his account and kept it secret. Williamson suggests release of the true story was held up by one official. The material was all ready to go, he says, but could not be published "until a certain person retired."
Apparently, the "certain person" eventually left government service. In late 1997, the Communications-Electronics Security Group posted on its Web site Ellis's 1987 history along with the earlier papers he, Cocks, and Williamson had written. (The papers are available at www.cesg.gov.uk/about/nsecret.htm.) Some weeks earlier, on November 25, James Ellis had died.
In 1979, National Security Agency chief Bobby Inman publicly stated that, all the noise about Diffie-Hellman and RSA aside, the intelligence establishment had known about public key cryptography for some time. To Diffie, the suggestion that someone, somewhere had discovered public key before him had long been troublesome, and he tried to find out what Inman meant. In the early '80s, he finally pried two names out of an NSA source: Clifford Cocks and James Ellis of the GCHQ in Cheltenham. At the time, Diffie was employed by the research affiliate of Canada's Northern Telecom. Working through a couple of connected associates, he asked to meet with Cocks and Ellis. Only Ellis agreed.
They met in the fall of 1982 – more than six years since Ellis's discovery and almost a decade since Diffie had independently come up with the same idea. Ellis lived on a hill on Cheltenham's outskirts and had a beautiful view of the town. He raised bees in the backyard. The GCHQ senior scientist was in his late 50s – a tall man, going gray. After some small talk with Ellis and his wife, Diffie and his fellow cryptographer headed for a pub.
Diffie turned to Ellis as they pulled out of the driveway. "Tell me," he said, "how you invented nonsecret encryption."
"Who says I did?" Ellis asked.
Diffie said the name of his NSA source.
"Do you work for him?" asked Ellis. Diffie said he didn't. At the pub, as Diffie got tipsy, Ellis – a solid GCHQ man – talked about anything but the subject Diffie most wanted to discuss. Still, the meeting was the beginning of a long friendship between the Diffie and Ellis families. It was a relationship in which Diffie's wife, Mary Fischer, sensed something wistful in a man who never got credit for his truly revolutionary insight.
Thinking back to their first meeting, Diffie says that Ellis made a telling statement, one whose very obliqueness speaks volumes about the world he lived in as a spy.
The British spook said it on the way to the pub – a seemingly random confession that stood out in contrast to the polite evasions that were Ellis's standard form of reply. Public key cryptography? "You did a lot more with it than we did," he said. Then he said no more. The nonsecret secret would stay a secret for the rest of his life.
Infoseceye (Read the blog entries!)
Malicious code and malware.
Misconfigured access rights
Risks of portable devices
Advert of sorts
The Story of Alice and Bob
(Short extract from after-dinner speech by John Gordon at The Zurich Seminar April 1984) I go to lots of conferences on Coding Theory in which complicated protocols get discussed. You know the sort of thing:
"A communicates with someone who claims to be B. So to be sure, A tests that B knows a secret number K. So A sends to B a random number X. B then forms Y by encrypting X under key K and sends Y back to A." and so on.
Because this sort of thing is is quite hard to follow, a few years ago theorists stopped using the letters A and B to represent the main players, and started calling them Alice and Bob.
So now we say "Alice communicates with someone claiming to be Bob. So to be sure, Alice tests that Bob knows a secret number K. Alice sends to Bob a random number X. Bob then forms Y by encrypting X under key K and sends Y back to Alice."
It's supposed to make it easier to understand. Now there are hundreds and hundreds of papers written about Alice and Bob. Alice and Bob have been used to illustrate all sorts of protocols and bits of coding theory in scientific papers. Over the years Alice and Bob have tried to defraud insurance companies, they've exchanged secret messages over a tapped line, and the've played poker for high stakes by mail. Now if we put together all the little details from lots of papers - a snippet from here, a snippet from there - we get a facinating picture of their lives.
This may be the first time in the history of coding theory that a definitive biography of Alice and Bob has been given.
Take Bob. Bob is often selling securities to speculators so we can be pretty sure he's a stockbroker. But from his concern about eavesdropping he is probably into something subersive on the side too.
Take Alice. From the number of times Alice tries to buy stock from him we can say she is probably a speculator. And she's also worried that her husband doesn't get to find out about her financial dealings.
So Bob is a subversive stockbroker and Alice is a two-timing speculator. But Alice has a number of serious problems. She and Bob only get to talk by telephone or by email. And in the country where they live the phone service is very expensive. And Alice and Bob are cheapskates.
So the first thing Alice must do is MINIMISE THE COST OF THE PHONE CALL.
The telephone in their country is also pretty lousy. The interference is so bad that Alice and Bob can hardly hear each other. So the second thing Alice must do is to PROTECT HER MESSAGES AGAINST ERRORS in transmission. On top of that Alice and Bob have very powerful enemies. One of their enemies the is the Tax Authority. Another is the Secret Police.
These enemies have almost unlimited resources. They always listen in to telephone conversations between Alice and Bob. This is a pity since Bob and Alice are always plotting tax frauds and overthrowing the government.
So the third thing ALICE must do is PROTECT HER COMMUNICATIONS FROM EAVESDROPPING. And these enemies are very sneaky. One of their favourite tricks is to telephone Alice and pretend to be Bob. So the fourth thing Alice has to do is to BE SURE SHE IS COMMUNICATING WITH WHOM SHE THINKS SHE IS. Well, you think, so all Alice has to do is listen very carefully to be sure she recognises Bob's voice. But no. You see Alice has never met Bob. She has no idea what his voice sounds like.
All in all Alice has a whole bunch of problems. Oh yes, and there is one more thing I forgot so say - Alice doesn't trust Bob.
Now most people in Alice's position would give up. Not Alice.She has courage which can only be described as awesome. Against all odds, over a noisy telephone line, tapped by the tax authorities and the secret police, Alice will happily attempt, with someone she doesn't trust, whom she can't hear clearly, and who is probably someone else, to fiddle her tax return and to organise a cout d'etat, while at the same time minimising the cost of the phone call.
A coding theorist is someone who doesn't think Alice is crazy. (C) John Gordon 1984