×

A new quantum algorithm for computing RSA ciphertext period. (English) Zbl 1389.81012

Summary: A quantum polynomial-time integer factorization algorithm had been previously proposed to break the RSA public-key cryptosystem. In this paper, we propose a new quantum algorithm for breaking RSA by computing the order of the RSA ciphertext \(C\). The new algorithm has following properties: 1) recovering the RSA plaintext \(M\) from the ciphertext \(C\) without factoring \(n\); 2) avoiding the even order of the element; 3) having higher success probability than the previous one; 4) having the same complexity as the previous one.

MSC:

81P68 Quantum computation
81P94 Quantum cryptography (quantum-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Yan S Y. Computational Number Theory and Modern Cryptography [M]. Beijing: Higher Education Press, 2013(Ch). · Zbl 1273.94004
[2] Yan S Y. Number Theory for Computing [M]. 2nd Edition. Berlin: Springer-Verlag, 2002.
[3] Yan S Y. Primality Testing and Integer Factorization in Public-key Cryptography [M]. 2nd Edition. Berlin: Springer-Verlag, 2009. · Zbl 1048.11103
[4] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public key cryptosystems [J]. Communications of the ACM, 1978, 21(2): 120–126. · Zbl 0368.94005 · doi:10.1145/359340.359342
[5] Pomerance C. Smooth numbers and the quadratic sieve [C] // Algorithmic Number Theory. Cambridge: University Press, 2008,44: 69–81. · Zbl 1188.11065
[6] Lenstra A K, Lenstra H W. The Development of the Number Field Sieve, Lecture Notes in Mathematics 1554 [M]. Berlin: Springer-Verlag, 1993. · Zbl 0777.00017
[7] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring [C] // Proceedings of 35th Annual Symposium on Foundations of Computer Science. Washington D C: IEEE Computer Society Press, 1994: 124–134.
[8] Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer [J]. SIAM Journal on Computing, 1997, 26(5): 1484–1509. · Zbl 1005.11065 · doi:10.1137/S0097539795293172
[9] Yan S Y. Cryptanalytic Attacks on RSA [M]. Berlin: Spring-Verlag, 2008.
[10] Nielson M A, Chuang I L. Quantum Computation and Quantum Information [M]. Cambridge: Cambridge University Press, 2000.
[11] Long G L, Pei S Y, Zeng J Y. Recent Progress in Quantum Mechanics, Fourth Volume [M]. Beijing: Tsinghua University Press, 2007 ( Ch).
[12] Wang Y H, Yan S Y. A new quantum algorithm for breaking RSA [J]. Computer Science, 2016, 43(4):24–27(Ch).
[13] Zhang H G, Wang L N, Du R Y, et al. Research on information security discipline [J]. Journal of Wuhan University (Natural Science Edition), 2010, 56(5): 614–620(Ch).
[14] Zhang H G, Han W B, Lai X J, et al. Survey on cyberspace security [J]. Science China Information Sciences, 2015, 58(11): 1101011–43.
[15] Smolin J A, Smith G, Vargo A. Oversimplifying quantum factoring [J]. Nature, 2013, 499(7457): 163–165. · doi:10.1038/nature12290
[16] Gilowski M, Wendrich T, Müller T, et al. Gauss sum factoring with cold atoms [J]. Physical Review Letters, 2008,100(3): 0302011–4. · doi:10.1103/PhysRevLett.100.030201
[17] Peng X H, Liao Z Y, Xu N Y, et al. Quantum adiabatic algorithm for factorization and its experimental implementation [J]. Physical Review Letters, 2008, 101(22): 2204051–4.
[18] Xu N Y, Zhu J, Lu D W, et al. Quantum factorization of 143 on a dipolar-coupling nuclear magnetic resonance system [J]. Physical Review Letters, 2012, 108(13): 1305011–5.
[19] Geller M R, Zhou Z Y. Factoring 51 and 85 with 8 qubits [J]. Scientific Reports, 2013, 3(3023): 1–5. · doi:10.1038/srep03023
[20] Parker S, Plenio M B. Efficient factorization with a single qubit and logN mixed qubits [J]. Physical Review Letters, 2000, 85(14): 3049–3052. · doi:10.1103/PhysRevLett.85.3049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.