ทางลัดสู่การแลกเปลี่ยนคีย์ Diffie-Hellman

จำได้ว่าสำหรับ $\forall x\in\mathbb N$, $\forall m,u,v\in\mathbb N^*$มันถือ ${(x^u\bmod m)}^n\equiv{(x^u)}^v\equiv x^{u\times v}\pmod m$, ที่ไหน $y\equiv x\pmod m$ วิธี $m$ แบ่ง $x-y$, และ $x\bmod ม$ เป็นจำนวนเต็มที่กำหนดไม่ซ้ำกัน $y$ ดังนั้น $0\le y<m$ และ $y\equiv x\pmod m$.

ความลับที่ใช้ร่วมกันคือ $K=(g^a\bmod p)^b\bmod p=(g^b\bmod p)^a\bmod p$หรือเทียบเท่า $K=g^{a\times b}\bmod p$. เราได้รับมอบหมายให้ประเมินสิ่งนี้สำหรับ $a=6$, $b=8$, $g=2$, $p=19$.

วิธีการในคำถามคือ: $$\begin{อาร์เรย์}{} 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{อาร์เรย์}$$ และ (การรักษาคอลัมน์ขวาสุด) สามารถย่อเป็น: $$K\equiv2^{6\times8}\equiv8^{2\times8}\equiv7^8\equiv11^4\equiv7^2\equiv11\pmod{19}\ \text{ ดังนั้น }\ K=11$$

ถ้าผมจะคำนวณโดยไม่ใช้เครื่องคิดเลข ผมจะเขียนสิ่งนี้เป็น $K=2^{48}\bmod19$แล้วใช้ทฤษฎีบทเล็กของแฟร์มาต์ มันบอกว่าเมื่อ $p$ เป็นนายกและ $g$ ไม่ใช่ผลคูณของ $p$, ถ้าถือ $g^{p-1}\bmod p=1$. ที่ช่วยลดโมดูโล $(p-1)$ เลขยกกำลังใดๆ ของ $g$ เมื่อคำนวณโมดูโล $p$. การคำนวณที่สมบูรณ์ไป: $$\begin{อาร์เรย์}{} 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{อาร์เรย์}$$

หมายเหตุ: ใน $48-18\times2=12$, $2$ จะได้รับเป็นผลหาร $\lfloor48/18\rชั้น$มากเช่นใน $4096-19\times215=11$ เดอะ $215$ เป็น $\lfloor4096/19\rชั้น$.

การเข้ารหัสจริงใช้จำนวนเต็มมากเกินไปสำหรับการคำนวณของมนุษย์ที่เชื่อถือได้ เช่น. $p$ อาจเป็น 2048 บิต นั่นคือ 617 หลักทศนิยม