{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2d65c91c",
   "metadata": {},
   "source": [
    "[Home](Home.ipynb) <br/>\n",
    "[Crypto](Crypto.ipynb)\n",
    "\n",
    "# Euclid's Extended Algorithm (EEA)\n",
    "\n",
    "While in the process of discovering the gcd of two numbers, a and b, it's possible, at the same time, to extract two additional integers, m and n, such that: \n",
    "\n",
    "$$\n",
    "a\\ m + b\\ n = gcd(a, b)\n",
    "$$\n",
    "\n",
    "m or n will be negative.\n",
    "\n",
    "The idea is two multiples of a and b (say m and n) will get them within one GCD of one another, i.e. the GCD brick will divide both a and b bricks (by definition), so there's a way to stack a and b side by side such that the only difference in height between the two stacks is their greatest in-common divisor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "abd5ded7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def gcd(a, b):\n",
    "    \"\"\"\n",
    "    Recursive version of gcd\n",
    "    \"\"\"\n",
    "    if b == 0:  # no remainder, b (now a) was gcd\n",
    "        return a\n",
    "    return gcd(b, a%b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "61d22251",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gcd(20, 170)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "9f145785",
   "metadata": {},
   "outputs": [],
   "source": [
    "def xgcd(a, b):\n",
    "    \"\"\"\n",
    "    Extended Euclidean Alg.\n",
    "    \n",
    "    take positive integers a, b as input, and return \n",
    "    a triple (g, x, y), such that ax + by = g = gcd(a, b).\n",
    "    \"\"\"\n",
    "    x0, x1, y0, y1 = 1, 0, 0, 1\n",
    "    while b != 0:\n",
    "        q, a, b = a // b, b, a % b\n",
    "        x0, x1 = x1, x0 - q * x1\n",
    "        y0, y1 = y1, y0 - q * y1\n",
    "    return  a, x0, y0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d58d2e69",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(5, 6, -7)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a, b = 100, 85\n",
    "gcd_, m, n = xgcd(a, b)\n",
    "gcd_, m, n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "906c1637",
   "metadata": {},
   "source": [
    "The GCD is the leftmost number, then come m and n such that:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "46e6401c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a * m + b * n == gcd(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "7e990e45",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, -6, 5)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a, b = 14, 17\n",
    "gcd_, m, n = xgcd(a, b)\n",
    "gcd_, m, n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "3b95fed3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a * m + b * n == gcd(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "6ce55157",
   "metadata": {},
   "outputs": [],
   "source": [
    "def invmod(a, N):\n",
    "    \"\"\"\n",
    "    What is the multiplicative inverse of a, inv_a,\n",
    "    such that a * inv_a = 1 mod N.\n",
    "    \"\"\"\n",
    "    return xgcd(a, N)[1] % N  # inv_a (gcd is 1, a * x0 + N * x1 = 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "a6a62e0c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "invmod(14, 17) # what number times 14, mod 17, is 1?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "e284898a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(14 * 11) % 17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "29e4237b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "invmod(3, 17)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "63c23786",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(3 * 6) % 17"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb1c5a4f",
   "metadata": {},
   "source": [
    "Lets see where ```invmod``` fits in to the [RSA](RSA.ipynb) algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "eba873d9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "356393"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = 593\n",
    "q = 601\n",
    "N = p * q  # public key comprised of two primes\n",
    "N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "40d6beeb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "355200"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "phiN = (p-1)*(q-1)  # phi(ab)=phi(a)phi(b)\n",
    "phiN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "e32e3c52",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "167153"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "e = 17\n",
    "d = invmod(e, phiN) # what is e's multiplicative inverse mod phiN?\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "725310cc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2841601"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "e * d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "b2e781d1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(e*d) % phiN"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6cf96ed",
   "metadata": {},
   "source": [
    "But what size public keys are we really talking about?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "231016ad",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Check!\n"
     ]
    }
   ],
   "source": [
    "RSA232 = \\\n",
    "17969491597941066732916128449573246156367561808012600070888918835531726460341490933493372247868650755230855864199929221814436684722874052065257937495694348389263171152522525654410980819170611742509702440718010364831638288518852689\n",
    "p = 4528450358010492026612439739120166758911246047493700040073956759261590397250033699357694507193523000343088601688589\n",
    "q = 3968132623150957588532394439049887341769533966621957829426966084093049516953598120833228447171744337427374763106901\n",
    "\n",
    "if RSA232 == p*q:\n",
    "    print(\"Check!\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "f232a8e5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'2f68a7dece4554b9f829dd67abf99118633a653e8c7b56f8f86820570cbd9399915e2c5d0c790156bda44c0632e8371f14161b55abb9066263e8846980abc14978f29380efd9a432d5fc7d139e1ab27bb6197962f18d672a0cc7e108337b051'"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hex(RSA232)[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "5e0f8f39",
   "metadata": {},
   "outputs": [],
   "source": [
    "N = RSA232\n",
    "phiN = (p-1)*(q-1) # 𝜙(a * b) = 𝜙(a) * 𝜙(b) if a, b coprime, 𝜙(p) = p-1 if p prime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "1b612b94",
   "metadata": {},
   "outputs": [],
   "source": [
    "e = 17\n",
    "d = invmod(e, phiN) # what d, multiplied by e, will be 1 mod phiN?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "ee25982a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10570289175259451019362428499748968327275036357654470629934658138548074388436171137349042498746265150135797567176423956018503248984269945430046922024466863299558267938031191018569191870150828300405595010449202998525804603031798353"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d  # secret key (stays safe with the public key holder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "7ac055b5",
   "metadata": {},
   "outputs": [],
   "source": [
    "m = int(bytes.hex(b'attack at dawn!'), 16)\n",
    "c = pow(m, e, N)  # encrypt using N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "fdfd5c6c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'attack at dawn!'"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "outcome = pow(c, d, N)  # decrypt using d\n",
    "bytes.fromhex(hex(outcome)[2:])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}