Even with the advent of quantum computers, the RSA cryptosystem may not be broken

Quantum computerThe possibility of breaking through the RSA cryptosystem that is currently popular, there is a possibility that the crisis of cryptographic system is being screamed. However, a research team at the University of Pennsylvania announced that it developed an algorithm to create an RSA cryptographic key that can not be broken by a quantum computer newly, and the possibility that the RSA cryptographic key system can compete with the quantum computer has been shown .

Cryptology ePrint Archive: Report 2017/351
https://eprint.iacr.org/2017/351

Why Quantum Computers Might Not Break Cryptography
https://www.quantamagazine.org/why-quantum-computers-might-not-break-cryptography/

RSA encryptionThe basic idea of ​​the system takes advantage of the fact that a huge number of prime factorization is difficult with classical computers. Even though the multiplication of huge prime numbers is easy, it takes a huge amount of time to decompose a huge multiplied number, which is impossible in reality, so we use the multiplied number as the public key and prime factorized secret key as the multiplied factor By doing so, it is the public key cryptosystem that only the ones with the secret key can decrypt it, and as the current general cryptosystem, it supports the encryption technology of the Internet world.

However, in 1994 Professor Peter Shore of MIT was able to solve prime factor decomposition in polynomial time by a polynomial time, so that a huge number impossible with a classical computer which has only algorithms capable of solving prime factorization with quasi-exponential time Even in prime factorization of quantum computers, it was found that using quantum computer can be solved in realistic time, the possibility that the RSA cryptosystem will be broken has increased. It is said that "the crisis of the cryptographic system" is because the existing cryptosystem is inevitable by the practical application of the quantum computer.

Prior to the quantum computer, the research team of Nadia Henninger and colleagues at the University of Pennsylvania developed an algorithm that efficiently creates terabyte-level encryption keys against the common belief that the RSA cryptosystem is toothless. In order to decipher the RSA cryptosystem using this terabyte class cryptographic key, it is said that even a quantum computer requires a huge number of arithmetic operations of 2 to the 100th power. The number of 2 to the 100 th power is said to be half the number of all the bacterial cells on Earth, and even quantum computers can not calculate in a realistic time.


It is a countermeasure by the duty industry to prevent encryption system from being deciphered by creating a terabyte (several trillion bit) class encryption key while the encryption key size currently used in the RSA encryption system is thousands of bits Even with the algorithm developed by the research team at the University of Pennsylvania, it takes about 5 days to create and decrypt the encryption key, so it seems that it can not be said that it is a practical level because it is a substitute that can not be used at the moment. However, there seems to be a possibility that it is a technology which largely denies the opinion that "the RSA cryptosystem will collapse by the quantum computer" which was conventionally said. Associate Professor Henninger said, "Apart from practicality, it is interesting to see that the conventional legendary knowledge is wrong."

·bonus
Professor Adi Shamia, co-inventor of the RSA cryptosystem, was awarded the Japan International Prize with the achievement of contributing to the progress of science and technology and was awarded the Japan International Prize, but at the awards' interview, "Optimistically than people studying quantum computers I am thinking that I do not believe quantum computers will decipher the cipher within the past ten or fifteen years. "

News commentary - "RSA cryptography is not broken by quantum computer", the creator got awarded the Japan International Awards spirit: ITpro
http://itpro.nikkeibp.co.jp/atcl/column/14/346926/042700954/