2
$\begingroup$

I've been working on this problem for a while now. Could someone please help me see where I'm going wrong?

"Alice and Bob agree to use a Diffie-Hellman key exchange with values p = 431 and primitive root α = 23 Alice’s random number generator gives her 102 and Bob’s gives him 397. What is the common key they will use?"

Ok so I assume that to find the key, I want to compute the discrete logs of $23^x \equiv 102 \pmod{ 431}$ and $23^x \equiv 397 \pmod{ 431}$.

Trying with $\beta = 102$ first, I attempted the "baby step, giant step" algorithm, where $N = [\sqrt{p-1}] +1 = 21$.

I never came up with a match though. My values for $\alpha^j \pmod p $ were {23, 98, 99, 122, 220, 319, 10, 230, 118, 128, 358, 45, 173, 100, 145, 318, 418, 132, 19, 6, 138}

and my values for $\beta \alpha^{-Nk} \pmod p$ were {323, 206, 420, 78, 113, 335, 93, 85, 416, 28, 350, 65, 166, 351, 293, 430, 203, 167, 148, 126, 282}

(j and k go from 1 to N-1.)

So then I tried using index calculus.

I let my base be {2, 3, 5, 11}

$23^3 \equiv 99 = (3^2)(11) \pmod p$

$23^5 \equiv 220 = (2^2)(5)(11)$

$23^7 \equiv 10 = 2(5)$

$23^{10} \equiv 128 = 2^7$

So then

$3 = 0L_\alpha(2) + 2L_\alpha(3) +0L_\alpha(5) + 1L_\alpha(11)$

$5 = 2L_\alpha(2) + 0L_\alpha(3) +1L_\alpha(5) + 1L_\alpha(11)$

$7 = 1L_\alpha(2) + 0L_\alpha(3) +1L_\alpha(5) + 0L_\alpha(11)$

$10 = 7L_\alpha(2) + 0L_\alpha(3) +0L_\alpha(5) + 0L_\alpha(11) \pmod {p-1}$

And I found $L_\alpha(2) = 370$, $L_\alpha(5) = 67$, and $L_\alpha(11) = 58$

However, when I tried to solve for $L_\alpha(3)$ I got stuck with an equation that can't be solved $\pmod {430}:$

$2L_\alpha(3) \equiv 375 \pmod {430}$

Any help would be much appreciated.

$\endgroup$
2
$\begingroup$

I think you slightly misunderstand the question and/or the key-exchange protocol. Alice will compute

$$23^{102} \mod 431$$

and send it to Bob and Bob will compute

$$23^{397} \mod 431$$

and send it to Alice. Then Alice takes the number received from Bob and computes

$$(23^{397})^{102} \mod 431.$$

Bob takes the number received from Alice and computes

$$(23^{102})^{397} \mod 431$$

and this of course is the common key which they both share now. The discrete logarithm problem comes in when Eve the eavesdropper ONLY sees the four numbers being communicated between Alice and Bob and tries to figure out what the exponents are. Alice and Bob of course know their own exponents from the RNG.

$\endgroup$
  • $\begingroup$ you're right, I thought the random number generator was the whole process of raising $\alpha$ to a power instead of the actual number that $\alpha$ is raised to. Thank you so much for clarifying $\endgroup$ – Amber Nov 1 '13 at 21:17

Your Answer

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

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