"
]
},
{
"cell_type": "markdown",
"id": "3d8019b3-0201-4260-8ded-2d2daab58607",
"metadata": {},
"source": [
"Elliptische Kurven haben eine exponierte Stellung in der Mathematik. Spätestens in den 1990er Jahren, in denen Andrew Wiles den berühmten großen Satz von Fermat mit ihrer Hilfe bewies, zeigte sich die Tragweite der Theorie. Bekannt sind elliptische Kurven aber schon weitaus länger."
]
},
{
"cell_type": "markdown",
"id": "5869fdbb-5320-4fb0-9fb4-f148d955244b",
"metadata": {},
"source": [
"### Großer Satz von Fermat\n",
"***\n",
"
\n",
"Für $2\n",
"\n",
"***"
]
},
{
"cell_type": "markdown",
"id": "6529a6db-1c8b-49f8-9188-4edf3361a37a",
"metadata": {},
"source": [
"Der Fokus dieses Notebooks soll aber auf einer weiteren Anwendung von elliptischen Kurven liegen, die in den Bereich der Kryptographie fällt. Die bis heute gängige Verschlüsselung im Internet basiert auf dem sogenannten [RSA-Verfahren](https://de.wikipedia.org/wiki/RSA-Kryptosystem). Es gibt allerdings ein deutlich effizienteres und dazu sicheres Verfahren Nachrichten zu verschlüsseln, das sogenannte Elliptic Curve Cryptography (ECC) oder zu Deutsch: Elliptische-Kurven-Kryptographie; weshalb aktuell vom RSA-Standard auf ECC-Standard umgestellt wird. Ziel dieses Notbooks ist es, das ECC-Verfahren zu verstehen.\n",
"\n",
"Für diejenigen, die mehr über den Bezug vom Großen Fermatschen Satz zu elliptischen Kurven wissen möchten, sei allerdings auf den folgenden Abschnitt verwiesen, der sich diesem Thema widmet. Alle anderen können den Abschnitt getrost übergehen."
]
},
{
"cell_type": "markdown",
"id": "fbb717dc-5461-4faa-8bf9-1866a1769fa3",
"metadata": {
"tags": []
},
"source": [
"### Andrew Wiles' Beweis des Großen Fermatschen Satzes\n",
"***\n",
"Die Theorie der elliptischen Kurven scheint eng mit der Theorie von sogenannten elliptischen Modulformen verknüpft zu sein. Das sind Funktionen $f$ auf der oberen Halbeebene (d.h. $f:\\mathbb{H}\\to\\mathbb{H}$, wobei $\\mathbb{H}:=\\{z\\in\\mathbb{C}| \\Im(z)>0\\}$ die Menge der komplexen Zahlen mit positivem Imaginärteil ist), die eine ungeheure Menge an Symmetrien aufweisen. Tatsächlich gibt es nämlich für eine Modulform $f$ ein $k \\in \\mathbb{Z}$, sodass für jede Matrix $A:=\\left(\\begin{matrix}\n",
"a & b \\\\\n",
"c & d\n",
"\\end{matrix}\\right) \\in \\mathbb{Z}^{2\\times 2}$ mit $det(A)=1$ die Gleichung $f(\\frac{az+b}{cz+d})= (cz+d)^kf(z)$ erfüllt ist. Sie finden im Internet viele Bilder und Videos dazu, die diese Symmetrien veranschaulichen. Die Definition von Modulformen fordert außerdem noch komplexe Differenzierbarkeit.\n",
"\n",
"Man vermutet nun, dass man zu jeder elliptischen Kurve $E$ eine Modulform finden kann, die auf spezielle Weise mit $E$ zusammenhängt (Das ist die sogenannte Taniyama-Shimura-Vermutung). Diese Vermutung konnte aber bisher nicht bewiesen werden. Elliptische Kurven, für die man so eine Modulform finden kann, nennt man modular. Die Taniyama-Shimura-Vermutung besagt also, dass alle elliptischen Kurven modular sind.\n",
"\n",
"1990 konnte Kenneth Ribet zeigen: Falls es eine ganzzahlige Lösung der Gleichung $a^n+b^n=c^n$ gibt, dann ist die Frey-Kurve $y^2 = x(x-a^n)(x+b^n)$ eine elliptische Kurve, die nicht modular ist und damit im Widerspruch zur Taniyama-Shimura-Vermutung steht.\n",
"\n",
"Die Arbeit Andrew Wiles' bestand nun darin, dass er für eine große Klasse von elliptischen Kurven (zu denen die besagte Frey-Kurve zählt) zeigen konnte, dass sie modular sind. Der Große Satz von Fermat ist also ein einfaches Korollar seiner Arbeit.\n",
"***"
]
},
{
"cell_type": "markdown",
"id": "647b9298-97d2-4c47-9643-e37e938e741b",
"metadata": {},
"source": [
"Widmen wir uns nun also dem eigentlichen Thema: ECC. Wir starten mit der Definition elliptischer Kurven."
]
},
{
"cell_type": "markdown",
"id": "f03aefe7-0d94-40b3-92c5-05efa6689369",
"metadata": {
"tags": []
},
"source": [
"
\n",
" \n",
"### Definition - Elliptische Kurve\n",
"\n",
"Sei $K$ ein Körper mit\n",
"1. $char(K) \\not \\in \\{2,3\\}$ und\n",
"2. $a,b\\in K$ mit $4a^2-27b^2\\not=0$\n",
" \n",
"Für das Polynom $p(x,y):=-y^2+x^3+ax+b \\in K[x,y]$ nennen wir $\\mathcal{V}(p):=\\{(x,y)\\in\\mathbb{R}^2| p(x,y)=0\\} \\cup \\{\\mathcal{O}\\}$ die elliptische Kurve von $p$ (über $K$). Eine elliptische Kurve ist demnach die Lösungsmenge der Gleichung $y^2=x^3+ax+b$ in $K^2$ vereinigt mit einem \"unendlich fernen Punkt\" $\\mathcal{O}$.\n",
" \n",
"Erinnerung:\n",
"- $K[x,y] := \\{\\sum_{i=0}^n\\sum_{j=0}^ma_{ij}x^iy^j|a_{ij} \\in K; n,m \\in \\mathbb{N}\\}$ bezeichnet den Polynomring in $x$ und $y$. Dabei definieren wir $x^0:=y^0:=1$.\n",
"- Die Charakteristik $char(K)$ eines Körpers K ist definiert als der positive Erzeuger des Kerns des Ringhomomorphimus $\\varphi: \\mathbb{Z} \\to K$ mit $\\varphi(1):=1$. \n",
"D.h. die Charakteristik gibt an wie oft wir $1$ mit sich selbst addieren müssen, bis wir $0$ erhalten, insbesondere gilt: $char(\\mathbb{Z}\\big/p\\mathbb{Z}) = p$ für $p\\in \\mathbb{Z}$ (positive) Primzahl.\n",
" \n",
"Bemerkung: Die Bedingung 1. erlaubt es uns die elliptische Kurve in der einfachen Form hinzuschreiben, in der wir sie angegeben haben. Die zweite Bedingung sorgt dafür, dass die sogenannte Diskriminante der Kurve nicht verschwindet (d.h. ungleich Null ist). Dadurch hat die Kurve \"schöne Eigenschaften\", z.B. ist dann für $k=\\mathbb{R}$ an jedem Punkt die Tangente wohldefiniert. Die Bedingungen sind beide etwas technisch, weshalb wir darauf nicht weiter eingehen wollen.\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "61e4af03-ef78-4b14-9d0e-04de21f6c2d1",
"metadata": {},
"source": [
"Die Definition kann auf den ersten Blick etwas abstrakt wirken. Der Begriff elliptische Kurve wird allerdings stark durch den Fall $K=\\mathbb{R}$ motiviert, in dem $\\mathcal{V}(p)\\setminus\\{\\mathcal{O}\\}$ eine Kurve im analytischen Sinn ist."
]
},
{
"cell_type": "markdown",
"id": "66aef4f7-cef4-4d38-8fd0-4bf850d4b08d",
"metadata": {},
"source": [
"
\n",
"Denkanstoß: Parametrisieren Sie die Kurve für $K=\\mathbb{R}$ (dabei können Sie den Punkt $\\mathcal{O}$ außer Acht lassen).\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "01c117ce-92c3-47c4-8760-c4e70523db2c",
"metadata": {},
"source": [
"Die Lösungsmenge $\\mathcal{V}(p)\\setminus\\{\\mathcal{O}\\}$ der polynomiellen Gleichung $p(x,y)=0$ lässt sich als Teilmenge des $\\mathbb{R}^2$ gut visualisieren.\n",
"Führen Sie die zwei Codeblöcke nacheinander aus, um eine Visualisierung der Kurve zu erhalten. Sie können an den zugehörigen Reglern für $a$ und $b$ verschiedene Werte festlegen.\n",
"\n",
"Es ist nicht notwendig, dass Sie den Programmcode verstehen. Sie sollten aber folgende Zeile einmal laufen lassen, damit der Programmcode fehlerfrei funktioniert."
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "f60d933b-434d-48ea-9775-9c5f2c3ac152",
"metadata": {},
"outputs": [],
"source": [
"# Achten Sie darauf, dass Sie Python 3 und nicht Julia verwenden \n",
"# FOLGENDE ZEILE BITTE UNBEDINGT EINMAL ZU BEGINN AUSFÜHREN!"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "6707c838-d6f4-402b-9f55-0243ec06c4f8",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Collecting plotly\n",
" Using cached plotly-5.18.0-py3-none-any.whl (15.6 MB)\n",
"Requirement already satisfied: packaging in /opt/conda/lib/python3.9/site-packages (from plotly) (21.0)\n",
"Collecting tenacity>=6.2.0\n",
" Using cached tenacity-8.2.3-py3-none-any.whl (24 kB)\n",
"Requirement already satisfied: pyparsing>=2.0.2 in /opt/conda/lib/python3.9/site-packages (from packaging->plotly) (2.4.7)\n",
"Installing collected packages: tenacity, plotly\n",
"Successfully installed plotly-5.18.0 tenacity-8.2.3\n",
"Note: you may need to restart the kernel to use updated packages.\n"
]
}
],
"source": [
"pip install plotly"
]
},
{
"cell_type": "markdown",
"id": "52252410-7130-47ce-a74d-7f5c3a2be10f",
"metadata": {},
"source": [
"Lassen Sie folgende Zeile einmal laufen, um eine interaktive Visualisierung von elliptischen Kurven zu erhalten."
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "0798a650-15d3-42f7-9fe8-ef47677162a2",
"metadata": {},
"outputs": [
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "3927e21074bf49e899da7197d1df7787",
"version_major": 2,
"version_minor": 0
},
"text/plain": [
"interactive(children=(FloatSlider(value=-0.5, description='a', max=1.0, min=-2.0, step=0.01), FloatSlider(valu…"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
""
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# ALGORITHMUS 1\n",
"import matplotlib.pyplot as plt\n",
"import numpy as np\n",
"from ipywidgets import interact\n",
"\n",
"# Funktion zur Erstellung des Graphen\n",
"def create_implicit_graph(a, b):\n",
" x = np.linspace(-10, 10, 200)\n",
" y = np.linspace(-10, 10, 200)\n",
" X, Y = np.meshgrid(x, y)\n",
" Z = Y**2 - X**3 - a * X - b\n",
"\n",
" plt.figure(figsize=(8, 6))\n",
" plt.contour(X, Y, Z, levels=[0], colors='r', linewidths=1)\n",
" plt.xlim(-10, 10)\n",
" plt.ylim(-10, 10)\n",
" plt.xlabel('x')\n",
" plt.ylabel('y')\n",
" plt.title('Elliptische Kurven: $y^2 = x^3 + {}x + {}$'.format(a, b))\n",
" plt.grid(True)\n",
" plt.show()\n",
"\n",
"# Interaktive Schieberegler für a und b\n",
"interact(create_implicit_graph, a=(-2.0, 1.0, 0.01), b=(-1.0, 2.0, 0.01))\n"
]
},
{
"cell_type": "markdown",
"id": "55e670a4-bcb2-40cf-be33-e68484b91f83",
"metadata": {},
"source": [
"
\n",
"Denkanstoß: Warum ist die Kurve symmetrisch zur $x$-Achse?\n",
" \n",
"
"
]
},
{
"cell_type": "markdown",
"id": "709f2043-585f-4103-a102-eb65584a8f14",
"metadata": {},
"source": [
"Bisher wirkt der zusätzliche Punkt $\\mathcal{O}$ eher störend als nutzbringend. Seine Daseinsberechtigung erörtern wir im Folgenden. Wir werden dabei weitestgehend auf Beweise verzichten, da die Konzepte intuitiv verstanden werden können, die zugehörigen Beweise aber recht technisch sind."
]
},
{
"cell_type": "markdown",
"id": "f88e209b-b9a9-4432-9119-f277dfbd42c0",
"metadata": {},
"source": [
"Sei für den Rest des Notebooks $K=\\mathbb{Q}$ und $\\mathcal{V}$ eine elliptischen Kurve über $K$.\n",
"\n",
"Dann lässt sich auf $\\mathcal{V}$ eine Gruppenstruktur definieren. Diese ist geometrisch motiviert: \n",
"Betrachten wir zwei rationale Punkte $P,Q$, so erhalten wir zwischen ihnen eine Gerade (falls $P=Q$ betrachte die Tangente). Falls die Gerade $\\mathcal{V}\\setminus\\{\\mathcal{O}\\}$ in einem dritten Punkt schneidet, bezeichnen wir diesen Punkt als $R = (r_1,r_2) \\in \\mathbb{Q}^2$. Falls $R$ existiert, definieren wir $P+Q:=(r_1,-r_2)=:-R$. Andernfalls setzen wir $P+Q:=\\mathcal{O}$."
]
},
{
"cell_type": "markdown",
"id": "75849858-592c-446b-8566-6e7a4fc05805",
"metadata": {},
"source": [
"
\n",
"Denkanstoß: Überlegen Sie, wie viele Schnittpunkte eine Gerade mit einer elliptischen Kurve hat. Die Antwort variiert je nach Gerade, können Sie die Abhängigkeit ermitteln?\n",
" \n",
"Hinweis: Betrachten Sie den Grad des zugehörigen Polynoms (bzgl. $x$).\n",
"
\n",
" \n",
"### 1. Aufgabe\n",
"***\n",
"- 1.1 Bestimmen Sie anhand einer Skizze zu einem Punkt $P\\in\\mathcal{V}$ das Inverse und überlegen Sie, warum diese Konstruktion im Allgemeinen möglich ist.\n",
"- 1.2 Überlegen Sie sich, warum $\\mathcal{O}$ ein Neutralelement bzgl. der Verknüpfung bildet.\n",
"- 1.3 Argumentieren Sie, warum die so definierte Verknüpfung kommutativ ist.\n",
" \n",
"Hinweis zur 1.1: Betrachten Sie die Vertikale und erinnern Sie sich an die Interpretation von $\\mathcal{O}$ als Punkt im Unendlichen. \n",
"Bemerkung: Mit der Bearbeitung der 1.2 zeigen Sie also (informell) insbesondere, dass für alle Punkte Inverse existieren.\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "5b84dab9-a5c0-4f9e-97d3-f8f0a23c2f57",
"metadata": {},
"source": [
"Es stellt sich heraus, dass die Verknüpfung assoziativ ist, das heißt $(\\mathcal{V},+)$ bildet eine abelsche Gruppe."
]
},
{
"cell_type": "markdown",
"id": "e7db077d-4129-41f1-b014-7d622c90b24e",
"metadata": {},
"source": [
"
\n",
"Denkanstoß: Machen Sie sich anhand einer Skizze klar, dass die Verknüpfung assoziativ ist.\n",
" \n",
"Hinweis: Betrachten Sie drei paarweise verschiedene Punkte $P,Q,R \\in \\mathcal{V}$ und zeichnen Sie die zugehörigen Geraden ein. Zeichnen Sie nun $P+Q$, $Q+R$ und daraufhin $(P+Q)+R$ und $P+(Q+R)$ ein. Sie werden feststellen, dass die letztgenannten Punkte gleich sind (zumindest, wenn Sie genau genug zeichnen). Überlegen Sie, warum dies im Allgemeinen gilt.\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "2ce38bb7-9eff-444a-94cf-50c30387c8b0",
"metadata": {},
"source": [
"Die Gruppenstruktur auf elliptischen Kurven eignet sich um eine sogenannte Falltürfunktion zu definieren."
]
},
{
"cell_type": "markdown",
"id": "4eacef3f-d726-438d-afc7-ba5d8e1ba95d",
"metadata": {},
"source": [
"
\n",
" \n",
"### Definition - Falltürfunktion\n",
"***\n",
"Der Begriff Falltürfunktion kommt aus der Informatik. Damit bezeichnet man Funktionen $f:\\mathbb{A}\\to\\mathbb{B}$, sodass sich der Funktionswert $y=f(x)$ für gebenes $x\\in A$ effizient (d.h. in polynomieller Laufzeit) berechnen lässt. Andersrum soll für gegebenes $y=f(x)\\in \\mathbb{B}$ der Urbildwert $x$ schwer zu berechnen sein.\n",
" \n",
"Bemerkung: Wir werden nicht formal definieren, was dieses schwer bedeutet. Die Schwierigkeit bei der Definition rührt daher, dass man auch probabilistische Algorithmen in Betracht ziehen muss. Das heißt die exakte Berechnung soll nicht nur ineffizient sein (also nicht-polynomieller Laufzeit - z.B. exponentiell), sondern auch \"unwahrscheinlich zu erraten\" sein.\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "4a66ee19-ac0e-4b1d-94a2-32c20be3bdef",
"metadata": {},
"source": [
"Ein bekanntes Beispiel für Falltürfunktionen ist die Produktbildung von Primzahlen. Es ist sehr einfach, zwei Primzahlen zu multiplizieren (Eine Multiplikation entrspricht einem flop, d.h. einer floating point operation, der Einheit in der man Rechenaufwand typischerweise angibt. Insbesondere ist die Laufzeit $\\mathcal{O}(1)$, wobei wir die $\\mathcal{O}$-Notation verwenden. Nicht zu verwechseln mit unserem \"unendlich fernen Punkt\" $\\mathcal{O}$ auf der elliptischen Kurve). \n",
"Um allerdings die Primfaktorzerlegung einer beliebigen Zahl zu finden, wird erheblich mehr Aufwand benötigt (wen genauer interessiert, was \"erheblich mehr\" bedeutet, der kann dazu [hier](https://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity) mehr erfahren). \n",
"Ein weiterer sehr verbreiteter Algorithmus zur Datenverschlüsselung, das sogenannte [RSA-Kryptosystem](https://de.wikipedia.org/wiki/RSA-Kryptosystem), benutzt genau diese Falltürfunktion.\n",
"\n",
"Man kann die Primfaktorzerlegung einer Zahl aber tatsächlich mithilfe des [Shor-Algortihmus](https://de.wikipedia.org/wiki/Shor-Algorithmus) in polynomieller Laufzeit berechnen. Dieser lässt sich allerdings nur auf Quantencomputern implementieren. Das soll aber hier nicht weiter thematisiert werden."
]
},
{
"cell_type": "markdown",
"id": "8fc5378d-bd8d-4e2e-bde4-9415ea2594cc",
"metadata": {},
"source": [
"***"
]
},
{
"cell_type": "markdown",
"id": "2dea37e9-1015-4b5e-b97a-bfc015dc271a",
"metadata": {},
"source": [
"Bevor wir uns der Frage widmen, wie uns Falltürfunktionen dabei helfen Daten zu verschlüsseln, möchten wir einmal herausarbeiten, wie genau die Gruppenstruktur auf der elliptischen Kurve uns solch eine Funktion liefert."
]
},
{
"cell_type": "markdown",
"id": "c82ec15c-06ec-4c4a-b960-4fced1694858",
"metadata": {},
"source": [
"Betrachten Sie dazu für $n \\in \\mathbb{Z}$ und $P \\in \\mathcal{V}$ den Punkt $nP=P+...+P$, der als die $n$-fache Addition von $P$ definiert ist. Für festes $P\\in E$ erhalten wir nun die Falltürfunktion $f_P:\\mathbb{Z} \\to \\mathcal{V}, (n,P) \\mapsto f_P(n):=f(n,P):=nP$"
]
},
{
"cell_type": "markdown",
"id": "8d12228a-bff5-4dfa-9d3a-255d6fe7135b",
"metadata": {},
"source": [
"
\n",
"Denkanstoß: Wie kann man $P+P$ geometrisch interpretieren?\n",
" \n",
"Hinweis: Betrachten Sie die Tangente im Punkt $P$.\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "74ca1d37-9dc5-4f8d-853f-86ffbe3ab49e",
"metadata": {},
"source": [
"Um zu zeigen, dass $f$ der Definition einer Falltürfunktion genügt, müssen wir zeigen, dass für gegebenes $n\\in\\mathbb{Z}$, $P\\in \\mathcal{V}$ der Funktionswert $f(n,P)$ leicht zu berechnen ist. \n",
"Apriori ist der Aufwand linear, d.h. $\\mathcal{O}(n)$, denn wir müssen $P$ ja $n$-mal addieren.\n",
"\n",
"Allerdings gibt es einen schnelleren Weg. Betrachte dazu die Binärdarstellung von $n$, sagen wir: $n=35=2^5+2^1+2^0=100011_{2}$. (Wenn wir Zahlen in einer anderen Basis als Basis 10 darstellen, schreiben wir die Basis als Index dazu. Für Binärdarstellungen also Index $2$) \n",
"Um Zweierpotenzen $2^kP$, $k\\in \\mathbb{N}$ von $P$ zu berechnen, müssen wir $P$ nicht $2^k$ mal addieren. Stattdessen addieren wir um $2^kP$ zu berechnen $2^{k-1}P$ mit sich selbst, das heißt wir brauchen lediglich $k$ Schritte für die Berechnung."
]
},
{
"cell_type": "markdown",
"id": "dd142911-4f13-4729-b551-c34f2c6cd8ec",
"metadata": {},
"source": [
"#### Berechnung von $2^3P$\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "1b40e48b-8206-4197-afa4-839813c8c330",
"metadata": {},
"source": [
"Möchten wir $nP$ berechnen und $n$ ist keine Zweierpotenz, können wir einfach die Binärdarstellung betrachten und die einzelnen Zweierpotenzen addieren. Im Wesentlichen ist die Berechnung also logarithmischer Laufzeit, das heißt für Eingabe $(n,P)$ liegt die Berechnung von $f(n,P)$ in der Größenordnung $\\mathcal{O}(log_2(n))$."
]
},
{
"cell_type": "markdown",
"id": "45c16b7e-1320-4679-84fc-42a9ca9b5984",
"metadata": {},
"source": [
"Die Umkehrung des Problems wäre nun, für gegebenes $(P,Q=nP) \\in \\mathcal{V}^2$ dieses $n\\in\\mathbb{N}$ zu finden, sodass $f(n,P)=Q$. \n",
"Dafür bleibt einem aber nicht viel anderes übrig, als die Brute-Force-Methode zu benutzen, also einfach durchzuprobieren. Man muss also nacheinander für jedes $k\\in\\mathbb{N}$ den Funktionswert $f(k,P)=kP$ berechnen, bis $kP=Q$ gilt (oder zumindest ist kein wesentlich besseres Verfahren bekannt). Die Funktion erfüllt also unsere Definition und ist damit eine Falltürfunktion.\n",
"***"
]
},
{
"cell_type": "markdown",
"id": "af379642-0f5d-49b8-9147-fdf0cf9bd0c3",
"metadata": {},
"source": [
"Im Folgenden werden wir erklären, wie wir unsere konkrete Falltürfunktion dafür nutzen können Daten zu verschlüsseln. Im Grunde funktioniert das so analog für jede andere Falltürfunktion, siehe dafür [Asymmetrisches Kryptosystem](https://de.wikipedia.org/wiki/Asymmetrisches_Kryptosystem)."
]
},
{
"cell_type": "markdown",
"id": "4279d709-643f-4a82-80a7-4b9a830b59e9",
"metadata": {},
"source": [
"Man kann sich leicht überlegen, das verschlüsselte Kommunikation zwischen zwei Parteien $A$ und $B$ schon dann möglich ist, wenn $A$ und $B$ beide eine geheime Zahl kennen, die außer ihnen niemand kennt.\n",
"\n",
"Nehmen wir dazu an, dass Alice und Bob geheime Nachrichten austauschen wollen und gehen wir weiterhin davon aus, dass Sie ihre unverschlüsselten Nachrichten mit $N=26$ Buchstaben schreiben (also dem gängigen Alphabet. Sie können aber auch jedes andere $N>1$ wählen, wenn Sie ihrem Alphabet z.B. Großbuchstaben oder Sonderzeichen hinzufügen wollen). \n",
"Wir wollen zeigen, dass Alice und Bob schon dann geheim kommunizieren können, wenn Sie eine gemeinsame Zahl $z\\in\\mathbb{Z}$ kennen, die sonst niemand kennt."
]
},
{
"cell_type": "markdown",
"id": "b3b3c201-3c38-43fb-a4b7-ccd8fcaa4e3d",
"metadata": {},
"source": [
"
\n",
"Solch eine Zahl, die nur Alice und Bob kennen, bezeichnet man auch als (gemeinsamen) Schlüssel.\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "d0e34719-102c-4aab-9509-ca53efeccdc5",
"metadata": {},
"source": [
"Sei also $z$ ein Schlüssel.\n",
"\n",
"Betrachten wir nun die Menge $S_\\mathbb{A}:=\\{\\varphi:\\mathbb{A}\\to \\mathbb{A}| \\varphi \\text{ ist bijektiv}\\}$ der Permutationen auf unserem Alphabet $\\mathbb{A}$. Das ist gerade isomorph zur $S_N=\\{\\varphi:\\{1,...,N\\} \\to \\{1,...,N\\}| \\varphi \\text{ ist bijektiv}\\}$, da nach Voraussetzung gilt $|\\mathbb{A}|=N$ und wir demnach $\\mathbb{A}$ mit $\\{1,...,N\\}$ identifizieren können. \n",
"Aus der linearen Algebra ist bekannt, dass $N!=|S_N|=|S_\\mathbb{A}|$. Wir können die $S_\\mathbb{A}$ also durchnummerieren. Sei $\\varphi_i$ für $i\\leq N!$ die $i$-te Permutation auf $\\mathbb{A}$ bezüglich dieser Nummerierung.\n",
"\n",
"Nun kommen wir zur eigentlichen Idee zur Verschlüsselung. Betrachten wir die Zahl $\\bar{z}:= z \\text{ mod } N! \\in \\mathbb{Z}\\big/N!\\mathbb{Z}$, dann gibt es einen Repräsentanten $R$ von $\\bar{z}$ in $\\{1,...,N!\\}$. Die Verschlüsselung besteht nun darin, dass Alice auf ihre Nachricht $\\varphi_R$ anwendet (was das genau bedeutet diskutieren wir gleich), bevor Sie sie abschickt. Bob muss dann bevor er die Nachricht liest nur $\\varphi_R^{-1}$ auf die Nachricht anwenden, dadurch wird der Text wieder lesbar.\n",
"\n",
"Mit der Anwendung eines Elements aus $S_\\mathbb{A}$ auf eine Nachricht ist Folgendes gemeint: \n",
"Eine Nachricht $T$ von Alice ist ein String von Zeichen. Ist unser Alphabet $\\mathbb{A}=\\{A,k,u\\}$ hat $T$ also zum Beispiel folgende Form: $T=Akku$ \n",
"Die Anwendung von $\\varphi\\in S_\\mathbb{A}$ auf $T$ ist nun nichts anderes als die Anwendung auf die einzelnen Buchstaben. Sei beispielsweise $\\varphi(A):=k,\\ \\varphi(u):=u, \\ \\varphi(k):=A$, dann ist $\\varphi(T):=\\varphi(A)\\varphi(k)\\varphi(k)\\varphi(u)=kAAu$."
]
},
{
"cell_type": "markdown",
"id": "11a1feea-d5cd-4674-b49e-fca0f4d19854",
"metadata": {},
"source": [
"Für die Praxis ist dieser Algorithmus natürlich viel zu simpel. Außerdem müsste man noch viele Details beachten, wie zum Beispiel, dass eine Verschlüsselung mit der Identiät $id\\in S_\\mathbb{A}$ natürlich wenig Sinn macht. Aber dieses Beispiel zeigt eben, dass es ausreicht, eine Zahl zu kennen, um verschlüsselt zu kommunizieren. Wir konnten unser Problem verschlüsselt zu kommunizieren also auf Generierung eines gemeinsamen Schlüssels reduzieren. Sobald Alice und Bob das können, können sie ihr Nachrichten ver- & entschlüsseln."
]
},
{
"cell_type": "markdown",
"id": "2320d026-9cbd-4fa8-86e5-8f1dac30f42a",
"metadata": {},
"source": [
"
\n",
" \n",
"### 2. Aufgabe\n",
"***\n",
"Denken Sie sich nun selbst ein Verfahren aus mit dem Alice und Bob ihre Nachrichten ver- und entschlüsseln können, wenn sie einen gemeinsamen Schlüssel haben.\n",
" \n",
"Hinweis: Sie dürfen sich dabei auf Nachrichten fixer Länge beschränken. Das heißt für gegebenes $L\\in\\mathbb{N}$ sollen Sie ein Verfahren konstruieren, dass Nachrichten der Länge $L$, also mit $L$ Buchstaben, ver- und entschlüsseln kann.\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "42d89f53-f4e8-44ab-aa8d-55cddd1980a1",
"metadata": {},
"source": [
"Wir geben nun ein Verfahren an, wie sich Alice und Bob mithilfe der elliptischen Kurven einen gemeinsamen Schlüssel generieren können. \n",
"Dazu wähle sich Alice eine beliebige Zahl $A\\in\\mathbb{Z}$. Analog wähle Bob eine Zahl $B\\in\\mathbb{Z}$. Dies können Sie natürlich im Geheimen tun, sodass niemand ausßer Alice $A$ und niemand außer Bob $B$ kennt. \n",
"Alice und Bob einigen sich nun öffentlich auf eine elliptische Kurve $E$, d.h. sie legen die Koeffizienten $a,b$ des Polynoms $-y^2+x^3+ax+b$ fest. Außerdem einigen sie sich auf einen Punkt $P\\in E$ auf der elliptischen Kurve $E$ und eine Zahl $n\\in \\mathbb{Z}$. \n",
"Über die Informationen $n,a,b$ und $P$ verfügt also theoretisch auch jeder Dritte, der Alice und Bobs Gespräch abhören möchte, nennen wir ihn Claus."
]
},
{
"cell_type": "markdown",
"id": "336d8df5-f57d-4f51-b15d-388716d72bc8",
"metadata": {},
"source": [
"
\n",
" \n",
"Unter einer öffentlichen Einigung verstehen wir ein unverschlüsseltes Gespräch, welches theoretisch von Dritten mitgehört werden kann. \n",
"Analog sprechen wir von geheimen Prozessen, wenn keine Drittparteien auf die Informationen, um die es in dem Prozess geht, zugreifen können.\n",
" \n",
"Bemerkung: Das heißt öffentlich ist das, von dem Claus weiß und geheim ist das, von dem Claus nichts weiß.\n",
" \n",
"
"
]
},
{
"cell_type": "markdown",
"id": "a7bbbf4b-997d-408d-8b73-d9bf4eacb7df",
"metadata": {},
"source": [
"Nun kann sich Alice einen sogenannten öffentlichen Schlüssel generieren. Das ist nämlich gerade $f_P(A)=AP$. Analog verfügt Bob über einen eigenen öffentlichen Schlüssel $f_P(B)$. Diese öffentlichen Schlüssel tauschen Alice und Bob nun öffentlich (wie der Name schon vermuten lässt) aus. Claus kennt die öffentlichen Schlüssel also auch. "
]
},
{
"cell_type": "markdown",
"id": "255a205c-4c1f-4c94-ba6a-b2a0185ab324",
"metadata": {},
"source": [
"Wir haben bereits geklärt, dass $(\\mathcal{V},+)$ kommutativ ist. Insbesondere gilt also $P\\in \\mathcal{V}$ und folgende Gleichheit: $f_{AP}(B) =B(AP)= (BA)P=(AB)P=A(BP)=f_{BP}(A)$. "
]
},
{
"cell_type": "markdown",
"id": "c092627c-33b9-4eff-bca4-aad0f008e616",
"metadata": {},
"source": [
"
\n",
"Denkanstoß: Warum gelten die einzelnen Gleichheiten?\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "4b7436d8-8407-47bc-a90d-6bb2da42a349",
"metadata": {},
"source": [
"Nach dieser Überlegung kennen also sowohl Alice als auch Bob den Punkt $ABP\\in E$. Claus braucht allerdings für die Berechnung von $ABP$ noch die Zahl $A$ oder $B$. Da $f$ aber eine Falltürfunktion ist, benötigt er unverhältnismäßig viel Aufwand, um $A$ oder $B$ und damit $ABP$ zu berechnen. $ABP$ führt uns aber unmittelbar zu einer (rationalen) Zahl $x$, der $x$-Koordinate von $ABP$, die Alice und Bob als gemeinsamen Schlüssel verwenden können.\n",
"\n",
"Natürlich können sich Dritte den Schlüssel theoretisch trotzdem generieren, aber in der Praxis wird der Zusatzaufwand, den dieser Dritte hat, einfach so skaliert, dass sich der Aufwand nicht rechnet. Häufig sind wirtschaftliche Interessen die Motivation für Datendiebstahl, aber wenn die Kosten um die Verschlüsselung zu knacken höher sind als die Erlöse, die etwa durch Datenverkauf entstehen, dann wird niemand ernsthaft daran interessiert sein diesen Deal einzugehen."
]
},
{
"cell_type": "markdown",
"id": "a6a4f4d0-6dd6-4289-a3d0-615eebc65de7",
"metadata": {},
"source": [
"***"
]
},
{
"cell_type": "markdown",
"id": "7e89dd1a-41d2-45e5-b7e8-ede187c983a2",
"metadata": {},
"source": [
"Grundsätzlich wären wir an dieser Stelle fertig. Wir haben unseren gemeinsamen Schlüssel $x$ gefunden (dieser ist zwar rational, aber wenn ein ganzzahliger Schlüssel erwünscht ist, können wir natürlich einfach mit dem Nenner multiplizieren), Alice und Bob können sich also ungestört Nachrichten hin- & herschicken. \n",
"Allerdings findet die Berechnung von den Funktionswerten von $f$ natürlich auf einem Computer statt, auf dem auch Rundungsfehler auftreten können. Auch wenn diese Rundungsfehler klein sind, führt das natürlich zu einem anderen Schlüssel und wenn Bob mit dem vermeintlich gemeinsamen Schlüssel versucht Alices Nachricht zu entschlüsseln, wird ihm das wohl kaum gelingen. Glücklicherweise gibt es eine äußerst elegante Methode diesen Fall zu umgehen."
]
},
{
"cell_type": "markdown",
"id": "05184baa-1da3-47bb-a719-7957bc93693c",
"metadata": {},
"source": [
"Anstatt die rationalen Zahlen als Grundkörper zu betrachten, nehmen wir einen endlichen Grundkörper $\\mathbb{F}_p=\\mathbb{Z}\\big/p\\mathbb{Z}$ (wobei $p\\in\\mathbb{N}$ eine Primzahl ist) und betrachten eine elliptische Kurve über diesem Körper. Erstaunlicherweise liegt auch hier eine Gruppenstruktur vor."
]
},
{
"cell_type": "markdown",
"id": "6a57b48e-27b0-4351-9da4-5d14f384212a",
"metadata": {},
"source": [
"# Exkurs zur Ringtheorie\n",
"***"
]
},
{
"cell_type": "markdown",
"id": "ac17f027-bf3e-42b1-be2f-a483f4050b15",
"metadata": {},
"source": [
"In der linearen Algebra haben Sie bereits bewiesen, dass $\\mathbb{F}_p$ ein Körper ist. In diesem Exkurs wollen wir noch einmal genauer verstehen welche Eigenschaften von $\\mathbb{Z}$ und welche Eigenschaften der Primzahlen für diesen Umstand sorgen. Dafür machen wir uns einige wichtige Konzepte aus der Ringtheorie klar."
]
},
{
"cell_type": "markdown",
"id": "688adb50-bbaa-4c2c-aa64-1a0ea4a0b606",
"metadata": {},
"source": [
"
\n",
" \n",
"### Definition - Ring\n",
"***\n",
"Sei $(R,+)$ eine abelsche Gruppe. $(R,+,\\cdot)$ heißt Ring, falls $\\cdot: R\\times R \\to R$ assoziativ ist und das Distributivgesetz erfüllt, d.h. $(a+b)\\cdot c=a \\cdot c + b\\cdot c \\ \\forall a,b,c\\in R$. \n",
"\"$+$\" wird als Addition und \"$\\cdot$\" wird als Multiplikation bezeichnet.\n",
"\n",
"Wir nennen $1$ ein Einselement, wenn $1\\cdot a=a=a\\cdot 1 \\ \\forall a \\in R$. \n",
"$R$ heißt kommutativ, falls $a\\cdot b = b\\cdot a \\ \\forall a,b\\in R$.\n",
" \n",
"Einen kommutativen Ring mit Einselement nennen wir Kring.\n",
" \n",
"Sei nun $(R,+,\\cdot)$ ein Kring. Dann bezeichnen wir mit $R^\\times:=\\{a\\in R|\\ \\exists \\ a^{-1}\\in R: a\\cdot a^{-1}=1\\}$ die Einheitengruppe des Krings. Elemente der Einheitengruppe heißen Einheiten. \n",
"Elemente $n \\in R\\setminus \\{0\\}$ heißt Nullteiler, falls ein $k\\in R$ mit $k\\cdot n=0$ existiert. \n",
"Wenn kein Nullteiler $n \\in R\\setminus \\{0\\}$ existiert, dann nennen wir $R$ nullteilerfrei.\n",
" \n",
"Nullteilerfreie Kringe heißen Integritätsbereiche.\n",
" \n",
"
\n",
"Denkanstoß: Überlegen Sie sich, dass das Einselement in Kringen eindeutig ist und, dass die Einheitengruppe eine Gruppe bzgl. der Multiplikation ist.\n",
"
\n",
" \n",
"### Definition - Ideal\n",
"***\n",
"Sei $(R,+,\\cdot)$ ein Kring. \n",
"Dann schreiben wir für zwei Mengen $I,J \\subseteq R$ $I\\cdot J:= \\{i*j | i\\in I, j\\in J\\}$. Ist $I=\\{i\\}$ einelementig, schreiben wir auch $iJ$, analog schreiben wir $I\\cdot j$ für $J=\\{j\\}$ einelementig.\n",
" \n",
"Eine Untergruppe $I\\subseteq R$ heißt Ideal in $R$ oder auch $R$-Ideal, falls $R\\cdot I\\subseteq I$. Wenn immer wir $I \\unlhd R$ schreiben, so meinen wir $I$ ist Ideal in $R$. \n",
"Gilt sogar $I\\subset R$, so nennen wir $I$ echtes Ideal. Dabei bezeichnet \"$\\subset$\" hier und fortan die echte Teilmengenrelation.\n",
"\n",
"Ist $I\\unlhd R$ ein Ideal, so ist $R\\big/I$ ebenfalls ein Ring.\n",
"\n",
"
\n"
]
},
{
"cell_type": "markdown",
"id": "1640734f-f0d2-424f-b7d5-8ffdca5220f8",
"metadata": {},
"source": [
"Wir gehen zunächst näher darauf ein, was es heißt eine Primzahl zu sein und klären dabei einen weiteren wichtigen Begriff der Ringtheorie."
]
},
{
"cell_type": "markdown",
"id": "5d696a4b-4deb-4da2-8864-252f787e4478",
"metadata": {},
"source": [
"
\n",
" \n",
"### Definition - Prim und Irreduzibel\n",
"***\n",
"Sei $(R,+,\\cdot)$ ein Kring. \n",
"Für $a,b\\in R$ schreiben wir $a|b$ (gesprochen \"$a$ teilt $b$\"), falls $R\\cdot b \\subseteq R\\cdot a$.\n",
" \n",
"Ein Kringelement $p\\in R$ heißt irreduzibel, falls $p$ keine Einheit ist und aus $p=ab$ mit $a,b\\in R$ folgt, dass $b$ oder $c$ eine Einheit ist. \n",
"Man nennt $p \\in R$ prim, falls aus $ab|p$ folgt, dass einer der Faktoren $p$ teilt, das heißt es gilt: $a|p \\lor b|p$.\n",
"\n",
"Für $I, J \\unlhd R$, schreiben wir $I|J$ (gesprochen \"$I$ teilt $J$\"), falls $J \\subseteq I$.\n",
"Ein $R$-Ideal $\\mathscr{p}$ heißt Primideal, falls für $\\mathscr{a,b}\\unlhd R$ aus $\\mathscr{a}\\mathscr{b}:=(\\mathscr{a}\\cdot\\mathscr{b})|\\mathscr{p}$ folgt, dass einer der Faktoren $\\mathscr{p}$ teilt, wenn also $\\mathscr{a}|\\mathscr{p}$ oder $\\mathscr{b}|\\mathscr{p}$ gilt. \n",
"Man nennt $\\mathscr{m}\\unlhd R$ Maximalideal, falls es kein echtes Ideal gibt, das echte Obermenge von $\\mathscr{m}$ ist. Das heißt aus $\\mathscr{m}\\subset I \\unlhd R$ folgt $I=R$.\n",
"\n",
"Bemerkung: Sie rechnen schnell nach, dass $R\\cdot x$ für alle $x\\in R$ ein Ideal in $R$ ist. Insbesondere ist $R\\cdot e=R \\ \\forall e\\in R^\\times$. \n",
"
\n",
" \n",
"### Definition - Hauptidealring\n",
"***\n",
"Sie $(R,+,\\cdot)$ ein Kring.\n",
"\n",
"Dann heißt $I\\unlhd R$ Hauptideal, falls $I=R\\cdot a$ für ein $a\\in R$. Wir schreiben auch $(a):=R\\cdot a$, wenn aus dem Kontext klar ist, in welchem Kring wir sind. \n",
"Ist jedes Ideal aus $R$ ein Hauptideal, so nennen wir $R$ einen Hauptidealring.\n",
"
\n",
" \n",
"### 3. Aufgabe\n",
"***\n",
"Sei $(R,+,\\cdot)$ ein Kring.\n",
"- 3.1 Zeigen Sie, dass Primideale Maximalideale sind, falls $R$ Hauptidealring ist.\n",
"- 3.2 Zeigen Sie, dass die Primzahlen in $\\mathbb{Z}$ sowohl irreduzibel als auch prim sind.\n",
"- 3.3 Zeigen Sie, dass $(p)$ für $p\\in \\mathbb{Z}$ prim ein Prim- und damit Maximalideal ist.\n",
"- 3.4 Zeigen Sie, dass $R\\big/I$ für $I\\unlhd R$ Primideal ein Integritätsbereich ist.\n",
"- 3.5 Zeigen Sie, dass $R\\big/I$ für $I\\unlhd R$ Maximalideal ein Körper ist.\n",
" \n",
"Hinweis: Besinnen Sie sich auf Aussagen der linearen Algebra zurück und recherechieren Sie gegebenenfalls.\n",
"Bemerkung: Sie dürfen ohne Beweis verwenden, dass Maximalideale prim sind.\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "b6b5071b-78b9-4c95-b325-1a771efd8e7a",
"metadata": {},
"source": [
"***"
]
},
{
"cell_type": "markdown",
"id": "df00555f-2349-4a14-a40d-df755a44a8f3",
"metadata": {},
"source": [
"Der folgende Codeblock generiert Ihnen bei Ausführung ein Beispiel einer elliptischen Kurve über einem endlichen Körper ($a=2, \\ b=3, \\ p=19$). Sie können gerne eigene Zahlenbeispiele eingeben und sich ansehen, wie die Kurve dann aussieht. Beachten Sie, dass $p$ eine Primzahl sein muss. Im Code ist markiert, wo sie die zugehörigen Werte ändern können. Sie brauchen den restlichen Programmcode nicht zu verstehen."
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "1176f200-bac8-45ae-a767-c540744fc17e",
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEWCAYAAABrDZDcAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/MnkTPAAAACXBIWXMAAAsTAAALEwEAmpwYAAAv40lEQVR4nO2deZwcVbm/nxdCYGCGRcOSsEWUAAqIE0DGCyQwCIohCF41qAioUeNVAUUBEQIkbkBAr17BsLkAQQVZEreEQBB+GZbMGCCYsBqWZBARkLBIWN7fH6c6KZqp6emq7q7K9Pf5fOozvdR5znumu+tU1anzlrk7Qgghmpe18g5ACCFEvqgjEEKIJkcdgRBCNDnqCIQQoslRRyCEEE2OOgIhhGhyBk1HYGZHm9mtseduZu+IHl9gZqdmcN9rZmOzRykGC2Y2zMwmm9n78o6lEmb2ETP7hpkNyTuWNQUz29TM7jOz9RpQ1+lmdlkdvOua2RIz26zSumtUR2BmS83sJTN7Prb8pFI5d/+iu08ZYB0/N7OpZeXf5e7zUsQ7NPqQHzCzF6L4LzGzkdW6BgtmNjLqpOOf4V0Vygw3s+vNbHlUdmTZ+1ua2XVm9rSZPW5mX6xzGzYAfg+8H5hlZu8pe38vM5sTxfNPM/utmQ2vZ0z9xPpx4CLgk8AlZmZl759lZo+Z2XNm9oiZnVKHGD5kZrea2bNm9oSZXWhmbbWup0IMl5lZb9TO+83scxWKnARc6u7/aUR8SUTbkKuibYeX75Ca2cZm9gszezJaTi+95+4vA5cAJ1aqZ43qCCIOcffW2PLlvAPqh6uA8cAngI2AdwPdQGe1ojVxb65CzBvHPsN3V1C9DvwJ+EjC+5cBfwc2Bz4EfNfM9qs64AFgZusAVwN/A/YFJgHXm9l2sdU2AaYDI4FtgRXApfWIpz/M7ADgh4QOa19gO+CsstUuBnZ09w2B9wGfMLPDB+hfOsCdmo2AqcAIYCdgK+DsgdRRof6jzeznA1z9e8DIqJ3jgalmNjrBuy5wFOF7VQRuBT4FPNHHe+cB6xO+a3sCR5rZMbH3rwCOitqUjLuvMQuwFDgg4b2jgVtjzx14R/T458DU6PFY4HHgW8BTkfOT0XufB14BVgLPAzPL6wXWjso+RPiBdwNb9xHPAcBLfb2X1B7gdOCy6PHIqA2fBR4F/kLYGH65zHEXcHj0eEdgDvA0cB/wsX7qHgFcH637IDAx9vpLwFti674n+l+tEz3/DLAYeAb4M7Bt2f/9f4AHgL/3UW+pXUNSfP5DorIjY6+1Rq9tGnttOvCrFP51o//HLrHXNov+H5sCBlwOnA9YbJ0PA/cCmyd424EVNf4tvD2KtT32uT0FjI2e7x59R3eNldkAmAuckODcErgH+GYVv8eRKWI/HLgnevwWwu/xkNjn+SDw6QF4jgZ+nqL+HYDepN8HodN8sOy1eYTObD7RtgF4a/R9eA64s+x7+b7otX9Hf98Xe+9twM2E7ccc4CdEv/sKcT9e+nxjrz0F7BF7/i3glrJ1HgDG9OdeE48IasEWwDDCF/8oYLqZ7eDu0wkf7Fke9lQP6aPs14AjgIOBDQkbxRf7WO8A4A53fyxjrGMIe1EHEXr3I0pvmNk7CXucv49OV8yJ1tksWu+nZvauBO8MwhdrBPDfhL3oTndfDnTxxr3vTwBXufsrZvZhwpftcMLG8ZbIFefDwHuBd6ZrclVY2d/S450TC4RTFHuXv+7hUPpKwt5XiSOAG9z9nx74pLtP8ugXFpW71sPpw38kVLkvoaNIiuenUUx9LXf3VcbdHyIc8l9uZusTjjh+7tEpTHdf4O5vd/e7Y2VecPdOdz+nrP6TzOx5wvdhA8J3qJ6s+n+4+9OE39CF0bns84CF7v7LWlca/Z9fBJYQOoI/JKy6C2FHqpwJwJGE7cbbCb+TSwmd2WJgclTPWwinDv+X0FmcS/iNvjXyXEHYgRwGTCFsgzI1rexx+Xd/MeFsRDLV9qZ5LoQ9kOeBZ2NLaU/2aAZ+RPAqsEFs3d8Ap5avW1Zv6YjgPuDQAcR6IXDlANpT6Yhgu9j7bcALRHvgwHeAS6LHH+fNewI/Ayb3Ue/WwGtAW+y17xHtXQGfA26MHhvwGLBv9PyPwGdj5dYidISlmBzYv582l9oV/wz73EPto+ybjgii128FfgysR9j7fhq4L+V37L1Re9eKni+gnyOrAfh2jeLZp06/iesJe/F3A+tm8BjhyO+M+PdiAN/fkVXW837CkeSostd/HLVjOfDWAbqOpsojAsIR/d7At4mOcPtY55Ty3y7hiOCU2PNpwB9jzw8hdGAQOos7ysp3RfFuw5u3P1eQ/ojgMuB3hG3DOwhHgS+XrXM5cFp/7jXxiODD7r5xbLkwheMZd38h9vwRwp7xQNia8M+uxL+AWgwQrjqicPcVhD2NCdFLEwgfMoQjg/fG9yYJA4Rb9OEcATwd+Uo8QtjTgTC20WFmIwh7b07Y8y/V86NYHU8TNiJbxlwDOQoaFvsMz6m8er98knC4/RjhtM3lhB9N1bj77YTOdoyZ7Uj4cV2fxmXhqrU/Ase6+y2V1k/JhYQ9wB97OKJJhQf+SjgNdkZf65jZNmXfr22Au2OvfaK/OsxsL8JG77/d/f6yt6dH7bjU3f/Vj+Onsfp/ShjT6Pfoqaydr7n7rYRxikkJqz1D2LCWEz/ie6mP563R4xGE31Oc0u9rBH1vf9Ly1ajuB4DrWH2kH6eNsMOVyJrYEdSCTaJTKSW2IeyJQNjo9cdjhMPCStwA7GlmW/WzzguEgZ4SfW20y+OZARxhZh1AC3BTLK6byzrJVnfv68u+HHhL2ZUb2wDLANz9WWA28DHCaaEZHu1aRPV8oayeFnef30/MdcXdH3H3ce6+qbu/l3A4fkcG5S8Ip4eOJJwSq/rKETPblvAdmOLuv6qw7gVlV1HFl/5OKbUSBoMvBk6PTklkZQgJ3293fzT+uRPGrnaNvZZ4Sim6sup64DPuPrfsvbUJR6+/BCZFHWifuPuXYvV/CbgiVv+utWgn4ehqVBWucpYTdpjilH5fvfS9/UmFuz/t4XTlFu7+LsI2vfy7vxNhLDGRZu0IAM6ILs3aBxgH/DZ6/R+EqyuSuAiYYmbbW2DX2Lm/Vbj7DYRz9teY2WgzG2JmbWb2RTP7TLTaQmCCma1jZrsTztVX4g+EL9mZwK/d/fXo9VnAKDM7MvKtY2Z7mNlOfcT2GGHQ63tmtp6Z7UoYlL48ttoVwKcJYwXxH/gFwMmlsQcz28jMPjqAuDNh4Xru0pUP61rs+m4z2yn63w41s08BBxLOy6blV8BhhM6g6nPVZrYlcCPwf+5+QaX1PVze3JqwJI3xAPwI6Hb3zxGOFCvWVRbnWmb2BTPbJPou70kY6J9bqWyV9exMuNDhK+4+s49VvhX9/QxwDvDLqHOoVf2bmdkEM2s1s7XN7CDC2M+NCUXuADaOPsc0/IHwW/xE9Lv/OGG8bJa7P0I43Vja/uxNOK3UX/zx7/vQ6Ddr0XtvN7O3Ru36IOGCl6mxslsSxjBu6zfigZ5bK8JCOCf5EmGcoLRc46vPF1Zz1dAphBH3R4EjY+W2J2ygnwWujdUbv2ro24TLFVcQrgjYKiHeoYTD7AcJe/+PEDqSbaL3twNuj9pRGlwqHyN409U1hD1AJ3a1QPT6DpHnn4RTUzcCuyXEthWh83iacKrri2Xvt0Ttu7ePskcSzuc+RzhCuKSv/3tCvYntqvDZe/kSe++4qM0vEMYLdq/gep4K5+wJe/NLiV0dVEWsk6MY49/T52v8WziUsIf5luh56WqbT1bhWIuwgX46ivF+wkZ5QG1mgGMEhAHV18v+H/dG740mnIop/VbXBv4fsfPx/XiPZgBjBISLGm4m/Kafi767EyuUORs4MfZ8HvC52POp8boJF4c8GHu+N2FA+N/R371j721HONX6PAO4aij6P5d//0dG732McATyImG7dVBZ2W8A51b6H1m0ctNgYULGZe7e3ykb0eSY2SXAcnf/dt6xiMZjZqUr4t7j7i/lHU8aLMwduItwoceT/a27xk1SEqLeWJgkdTjhKhrRhLj7PwnzctZYPFw8MKA2NPMYgSgQ/QyYVnXeuwZxTAEWAWe7+98bWbcQedF0p4aEEEK8ER0RCCFEk7NGjREMGzbMR44cmarsihUraGvLlvBQjsHpKEIMcshRT0d3d/dT7r5p4gq1vKSt3svo0aM9LcuWLUtdVo7B7ShCDHLIUU8HsMD72bbq1JAQQjQ5TdMRXHhhmpREcjSDowgxyCFHIxxJNE1HIIQQom/UEQghRJPTNB3BmDFj5JCjsDHIIUcjHEnkOqHMzI4FJhLy2V/o7j/sb/3dd9/dFyxY0IjQhBBi0GBm3e6+e9L7uR0RRKlpJxJuuPxuYJyZbV+v+qZNm5apfFcXnHHGNLq68nVA9rbUwjGY2lKEGOSQoxGOJPI8NbQTcJu7v+jurxLSxB5Wr8qef/751GW7uqCzE+B5OjtJtfGrhaNElrbUwjGY2lKUGOSQoxGOJHI7NRTdMOU6oINwj4G5hEkPXylb7/OEmy2w+eabj540afUNtyZOnAi88bKqMWPGMHbsWKZNm7bqHzd8+HB6e3tpb2+np6dn1bpf+9rXWL58OVdeeeWq18aNG8fo0aM544zVd+szG8WZZx7Bqae+8Q5+kydPpru7m1mzZq16bcKECYwYMYJzz119X5T29nYWLTqERx6ZzvDhvdGrrUye/HXmzZvHzTffnKpNn//855k5c2aqNpXinzFjBvfff/8bXhtIm3p62mlv76G3d/iqNrW2tvL1r1fXpnhMWds0atQojjjiiNRtam9v55BDDmH69On09qZvU9rPqRRrljaV+/JuU96fU6ldWdoUr7sIbUrzOY0fP77fU0O5zhQm3BWrB/gL4e5K5/W3fpaZxT/72c9Sl50/372lxf0LX/iZt7SE53k4SmRpSy0cg6ktRYlBDjnq6aDCzOLCZB81s+8Cj7v7T5PWyXOwuKsL5s2DsWOhoyM/R1EYTG0RYrBT2MFiCPcSjf5uQ7gRyIx61TVzZl+3Sh04HR2w884zM230auGA7G2phWMwtaUIMcghRyMcSeQ9j+BqM/sbMBP4H3d/pl4Vxc/7ySFH0WKQQ45GOJLINQ21u++TZ/1CCCHyPyIQQgiRM4UZLB4IWQaL874xhBzFdRQhBjnkqKej6IPFx5vZvWa2yMxmmNl69apr+fLlcshR2BjkkKMRjiTyTDGxJfBVYHd33xlYG5hQr/rKJ9rIIUeRYpBDjkY4ksh7jGAI0GJmQ4D1gfp1eUIIIfqkCNlHv0NIMTHb3T/Zxzq5p5goTR/vK0VDEaaP55FiovS/LP1v07ZJKSaUYqJSm5RiYhCnmAA2AW4ENgXWAa4FPtVfmSwpJhYsWJC6rByD21GEGOSQo54Oippiwsw+CnzA3T8bPf80sJe7fympjO5HIIQQ1VPkq4YeBfYys/XNzIBOYHG9Kis/LSKHHEWKQQ45GuFIIreOwN1vB64iZB+9J4plel7xCCFEs5J3ionJwOQ8YxBCiGYn78tHG8aoUaPkkKOwMcghRyMcSTRNigkhhGhWCjtYbGY7mNnC2PKcmR1Xr/pmzMh+qwM5BqejCDHIIUcjHEnkOVh8n7vv5u67AaOBF4Fr6lVffJKHHHIULYaiOLq6gqOrK9845KiPI4mijBF0Ag+5+yN5ByJEs9LVBZ2d4XFnJ5k7A7HmUIgxAjO7BOhx95/08Z5STCjFROFSFwzGFBNDhkzk/PNh4kSlmIi3qRlSTOTeEZjZUEKyuXe5+z/6W1eDxULUj9IRwcqVMHQozJ1L5ntSi2JQ2MHiGB8kHA302wlkpbu7Ww45ChtDERwdHWHjf/rp3Zk7gbzbIkd1FKEjOAKo33B4RPzQTA45ihZDURwdHfDaa7MyHwkUoS1yDJy871C2PvB+4Hd5xiGEEM1M3ikmXgTemmcMQgjR9PSXo7poS5b7ESxZsiR1WTkGt6MIMcghRz0dVLgfQRHGCBrCiBEj5JCjsDHIIUcjHEnkPUawsZldZWZLzGyxmdXtYrXya4HlkKNIMcghRyMcSeR9RPAj4E/uviPwbup4YxohikxpFq9m84o8yDPp3IbAvsDFAO6+0t2fzSseIfJCqR1E3uR5z+LdCHck+xvhaKAbONbdXyhbryYpJoYPHw6QaUr8eeedx3PPPbfq9aJMH0/Tpg033JDjjz8+05R4gN7e3kxt+u53v8srr7xSkzYVfZp/pTY98sg2/PKXx3DqqenbtGjRIhYtWlSYNuX9Oe24447ss88+mdp07bXX8vDDDxemTYMqxYSZ7Q7cBvyXu99uZj8CnnP3U5PKKMWEGIwotYOoN0VOMfE48LiHexdDuH9xe70qmz49++2Q5RicjrxjKKV2OO206Zk7gbzbIkexHUnkeT+CJ4DHzGyH6KVOwmmiulA63JJDjiLG0NEB7r2ZjwSK0BY5iutIIteZxcBXgMujDKQPA8fkHI8QQjQdeaeYWAgknreqJa2trXLIUdgY5JCjEY4kcr8fQTVosFgIIaqnyIPFDWXevHlyyFHYGOSQoxGOJPJOMbHUzO4xs4VmVtdd/fLb18khR5FikEOORjiSKMIRwX7uvlt/hy1Z0fR9IYRIpggdQV3R9H0hhOifXAeLzezvwDOAAz9z9zfNmKhFione3uFcf/049tijm/b29FPiL730Uh599NFVrxdl+niaaf7bbLMNxxxzTKYp8aNHj2bWrFmZ2nT22Wfz4osv1qRNRZ/mX6lNe++9N52dnZnatNZaa3HFFVcUpk15f04f/vCH2XTTTTO1adGiRcyePbswbapHiolcbzQDjIj+bgbcBezb3/ppbkwzf757S4v7llsu85aW8Dwty5YtS19YjsI6ihCDHHLU00GRb0zj7sujv08C1wB71rqO0vT9iRMvzDx9P94DyzF4HEWIQQ45GuFIIs801BuYWVvpMXAgsKj/UukobfyVyEsIId5MnjOLNweuMbNSHFe4+59yjEcIIZqS3DoCd3+YcB+ChjBmzBg55ChsDHLI0QhHEkoxIYQQgxylmIiYNm2aHHIUNgY55GiEI4ncOwIzW9vM/mpmsyqvnZ7StbVyyFHEGOSQoxGOJHLvCIBjgcV5ByGEEEWl3mly8k46txXwIeCietdVunm9HHIUMQY55EiilCant3d43dLk5J1i4irge0AbcIK7j+tjncwpJtakKfFqk9qkNqlN8TZNmTKP119f3aYhQyZyzDGDJMUEMA74afR4LDCrUpk0KSZKXH/99anLyjG4HUWIQQ45kiilyRk//vrUaXIocIqJ/wLGm9lS4EpgfzO7rF6VxXt5OeQoWgxyyJFEKU1Oe3tP5jQ5SeTWEbj7ye6+lbuPBCYAN7r7p/KKRwghikq90+QU4aohIYQQOdI0M4tXrFhBW1tbpvrlGJyOIsQghxz1dGhmccTy5cvlkKOwMcghRyMcSTRNRxC//EsOOYoWgxxyNMKRRJ73I1jPzO4ws7vM7F4zO6NyKSGEELUmz/sRvAzs7+7Pm9k6wK1m9kd3vy3HmIQQounI834EDpSyKK0TLXUbuR437k2TluWQozAxyCFHIxxJ5J1iYm2gG3gH8H/ufmIf6yjFhNqkNqlNalOGNhU2xUR8ATYGbgJ27m+9LCkmTj/99NRl5RjcjiLEIIcc9XRQ4BQTq3D3Z4F5wAfyjUQIIZqPPK8a2tTMNo4etwAHAEvyikcIIZqVPK8aGg78IhonWAv4jbvX7S5lo0aNkkOOwsYghxyNcCTRNCkmhBCiWVGKiYgZM2bIIUdhY5BDjkY4kmiajiB+SZccchQtBjnkaIQjiTwHi7c2s5vMbHGUYuLYvGIRQohmJs8jgleBr7v7TsBewP+Y2TtzjKdpKN38uh43wRZCrHkUZrDYzK4DfuLuc5LW0WBxdrq6oLMTVq6EoUOp263vhBDFodJgcZ6Xj67CzEYC7wFu7+O9eIqJN0zrrmaq9ejRo1m+fHmm6ePnn38+Tz755KrXizJ9vNo2nXgiPPHEZlx44STmzJnB7NnppsSPGDGC7u7uTG36/ve/z8svv5y5TfHPqajT/Cu1aZddduHwww/P1KannnqKG264oTBtyvtz2nvvvdlpp50ytemWW27hzjvvLEyb0nxOFelv2nEjFqCVkG/o8ErrKsVEdsf8+e4tLcHR0hKe5xFHkRxFiEEOOerpoMgpJqL001cDl7v77/KMpVno6Aing0CnhYQQgTyvGjLgYmCxu59baX1RO0obf3UCQgggv1NDwN6E+w/cDSyMloP7K5Pl1NCSJUtSl5VjcDuKEIMcctTTQYVTQ3nemOZWwBpV34gRI+SQo7AxyCFHIxxJNM3M4vgIvRxyFC0GOeRohCOJpukIhBBC9E3eVw1dYmZPmtmiPOMQQohmJu8jgp/ToLuStbe3yyFHYWOQQ45GOJLIPcVENKt4lrvvXGldpZgQQojqWSNSTPRHrVJMlP5mmRIfT4cAxZk+nqZN6667LieddFKmKfGltmRp05QpU3j99ddr0qaiT/Ov1KaNNtqI4447LlObbrzxxjekQcm7TXl/TsOGDeOwww7L1KZLL72UZ555pjBtGqwpJkYCiwayrlJMyFEPRxFikEOOejoocooJIYQQ+dM0HUFra6scchQ2BjnkaIQjiVwHi81sBjAWGAb8A5js7hcnra/BYiGEqJ5C37ze3Y9w9+Huvo67b9VfJ5CVefPmySFHYWOQQ45GOJJomlND8VF3OeQoWgxyyNEIRxJN0xEIIYTom7xTTHzAzO4zswfN7KQ8YxFCiKalv2tL67kAawMPAdsBQ4G7gHf2VybLPIJly5alLjvYHPPnu0+duizTbSprEUdRHEWIQQ456ukg6zwCM/uymW1Shz5oT+BBd3/Y3VcCVwKH1qEeEaOrCzo74fzzw9+urrwjEkLkzUBSTGwB3GlmPcAlwJ+jHiYrWwKPxZ4/Dry3fKVapZjo7e2lvb0905T4eD1QnOnj1bbpxBPD61OmTGbOnBnMnp1uSnxPT8+q/23aNsVfW5NSF9TjcyrFmqVN5b6825T351RqV5Y2lf/u825TbikmCHcSO4iw1/4g8F3g7QMp24/zo8BFsedHAj/ur4xSTGR3zJ/v3tISHC0tnun0UN5tqZWjCDHIIUc9HdQixUQkeiJaXgU2Aa4ys7MGUj6Bx4GtY8+3ApZn8IkB0NEBc+eGx3Pn6gb2QogBnBoys68CRwFPARcB33D3V8xsLeAB4Jsp674T2N7M3gYsAyYAn0jpqsiYMWPkiOjogJdfHpO5EyhCW2rhKEIMcsjRCEcSFVNMmNmZwMXu/kgf7+3k7otTV252MPBDwhVEl7j7d/pbXykmhBCiejKnmHD30/rqBKL3UncCUfk/uPsod397pU4gK9OmTZNDjsLGIIccjXAk0TQzi0sj6XLIUcQY5JCjEY4kmqYjEEII0Te5dARm9lEzu9fMXjezxPNWtaR0u0o55ChiDHLI0QhHErncj8DMdgJeB34GnODuAxoB1mCxEEJUTyHvR+Dui939vkbWOaDZdXI0paMIMcghRyMcSQwkxUSu1DLFBJBpSnxPT88byqedPt7T05N5+nhvb2+maf4AhxxySKYp8T09PfT29maaEh//n2ZJXdDT05Npmn9PT0/maf5tbW2ZU0wccsghmVIXlH9H07Qp7siSYqKnpydzOoZRo0ZlTjExevToTCkmyv+nadoUd2RJMdHT05Nfiok0C3ADsKiP5dDYOvOA3QfqVIoJOerhKEIMcshRTwcVUkzU7YjA3Q+ol1sIIUTtyPvm9fNo0GDxihUraGtrS1VWjsHtKEIMcshRT0chB4vN7DAzexzoAH5vZn+ud53Ll2fPZyfH4HQUIQY55GiEI4m8rhq6xt23cvd13X1zdz+o3nWWD8rJIUeRYpBDjkY4ktDMYiGEaHLUEQghRJOT1xjB2Wa2xMzuNrNrzGzjetc5btw4OeQobAxyyNEIRxJ5pZg4ELjR3V81sx8AuPuJlcopxYQQohnp6oJ582Ds2HR3FSzkVUPuPtvdX42e3ka4TWVdKZ9VK4ccRYpBDjmS6OqCzk5YufIMOjvD81qT6zwCADObCfza3S9LeD+eYmL0pEmTVr1XbYqJUlqEEtWmmCj/MNOmmIB06RjSpi5ISjExefLkzCkm4uk70rQpHlPWNmVJMVFqU56fUynWLG0q9+Xdprw/p1K7srQpXncebZoyZR6vv766TUOGTOSYY6r7nMaPH9/vEUHeKSZOAa4h6pAqLUoxIUc9HEWIQQ45kpg/372lJThaWsLzaqGoKSbM7ChgHNAZBVpXRo0aJYcchY1BDjmS6OiAuXNhzpxRzJ2bboygEnkNFn8AOBcY4+7/HGg5DRYLIUT1FHKwGPgJ0AbMMbOFZnZBvSucMWOGHHIUNgY55GiEI4lc7kfg7u9odJ3xARw55ChaDHLI0QhHEppZLIQQTY46AiGEaHLyGiyeAhxKuIH9k8DR7l4xx6oGi4UQonqKOlh8trvv6u67AbOA0+pZWVcXTJ3anXlGXnd3d+ZY5CieowgxyCFHIxxJ5JVi4rnY0w2Auh2WlKZnv/barMzTs+OzA+UYPI4ixCCHHI1wJJFbigkz+w7waeDfwH5J8wlqkWKit3c4w4f30tPTTnu7UkzE41eKieJ8TqVYlWJCKSb6a1Oaz6nQKSai9U4GzhiIM02KiVpMzy6R91RzOerjKEIMcshRTwcVUkzUrSMY6AJsCywayLppcw3Nn+8+deqSTJ2Au/uSJUuyCeQopKMIMcghRz0dlTqCXCaUmdn27v5A9HQ8sKSe9XV0wM47j6CtLZtnxIgRmWORo3iOIsQghxyNcCSR11VD3zezRWZ2N3AgcGy9Kyw/zyeHHEWKQQ45GuFIIq8UEx/Jo14hhBBvRjOLhRCiyWmajqC9vV0OOQobgxxyNMKRRK63qjSzE4CzgU3d/alK6yvFhBBCVE9RU0xgZlsD7wcebUR906dPl0OOwsbQ1QVnnjk9cxqUIrRFjuI6ksjz1NB5wDepY3qJOKXZenLIUbQYSmlQ3Hszp0HJuy1yFNuRRF7ZR8cT7lV8rJktBXZPOjVUixQTpTQIpbQIJZRiQikmivQ5AUyZMplTT1WKiXiblGJikKaYAG4HNorWWwoMG4gz7cxid/dzzjkndVk5Brcj7xhKaVC+/vVzMqdBybstchTTQYWZxQ0/IjCzXYC5wIvRS1sBy4E93f2J/spqsFgMVrq6YN48GDs2zIQXopYUbrDY3e9x983cfaS7jwQeB9ordQJZmTdvnhxyFDaGjg7o6JiXuRMoQlvkKK4jiaaZR1B+3lAOOYoUgxxyNMKRRC4pJuJERwVCCCFyommOCIQQQiTQ30hy0ZYsVw0tW7YsdVk5BrejCDHIIUc9HVS4aiiXIwIzO93MlpnZwmg5OI84hBBC5Dyz2N13i5Y/1Luy+OQLOeQoWgxFcXR1BUfWVBdFaIscA0djBEIIYHWqCyBzqguxZpFXionTgaOB54AFwNfd/ZmEdZViQikmCpe6oF4pJiZPnpypTVlSTAwZMpHzz4eJE5ViIt4mpZioX4qJzYG1CUck3wEuGYgzy2DxTTfdlLqsHIPbUYQYiuAopbrYb7+bMqe6yLstcrwRipZiohwzGwnMcvedK62rFBNC1BeluhicFC7FBICZDY89PYxwpFBXpk2bJocchY2hKI6ODhg6dFrmTqAIbZFj4OQ1s/gsM9uNcC+CpcAX6l1h6byZHHIUMQY55GiEI4lcOgJ3PzKPeoUQQryZprl8dPjw4ZVXkqMpHUWIQQ45GuFIIvfB4mrQYLEQQlRPIQeLAczsK2Z2n5nda2Zn1bu+mTNnyiFHYWOQQ45GOJLI66qh/QjzCXZ193cB59S7zvgkETnkKFoMcsjRCEcSeR0RTAK+7+4vA7j7kznFIYQQTU9eKSYWAtcBHwD+A5zg7ncmrKsUE0oxUbjUBYMxxUSjvntKMVG8FBN16wjM7AZgiz7eOoWQVuJG4FhgD+DXwHZeIZgsg8UrVqygra0tVVk5BrejCDHIIUc9HbkNFrv7Ae6+cx/LdYQb1v8uSoNxB/A6MKxesQAsX75cDjkKG4MccjTCkUReYwTXAvsDmNkoYCjwVD0rLD9klkOOIsUghxyNcCSRV4qJS4BLzGwRsBI4qtJpISGEEPUhrxQTK4FP5VG3EEKIN9I0KSbGjRsnhxyFjUEOORrhSEIpJoQQYpBTyBQTZvZrM1sYLUujeQV1pfwaejnkKFIMcsjRCEcSuXQE7v5xd9/N3XcDrgZ+l0cc1VC6kXeWG3rXwlEUBlNbhGh2ch0jMDMDPgbMyDOOSnR1QWdneNzZmW7jVwtHURhMbRFC5DxGYGb7Auf2O/W5Rikm2traaG1tTTUl3mwUZ555BMcffw6trS+ser2a6eOLFh3CI49MZ/jw3ujVViZPzm+a/wYbbMAJJ5yQekp8T087G2zwPBtuuGJVm9JMiZ86dSqvvfZaTdpU9Gn+ldq02WabMWnSpExtuuOOO3j44YcL06a8P6dtttmGgw46KFObrrzyyjdM5sq7TYMmxUQ0uxgzOx940N0HdDPOvAaLS3vAK1fC0KEwd271N/auhaMoDKa2CNEMFDXFBGY2BDickGeo7syYkf7sU0dH2NiddtqM1Bu9WjhKZGlLLRyDqS1FiUEOORrhSCLPMYIDgCXu/ngjKosfrqWhowPc78+00auFA7K3pRaOwdSWIsQghxyNcCSRZ0cwgYIPEgshRDOQV64h3P3ovOoWQgixGs0sFkKIQU4hZxbnQXd3txxyFDYGOeRohCOJvFJM7GZmt0UpJhaY2Z71rjN+Ha8cchQtBjnkaIQjibyOCM4CzohSTJwWPRdCCEApTBpNXh2BAxtGjzcC6ncPNiHEGoVSmDSeXAaLzWwn4M+AETqj97n7Iwnr1iTFxJgxY7j//vszTYm/8MIL3zDVvCjTx9O0acSIEUycODHTlPhRo0Zx8803Z2rTD37wA/7zn//UpE1Fn+ZfqU277747H/rQhzK16aWXXuK6664rTJuyfk5XXjmBI48cwSuvpPucDjzwQLbddttMbbrzzju55ZZbatYmpZgInAJ0Aje7+9Vm9jHg8+5+QCVnlquGVqxYQVtbW6qycgxuRxFikGM1pSOCoUNXsHJlW6bZ63m3pSiOoqaYOIrVqad/C9R9sDje+8ohR9FikGM1pRQmxx9/buYUJnm3pWiOJPIaI1gOjIke7w88kFMcQogCUtr4K5lhY8hrZvFE4EdR4rn/EI0BCCGEaDy5dATufiswupF1tre3yyFHYWOQQ45GOJJQigkhhBjkKMVExPTp0+WQo7AxyCFHIxxJ5JVi4t1m1mVm95jZTDPbsHKpbJSuzZVDjiLGIIccjXAkkdcRwUXASe6+C3AN8I2c4hBCFBClmGgseXUEOwB/iR7PAT5S7wpbW1vlkKOwMcixmtKEshUrWjOnmMi7LUVzJJFXion5wA/c/Toz+xohAV2fU+ZqlWKimVMXqE1q05rapqwpJorYpiKmmMDd67IANwCL+lgOBXYEZgPdwGTgXwNxjh492tNy0003pS4rx+B2FCEGOVYzf757S4v7fvvd5C0t4XkecQwmB7DA+9m25pJiwt2XuPuB7j6acN/ih+oVR4l4jyqHHEWLQY7VlFJMjBlzc+YUE3m3pWiOJPK6amiz6O9awLeBC/KIQwhRTJRiorHkNVh8hJndDywh5B26NKc4hBBC9HfeqGhLljGCZcuWpS4rx+B2FCEGOeSop4O8xgiEEEKsGTRNRxC/1EoOOYoWgxxyNMKRRNN0BEIIIfpGHYEQQjQ5a1QaajP7J9DnTe4HwDDgqYwhyDE4HUWIQQ456unY1t03TXy3v5HkwbRQYdRcjuZ1FCEGOeRohCNp0akhIYRoctQRCCFEk9NMHUEtbu8jx+B0FCEGOeRohKNP1qjBYiGEELWnmY4IhBBC9IE6AiGEaHKaqiMws3ebWZeZ3WNmM81swxSO3czsNjNbaGYLzGzPFI5fR+UXmtlSM1tYrSPyfMXM7jOze83srBTlTzezZbFYDk4Zxwlm5mY2LEXZKWZ2d1T/bDMbkcJxtpktiTzXmNnGKRwfjf6Pr5tZ8p2c+i77gehzeNDMTkpR9yVm9qSZLaq2bMyxtZndZGaLo3Ycm8KxnpndYWZ3RY4zKpfq07O2mf3VzGZVXjvRsTT6nS40swUpym9sZldF34vFZlZVQmsz2yH2u1hoZs+Z2XEp4jg++l8uMrMZZrZeCsexUfl708QwIOp1XWoRF+BOYEz0+DPAlBSO2cAHo8cHA/MyxjQNOC1Fuf0Id4FbN3q+WQrH6cAJGePfGvgzYaLfsBTlN4w9/ipwQQrHgcCQ6PEPCLdBrdaxE+Fe2vOA3asotzbhxkrbAUOBu4B3Vln3vkA7sCjD5zAcaI8etwH3p4jDgNbo8TrA7cBeKWL5GnAFMCtDe5am+T7Fyv8C+Fz0eCiwcQbX2sAThElZ1ZTbEvg70BI9/w1wdJWOnQl3dlwfGBL95rdP25akpamOCAg/9L9Ej+cAH0nhcKB0JLER4X4KqTAzAz5GuEtbtUwCvu/uLwO4+5Np48jIecA3Cf+XqnH352JPN0jjcffZ7v5q9PQ2YKsUjsXufl+15YA9gQfd/WF3XwlcSbgdazV1/wV4OkXdcUevu/dEj1cAiwkbomoc7u7PR0/XiZaqPg8z2wr4EHBRNeVqSXSkvy9wMYC7r3T3ZzMoO4GH3D1NVoMhQIuZDSFszKvdXuwE3ObuL0bf8ZuBw1LE0S/N1hEsAsZHjz9K2JutluOAs83sMeAc4OQM8ewD/MPdH0hRdhSwj5ndbmY3m9keKWP4cnRK5RIz26SagmY2Hljm7nelrLvk+U70//wkcFoWF+FI748ZHdWwJfBY7PnjVLkBrjVmNhJ4D2GPvtqya0enKp8E5rh7tY4fEnYMXq+27jIcmG1m3Wb2+SrLbgf8E7g0OkV1kZltkCGWCaTYWXP3ZYRtxKNAL/Bvd59dpWYRsK+ZvdXM1iechUiz3eqXIbUW5o2Z3QBs0cdbpxA2Ev9rZqcB1wMrUzg6gePd/Woz+xhhr+OAahzufl30+Aj6+YJViGMIsAmwF7AH8Bsz286j48kBOs4HphB+dFMIp6k+U0X5bxFOy/RLpf+Fu58CnGJmJwNfBiZX64jWOQV4Fbg8TRyV2pGA9fFabtdkm1krcDVwXNnR1oBw99eA3aJxlmvMbGd3H9DYhZmNA550924zG1tt3WX8l7svt3Bb2zlmtiQ6choIQwin2r7i7reb2Y+Ak4BTqw3CzIYSdh6r3uGLdqwOBd4GPAv81sw+5e6XDdTh7ovN7AeEMxjPE049vtp/qRTU+lzTmrIQ9qjvSFHu36yef2HAcynrHwL8A9gqZfk/AWNjzx8CNs3w/xhJFeeogV0Ie41Lo+VVwp7PFhli2LaaGMrKHgV0Aetn/F7Mo7oxgg7gz7HnJwMn1/v/n+BYhzBe87UsnphvMlWMIQHfIxwRLSWcU38RuKwGcZxeZRxbAEtjz/cBfp+y7kOB2SnLfhS4OPb808BPM/4vvgt8qRafb3xpqlND0d4FZrYW8G3gghSa5cCY6PH+QJrTOhCOIpa4++Mpy18b1Y+ZjSIMiFWVmdDMhseeHkY4DB0Q7n6Pu2/m7iPdfSRhA9Du7k9UGcP2safjCfexrgoz+wBwIjDe3V+stnxG7gS2N7O3RXuPEwhHmw0lGm+6GFjs7uemdGxauuLKzFqIvqMDLe/uJ7v7VtH3YQJwo7t/KkUcG5hZW+kx4aizmu/mE8BjZrZD9FIn8Ldq44jo96i9Ao8Ce5nZ+tHn00kYu6mK2HZrG+DwDPEkU+uepcgLcCzhaor7ge8T7dlX6dgb6CYcot0OjE4Zy8+BL2Zoy1DgMsIPpAfYP4XjV8A9wN2EjdfwDPEsJd1VQ1dHbbgbmAlsmcLxIOE8/cJoSXPl0WGEzuxlwpHan6soe3D0nXqIcJqp2rpnEM4hvxLF8NmU30uP/o+l/8PBVTp2Bf4aORaR4mq2mGssKa8aIpzjvyta7k35P90NWBC15VpgkxSO9YF/ARtl+D+cQehMF0W/t3VTOG4hdGR3AZ1pY+lvUYoJIYRocprq1JAQQog3o45ACCGaHHUEQgjR5KgjEEKIJkcdgRBCNDnqCIQQoslRRyCEEE2OOgIhMmBme0RJ+9aLZsTea2Y75x2XENWgCWVCZMTMpgLrAS3A4+7+vZxDEqIq1BEIkZEox9CdwH+A93nI4CnEGoNODQmRnbcArYQ7g1V9K0Ih8kZHBEJkxMyuJ9yZ7G2ExH1fzjkkIapi0N2YRohGYmafBl519yvMbG1gvpnt7+435h2bEANFRwRCCNHkaIxACCGaHHUEQgjR5KgjEEKIJkcdgRBCNDnqCIQQoslRRyCEEE2OOgIhhGhy/j8PxxFqu+PySQAAAABJRU5ErkJggg==\n",
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"# ALGORITHMUS 2\n",
"import matplotlib.pyplot as plt\n",
"import numpy as np\n",
"\n",
"def legendre_symbol(a, p):\n",
" return pow(a, (p - 1) // 2, p)\n",
"\n",
"def plot_elliptic_curve(a, b, p):\n",
" x_vals = []\n",
" y_vals = []\n",
"\n",
" for x in range(-((p-1)//2), (p-1)//2 + 1): # Symmetrisches Zahlensystem um die Null\n",
" y_squared = (x**3 + a * x + b) % p\n",
" if legendre_symbol(y_squared, p) == 1:\n",
" y = pow(y_squared, (p + 1) // 4, p)\n",
" x_vals.extend([x, x])\n",
" y_vals.extend([y, p - y])\n",
"\n",
" # Umrechnung der y-Koordinaten\n",
" y_vals = [(y - (p-1)//2) % p - (p-1)//2 for y in y_vals]\n",
"\n",
" # Hinzufügen des neutralen Elements (unendlich)\n",
" x_vals.append(float('inf'))\n",
" y_vals.append(float('inf'))\n",
"\n",
" # Gitter hinzufügen\n",
" plt.grid(True, linewidth=1, linestyle='--', color='gray')\n",
"\n",
" # Ganzzahlige Tick-Abstände für x- und y-Achse\n",
" plt.xticks(np.arange(-((p-1)//2), (p-1)//2 + 1, 1))\n",
" plt.yticks(np.arange(-((p-1)//2), (p-1)//2 + 1, 1))\n",
"\n",
" plt.scatter(x_vals, y_vals, marker='.', color='b')\n",
" plt.title(f'Elliptic Curve over F_{p} : y^2 = x^3 + {a}x + {b} (mod {p})')\n",
" plt.xlabel('x')\n",
" plt.ylabel('y')\n",
" plt.show()\n",
"\n",
"# Geben Sie hier ihre eigenen Zahlenwerte ein!\n",
"a = 2\n",
"b = 3\n",
"p = 19\n",
"\n",
"# Elliptische Kurve plotten\n",
"plot_elliptic_curve(a, b, p)\n"
]
},
{
"cell_type": "markdown",
"id": "d218bc94-8e7b-49e6-a8d9-86a2faf724dd",
"metadata": {},
"source": [
"Auch hier gilt noch die geometrisch motivierte Definition der Verknüpfung. Sie können eine Gerade durch zwei Punkte $P$ und $Q$ zeichnen und den dritten Schnittpunkt an der $x$-Achse spiegeln. Sollten sie an den oberen Rand der Graphik stoßen, bevor sie den dritten Schnittpunkt treffen, können Sie einfach den aktuellen $x$-Wert beibehalten und unten weitermachen. Analog machen Sie links weiter, wenn sie an den rechten Rand treffen (im Prinzip genauso wie bei Pacman)."
]
},
{
"cell_type": "markdown",
"id": "bbb207f9-d225-4aa9-af07-e40f23f7c780",
"metadata": {},
"source": [
"
\n",
" \n",
"### 4. Aufgabe\n",
"***\n",
" \n",
"- 4.1 Wählen Sie gewisse $a,b,p$ und berechnen Sie mit dem gegebenen Algorithmus die Lösungsmenge der Polynomgleichung $y^2=x^3+ax+b$ über dem endlichen Körper $\\mathbb{F}_p$.\n",
"- 4.2 Zeichnen Sie den Graphen und wählen Sie zwei Punkte $P,Q$, die die Gleichung lösen (und nicht übereinander liegen). Zeichnen Sie $P+Q$ ein.\n",
"- 4.3 Zeigen Sie, dass ganzzahlige Lösungen der Polynomgleichungen auch Lösungen modulo $p$ sind.\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "bbadb7e6-af26-48bd-ad8e-32b10255dbed",
"metadata": {},
"source": [
"Der Vorteil dabei mit endlichen Körpern zu arbeiten, liegt darin, dass die Berechnungen exakt durchgeführt werden können. Um eine Zahl aus $\\mathbb{F}_p$ zu speichern braucht man höchstens so viele Bits wie zum Speichern von $p$ selbst. Rationale Zahlen hingegen benötigen jeweils nur endlich viel Speicherplatz, aber für jeden vorgegebenen Speicherplatz gibt es eine rationale Zahl, die mehr Speicher benötigen. Runden ist daher praktisch unvermeidbar."
]
},
{
"cell_type": "markdown",
"id": "6a7955e2-fc63-40b2-8f4f-4e3adf2d6c99",
"metadata": {},
"source": [
"
\n",
" \n",
"### Rückblick-Aufgabe\n",
"***\n",
"Suchen Sie sich, wenn möglich, einen (oder zwei) Partner. Sie und ihr Partner nehmen nun die Rolle von Alice und Bob ein. \n",
"Verfassen Sie eine kurze Nachricht und verschlüsseln Sie diese mit dem ECC-Algorithmus und der von Ihnen entwickelten Methode aus Aufgabe 2. Lassen Sie Ihren Partner die Nachricht entschlüsseln. \n",
"Kehren Sie die Rollen nun um und entschlüsseln Sie die Nachricht Ihres Partners.\n",
" \n",
"Sollten Sie zu dritt sein, übernimmt eine Person die Rolle von Claus. Ihre Aufgabe ist es die Nachrichten von Alice und Bob zu entschlüsseln — im Idealfall schafft sie es natürlich nicht. Claus muss die Aufgabe also nicht beenden, sondern kann nach hinreichend vielen Bemühungen aufgeben.\n",
" \n",
"Hinweis: Verwenden Sie für die Berechnung der $x$-Koordinate von $nP$ den unten stehenden Algorithmus 3. Die Parameter legen Sie im dafür vorgesehenen Code-Abschnitt fest (siehe Kommentierung). \n",
"Bemerkung: Der Code ist ausführlich kommentiert, Sie brauchen die programmiertechnischen Details nicht zu verstehen, aber Sie sollten in der Lage sein einen Menschen anzuweisen, wie man die Berechnungen durchführt. Der Code ist ebenfalls in Python und nicht in Julia geschrieben.\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "f8bc4fc0-bc3f-4785-b61e-30cfce99f7b2",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Die x-Koordinate von 8P ist 5\n"
]
}
],
"source": [
"# ALGORITHMUS 3\n",
"def add_points(p, a, b, P, Q):\n",
" # Funktion zum Addieren von zwei Punkten P und Q auf der elliptischen Kurve\n",
" # Rückgabe ist der resultierende Punkt R\n",
"\n",
" # Spezialfall: P ist der neutrale Punkt (Unendlich)\n",
" if P is None:\n",
" return Q\n",
" # Spezialfall: Q ist der neutrale Punkt (Unendlich)\n",
" if Q is None:\n",
" return P\n",
"\n",
" x_p, y_p = P\n",
" x_q, y_q = Q\n",
"\n",
" # Fall 1: P = -Q\n",
" if P == (x_q, -y_q % p):\n",
" return None # Ergebnis ist der neutrale Punkt (Unendlich)\n",
"\n",
" # Fall 2: P = Q\n",
" if P == Q:\n",
" m = (3 * x_p**2 + a) * pow(2 * y_p, -1, p) % p\n",
" # Fall 3: P ≠ Q\n",
" else:\n",
" m = (y_q - y_p) * pow(x_q - x_p, -1, p) % p\n",
"\n",
" x_r = (m**2 - x_p - x_q) % p\n",
" y_r = (m * (x_p - x_r) - y_p) % p\n",
"\n",
" return (x_r, y_r)\n",
"\n",
"def multiply_point(p, a, b, P, n):\n",
" # Funktion zum Multiplizieren eines Punktes P mit einer ganzen Zahl n\n",
" # Rückgabe ist der resultierende Punkt nP\n",
"\n",
" R = None\n",
" current_power_of_two = P\n",
"\n",
" # Schleife über die Binärdarstellung von n\n",
" for bit in bin(n)[2:]:\n",
" if bit == '1':\n",
" R = add_points(p, a, b, R, current_power_of_two)\n",
"\n",
" # Verdopple den aktuellen Punkt\n",
" current_power_of_two = add_points(p, a, b, current_power_of_two, current_power_of_two)\n",
"\n",
" return R\n",
"\n",
"# LEGEN SIE HIER DIE VON IHNEN GEWÜNSCHTEN PARAMETER FEST -------------------------------------------------------------------------------\n",
"p = 23 # Primzahl für den endlichen Körper F_p\n",
"a = 1 # Koeffizient a der elliptischen Kurve\n",
"b = 1 # Koeffizient b der elliptischen Kurve\n",
"\n",
"# Beachten Sie, dass P eine Lösung der Polynomgleich y^2=x^3+ax+b sein muss - vergewissern Sie sich mit Algorithmus 2, dass dies der Fall ist\n",
"P = (5, 7) # Ausgangspunkt auf der elliptischen Kurve \n",
"n = 8 # Ganze Zahl\n",
"\n",
"result = multiply_point(p, a, b, P, n)\n",
"print(f\"Die x-Koordinate von {n}P ist {result[0] % p}\")\n"
]
},
{
"cell_type": "markdown",
"id": "42bd15f4-ec5d-4952-a21c-d226628dd2d2",
"metadata": {},
"source": [
"### Literaturverzeichnis\n",
"- Integer factorization (2023). In Wikipedia, Die freie Enzyklopädie. https://de.wikipedia.org\n",
"- Shor Algorithmus (2023). In Wikipedia, Die freie Enzyklopädie. https://de.wikipedia.org\n",
"- RSA-Kryptosystem (2023). In Wikipedia, Die freie Enzyklopädie. https://de.wikipedia.org\n",
"- Asymmetrisches Kryptosystem (2023). In Wikipedia, Die freie Enzyklopädie. https://de.wikipedia.org\n",
"\n"
]
}
],
"metadata": {
"@webio": {
"lastCommId": "3cdd2328-bc86-4b74-96ff-540a63f8265e",
"lastKernelId": "dfc3c9fc-660a-469e-863a-c346b298c272"
},
"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.9.7"
}
},
"nbformat": 4,
"nbformat_minor": 5
}