New attacks on RSA with modulus N = p2q using continued fractions
In this paper, we propose two new attacks on RSA with modulus N = p2q using continued fractions. Our first attack is based on the RSA key equation ed - φ(N)k = 1 where φ(N) = p(p - 1)(q - 1). Assuming that and , we show that can be recovered among the convergents of the continued fraction expansion...
| Main Authors: | , |
|---|---|
| Format: | Conference or Workshop Item |
| Language: | English |
| Published: |
IOP Publishing
2015
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/43055/1/jpconf15_622_012019.pdf |
| _version_ | 1825929284023222272 |
|---|---|
| author | Asbullah, Muhammad Asyraf Kamel Ariffin, Muhammad Rezal |
| author_facet | Asbullah, Muhammad Asyraf Kamel Ariffin, Muhammad Rezal |
| author_sort | Asbullah, Muhammad Asyraf |
| collection | UPM |
| description | In this paper, we propose two new attacks on RSA with modulus N = p2q using continued fractions. Our first attack is based on the RSA key equation ed - φ(N)k = 1 where φ(N) = p(p - 1)(q - 1). Assuming that and , we show that can be recovered among the convergents of the continued fraction expansion of . Our second attack is based on the equation eX - (N - (ap2 + bq2)) Y = Z where a,b are positive integers satisfying gcd(a,b) = 1, |ap2 - bq2| < N1/2 and ap2 + bq2 = N2/3+α with 0 < α < 1/3. Given the conditions , we show that one can factor N = p2q in polynomial time. |
| first_indexed | 2024-03-06T08:54:32Z |
| format | Conference or Workshop Item |
| id | upm.eprints-43055 |
| institution | Universiti Putra Malaysia |
| language | English |
| last_indexed | 2024-03-06T08:54:32Z |
| publishDate | 2015 |
| publisher | IOP Publishing |
| record_format | dspace |
| spelling | upm.eprints-430552016-05-17T09:19:23Z http://psasir.upm.edu.my/id/eprint/43055/ New attacks on RSA with modulus N = p2q using continued fractions Asbullah, Muhammad Asyraf Kamel Ariffin, Muhammad Rezal In this paper, we propose two new attacks on RSA with modulus N = p2q using continued fractions. Our first attack is based on the RSA key equation ed - φ(N)k = 1 where φ(N) = p(p - 1)(q - 1). Assuming that and , we show that can be recovered among the convergents of the continued fraction expansion of . Our second attack is based on the equation eX - (N - (ap2 + bq2)) Y = Z where a,b are positive integers satisfying gcd(a,b) = 1, |ap2 - bq2| < N1/2 and ap2 + bq2 = N2/3+α with 0 < α < 1/3. Given the conditions , we show that one can factor N = p2q in polynomial time. IOP Publishing 2015 Conference or Workshop Item PeerReviewed application/pdf en http://psasir.upm.edu.my/id/eprint/43055/1/jpconf15_622_012019.pdf Asbullah, Muhammad Asyraf and Kamel Ariffin, Muhammad Rezal (2015) New attacks on RSA with modulus N = p2q using continued fractions. In: 3rd International Conference on Science & Engineering in Mathematics, Chemistry and Physics 2015 (ScieTech 2015), 31 Jan.-1 Feb. 2015, Bali, Indonesia. (pp. 1-9). 10.1088/1742-6596/622/1/012019 |
| spellingShingle | Asbullah, Muhammad Asyraf Kamel Ariffin, Muhammad Rezal New attacks on RSA with modulus N = p2q using continued fractions |
| title | New attacks on RSA with modulus N = p2q using continued fractions |
| title_full | New attacks on RSA with modulus N = p2q using continued fractions |
| title_fullStr | New attacks on RSA with modulus N = p2q using continued fractions |
| title_full_unstemmed | New attacks on RSA with modulus N = p2q using continued fractions |
| title_short | New attacks on RSA with modulus N = p2q using continued fractions |
| title_sort | new attacks on rsa with modulus n p2q using continued fractions |
| url | http://psasir.upm.edu.my/id/eprint/43055/1/jpconf15_622_012019.pdf |
| work_keys_str_mv | AT asbullahmuhammadasyraf newattacksonrsawithmodulusnp2qusingcontinuedfractions AT kamelariffinmuhammadrezal newattacksonrsawithmodulusnp2qusingcontinuedfractions |