Content |
2024
New quantum algorithm brings encryption collapse closer
On August 23, 2024, US researchers at the Massachusetts Institute of Technology (MIT) announced the development of a new algorithm for quantum computers that brings the collapse of traditional encryption closer. In the long term, the results of the work may contribute to the emergence of cryptographic methods that can resist hacking using quantum computers.
A widespread encryption scheme is RSA (Rivest, Shamir and Adleman): it is a public key cryptographic algorithm based on the computational complexity of the factorization problem (number decomposition into prime factors) of large semisimple numbers. In 1994, the American scientist Peter Shore proposed a quantum factorization algorithm that allows hacking public key cryptographic systems.
However, to run the Shore algorithm, a quantum computer will need about 20 million qubits. As of August 2024, the most powerful quantum systems operate about 1100 qubits. The more qubits a quantum computer has, the more complex calculations it can perform. But at the same time, the likelihood of errors due to interference increases. While some researchers are engaged in building more powerful quantum computers, others are trying to improve Shore's algorithm by making it less resource-demanding.
In 2023, a specialist from New York University, Oded Regev, proposed a theoretical improvement in Shore's algorithm, which allows it to speed up its work, but requires more memory. Based on these findings, the MIT researchers developed an approach combining the speed of the Regev method and the memory efficiency of the Shore algorithm. They found a way to calculate exponents using Fibonacci numbers: this requires simple multiplication, not squaring. Thus, only two units of quantum memory are needed to compute any exponent. In addition, scientists solved the problem of errors using the technique of filtering incorrect results. In the future, the researchers hope to make their algorithm even more efficient, making it possible to quickly hack traditional encryption systems.[1]
Russian scientists have denied the conclusion of researchers from China about the possibility of hacking quantum algorithms
A team of scientists from MISIS University, RCC and Sber conducted an in-depth analysis of the calculations used by researchers from China to simulate hacking a cryptosystem using a 400 + qubit quantum computer, and questioned their conclusion about the revolution in cryptography. Russian scientists believe that the algorithm of colleagues is not working due to "pitfalls" in the classical part and the complexity of the implementation of quantum. MISIS announced this on January 10, 2024.
RSA is one of the first public key cryptosystems and is used for secure data transfer. It is believed that most public key cryptosystems used in January 2024 are protected from attacks through ordinary powerful computers, but not through quantum ones.
In December 2022, scientists from China published an article in which they said that they managed to factor a 48-bit number by simulating a hack of an RSA algorithm using a 10-qubit quantum computer. Based on the classical Schnorr factorization method, the authors use quantum acceleration to solve the problem of finding a short vector in a lattice (SVP, shortest vector problem) of small dimension - which allowed them to make a sensational statement that factorization, i.e. decomposition of a large number into factors, requires fewer qubits than its length, as well as quantum schemes of less depth than previously thought. The researchers concluded that it was possible to crack a 2048-bit number using a computer with 372 physical qubits, although it was previously thought that 20 million were needed for these purposes. After IBM demonstrated the readiness of the 433-qubit Osprey quantum processor, many doubted the reliability of asymmetric cryptography and post-quantum cryptosystems based on SVP computing.
Researchers at NITU MISIS, RCC and Sber consider the conclusion about the possibility of hacking the 2048-bit RSA algorithm hasty.
 | The Schnorr method does not have an accurate estimate of complexity. The main difficulty lies not in solving one shortest vector problem, but in correctly selecting and solving many such problems. It follows from this that this method is probably not suitable for RSA numbers of such sizes that are used in modern cryptography, "said Alexey Fedorov, director of the Institute of Physics and Quantum Engineering NUST MISIS, head of the scientific group" Quantum Information Technologies "RCC. |  |
Scientists emphasize that the method used by researchers in China gives only an approximate solution to the problem, which can be easily obtained for small numbers and small lattices, but is almost impossible for real parameters of cryptosystems. Details of the study are published in one of the scientific journals IEEE Access (Q1).
| | Science moves forward not only by obtaining its own positive results, but also by scrupulous, critical analysis of the results of other research teams. We showed the pitfalls that arise in the algorithm proposed by Chinese colleagues to hack modern encryption algorithms. However, despite the fact that a specific implementation may be ineffective, a quantum computer can still become a serious risk of information security in the future. Therefore, it makes sense to consider ways to minimize these risks, - said Albert Efimov, Ph.D. n., Head of the Department of Engineering Cybernetics, NUST MISIS, Vice President and Director of the Research and Innovation Department of Sberbank PJSC. | |
Researchers argue that the method of scientists from China does not lead to an instant hacking of existing cryptographic algorithms, but the emergence of new classical and quantum cryptanalysis algorithms is an inevitable step towards the introduction of post-quantum cryptography.
2022: Quantum computer hacking
On December 23, 2022, the results of a study by Chinese scientists were released, saying that RSA encryption keys were hacked using quantum computers.
The RSA public key cryptographic algorithm is based on the computational complexity of the factorization (factorization) problem of large primes. But theoretically, this process can be significantly accelerated using advanced quantum computers and the Shore algorithm. Previously, it was believed that to crack RSA, it was necessary to use a quantum system with several thousand logical qubits. Now researchers from China have demonstrated that it is possible to get by with a few hundred qubits.
Reportedly, the authors of the work are associated with a number of the most prestigious universities in the PRC, as well as with state research laboratories that receive direct funding and support from Beijing. Scientists used a 10-qubit quantum computer, which, allegedly, managed to quickly crack the 48-bit RSA encryption key. At the same time, the group of researchers claims that a quantum system with 372 qubits will be required to crack a full-fledged 2048-bit RSA key.
A quantum processor with more than 400 qubits has already been unveiled by IBM. Thus, theoretically, it will soon be possible to hack RSA keys with 2048 bits, and this will actually put an end to the algorithm, the history of which dates back to 1976. But many experts question the results of the work of Chinese scientists. The fact is that the study has not passed any significant expert assessment, which is usually considered a necessary minimum standard for confirming the practical value of the scientific work presented.[2]
Notes
| The site content is translated by machine translation software powered by PROMT. The machine-translated articles are not always perfect and may contain errors in vocabulary, syntax or grammar. Read original article If you find inaccuracies or errors in the results of machine translation, please write to editor@tadviser.ru. We will make every effort to correct them as soon as possible. |