Certifying multi‐power RSA
Xiaona Zhang, Liping Wang, Jun Xu · IET Information Security · 2018
In this study, the authorspresent two rigorous algorithms to certify the trapdoor permutation property of the RSAfunction , where is a multi‐power RSA modulus with unknown factorisation and r is a known positive integer. Their work gives effective certification for a prime exponent e when and for a composite integer when for , where is a known prime, is a positive integer, and is some small enough constant. The algorithms apply Coppersmith's method for solving univariate modular polynomial equations and run in time , where is a constant number.