Dockerfile

FROM registry.gitlab.com/sagemath/sage/sagemath:9.2.beta2
# Copy Sample Notebook to Image
COPY --chown=sage:sage . .

sidh.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "In diesem interaktiven Notebook werden wir uns heute das Verfahren SIDH anschauen.\n",
    "\n",
    "Ziel ist es, dieses Verfahren näher zu bringen und die mathematischen Objekte dahinter besser kennenzulernen.\n",
    "\n",
    "Falls ihr bisher noch keine Jupyter Notebooks (dieses Dokument) benutzt habt, gibt es hier [eine kleine Einführung](https://www.youtube.com/watch?v=tpLk-FC9kHI).\n",
    "\n",
    "In diesem Notebook benutzen wir die Sprache [sagemath](https://www.sagemath.org/), welche auf Python basiert. Ich werde die einzelnen Objekte beschreiben, die wir benutzen werden."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# SIDH\n",
    "\n",
    "Als erstes schauen wir uns SIDH an. Wie in der Vorlesung beschrieben, hat SIDH folgende Parameter:\n",
    "\n",
    "- $p = 2^{e_2} 3^{e_3} - 1$ um den Körper $\\mathbb{F}_{p^2}$ zu beschreiben (p muss eine Primzahl sein)\n",
    "- Eine Anfangskurve $E_0/\\mathbb{F}_{p^2}$\n",
    "- Zwei Punkte in jeweils $E_0[2^{e_2}]$ und $E_0[3^{e_3}]$\n",
    "\n",
    "Legen wir diese jetzt fest:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "e_2 = 5\n",
    "e_3 = 3\n",
    "p = 2^e_2 * 3^e_3 - 1\n",
    "print(p, p.is_prime())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Wir haben eine passende Primzahl. Wir brauchen nun eine Anfangskurve. Die Entwickler des SIDH- und SIKE-Verfahrens (welches SIDH benutzt) haben hierfür eine bestimmte Kurve ausgesucht: $E_0/\\mathbb{F}_{p^2}\\colon y^2=x^3+6x^2+x$.\n",
    "\n",
    "Wir definieren als nächstes $\\mathbb{F}_{p^2}$ und $E_0$.\n",
    "\n",
    "Sage hat hierfür die Funktion `GF`, welches ein `GaloisField` erstellt. Einfach gesagt: Eine endliche Gruppe. Als Argument übergeben wir die Größe des Körpers. In unserem Fall $p^2$. Dann legen wir in dem Körper die Kurve $E_0$ fest und geben das Endresultat aus.\n",
    "\n",
    "Es fehlen nur noch die zwei Punkte in den beiden Torsionsmengen:\n",
    "\n",
    "- $P_A, P_B \\in E_0[2^{e_2}]$\n",
    "- $Q_A, Q_B \\in E_0[3^{e_3}]$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "F.<i> = GF(p^2)\n",
    "E_0 = EllipticCurve(F, [0, 6, 0, 1, 0])\n",
    "E_0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "P_A = E_0(642*i + 740, 576*i + 726)\n",
    "P_B = E_0(408*i + 633, 512*i + 586)\n",
    "Q_A = E_0(203*i + 16, 9*i + 326)\n",
    "Q_B = E_0(493*i + 319, 745*i + 703)\n",
    "\n",
    "P_A.order() == 2^e_2 and P_B.order() == 2^e_2 and Q_A.order() == 3^e_3 and Q_A.order() == 3^e_3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Nun generieren Alice und Bob ihre privaten Schlüssel. Diese sind ganze Zahlen kleiner gleich als deren jeweilige Basis-Größe. Für Alice ist das $2^{e_2} = 32$ und Bob $2^{e_3} = 27$.\n",
    "\n",
    "In diesem Beispiel wirst du die Rolle von Alice übernehmen. Schreibe bitte einen privaten Schlüssel für `m_A` ein."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "m_A = 100# <füge eine Zahl ein, die <32 >\n",
    "m_B = randint(1, 3^e_3 - 1)\n",
    "assert m_A <= 2^e_2, \"Der private Schlüssel muss kleiner gleich 2^e_2 sein\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Nun werden die Basispunkte der jeweiligen ersten Isogenie ausgerechnet. Sie ergeben sich aus den folgenden Gleichungen:\n",
    "\n",
    "\\[R_A = [m_A]P_A + Q_A \\]\n",
    "\\[R_B = [m_B]P_B + Q_B \\]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "R_A = m_A*P_A + Q_A\n",
    "R_B = m_B*P_B + Q_B"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Und nun kommen wir zur ersten Isogenie von Alice und Bob. Sie hat als Kern die Untergruppe, die durch den gerade ausgerechneten Punkt definiert ist."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "Iso_A_1 = E_0.isogeny(R_A)\n",
    "E_A = Iso_A_1.codomain() # Die 'codomain' ist die Kurve auf welche die Isogenie 'zeigt'\n",
    "Iso_B_1 = E_0.isogeny(R_B)\n",
    "E_B = Iso_B_1.codomain()\n",
    "\n",
    "E_A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Wir schicken Bob seine neuen Basispunkte, sowie die Kurve $E_A$. Dafür bekommen wir unsere neuen Punkte und seine Kurve:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "P2_B = Iso_A_1(P_B)\n",
    "Q2_B = Iso_A_1(Q_B)\n",
    "\n",
    "P2_A = Iso_B_1(P_A)\n",
    "Q2_A = Iso_B_1(Q_A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Mit diesen neuen Punkten berechnen wir erneut eine Isogenie mit unserem privaten Schlüssel:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "R2_A = m_A*P2_A + Q2_A\n",
    "R2_B = m_B*P2_B + Q2_B\n",
    "\n",
    "Iso_A_2 = E_B.isogeny(R2_A)\n",
    "E_A2 = Iso_A_2.codomain()\n",
    "Iso_B_2 = E_A.isogeny(R2_B)\n",
    "E_B2 = Iso_A_2.codomain()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Wir haben also `E_A2` und Bob hat `E_B2`. Diese zwei Kurven sind isomorph zueinander und sollten die gleiche j-Invariante besitzen. Probieren wir das mal aus:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "print(E_A2.j_invariant())\n",
    "print(E_B2.j_invariant())\n",
    "E_A2.j_invariant() == E_B2.j_invariant()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Es hat geklappt! Wir haben es geschafft den SIDH Schlüsselaustausch manuell durchlaufen zu lassen. \n",
    "\n",
    "Wenn du möchtest, kannst du nun etwas herumprobieren. Klappt es auch mit einem anderen secret key? \n",
    "Was passiert, wenn du andere Basispunkte nimmst? Die vielleicht nicht in der Torsionsgruppe liegen?\n",
    "(Vergiss nicht immer alle nachfolgenden Zellen mit Shift+Enter noch einmal ausführen zu lassen.)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath (system-wide)",
   "language": "sagemath",
   "metadata": {
    "cocalc": {
     "description": "Open-source mathematical software system",
     "priority": -1,
     "url": "https://www.sagemath.org/"
    }
   },
   "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.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}