Score:2

Shortcut to working out Diffie-Hellman Key Exchange

cn flag

I am trying to calculate Alice and Bob's shared key by hand without the use of a calculator as I feel this is an important trait when progressing into cryptography.

I understand you can use the square and multiply method however we are being taught a shortcut method which I don't quite understand fully.

Question Example:

Alice and Bob use the DH protocol with p = 19,g = 2 and secrets a = 6 and b = 8. What key do they agree on?

They have given us this process without much explanation: $$ K = 2^{6×8} ≡8^{2×8} ≡7^8 ≡11^4 ≡7^2 ≡11 \pmod{19} $$

$2^{6×8}$, not sure how to put multiplication as power for the above problem.

If someone could explain in-depth the shortcut process completed above, step by step. I would really appreciate it

I understand some parts, like $g^a*b \pmod{19} = 6 = 2^3 = 8$, however I get slightly confused from there.

fgrieu avatar
ng flag
I polished some of the question, but left the last paragraph as is.
cn flag
Thankyou so much, In regards to your handheld calculations, i was wondering, where you did 2^48-18*2 - Why did you multiply it 2 at the end, and is that 2 the Generator? So is it g^48 mod(19-1)*g And Another thing, how did you know to use 19 and 215. This is where i struggle with the most.
fgrieu avatar
ng flag
In my $48-18\times2=12$, the $2$ is $\lfloor48/18\rfloor$, unrelated to $g$. This is to compute $48\bmod18$, and that modulus is $p-1$. In my $4096-19\times215=11$ I use $19$ because that's the modulus $p$. My $215$ was obtained (digit by digit) as$\lfloor4096/19\rfloor$. This is to compute $4096\bmod19$. I've added some of this in [my answer](https://crypto.stackexchange.com/a/96047/555).
kelalaka avatar
in flag
@fgrieu unfortunately this is a crossposted question with [math](https://math.stackexchange.com/q/4301903/338051). anthonymicheals1, you should need to learn that [this is is not a good ethic in so](https://meta.stackexchange.com/questions/64068/is-cross-posting-a-question-on-multiple-stack-exchange-sites-permitted-if-the-qu)
kelalaka avatar
in flag
If the answer is good you can upvote (min rep 15 required, that you have passed), if the answer satisfies you can accept it. This is the way of [so].
Score:2
ng flag

Recall that for $\forall x\in\mathbb N$, $\forall m,u,v\in\mathbb N^*$, it holds ${(x^u\bmod m)}^n\equiv{(x^u)}^v\equiv x^{u\times v}\pmod m$, where $y\equiv x\pmod m$ means $m$ divides $x-y$, and $x\bmod m$ is the uniquely defined integer $y$ such that $0\le y<m$ and $y\equiv x\pmod m$.

The shared secret is $K=(g^a\bmod p)^b\bmod p=(g^b\bmod p)^a\bmod p$, or equivalently $K=g^{a\times b}\bmod p$. We are tasked to evaluate this for $a=6$, $b=8$, $g=2$, $p=19$.

The method in the question goes: $$\begin{array}{} K&={(2^6\bmod19)}^8\bmod19&&=2^{6\times8}\bmod19\\ &=2^{(3\times2)\times8}\bmod19&={(2^3)}^{2\times8}\bmod19&=8^{2\times8}\bmod19\\ &={(8^2)}^8\bmod19&=64^8\bmod19\\ &&=(64-19\times3)^8\bmod19&=7^8\bmod19\\ &={(7^2)}^4\bmod19&=49^4\bmod19\\ &&=(49-19\times2)^4\bmod19&=11^4\bmod19\\ &={(11^2)}^2\bmod19&=121^2\bmod19\\ &&=(121-19\times6)^2\bmod19&=7^2\bmod19\\ &=49\bmod19&=49-19\times2&=11\\ \end{array}$$ and that (keeping the rightmost column) can be condensed to: $$K\equiv2^{6\times8}\equiv8^{2\times8}\equiv7^8\equiv11^4\equiv7^2\equiv11\pmod{19}\ \text{ thus }\ K=11$$

If I was to compute this without calculator, I would write this as $K=2^{48}\bmod19$, then use Fermat's Little Theorem. It says that when $p$ is prime and $g$ is not a multiple of $p$, if holds $g^{p-1}\bmod p=1$. That allows to reduce modulo $(p-1)$ any exponent of $g$ when computing modulo $p$. The complete calculation goes: $$\begin{array}{} K&=2^{6\times8}\bmod19&&=2^{48}\bmod19\\ &=2^{48\bmod(19-1)}\bmod19&=2^{48-18\times2}\bmod19&=2^{12}\bmod19\\ &=4096\bmod19&=4096-19\times215&=11\end{array}$$

Note: In $48-18\times2=12$, the $2$ is obtained as the quotient $\lfloor48/18\rfloor$, much like in $4096-19\times215=11$ the $215$ is $\lfloor4096/19\rfloor$.


Actual cryptography uses integers much too large for reliable human computation; e.g. $p$ could be 2048-bit, that is 617 decimal digits.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.