New attacks on prime power N = prq using good approximation of φ(N)
This paper proposes three new attacks. Our first attack is based on the RSA key equation ed − kφ(N) = 1 where φ(N) = pr-1(p-1)(q-1). Let q <p <2q and 2p 3r+2/r+1 |p r-1/r+1 – q r-1/r+1| < 1/6Ny with d = Nδ. If δ < 1-y/2 we shows that k/d can be recovered among the convergents of the cont...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Institute for Mathematical Research, Universiti Putra Malaysia
2017
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/58180/1/121-138.pdf |
| _version_ | 1796976848080470016 |
|---|---|
| author | Shehu, Sadiq Kamel Ariffin, Muhammad Rezal |
| author_facet | Shehu, Sadiq Kamel Ariffin, Muhammad Rezal |
| author_sort | Shehu, Sadiq |
| collection | UPM |
| description | This paper proposes three new attacks. Our first attack is based on the RSA key equation ed − kφ(N) = 1 where φ(N) = pr-1(p-1)(q-1). Let q <p <2q and 2p 3r+2/r+1 |p r-1/r+1 – q r-1/r+1| < 1/6Ny with d = Nδ. If δ < 1-y/2 we shows that k/d can be recovered among the convergents of the continued fractions expansions of e/N-2N r/r+1 + N r-1/r+1. We furthered our analysis on j prime power moduli Ni = priqi satisfying a variant of the above mentioned condition. We utilized the LLL algorithm on j prime power public keys (Ni, ei) with Ni = priqi and we were able to factorize the j prime power moduli Ni = priqi simultaneously in polynomial time. |
| first_indexed | 2024-03-06T09:31:37Z |
| format | Article |
| id | upm.eprints-58180 |
| institution | Universiti Putra Malaysia |
| language | English |
| last_indexed | 2024-03-06T09:31:37Z |
| publishDate | 2017 |
| publisher | Institute for Mathematical Research, Universiti Putra Malaysia |
| record_format | dspace |
| spelling | upm.eprints-581802018-01-04T03:13:39Z http://psasir.upm.edu.my/id/eprint/58180/ New attacks on prime power N = prq using good approximation of φ(N) Shehu, Sadiq Kamel Ariffin, Muhammad Rezal This paper proposes three new attacks. Our first attack is based on the RSA key equation ed − kφ(N) = 1 where φ(N) = pr-1(p-1)(q-1). Let q <p <2q and 2p 3r+2/r+1 |p r-1/r+1 – q r-1/r+1| < 1/6Ny with d = Nδ. If δ < 1-y/2 we shows that k/d can be recovered among the convergents of the continued fractions expansions of e/N-2N r/r+1 + N r-1/r+1. We furthered our analysis on j prime power moduli Ni = priqi satisfying a variant of the above mentioned condition. We utilized the LLL algorithm on j prime power public keys (Ni, ei) with Ni = priqi and we were able to factorize the j prime power moduli Ni = priqi simultaneously in polynomial time. Institute for Mathematical Research, Universiti Putra Malaysia 2017 Article PeerReviewed application/pdf en http://psasir.upm.edu.my/id/eprint/58180/1/121-138.pdf Shehu, Sadiq and Kamel Ariffin, Muhammad Rezal (2017) New attacks on prime power N = prq using good approximation of φ(N). Malaysian Journal of Mathematical Sciences, 11 (spec. Aug.). pp. 121-138. ISSN 1823-8343; ESSN: 2289-750X http://einspem.upm.edu.my/journal/fullpaper/vol11saugust/121-138.pdf |
| spellingShingle | Shehu, Sadiq Kamel Ariffin, Muhammad Rezal New attacks on prime power N = prq using good approximation of φ(N) |
| title | New attacks on prime power N = prq using good approximation of φ(N) |
| title_full | New attacks on prime power N = prq using good approximation of φ(N) |
| title_fullStr | New attacks on prime power N = prq using good approximation of φ(N) |
| title_full_unstemmed | New attacks on prime power N = prq using good approximation of φ(N) |
| title_short | New attacks on prime power N = prq using good approximation of φ(N) |
| title_sort | new attacks on prime power n prq using good approximation of φ n |
| url | http://psasir.upm.edu.my/id/eprint/58180/1/121-138.pdf |
| work_keys_str_mv | AT shehusadiq newattacksonprimepowernprqusinggoodapproximationofphn AT kamelariffinmuhammadrezal newattacksonprimepowernprqusinggoodapproximationofphn |