This paper proposes RSA parameters for which (1) key generation, encryption, decryption, signing, and verification are feasible on today’s computers while (2) all known attacks are infeasible, even assuming highly scalable quantum computers. As part of the performance analysis, this paper introduces a new algorithm to generate a batch of primes. As part of the attack analysis, this paper introduces a new quantum factorization algorithm that is often much faster than Shor’s algorithm and much faster than pre-quantum factorization algorithms. Initial pqRSA implementation results are provided.
The advent of quantum computing poses a funda- mental threat to public-key cryptography based on integer factoring (RSA) and discrete logarithms (ECC). This paper presents an empirical study bridging both sides of this challenge. On the threat side, we implement Shor’s algorithm from first principles using Qiskit and execute it on quantum simulators, successfully factoring N = 15 (50.1% success rate) and N = 21 (32.8%). Resource extrapolation based on Gidney and Ekera˚ (2021) places RSA-2048 at approximately 20 million noisy qubits—roughly four orders of magnitude beyond current hardware. On the defense side, we benchmark ML-KEM-768 (NIST FIPS 203) against X25519 over 10,000 iterations per operation, finding that ML- KEM-768 is 7–18× faster than X25519 on Apple Silicon (keygen: 9.6 µs vs. 66.3 µs median), with the primary cost being a 35× increase in key and ciphertext sizes (2272 B vs. 64 B total wire cost). Our integrated analysis demonstrates that the quantum threat is approaching but distant, while the post-quantum defense is ready and computationally inexpensive, supporting the case for immediate migration under the harvest-now-decrypt-later threat model.
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
eth 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.