# Finding Diffie-Hellman secret key with only some know values [closed]

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

• why the original values were deleted? – Fractalice Mar 11 at 21:58

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.

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