Encryption & Quantum computing
Encryption is an excellent way of protecting sensitive data from compromise. It is commonly accepted that once information is securely encrypted, it is safe from prying eyes and sabotage both now and in the foreseeable future.
However, the long-term security offered by many encryption systems (also known as cryptosystems) is under severe threat. A new type of computer -- the quantum computer -- has been theoretically proven to break most of today’s commonly used cryptosystems
So real is this threat that America's NIST (National Institute for Standards and Technology) has been soliciting proposals from around the world to evaluate and eventually standardise post-quantum cryptography.
This directly impacts the technology buying decisions of CISOs and CTOs today, because privacy legislation requires information like medical records to be kept confidential even after a person dies. This means that a buyer of encryption products faces two choices:
This article is a high-level introduction to the technical details behind quantum computers and their impact in breaking many of today’s commonly used encryption systems.
To date, Shor is the most important quantum algorithm to attack cryptography.
What is long-term data security?
Properly encrypting your data keeps it safe... for now. And in five or 10 years’ time. But as computing technology improves there will come a time when conventional encryption will not be safe against any sufficiently-equipped adversary. Once a cryptosystem is broken, then any unencrypted plaintext data it encrypted is available, and all secrets are accessible.
But data security is not a fixed absolute; it depends on the way encryption is implemented and used, and also on the resources of the attacker. Data security also degrades over time! Planning for long-term data security then means protecting sensitive data over a minimum of 20-30 year timeframes, which can only be achieved by predicting the efficiency of potential data attacks into the future and selecting technology accordingly.
Long-term data security is increasingly seen as a problem for legislators and technologists. For example, German law stipulates that medical and legal data remain confidential from third parties even after the death of a patient or client. Likewise, some confidential data archives will probably have lifetimes longer than the time it takes for new computer paradigms to threaten conventional cryptographic algorithms.
Current and future technologies
We’ll start by investigating the expected direction of computer technology over the coming decades.?In particular, we’ll discuss a new computing paradigm that threatens conventional cryptographic approaches, and some suggestions on mitigating this risk.
Classical and quantum computers
"Classical" computers are the computers we already know and use. Formally known as binary digital electronic computers, they operate by representing information as sequences of zeroes and ones ("binary digits" or "bits") and processing them with devices based on the physics of electrons ("electronic computers"). Each bit can hold one of two values: "0" or "1"; there are no intermediate values. Electronic computers execute algorithms on these bits using simple logic operations (AND, OR, NOT, etc.) to form useful results.
A new class of computing devices was proposed in the early 1980s involving quantum bits ("qubits") instead of bits. Any physics fan will recollect Dr.Richard Feynman. Unlike bits, qubits can be in a combination of states, and so hold a superposition of "0" and "1" states at any one time. As the number of qubits increases, so too does the number of states simultaneously held by the set of qubits. Qubits are processed using quantum computers. These execute algorithms using quantum gates, which are logical building-blocks that operate on all possible states of a set of qubits simultaneously. Once a quantum computation is complete, the output is measured, which causes the multiple entangled superposition of states to collapse to a single classical state. Quantum computers with many qubits are theoretically capable of operating much quicker than any classical computer.
Quantum computers are not a replacement for classical computers -- both have their strengths and weaknesses. However, quantum computers are fantastic for solving particular mathematical problems where classical computers struggle, so a problem that may take a classical computer quadrillions of years to solve will take a sufficiently powerful quantum computer just a few days.
Several types of encryption rely on these kinds of mathematical problems, and so "cracking" many types of encryption will be possible with quantum computers.
Classical and quantum algorithms
An algorithm is a sequence of steps taken by a computer in order to solve a problem.
One important quantum algorithm is Shor’s algorithm, developed in 1995, which decomposes an integer (a whole number) into its multiplicative factors. For example, the number 3276?can be factored into?2x2x3x3x7x13.
Factorisation of numbers becomes difficult as the numbers increase. Previously, it could take?quadrillions of computing-years ?to factor a large integer on a classical computer; Shor’s algorithm operating on a sufficiently powerful quantum computer, could instead factor the same number in several computing-days.
领英推荐
Cryptography and quantum computers
Cryptographic algorithms are used to encrypt a plaintext into a scrambled ciphertext using a unique key. The ciphertext can only be converted back to a readable plaintext using a complementary decryption algorithm, together with the key. The key encapsulates all of the secrecy in this process, and data can only be decrypted with the correct key. There is no secrecy embodied in the algorithm, which is assumed to be known by any potential attacker.
Quantum breakable: classical public-key cryptography
One form of cryptographic algorithm is public-key cryptography, where two parties (traditionally denoted "Alice" and "Bob") wish to communicate secretly over an insecure channel.
In public-key cryptography Alice and Bob each create public and private keys. Alice’s public key is sent to Bob, and used by him to encrypt messages to Alice, which can only be decrypted by her with her private key (which she keeps secret). Likewise, Bob’s public key is sent to Alice for her to encrypt messages to Bob.
Public and private keys are related by integer factorisations. Improved approaches to factoring large numbers, such as Shor’s?Algorithm running on a sufficiently large quantum computer, will improve the likelihood of breaking public-key cryptography. These algorithms are therefore deemed quantum-breakable, because their protection decreases as quantum computers become more powerful.
Quantum resistant: classical symmetrical
Another form of classical cryptographic algorithm uses symmetrical encryption, where Alice and Bob share a single key and this is used for all encryption and decryption operations. In general, symmetrical encryption algorithms like AES and its now-insecure predecessor, DES, do not involve integer factorisation, and so Shor’s algorithm provides no benefit. However, symmetric encryption algorithms are affected by a different quantum attack: Grover’s Algorithm does provide a significant speed-up by finding the solution in the square-root of the time of a classical computer.
For example, if a classical computer needs to search 2raise56?possible keys to be guaranteed to crack DES encryption, a quantum computer running Grover’s Algorithm only needs to do 2^28?searches. This is easier to understand when written in conventional notation:
Classical computer: 2^56?searches = 72,057,594,037,927,936
Quantum computer: 2^28?searches = 268,435,456
When measured in terms of time, assuming both computers can search at the same speed: If it takes a classical computer one day to crack a particular 56-bit encryption, it would take the quantum computer just 0.322 milliseconds -- or one thousandth the blink of an eye. And if it took a classical computer one year to crack 64-bit encryption, it would take a quantum computer 7.3 milliseconds.
Therefore, to counteract this quantum speed-up, larger key sizes must be used. For symmetric encryption to be regarded as quantum-resistant, it needs to have a key length of 256-bits. An encryption system like AES-256 will be equivalent to AES-128 in a post-quantum world.
Quantum-attack resistance of current and new cryptosystems
Luckily, not all of today’s cryptosystems are expected to yield to quantum attack. Shor’s algorithm (and similar algorithms) shows promise only for cryptosystems based on integer factorization, however other cryptosystems are available that rely on different "safer" mathematical bases.
For example, the symmetrical AES algorithm uses a substitution-permutation network to scramble and unscramble data, and as such its security is weakened slightly by quantum attacks. To compensate for this weakening, it is necessary to simply double the key length, with no change to the algorithm. This creates a secure cipher, resistant to quantum attack.
So selection of a quantum-resistant algorithm like AES-256, judiciously configured and carefully integrated, will result in a cryptosystem that will be secure today and in decades’ time.?
NIST estimates that quantum computers will be able to crack existing public-key infrastructure by 2029. Whether these new post-quantum cryptosystems will be available before the advent of sufficiently-powerful quantum computers remains to be seen
When making buying decisions now, it is important to choose a cryptosystem that is post-quantum secure to ensure the long term security of encrypted data.
all credit to Linus Chang adapted from his article.