A Short History of Public Key Cryptography

By Victoria de Quehen, Security Researcher, ISARA Corporation
Published on June 14, 2018 
While the ideal of public-key cryptography is to have a “set and forget" group of algorithms that will guarantee security forever, increasingly we are realizing this ideal is not viable. There is not one cryptographic algorithm with a fixed set of parameters that will last indefinitely. As computers become more powerful and new attacks are found on existing protocols, it is important to update our cryptography. This can involve increasing parameters on widely used algorithms. There have also been times when it involved switching to new cryptographic schemes entirely.
With the onset of large-scale quantum computing, we are currently at the start of the second major migration of public-key cryptography, part of the constantly evolving progression of cryptography.

Public Key Cryptography (1970s)

  • RSA and Diffie-Hellman, the first efficient algorithms in public-key cryptography, were invented.
  • These algorithms are simple to understand requiring only a basic understanding of number theory.

Elliptic Curve Cryptography (1985)

  • Koblitz and Miller introduced Elliptic Curve Cryptography (ECC).
  • Despite being more difficult to understand, ECC algorithms have the advantage of smaller key sizes, are faster and use less memory.

Shor's Algorithm (1994)

  • An algorithm by Peter Shor proved that if an adversary had a large-scale quantum computer, then they can break the currently standardized public-key cryptography.
  • RSA, Diffie-Hellman, as well as the elliptic curve algorithms including ECDSA and ECDH, are all vulnerable to a quantum attack using Shor's algorithm.

National Security Agency's (NSA) Suite B (2005)

  • The NSA introduced its set of Suite B algorithms which shifted public key cryptography towards ECC. This set included the Elliptic Curve Digital Signature Algorithm (ECDSA) and Elliptic Curve Diffie-Hellman (ECDH).
  • Following NSA's release of its Suite B cryptographic protocols, the largest migration of cryptography to date begins, replacing RSA and Diffie-Hellman by the more efficient ECC.

NSA Advises “Prepare for the Quantum Resistant Transition” (2015)

  • Advances in quantum computing turn Shor's algorithm into a near-future threat to modern cryptography causing the NSA to release the following statement: “Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, which has made it clear that elliptic curve cryptography is not the long-term solution many once hoped it would be. Thus, we have been obligated to update our strategy."
  • Unlike the migration to ECC, the transition to quantum-safe cryptography it is not simply a matter of efficiency, it’s a necessity.
  • The following statement by NSA gives an idea of the comparative importance of these two migrations: “for those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum-resistant algorithm transition."

European Technical Standards Institute (ETSI) Create New Industry Specification Group on Quantum-Safe Cryptography (2015)

  • The primary focus of the Industry Specification Group on Quantum-Safe Cryptography (ISG QSC) is the implementation issues, architecture, and other practical aspects of quantum-safe cryptographic services that will be encountered by industry. ISARA’s Chief Operating Officer, Mark Pecen, is the chairman of the group, and one of the founders.
  • The scope of this industry specification group includes analysis into the performance considerations, implementation capabilities, benchmarking, and practical architectural considerations for specific applications.
  • Therefore, the group focuses on questions and recommendations that include analysis of the consequences of deploying, for example, a certain primitive, key-exchange method, protocol, etc. for a specific purpose.
  • The ISG QSC became the Working Group for Quantum-Safe Cryptography (WG QSC) of ETSI Technical Committee Cyber in March 2017.

 NIST Begins Post-Quantum Cryptography Standardization Process (2017)

  • NIST has begun the process of standardizing new post-quantum, or quantum-safe, cryptographic algorithms. The call for Round 1 Submissions closed November 2017.
  • Most of the submissions fall into five major categories based on different branches of mathematics: lattice, isogeny, hash, code and multivariate-based. The promising algorithms in each branch are implemented in our ISARA Radiate™ Security Solution Suite cryptographic library.

The Imminent Quantum Threat

  • According to a report by NIST in 2016, “it is likely that a quantum computer capable of breaking 2000-bit RSA in a matter of hours could be built by 2030 for a budget of about a billion dollars."
  • This makes the migration to quantum-safe cryptography urgent, especially as history suggests that migration of cryptographic protocols is a lengthy process. In particular, the migration to ECC is still incomplete.
  • However, the threat is real today for large organizations and governments since highly confidential data can be harvested now and then decrypted when a large-scale quantum computer is built.
  • On an almost weekly basis, new developments in quantum computing are announced by tech giants such as Intel, IBM, Microsoft, and Google to name a few. Predictions regarding the timed arrival of a large-scale quantum computer capable of breaking public-key cryptography vary; estimates are in the range of around a decade, and include some within five years. A definitive date can’t be pinned down, but the question is no longer “if”, it's “when”, and forward-looking security leaders are taking notice and planning now.