Photo by sebastiaan stam on Unsplash
Fortunately, faced with the risks of these new uses, we have two major advantages. We have at our disposal two main families of cryptographic algorithms that provide us on the one hand with the guarantee of identity and on the other hand with the confidentiality of exchanges. The algorithms of the first family are based on asymmetric keys. In an exchange, each participant has a private key and a public key that he provides to his interlocutors. The private key allows him to sign his messages and recipients can ensure his integrity by verifying his signature with the public key.
The link between the public key and the private key also allows the recipient to verify the identity of the sender. They can also send an encrypted response with the public key and only the person in possession of the corresponding private key can decrypt it.
Very often, these keys are RSA keys, initials of the name of their inventors (Ronald Rivest, Adi Shamir and Leonard Adleman). Their principle has been known since 1977. It is based on the difficulty of finding each of its prime numbers from the product of two large prime numbers. If the number of bits required to represent this product is less than 256 bits, the key can be broken in a few minutes on any PC. The recommended length today is 2048 bits, which puts factoring out of reach of today's computers for many years to come. It is thanks to these keys that the vast majority of digital transactions are secured, from credit cards to health cards, the foundation of our society's digital transformation.
However, the appearance of quantum computers is shaking up all this; indeed, the mathematician Peter Williston Shor showed in 1994 that they could in theory be used to quickly factor large numbers, rendering inoperative not only the RSA keys, but also those using elliptic curve mechanisms. Last year, an article published in the journal Nature announced the factorization of the numbers 15, 143, 59989, and 376289 using 4, 12, 59, and 94 logical qubits. The qubit is the elementary unit that these quantum computers handle; unlike the bits of conventional computers, they do not correspond to a single possible state but to a set of states. The number of qubits is one measure of the power of quantum computers. These results were achieved using a D-WAWE 2000Q computer. As its name suggests, this computer consists of 2000 qubits, but these qubits are of a particular type that could not be used for the factorization problem. The quantum computers that can be used to run the Shor algorithm on them are currently much less powerful, with less than 80 qubits, because they are more complex to build. This is therefore a significant step. If there is still a long way to go for 2048-bit number factorization, since the largest of the first factorized numbers is 18 bits, there is now a Damocles sword above the security of RSA keys.
It is therefore important to start now to focus on finding new algorithms that will resist the advent of quantum computing. That is why the National Institute of Standards and Technology (NIST) launched a competition at the end of 2016 to designate the successor to the RSA algorithm. We are now in the 2nd round and the candidates in the running are known. Many French teams answered the call. The validation of the proposals, and the choice of one of them, will be a long process whose completion is not actually expected until 2024.
The other algorithm, which we have not yet discussed, ensures the confidentiality of the exchanges. This is the Advanced Encryption Standard (AES), which is also the result of a NIST competition that began in 1997. It’s vulnerable too, but to a lesser extent, to advances in quantum computation. The Grover algorithm would halve the security related to key length. Today the minimum length of a key considered secure is 128-bits, which will no longer be the case using the Grover algorithm. However, the standard length used nowadays is 256-bits and would therefore be sufficient.
In order to ensure a smooth transition, it is important to prepare for these changes as soon as possible. It is very difficult to predict when the first powerful enough quantum computers will be built or even if they will exist one day, but by the time they are there, it will be too late to act.
The link between the public key and the private key also allows the recipient to verify the identity of the sender. They can also send an encrypted response with the public key and only the person in possession of the corresponding private key can decrypt it.
Very often, these keys are RSA keys, initials of the name of their inventors (Ronald Rivest, Adi Shamir and Leonard Adleman). Their principle has been known since 1977. It is based on the difficulty of finding each of its prime numbers from the product of two large prime numbers. If the number of bits required to represent this product is less than 256 bits, the key can be broken in a few minutes on any PC. The recommended length today is 2048 bits, which puts factoring out of reach of today's computers for many years to come. It is thanks to these keys that the vast majority of digital transactions are secured, from credit cards to health cards, the foundation of our society's digital transformation.
However, the appearance of quantum computers is shaking up all this; indeed, the mathematician Peter Williston Shor showed in 1994 that they could in theory be used to quickly factor large numbers, rendering inoperative not only the RSA keys, but also those using elliptic curve mechanisms. Last year, an article published in the journal Nature announced the factorization of the numbers 15, 143, 59989, and 376289 using 4, 12, 59, and 94 logical qubits. The qubit is the elementary unit that these quantum computers handle; unlike the bits of conventional computers, they do not correspond to a single possible state but to a set of states. The number of qubits is one measure of the power of quantum computers. These results were achieved using a D-WAWE 2000Q computer. As its name suggests, this computer consists of 2000 qubits, but these qubits are of a particular type that could not be used for the factorization problem. The quantum computers that can be used to run the Shor algorithm on them are currently much less powerful, with less than 80 qubits, because they are more complex to build. This is therefore a significant step. If there is still a long way to go for 2048-bit number factorization, since the largest of the first factorized numbers is 18 bits, there is now a Damocles sword above the security of RSA keys.
It is therefore important to start now to focus on finding new algorithms that will resist the advent of quantum computing. That is why the National Institute of Standards and Technology (NIST) launched a competition at the end of 2016 to designate the successor to the RSA algorithm. We are now in the 2nd round and the candidates in the running are known. Many French teams answered the call. The validation of the proposals, and the choice of one of them, will be a long process whose completion is not actually expected until 2024.
The other algorithm, which we have not yet discussed, ensures the confidentiality of the exchanges. This is the Advanced Encryption Standard (AES), which is also the result of a NIST competition that began in 1997. It’s vulnerable too, but to a lesser extent, to advances in quantum computation. The Grover algorithm would halve the security related to key length. Today the minimum length of a key considered secure is 128-bits, which will no longer be the case using the Grover algorithm. However, the standard length used nowadays is 256-bits and would therefore be sufficient.
In order to ensure a smooth transition, it is important to prepare for these changes as soon as possible. It is very difficult to predict when the first powerful enough quantum computers will be built or even if they will exist one day, but by the time they are there, it will be too late to act.
About Serge Adda - CTO WALLIX
Serge Adda - CTO WALLIX
Serge Adda has more than twenty years of experience in the world of IT and software publishing. For 15 years, he was Vice President of Research and Development at Infovista. He has been Product Vice President of WALLIX GROUP since 2012, in charge of research and development, roadmaps and product life cycle. Serge Adda graduated from the Ecole Nationale des Mines de Saint-Etienne in France.