**Weak keys of the Diffe Hellman key exchange I**

*A. A. Kalele and V. R. Sule*

**Abstract: **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.

**Category / Keywords: **Discrete logarithms, Diffie Hellman key exchange, Finite fields, General linear group

**Date: **received 27 Jan 2005, last revised 28 Sep 2005

**Contact author: **vrs at ee iitb ac in

**Available format(s): **PDF | BibTeX Citation

**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.

**Version: **20050928:074033 (All versions of this report)

**Short URL: **ia.cr/2005/024

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]