Skip to main content
placeholder image

Generalised cycling attacks on RSA and strong RSA primes

Chapter


Abstract


  • Given an RSA modulus n, a ciphertext c and the encryption exponent e, one can construct the sequence x0 = c mod n, xi+1 = xei mod n, i = 0,1,… until gcd(xi+1 – x0, n) ≠ 1 or i > B, B a given boundary. If i ≤ B, there are two cases. Case 1: gcd(xi+1 – x0,n) = n. In this case xi = m and the secret message m can be recovered. Case 2: 1 ≠ gcd(xi+1 - x0,n) = n. In this case, the RSA modulus n can be factorised. If i ≤ B, then Case 2 is much more likely to occur than Case 1. This attack is called a cycling attack. We introduce some new generalised, cycling attacks. These attacks work without the knowledge of e and c. Therefore, these attacks can be used as factorisation algorithms. We also translate these attacks to elliptic curves. For this case we call these attacks EC generalised, cycling attacks. Finally, we review criteria that a strong RSA prime must satisfy.

Publication Date


  • 1999

Citation


  • Gysin, M., & Seberry, J. (1999). Generalised cycling attacks on RSA and strong RSA primes. In Unknown Book (Vol. 1587, pp. 149-163). doi:10.1007/3-540-48970-3_13

International Standard Book Number (isbn) 13


  • 9783540657569

Scopus Eid


  • 2-s2.0-84961384198

Web Of Science Accession Number


Book Title


  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Start Page


  • 149

End Page


  • 163

Abstract


  • Given an RSA modulus n, a ciphertext c and the encryption exponent e, one can construct the sequence x0 = c mod n, xi+1 = xei mod n, i = 0,1,… until gcd(xi+1 – x0, n) ≠ 1 or i > B, B a given boundary. If i ≤ B, there are two cases. Case 1: gcd(xi+1 – x0,n) = n. In this case xi = m and the secret message m can be recovered. Case 2: 1 ≠ gcd(xi+1 - x0,n) = n. In this case, the RSA modulus n can be factorised. If i ≤ B, then Case 2 is much more likely to occur than Case 1. This attack is called a cycling attack. We introduce some new generalised, cycling attacks. These attacks work without the knowledge of e and c. Therefore, these attacks can be used as factorisation algorithms. We also translate these attacks to elliptic curves. For this case we call these attacks EC generalised, cycling attacks. Finally, we review criteria that a strong RSA prime must satisfy.

Publication Date


  • 1999

Citation


  • Gysin, M., & Seberry, J. (1999). Generalised cycling attacks on RSA and strong RSA primes. In Unknown Book (Vol. 1587, pp. 149-163). doi:10.1007/3-540-48970-3_13

International Standard Book Number (isbn) 13


  • 9783540657569

Scopus Eid


  • 2-s2.0-84961384198

Web Of Science Accession Number


Book Title


  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Start Page


  • 149

End Page


  • 163