Hello @CodesInChaos :))))

hi

@CodesInChaos How are you?

@CodesInChaos I have a question. Is it possible to ask it to you or don't you have time?

Alice and Bill use the Diffie-Hellman protocol at the group $\mathbb{Z}_{61}^{\star}$ with base $g=\overline{2}$ (it's a generator). Alice sends to Bill the value $y_A=\overline{38}$ and Bill sends the value $y_B=\overline{50}$. You watch the communication and you know these values. Calculate the common key that they create. @CodesInChaos

Any hints?

You could brute-force the private key for one of them

How can we brute-force the private key for one of them? @CodesInChaos

just check the equation y_A = ModPow(g, x_A, 61) for all values of x_A.

It's probably possible to use the smoothness of p-1 to do it more efficiently, but with such small numbers I wouldn't even bother.

@CodesInChaos With ModPow(g, x_A, 61) do you mean $g^{x_A} \mod{61}$ ?

yes

@CodesInChaos I tried all the values till 26, but with no effort. :(

just one more :)

Alice has 27, Bob has 45

Ahahah :) Do we find the private key of Bob again with brute force? Do we have to try 45 values? :o @CodesInChaos

If you use brute-force yes.

There are fancier algorithms that are faster.

To compute the shared key, one private key is enough.

Are you doing the computation with pen and paper, or why does it take so long?

> We found the private key from Alice which is 27. How can we find the shared key?

Read the DH algorithm page on wikipedia

If p-1 is smooth, you can separate the issue into sub-problems. In your case, solving it mod 3, mod 4, and mod 5, since p-1=60=2^2*3*5.

Then there is Pohlig–Hellman

And generic discrete logarithm algorithms, like pollard rho, which run in $O(q^{1/2})$ steps where $q$ is the order.

@CodesInChaos The shared key is $38^{27} \mod{61}=24$, correct?

@CodesInChaos p-1=3^2*3*5

Wrong on both counts.

READ the wikipedia article

Or any other explanation of DH

Sorry! The shared key is 50^(27) mod 61=11. Correct? @CodesInChaos

to check for consistency, you can do the computation, once like alice would, and once like Bob would

If you get the same value, you're probably right

@CodesInChaos This check? (2^(27))^(11) mod 61=(2^(45))^(11) mod 61

no

Ah... You mean 50^(27) mod 61=38^(45) mod 61=11, correct? @CodesInChaos

yes

@CodesInChaos Now I am trying to understand Pohlig-Hellman

Don't ask me about it. Never bothered to learn how it works.

@CodesInChaos Ok, I will ask it at main. I may ask you something else later. Thanks so far. :))))

@CodesInChaos Is there a trick how to find an a and an i such that if n-1=2^t*u, then $a^{2^{i-1}u} \not\equiv \pm 1 \mod n$ and $a^{2^{i} u} \equiv 1 \mod n$ ? (Rabin-Miller)