2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I polished some of the question, but left the last paragraph as is. $\endgroup$
    – fgrieu
    Nov 10 '21 at 9:32
  • $\begingroup$ 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. $\endgroup$ Nov 10 '21 at 9:43
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Nov 10 '21 at 14:38
  • $\begingroup$ @fgrieu unfortunately this is a crossposted question with math. anthonymicheals1, you should need to learn that this is is not a good ethic in so $\endgroup$
    – kelalaka
    Nov 10 '21 at 18:19
  • $\begingroup$ 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 Stack Overflow. $\endgroup$
    – kelalaka
    Nov 11 '21 at 18:03
2
$\begingroup$

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.

$\endgroup$
0

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.