Weak Composite Diffie-Hellman

Kooshiar Azimian ； Javad Mohajeri ； Mahmoud Salmasizadeh

《International Journal of Network Security》 7卷3期 (2008/11) Pp. 383-387

https://doi.org/10.6633/IJNS.200811.7(3).09

並列摘要

In 1985, Shmuley proposed a theorem about intractability of Composite Diffie-Hellman. The theorem of Shmuley may be paraphrased as saying that if there exist a probabilistic polynomial time oracle machine which solves the Diffie-Hellman modulo an RSA-number with odd-order bases then there exist a probabilistic algorithm which factors the modulo. In the other hand Shmuely proved the theorem only for odd-order bases and left the even-order case as an open problem. In this paper we show that the theorem is also true for even-order bases. Precisely speaking we prove that even if there exist a probabilistic polynomial time oracle machine which can solve the problem only for even-order bases still a probabilistic algorithm can be constructed which factors the modulo in polynomial time for more than 98% of RSA-numbers.

並列關鍵字

Computational number theory ； cryptography foundation ； Diffie-Hellman problem ； factoring ； public key cryptography