The complexity of public key algorithms like RSA and variants of Elgamal is based on the involvement of exponentiation in encryption and decryption. RSA is based on integer factorization and variants of Elgamal or based on discrete logarithms and are formed as hard problems. To achieve the perceived level of security, the required key length for public key cryptosystem needs to be determined. Quantum computers are capable of conducting an exponential number of simultaneous computations because of which they can find factors in polynomial time. Shor’s algorithm is popular algorithm for factoring huge integers in polynomial time on quantum computers. This paper presents RSA algorithm followed by various possible attacks for factoring and demonstrates Shor’s algorithm for factoring and discuss results for interpretations.The complexity of public key algorithms like RSA and variants of Elgamal is based on the involvement of exponentiation in encryption and decryption. RSA is based on integer factorization and variants of Elgamal or based on discrete logarithms and are formed as hard problems. To achieve the perceived level of security, the required key length for public key cryptosystem needs to be determined. Quantum computers are capable of conducting an exponential number of simultaneous computations because of which they can find factors in polynomial time. Shor’s algorithm is popular algorithm for factoring huge integers in polynomial time on quantum computers. This paper presents RSA algorithm followed by various possible attacks for factoring and demonstrates Shor’s algorithm for factoring and discuss results for interpretations.

AIP conference proceedingsJan 1, 20245 citations

Generation of Shared RSA Keys by Two Parties

Guillaume Poupard, Jacques Stern

Lecture notes in computer scienceJan 1, 199849 citations

Generation of Shared RSA Keys by Two Parties

Guillaume Poupard, Jacques Stern

Jan 1, 19980 citations

Quantum Algorithm for Attacking RSA Based on the eth Root

Yahui WANG, Huanguo Zhang, Houzhen Wang

The emergence of some quantum algorithms has brought a serious threat to modern cryptography,among which Shor’s algorithm is the most important threatening algorithm for cryptanalysis currently.Shor’s algorithm can solve the integer factorization problem (IFP) and discrete logarithm problem (DLP) in polynomial-time,which makes the current widely used RSA,ElGamal and ECC public key cryptosystem unsafe any more under the quantum computing environment.Therefore,it is necessary to research the cryptanalysis in the quantum computing environment.Solving the IFP is the core idea of Shor’s algorithm for attacking RSA,but breaking RSA does not have to be solved by solving the IFP.A quantum algorithm is designed to attack the RSA cryptosystem starting from the angle of non-factorization.Focusing on the characteristics of RSA public key cryptosystem,using the quantum Fourier transform,the RSA plaintext $M$ can be got by calculating the ${e^{{th}}}$ root modulus $n$ .That is,without solving the IFP,RSA is broken.Different from the previous practices that cryptanalysts try to recover the private-key,a ciphertext-only attack algorithm for RSA,directly from recovering the plaintext $M$ to start, is presented.Results show that the probability of success of the new algorithm is higher than that of Shor’s algorithm attacking RSA.At the same time,the new algorithm does not recover the RSA plaintext from the ciphertext without factoring the modulus $n$ ,and avoids the restriction that the order of ciphertext $C$ modules $n$ is even.The emergence of some quantum algorithms has brought a serious threat to modern cryptography,among which Shor’s algorithm is the most important threatening algorithm for cryptanalysis currently.Shor’s algorithm can solve the integer factorization problem (IFP) and discrete logarithm problem (DLP) in polynomial-time,which makes the current widely used RSA,ElGamal and ECC public key cryptosystem unsafe any more under the quantum computing environment.Therefore,it is necessary to research the cryptanalysis in the quantum computing environment.Solving the IFP is the core idea of Shor’s algorithm for attacking RSA,but breaking RSA does not have to be solved by solving the IFP.A quantum algorithm is designed to attack the RSA cryptosystem starting from the angle of non-factorization.Focusing on the characteristics of RSA public key cryptosystem,using the quantum Fourier transform,the RSA plaintext $M$ can be got by calculating the ${e^{{th}}}$ root modulus $n$ .That is,without solving the IFP,RSA is broken.Different from the previous practices that cryptanalysts try to recover the private-key,a ciphertext-only attack algorithm for RSA,directly from recovering the plaintext $M$ to start, is presented.Results show that the probability of success of the new algorithm is higher than that of Shor’s algorithm attacking RSA.At the same time,the new algorithm does not recover the RSA plaintext from the ciphertext without factoring the modulus $n$ ,and avoids the restriction that the order of ciphertext $C$ modules $n$ is even.

Jan 1, 20180 citations

Threshold key-recovery systems for RSA

Tatsuaki Okamoto

Lecture notes in computer scienceJan 1, 19988 citations

RSA Prime Factorization on IBM Qiskit

Matthew Evans Audric Rengkung, Arya Wicaksana

The advancement of quantum computing in recent years poses severe threats to the RSA public-key cryptosystem. The RSA cryptosystem fundamentally relies its security on the computational hardness of number theory problems: prime factorization (integer factoring). Shor’s quantum factoring algorithm could theoretically answer the computational problem in polynomial time. This paper contributes to the experiment and demonstration of Shor’s quantum factoring algorithm for RSA prime factorization using IBM Qiskit. The performance of the quantum program is evaluated based on user time and the success probability. The results show that a more significant public modulus N in the RSA public key improves factorization’s computational hardness, requiring more quantum bits to solve. A further enhancement on implementing Shor’s oracle function is essential in increasing success probability and reducing the number of shots required.The advancement of quantum computing in recent years poses severe threats to the RSA public-key cryptosystem. The RSA cryptosystem fundamentally relies its security on the computational hardness of number theory problems: prime factorization (integer factoring). Shor’s quantum factoring algorithm could theoretically answer the computational problem in polynomial time. This paper contributes to the experiment and demonstration of Shor’s quantum factoring algorithm for RSA prime factorization using IBM Qiskit. The performance of the quantum program is evaluated based on user time and the success probability. The results show that a more significant public modulus N in the RSA public key improves factorization’s computational hardness, requiring more quantum bits to solve. A further enhancement on implementing Shor’s oracle function is essential in increasing success probability and reducing the number of shots required.

Journal of Internet Services and Information SecurityMay 30, 20238 citations

M

can be got by calculating the

{e^{{th}}}

root modulus

n

.That is,without solving the IFP,RSA is broken.Different from the previous practices that cryptanalysts try to recover the private-key,a ciphertext-only attack algorithm for RSA,directly from recovering the plaintext

M

to start, is presented.Results show that the probability of success of the new algorithm is higher than that of Shor’s algorithm attacking RSA.At the same time,the new algorithm does not recover the RSA plaintext from the ciphertext without factoring the modulus

n

,and avoids the restriction that the order of ciphertext

C

modules

n

is even.