Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
In this study, the authors present two rigorous algorithms to certify the trapdoor permutation property of the RSA function ${\rm RS}{\rm A}_{N\comma \, e}\lpar x\rpar := x^e\, \bmod \, N$RSAN,e(x):=xemodN, where $N = p^rq$N=prq 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 $e \ge 2N^{\left({\lpar {\rm gcd}\lpar r\comma \, e - 1\rpar \rpar /{\lpar r + 1\rpar }^2} \right)+ {\rm \epsilon }}$e≥2N(gcd(r,e−1))/(r+1)2+ϵ and for a composite integer $e = e_1^{s_1} e_2^{s_2} \cdots e_u^{s_u} $e=e1s1e2s2⋯eusu when $e_i \ge 2N^{\left({\lpar {\rm gcd}\lpar r\comma \, e_i - 1\rpar \rpar /{\lpar r + 1\rpar }^2} \right)+ {\rm \epsilon }}$ei≥2N(gcd(r,ei−1))/(r+1)2+ϵ for $i = 1\comma \; \, \ldots \comma \; \, u$i=1,…,u, where $e_i$ei is a known prime, $s_i$si is a positive integer, and ${\rm \epsilon } \gt 0$ϵ>0 is some small enough constant. The algorithms apply Coppersmith's method for solving univariate modular polynomial equations and run in time ${\cal O}\lpar {\rm \epsilon }^{ - 7}C\, \log ^2\, N\rpar $O(ϵ−7Clog2N), where $C \le ur^2$C≤ur2 is a constant number.