Post-Quantum Cryptography : Fortifying Tomorrow’s Security Today
The Basics:
What is encryption? What does WhatsApp mean when they say your chats are “end-to-end encrypted”?
Encryption is a process that converts the original representation of the information, technically known as plaintext, into an alternative form known as ciphertext. Ideally, only authorised parties can decipher a ciphertext back to plaintext and access the original information.Encrypting data means that we scramble the original data to hide the meaning of the text, while still making it possible for the data to be unscrambled using a secret key.
When we’re encrypting a message, a plaintext refers to the unencrypted message and ciphertext to the encrypted message. A cipher is composed of two functions; encryption, that turns a plaintext into a ciphertext. Decryption turns the cipher text back into a plaintext.
In essence, when your data is encrypted, even if an unauthorised person or entity gains access to it, they will not be able to make sense of it.
The History and Evolution of Encryption:
Encrypting messages dates way back to when kings and rulers used encrypted messages to communicate securely with each other. Classical ciphers predate computers and therefore work on letters rather than on bits.
The Caesar Cipher
The Caesar cipher is so named because the Roman historian Suetonius reported that Julius Caesar used it. He invented a cipher that shifts characters by three places in the alphabet: A becomes D, B becomes E, etc. A simple and effective encoding method at that time.
The Caesar Cipher is easy to break: to decrypt a given ciphertext, simply shift the letters three positions back to retrieve the plaintext.In fact, in 2006, the Italian Police arrested a mafia boss after decrypting messages written on small scraps of paper that were encrypted using a variant of the Caesar Cipher: ABC was encrypted to 456 instead of DEF, for example.
The Vigenère Cipher
The Vigenère Cipher is similar to the Caesar Cipher, except that the letters aren’t shifted by three places but rather by values defined by a key, a collection of letters that represent numbers based on their position in the alphabet.For example if the key is DUH, letters in the plaintext are shifted using the values 3,20,7. So the word CRYPTO would encrypt to FLFSNV using DUH as the key.
World War II
If you have watched Benedict Cumberbatch’s — Imitation game, you would’ve witnessed the genius behind the victory of the Allies in World War II.
For those of you who haven’t watched that fantastic movie — Benedict played the role of British Cryptographer Alan Turing. German engineer Arthur Scherbius invented the Enigma machine for commercial use. It uses several rather than the one rotor used by Hebert’s device. Recognising its genius, the German military began to use it to send coded transmissions. In 1932, Polish cryptographer Marian Rejewski discovered how Enigma works. And in 1939, Poland shared this information with the French and British intelligence services, allowing cryptographers like Alan Turing to figure out how to crack the key, which changed daily. It proved crucial to the Allies’ victory in the World War II.
Newest and Safest (Yet) Encryption Schemes
Encryption methodologies have continued to advance in this way, culminating in the newest and safest (yet) — RSA and AES encryption schemes.Advanced Encryption Standard 256-bit encryption is the strongest and most robust encryption standard that is commercially available today. RSA is a public key encryption and the standard for encrypting information transmitted via the internet. RSA encryption is robust and reliable because it creates a massive bunch of gibberish that frustrates would-be hackers, causing them to expend a lot of time and energy to crack into systems.
Symmetric vs Asymmetric encryption
In the previous example with the classic Caesar’s cipher, the deal was simple: the key to encrypt and decrypt were the same- if for encryption we shifted the letters forward by 3, to decrypt it we’ll have to shift it back by 3. This is what is known as “symmetric encryption”.
So the encryption and decryption keys are different in asymmetric encryption? Picture it like a high-stakes game of cryptographic chess. It involves a pair of keys: one, the public key, acts as a sentry allowing anyone to lock up information securely; the other, the private key, held closely by the intended recipient, who possesses the power to unlock the encrypted data. It’s a digital pas de deux ensuring data security without the need to share secret keys.
How RSA works:
Most of the newest encryption schemes are fundamentally nothing but mathematical problems that computers take long time to solve.
RSA derives its security from the difficulty of factoring large integers that are the product of two large prime numbers. Multiplying these two numbers is easy, but determining the original prime numbers from the product — or factoring — is considered infeasible due to the time it would take using even today’s supercomputers.
We choose two big prime numbers p and q, multiply them to get N, choose a public exponent e, and then calculate a private exponent d such that (d x e) divides ((p-1) x (q-1)) leaving 1 as the remainder. The pair (N, e) forms the public key, and the pair (N, d) forms the private key in RSA encryption. This process ensures that messages encrypted with the public key can only be decrypted by the corresponding private key, providing a secure way to send information over the internet.
How these keys are exchanged securely — The Diffie Hellman Key Exchange
The Diffie-Hellman key exchange is a mathematical method designed to securely swap cryptographic keys over a public channel. It stands as one of the initial public-key protocols, originating from Ralph Merkle’s concepts and bearing the names of Whitfield Diffie and Martin Hellman.
The Diffie-Hellman key exchange enables two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel.This resulting key becomes the foundation for encrypting future communications via a symmetric-key cipher.
General overview:
The process begins by having the two parties, Alice and Bob, publicly agree on an arbitrary starting colour that does not need to be kept secret. In this example, the colour is yellow. Each person also selects a secret colour that they keep to themselves — in this case, red and cyan. The crucial part of the process is that Alice and Bob each mix their own secret colour together with their mutually shared colour, resulting in orange-tan and light-blue mixtures respectively, and then publicly exchange the two mixed colours. Finally, each of them mixes the colour they received from the partner with their own private colour. The result is a final colour mixture (yellow-brown in this case) that is identical to their partner’s final colour mixture.
Cryptographic explanation
Below is a visualisation detailing who holds which information. Non-secret values are highlighted in blue, while the secret ones are marked in red.Here Eve is an eavesdropper — she watches what is sent between Alice and Bob, tampering with the content.
- g: Public base (primitive root) known to Alice, Bob, and Eve. g = 5
- p: Public modulus (prime) known to Alice, Bob, and Eve. p = 23
- a: Alice’s private key, exclusively known to Alice. a = 6
- b: Bob’s private key, exclusively known to Bob. b = 15
- A: Alice’s public key, recognised by Alice, Bob, and Eve. A = g^a mod p = 8
- B: Bob’s public key, acknowledged by Alice, Bob, and Eve. B = g^b mod p = 19
Threat!
Cracking RSA : Shor’s Algorithm
In 1995 AT&T researcher Peter Shor published an eye-opening article titled “Polynomial-Time Algorithms for Prime Factorisation and Discrete Logarithms on a Quantum Computer.”
Shor’s algorithm is a quantum algorithm for finding the prime factors of an integer. It is a quantum algorithm that causes exponential speed-up when solving the factoring, discrete logarithm (DLP), and elliptic curve discrete logarithm (ECDLP).
The problem that we are trying to solve is: given an odd composite number N, find its integer factors.
To achieve this, Shor’s quantum algorithm consists of two parts:
- A classical reduction of the factoring problem to the problem of order-finding. This reduction is similar to that used for other factoring algorithms, such as the quadratic seive.
- A quantum algorithm to solve the order-finding problem.The goal of the quantum subroutine of Shor’s algorithm is, given co-prime integers N and a to find the order r of a modulo N, which is the smallest positive integer such that .
You can’t solve these problems with a classical computer — It would take a classical computer around 300 trillion years to break a RSA-2048 bit encryption key. That’s why we all feel that we are “safe” from these attacks. However, these challenges could be resolved using a quantum computer. This implies that a quantum computer could potentially decipher any encryption dependent on these mathematical problems, such as RSA, Diffie-Hellman, ECDLP, and all existing public-key cryptographic mechanisms. (Shor might as well have titled his article “Breaking all the Public-Key Crypto on a Quantum Computer”).
Quantum Computers and Their Qbits
Quantum Bit is the smallest unit of information measurement in quantum computing. It is also called Qubit. Unlike, classical bits, a quantum bit can have multiple states at the same time. This property of Qubits is known as superposition. A classical bit can be either 0 or 1. Quantum bits (Qbits), or their clusters, are defined by quantities known as amplitudes, resembling probabilities but not really probabilities. While a probability falls within the range of 0 to 1, an amplitude takes the form of a complex number, expressed as a + b x i ,where ‘a’ and ‘b’ are numerical values and ‘i ’ is an imaginary unit.
In a quantum computer, registers consist of 1 or more qbits in a state of superposition characterised by a set of such complex numbers.
Owing to the qbit’s ability to superpose, it enables a quantum computer to simultaneously perform multiple calculations. Quantum computers can run the Shor’s algorithm in linear time which runs in exponential time on a classical computer, or in constant time when a classical computer needs linear time. Quantum computers are magic for certain, specialised algorithms (which can exploit the quantum superpositions and entanglement), i.e. provide more than a constant speedup, are better than classical computers for decrypting our current encryption schemes.
Quantum computers represent an entirely new paradigm of computation, setting aside binary bits for the complex computational spaces created using qubits, and solving problems that once seemed impossible.
Quantum Safe Cryptography
Quantum-safe cryptography secures sensitive data, access, and communications for the era of quantum computing. The most important thing to understand about quantum-safe cryptography standards is that they substitute the math problems that are easy for quantum computers to solve with math problems that are difficult for both classical and quantum computers to solve.Where earlier forms of cryptography relied on factoring large numbers, these new standards rely on lattice problems.
To understand what a lattice problem is, imagine a mathematician showed you a list of 1,000 large numbers. Now let’s say that mathematician showed you an even larger number, and told you they made it by adding up 500 numbers from the list. If they asked you to figure out which 500 numbers they used, classical and quantum computers wouldn’t be much use in finding the answer — but if the mathematician told you which 500 numbers they used, it would be easy to check whether they were telling the truth. That makes lattice problems good replacements for prime factorisation problems in cryptography.
There are already suggestions that sensitive data is being stolen by hackers to be decrypted in a quantum future, setting an urgency to update modern encryption methods.When data travels between two points, it is possible for hackers to intercept that transfer to “harvest” or “store” the encrypted data. This risk is known as “store now, decrypt later”, or SNDL.
So the good news is that quantum-safe cryptography already exists. NIST has selected CRYSTALS-Kyber (Public key), CRYSTALS-DILITHIUM (DSA), FALCON (DSA),SPHINCS+(DSA) for quantum safe cryptography
Fortifying Tomorrow’s Security Today
In the ever-evolving landscape of cybersecurity, the concept of encryption stands as an essential fortress guarding our digital world.The transition from classical to quantum computing presents both challenges and opportunities. While the promise of quantum computing brings revolutionary advancements, it also threatens the security of our existing encryption standards. However, the quest for quantum-safe cryptography is underway. Understanding the implications of Post-Quantum Cryptography is pivotal in fortifying our data against future threats. It’s not just about safeguarding information today but also anticipating the challenges posed by tomorrow’s technology. Post-Quantum Cryptography serves as a testament to our commitment to adapt, evolve, and fortify our digital assets against the challenges that lie ahead.
References
1. Aumasson, J.-P. (2017). Serious Cryptography: A Practical Introduction to Modern Encryption. No Starch Press.
2. MathNet.Ru: E. S. Malygina, A. V. Kutsenko, S. A. Novoselov, N. S. Kolesnikov, A. O. Bakharev, I. S. Khi lchuk, A. S. Shaporenko , N. N. Tokareva (2023). Main approaches in post-quantum cryptography: description, a comparative study. Journal Prikladnaya Diskretnaya Matematika. Supplement, 2023, Issue 16, Pages 58–65
DOI: https://doi.org/10.17223/2226308X/16/16
3.ScienceDirect: Chawla, D., & Mehra, P. S. (26 September 2023). A roadmap from classical cryptography to post-quantum resistant cryptography for 5G-enabled IoT: Challenges, opportunities and solutions. ScienceDirect. URL: https://www.sciencedirect.com/science/article/abs/pii/S2542660523002731
4. Taylor & Francis Online: Priya Sharma, Vrinda Gupta & Sandeep Kumar
Sood ( 29 Sep 2023) Post-Quantum Cryptography Research Landscape: A Scientometric Perspective . Journal of Computer Information Systems
URL : https://www.tandfonline.com/doi/abs/10.1080/08874417.2023.2260333
