Not So Safe Primes
"Generating DH parameters... this is going to take a long time"
Intro
Recall in Diffie-Hellman key exchange that we establish a shared secret as follows:
- Select parameters $(p, g)$ such that $p$ is prime and $g$ is a generator for $\mathbb{Z}^*_p$.
- Sample a random number $a$ in $[1, p-1]$, this is your secret key.
- Compute your public key $A$ as $g^a \text{ mod } p$.
- To establish a shared secret with Bob send your public key $A$ to Bob. Bob uses the same parameters and derives his keypair $(B, b)$ in the same fashion as you. Bob will send you his public key $B$
- Compute the shared secret as $B^a = g^{ab} \text{ mod } p$.
The Problem
Consider the following Diffie Hellman parameters:p = 0x0a38522d6c0b9a056801aa0cbe0329ce8457e9724acd1323f19ea310700d6e38 e0252e2eb5b2ba4846259c99e0006441199cf10053471486058a4caa04156a504b g = 0x2
I decided to generate these parameters myself because openssl was taking too long. I've set up an endpoint at:
https://id0-rsa.pub/problem/dh-oracle/[your_public_key_in_hex]/
We can use this endpoint for key exchange over the parameters I generated. It will return the shared secret (in hex) I computed using your public key and my secret key. What are the 50 last digits (in decimal) of my secret key?