Paper 2005/024

Weak keys of the Diffe Hellman key exchange I

A. A. Kalele and V. R. Sule


This paper investigates the Diffie-Hellman key exchange scheme over the group $\fpm^*$ of nonzero elements of finite fields and shows that there exist exponents $k$, $l$ satisfying certain conditions called the \emph{modulus conditions}, for which the Diffie Hellman Problem (DHP) can be solved in polynomial number of operations in $m$ without solving the discrete logarithm problem (DLP). These special private keys of the scheme are termed \emph{weak} and depend also on the generator $a$ of the cyclic group. More generally the triples $(a,k,l)$ with generator $a$ and one of private keys $k,l$ weak, are called \emph{weak triples}. A sample of weak keys is computed and it is observed that their number may not be insignificant to be ignored in general. Next, an extension of the analysis and weak triples is carried out for the Diffie Hellman scheme over the matrix group $\gln$ and it is shown that for an analogous class of session triples, the DHP can be solved without solving the DLP in polynomial number of operations in the matrix size $n$. A revised Diffie Hellman assumption is stated, taking into account the above exceptions.

Note: The paper has been rewritten with changes, additional examples and explaination. The title has also been revised in view of the second part of this paper which is also being submitted for this archive.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Discrete logarithmsDiffie Hellman key exchangeFinite fieldsGeneral linear group
Contact author(s)
vrs @ ee iitb ac in
2005-09-28: revised
2005-02-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {A.  A.  Kalele and V.  R.  Sule},
      title = {Weak keys of the Diffe Hellman key exchange I},
      howpublished = {Cryptology ePrint Archive, Paper 2005/024},
      year = {2005},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.