-1
$\begingroup$

I currently have the following information and I assume the first line separated by the : represents the prime number and generator. Is there any way I can find the secret key shared for the diffie-hellman key exchange with only these information.

43223423423:34234234242443423423

Alice's Public:OTEONZJTYZTOCTMETYDMQNMNCDNIOEIMDYAXYOTD Bob's Public: NDGZZNZGYNZNMJOEMCNITNATNIMQJKNTZZEMJDA

$\endgroup$
1
  • $\begingroup$ why the original values were deleted? $\endgroup$ – Fractalice Mar 11 at 21:58
3
$\begingroup$

You have

  • $p = 1219113036371115975795111736303119121$ a 120-bit prime number;
  • $g = 17746761831$ the generator;
  • $A = 929974118015962407341632575868523814$, Alice's public number;
  • $B = 798434686913373724514707188622048606$, Bob's public number.

Note: the values $A$ and $B$ are integers viewed in a decimal string, and then base64 encoded. So beware when converting back as an integer.

There exists $a$ and $b$ such that $A = g^a$ and $B = g^b$ and the shared Diffie-Hellman secret is $S = g^{ab}$.

To find $a$ (or $b$), it is necessary to solve a discrete logarithm. The factorization of $p-1$ is $$ p - 1 = 2^4 \cdot3^2 \cdot 5 \cdot 13 \cdot 130247119270418373482383732511017 $$ where the largest prime factor is a 107-bit prime number. Generic algorithms (Pohlig-Hellman followed by Pollard's rho algorithms) can solve it in time complexity $O(2^{53.5})$, but there exist better methods for this case.

For instance, the largest record for a discrete logarithm problem in this context is for a 795-bit prime number as you can see on Wikipedia.

So this very doable with the right tools. There is CADO-NFS but I am not sure it has the right parameters for this prime number.

$\endgroup$
2
  • 1
    $\begingroup$ Note that let $q= 130247119270418373482383732511017$ then $g^{q-1} \equiv 1 \pmod q$ $\endgroup$ – kelalaka Mar 11 at 16:22
  • $\begingroup$ Won't you correct this answer? Pohlig-Hellman is not necessary here. $\endgroup$ – kelalaka Mar 12 at 21:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.