Citation
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
Abstract
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.
Download File
Official URL or Download Paper: http://einspem.upm.edu.my/journal/fullpaper/vol11s...
|
Additional Metadata
| Item Type: | Article |
|---|---|
| Divisions: | Faculty of Science Institute for Mathematical Research |
| Publisher: | Institute for Mathematical Research, Universiti Putra Malaysia |
| Notes: | Special issue: The 5th International Cryptology and Information Security Conference (New Ideas in Cryptology) |
| Keywords: | Prime power; Factorization; LLL algorithm; Simultaneous diophantine approximations; Continued fractions |
| Depositing User: | Nabilah Mustapa |
| Date Deposited: | 04 Jan 2018 03:13 |
| Last Modified: | 04 Jan 2018 03:13 |
| URI: | http://psasir.upm.edu.my/id/eprint/58180 |
| Statistic Details: | View Download Statistic |
Actions (login required)
 |
View Item |