Weak Composite Diffie-Hellman

10.6633/IJNS.200811.7(3).09

Kooshiar Azimian；Javad Mohajeri；Mahmoud Salmasizadeh

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

International Journal of Network Security

7卷3期（2008 / 11 / 01）

383 - 387

英文

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.