3

I want to solve this Diffie Hellman problem:

public number: $g=5$

prime number: $p=23$

Alice: Secret number $a < p$, $m\equiv g^a\mod p$

$m=21$

Bob: Secret number $b < p$, $n=g^b\mod p$

$n=6$

Now I am searching for $a$ and $b$. How can I do this?

Thank you for your help!

Apurv
  • 3,363
  • 2
  • 26
  • 47
kilDasd
  • 31

1 Answers1

0

Solution can be found by iteration, no effective algorithm exist to solve logarithm problem.

In this case $p=23$, and discrete logarithm can be found by computational iterations.

Here is cloud.math script which does just that.

$5 ^ {13} = 1220703125 = 21 ( mod23 )$

$g^{14}\equiv13 (mod23)$
$g^{15}\equiv19 (mod 23)$
$g^{16}\equiv3 (mod p)$
$g^{17}\equiv 15(mod p)$

$g^{18}\equiv 6(mod p)$

$5 ^ {18} \equiv 3814697265625 \equiv 6 ( mod23 )$

Timo Junolainen
  • 639