2018-03-22-PostScryptum.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# SIDH toy example\n",
    "\n",
    "## Public parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = 2^8*3^5 - 1\n",
    "p.is_prime()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Finite Field in i of size 62207^2"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "_.<I> = GF(p)[]\n",
    "K.<i> = GF(p^2, modulus=I^2+1)\n",
    "K"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Elliptic Curve defined by y^2 = x^3 + x over Finite Field in i of size 62207^2"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E = EllipticCurve(K, [1, 0])\n",
    "E"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## $2^8$-torsion generators"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(37327*i + 60077 : 49881*i + 40582 : 1)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Pa = E(0)\n",
    "while (2^7)*Pa == 0:\n",
    "    Pa = 3^5 * E.random_point()\n",
    "Pa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(24108*i + 33045 : 19684*i + 10186 : 1)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Qa = Pa\n",
    "while Pa.weil_pairing(Qa, 2^8)^(2^7) == 1:\n",
    "    Qa = 3^5 * E.random_point()\n",
    "Qa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just for checking (Sage would be too slow on real world parameters)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(256, 256, 256)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Pa.order(), Qa.order(), Pa.weil_pairing(Qa, 2^8).multiplicative_order()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## $3^5$-torsion generators"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(16480*i + 42988 : 39515*i + 26185 : 1)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Pb = E(0)\n",
    "while (3^4)*Pb == 0:\n",
    "    Pb = 2^8 * E.random_point()\n",
    "Pb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(32542*i + 48178 : 49490*i + 54700 : 1)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Qb = Pb\n",
    "while Pb.weil_pairing(Qb, 3^5)^(3^4) == 1:\n",
    "    Qb = 2^8 * E.random_point()\n",
    "Qb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just for checking (Sage would be too slow on real world parameters)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(243, 243, 243)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Pb.order(), Qb.order(), Pb.weil_pairing(Qb, 3^5).multiplicative_order()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Alice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(37006*i + 60295 : 4768*i + 15927 : 1)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sa = randint(0, 2^8-1)\n",
    "R = Pa + Sa * Qa\n",
    "R"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Warning:** This computation does not use the isogeny walk algorithm, will not scale to real size parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Isogeny of degree 256 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field in i of size 62207^2 to Elliptic Curve defined by y^2 = x^3 + (29575*i+59258)*x + (19728*i+31732) over Finite Field in i of size 62207^2"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "phi = E.isogeny(R)\n",
    "phi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Public data sent to Bob"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Elliptic Curve defined by y^2 = x^3 + (29575*i+59258)*x + (19728*i+31732) over Finite Field in i of size 62207^2,\n",
       " (15528*i + 37501 : 56036*i + 43649 : 1),\n",
       " (6586*i + 11442 : 54633*i + 12189 : 1))"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Ea, phiPb, phiQb = phi.codomain(), phi(Pb), phi(Qb)\n",
    "Ea, phiPb, phiQb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bob"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(59278*i + 50914 : 1762*i + 14361 : 1)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sb = randint(0, 3^5-1)\n",
    "R = Pb + Sb * Qb\n",
    "R"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Warning:** This computation does not use the isogeny walk algorithm, will not scale to real size parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Isogeny of degree 243 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field in i of size 62207^2 to Elliptic Curve defined by y^2 = x^3 + (39774*i+22381)*x + (45349*i+47679) over Finite Field in i of size 62207^2"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "psi = E.isogeny(R)\n",
    "psi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Public data sent to Alice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Elliptic Curve defined by y^2 = x^3 + (39774*i+22381)*x + (45349*i+47679) over Finite Field in i of size 62207^2,\n",
       " (51173*i + 16345 : 1400*i + 43995 : 1),\n",
       " (54448*i + 54474 : 58859*i + 25975 : 1))"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Eb, psiPa, psiQa = psi.codomain(), psi(Pa), psi(Qa)\n",
    "Eb, psiPa, psiQa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Key establishment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "61541*i + 35145"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Eb.isogeny(psiPa + Sa*psiQa).codomain().j_invariant()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "61541*i + 35145"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Ea.isogeny(phiPb + Sb*phiQb).codomain().j_invariant()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Your turn, now: implement a real world example using"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = 2^250 * 3^159 - 1\n",
    "p.is_prime()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Write functions to generate torsion bases\n",
    "\n",
    "Alternatively, you can take the official basis points [from the spec](https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/SIKE.zip)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Write an isogeny walk algorithm\n",
    "\n",
    "You can either use a simple quadratic strategy using a for loop, or an advanced optimized strategy. See [the spec](https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/SIKE.zip) for both."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Write the key exchange functions for Alice and Bob\n",
    "\n",
    "Do not forget to check that $j$-invariants match in the end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Optional: optimize things\n",
    "\n",
    "- Replace Sage's elliptic curve class with your own implementation of Montgomery curves.\n",
    "- Replace Sage's implementation of GF(p²) with your own implementation on top of `Zmod(p)`.\n",
    "\n",
    "Do not forget to benchmarks things to see how much you gain!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 8.2.beta5",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}