1
$\begingroup$

This is a homework assignment that's been giving me some trouble:

By eavesdropping on a Diffie-Hellman key exchange, we observe

modulus $p$

the base $3$

$A\ =\ 3^a \bmod p\quad$ and

$B\ =\ 3^b \bmod p$

If we somehow had access to the secret $=\ 3^{ab} \bmod p$, how could you retrieve the secret exponents $a$ and $b$?

$p$ is 996-bit. $A$, $B$ also are very large numbers. I think I am missing something about exponential arithmetic. I've tried working on the actual numbers using PARI/GP, but the numbers are too big to use the built-in discrete logarithm functionality.

|improve this question
$\endgroup$
  • 1
    $\begingroup$ Common wisdom is that with $p$ , $3^a\bmod p$ and $3^b\bmod p$ known, additional knowledge of $3^{ab}\bmod p$ does not help decisively towards finding $a$ and $b$, for random choice of these. Also, in unauthenticated DH key exchange, the attacker only wants $a$ and $b$ in order to find $3^{ab}\bmod p$, thus it seems strange to assume that the later is known. Did you test if $p$ is prime? If it (or its factors if it is composite) is of the special form $\dfrac{r^e\pm s}t$ making SNFS possible? $\endgroup$ – fgrieu Mar 5 at 8:17
  • 1
    $\begingroup$ If $p$ is prime, do you know the factorization of $p-1$? Even if you can get its partial factorization, if the order of 3 consists solely of small factors, solving the discrete log problem to obtain $a$ or $b$ is easy... $\endgroup$ – poncho Mar 5 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.