{ "cells": [ { "cell_type": "markdown", "id": "beec0854", "metadata": {}, "source": [ "# RSA-Kryptosystem" ] }, { "cell_type": "markdown", "id": "4b52347b", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "71665922", "metadata": {}, "source": [ "
\n", "Ziel des Notebooks:\n", "\n", "- Grundlegende Konzepte der Kryptographie verstehen\n", " - formale Definition eines Kryptosystems\n", " - einfache Substitutionschiffren: Caesar-Chiffre, Vingènere-Chiffre\n", "- Algorithmen zur Berechnung eines minimalen Spannbaums verstehen und anwenden können\n", "\n", "
\n", " \n", "Mathematische Tools:\n", "- Zahlentheorie\n", " - Tonelli-Shanks-Algorithmus\n", " \n", "
" ] }, { "cell_type": "markdown", "id": "f6c7c837", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "2122daa4", "metadata": {}, "source": [ "## Formale Definition von Kryptosystemen" ] }, { "cell_type": "markdown", "id": "514fabd4", "metadata": {}, "source": [ "In der Kryptographie betrachtet man häufig die folgende Situation:\n", "\n", "Alice möchte eine geheime Nachricht an Bob schicken. Eve belauscht die beiden, weswegen sich Alice und Bob ein System ausdenken müssen, mit dem Alice ihre Nachrichten sicher verschlüsselt und nur Bob die verschlüsselte Nachricht (Chiffretext) entziffern kann.\n", "\n", "Mit solchen Kryptosysteme befasst sich genauer die Kryptographie. Das bedeutet u.a. das Untersuchen verschiedener Kryptosysteme auf Sicherheit, Effizienz und das Entwickeln neue Ansätze um bestehende Systeme zu verbessern oder neue Systeme zu etablieren.\n", "\n" ] }, { "cell_type": "markdown", "id": "5bf5fed1", "metadata": {}, "source": [ "
\n", " \n", "Ein Kryptosystem ist gegeben durch $(N,C,K,e,d)$, wobei \n", " \n", "- $N$ die Menge aller möglichen Nachrichten\n", "- $C$ die Menge aller möglichen Chiffretexten\n", "- $K$ die Menge aller möglichen Schlüssel\n", "sind und $e: N \\times K \\to C$, $d: C \\times K \\to N$ Abbildungen, genannt Verschlüsselung und Entschlüsselung, mit der Eigenschaft\n", " $$\\forall n\\in N \\ \\forall c\\in C \\ \\forall k \\in K : \\ d(e(n,k),k)=n$$\n", " \n", "
" ] }, { "cell_type": "markdown", "id": "69a2b161", "metadata": {}, "source": [ "Wir betrachten ein Beispiel. \n", "Eines der einfachsten Kryptosysteme, die Caesar-Chiffre, wird Ihnen sicherlich bekannt vorkommen. Um Operationen auf Buchstaben mathematisch korrekt formulieren zu können, fassen das deutsche Alphabet mit seinen 26 Buchstaben als Gruppe $\\mathbb{Z} / 26 \\mathbb{Z}$ auf, wobei $A \\ \\hat{=} \\ 0, B \\ \\hat{=} \\ 1, \\dots, Z \\ \\hat{=} \\ 25 $. Wir unterscheiden hier vorerst der Einfachheit halber nicht zwischen Klein- und Großschreibung und ignorieren Satzzeichen.\n", "\n", "Mit diesen Festlegungen ist die Caesar-Chriffre gegeben durch $N=C = \\bigcup_{i\\in\\mathbb{N}} \\{1,\\dots,26\\}^i$, $K = \\{1,\\dots,26\\}$ und die beiden Abbildungen $$e(n,k) = e((n_1,n_2,\\dots,n_l),k) = (n_1+k, n_2+k, \\dots, n_l+k) $$ $$ d(c,k) = d((c_1,c_2,\\dots,c_l),k) = (c_1-k, c_2-k, \\dots, c_l-k)$$\n", "für $n\\in N$, $c\\in C$, $k\\in K$." ] }, { "cell_type": "markdown", "id": "043f7577", "metadata": {}, "source": [ "Wir betrachten ein Beispiel. Die Nachricht \n", "\n", "> \"KRYPTOGRAPHIE IST TOLL\" \n", "\n", "soll anhand der Caesar Chiffre mit dem Schlüssel $k=13$ verschlüsselt werden. Wir berechnen zuerst die entsprechende Darstellung der Nachricht in der Gruppe $\\mathbb{Z} / 26 \\mathbb{Z}$ und erhalten:\n", "\n", "> $n = ( 10,17,24,15,19,14,6,17,0,15,7,8,4,8,18,19,19,14,11,11 )$\n", "\n", "Nach der Verschlüsselung sieht der fertige Chiffretext so aus:\n", "\n", "> $c = e(n,k) = ( 23,4,11,2,6,1,19,4,13,2,20,21,17,21,5,6,6,1,24,24) $\n", "\n" ] }, { "cell_type": "markdown", "id": "0b300e4d", "metadata": {}, "source": [ "Sie können sich sicherlich denken, dass dieses Kryptosystem nicht besonders sicher ist. Es lässt sich sogar per Hand mit einem Brute-Force-Ansatz lösen, Eve hat also ein leichtes Spiel." ] }, { "cell_type": "markdown", "id": "b5490a28", "metadata": {}, "source": [ "Ein ähnliches Kryptosystem, das bereits im 16. Jahrhundert verwendet wurde und schwieriger zu knacken ist, ist die Vingenère-Chiffre. Diese ist für Nachrichten der Länge $l\\in\\mathbb{N}$ und ein $m\\in\\mathbb{N}$ mit $m | l$ gegeben durch\n", "\n", "- $N=C = \\{1,\\dots,26\\}^l$\n", "- $K= \\{1,\\dots,26\\}^m$\n", "- $e: N \\times K \\to C, ((n_1,n_2,\\dots,n_l),(k_1, k_2,\\dots,k_m)) \\mapsto (c_1,\\dots, c_l)$ mit $c_i=n_i+k_{i \\text{ mod } m}$\n", "\n", "Dabei heißt $k\\in K$ auch Schlüsselwort und $(n_{i\\cdot m +1},\\dots,n_{i\\cdot m + m})$ für $0\\leq i \\lt \\frac{m}{l}$ nennen wir Block." ] }, { "cell_type": "markdown", "id": "f3cedea9", "metadata": {}, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "1. Erklären Sie anschaulich, was bei der Verschlüsselung der Vingenère-Chiffre passiert. \n", "2. Verschlüsseln Sie die Nachricht $n= \\text{\"KRYPTOSYSTEM\"}$ mit der Vingenère-Chiffre und dem Schlüsselwort $k= \\text{\"ZAHL\"}$.\n", "
" ] }, { "cell_type": "markdown", "id": "120cce4d", "metadata": {}, "source": [ "\n", "\n", "
\n", "Ein Kryptosystem heißt...\n", " \n", "- monoalphabetisch, wenn bei seiner Verschlüsselung jeder Buchstabe des Klartextes durch genau einen anderen Buchstaben des Alphabets ersetzt wird. Die Substitution ist während der gesamten Nachricht konstant. \n", "- polyalphabetisch, wenn jeder Buchstabe des Klartextes durch einen Buchstaben ersetzt wird, der von der Position im Text abhängt, d.h. derselbe Klartextbuchstabe an verschiedenen Stellen der Nachricht durch unterschiedliche Buchstaben ersetzt werden kann.\n", "
" ] }, { "cell_type": "markdown", "id": "f8605536", "metadata": {}, "source": [ "
\n", "Denkanstoß: Sind die obigen Kryptosysteme mono- oder polyalphabetisch?\n", "
" ] }, { "cell_type": "markdown", "id": "af01d05e", "metadata": {}, "source": [ "Auch für das Brechen der Vingenère-Chiffre gibt es inzwischen verschiedene vielversprechende Methoden. Daher gilt auch dieses Kryptosystem als unsicher, außer man wählt $m=l$ und lässt den Schlüssel zufällig generieren. Diese spezielle Form der Vingenère-Chiffre gilt als theoretisch perfekt sicher und nennt man auch Vernam-Chiffre.\n", "\n", "Aber wie erfährt Bob den geheimen Schlüssel? Beim Vingenère-Kryptosystem erstellt Alice diesen und schickt die verschlüsselte Nachricht ab Bob. Bevor Bob aber den empfangenen Chiffretext entschlüsseln kann, muss er den geheimen Schlüssel mitgeteilt bekommen.
\n", "Die Frage des Schlüsselaustauschs stellt in der Kryptographie ein weiteres wichtiges Problem dar.\n", "\n", "Es gibt Kryptosysteme, welche dieses Problem mit berücksichtigen und bereits eine Lösung eingebaut haben, z.B. Public-Key-Kryptosysteme." ] }, { "cell_type": "markdown", "id": "a5f6aaf2", "metadata": {}, "source": [ "\n", "\n", "
\n", "Ein Public-Key-Verschlüsselungsverfahren ist ein Kryptosystem, welches zwei verschiedene Arten von Schlüsseln besitzt:\n", " \n", "- einen öffentlichen Schlüssel, mit dem sich Klartexte verschlüsseln lassen\n", "- einen privaten Schlüssel, mit dem sich Chiffretexte entschlüsseln lassen\n", " \n", "Der private Schlüssel wird von einer Person erzeugt, anschließend geheim gehalten und nicht mitgeteilt. Der öffentliche Schlüssel ist für alle Personen zugänglich.\n", "
" ] }, { "cell_type": "markdown", "id": "d0cf2a50", "metadata": {}, "source": [ "Das RSA Verfahren zählt zu diesen Public-Key-Kryptosystemen.\n" ] }, { "cell_type": "markdown", "id": "c970174d", "metadata": {}, "source": [ "Um die Funktionsweise des RSA-Verfahren zu verstehen, brauchen wir noch ein paar mathematische Grundlagen aus der Zahlentheorie." ] }, { "cell_type": "markdown", "id": "9bef9b40", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "58f5e354", "metadata": {}, "source": [ "## Zahlentheoretische Grundlagen" ] }, { "cell_type": "markdown", "id": "c3660767", "metadata": {}, "source": [ "Wir beginnen mit der Definition von einer der wichtigsten Funktionen der algebraischen Zahlentheorie, die von Leonard Euler in den 1760er Jahren eingeführt wurde.\n", "\n", "
\n", " \n", "Die Eulersche Phi-Funktion ist definiert als\n", "$$\\varphi: \\mathbb{N} \\to \\mathbb{N}, n \\mapsto |\\{ a\\in \\mathbb{N} \\mid 1 \\leq a \\leq n \\land \\gcd(a,n)=1 \\}|$$\n", "und besitzt folgende Eigenschaften:\n", " \n", "- $\\varphi$ ist multiplikativ, d.h. für alle teilerfremden $m,n\\in \\mathbb{N}$ gilt $\\varphi(mn) = \\varphi(m) \\cdot \\varphi(n)$\n", "- $\\forall p\\in \\mathbb{P}: \\varphi(p) = p-1$, wobei $\\mathbb{P}$ die Menge der Primzahlen bezeichnet\n", "- $\\forall n\\in \\mathbb{N}: \\ n = \\sum_{d | n} \\varphi(d) $\n", "\n", "\n", "
\n", "\n", "\n", "\n", "\n", "\n", "
\n", " \n", "### Aufgabe\n", "***\n", "Beweisen Sie die drei Eigenschaften in der obigen Definition.\n", "
" ] }, { "attachments": { "32923de7-70d0-42f3-9239-cb45b1a4c585.png": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAbgAAAFfCAYAAAA8i9mJAAAgAElEQVR4Ae2dCZhT1fn/D6J1a6u2tVScJclkJsnNPplhFRRQEUVUxCIiVqRuKCqguABVEFxQAfUnoCJUUapWXGr/dpNq1Ra1WhW3KtWKuFFFZgEEsZx/T5gbw5AMyUxyc5cPz8OTTHJz7zmf8z3v956bvPcVgn8QgAAEIAABCEAAAhCAAAQgAAEIQAACEIAABCAAAQhAAAIQgAAEIAABCEAAAhCAAAQgAAEIQAACEIAABCAAAQhAAAIQgAAEIAABCLRFoHONq2p4TdeaH7W1Ee9BAAIQgAAELEXAW15eFajxbwkGw83hcGSpt6IiaKkO0FgIQAACEIBAJgLK4Hr07rdu6atr5WU3L9lW371XUzgce8Nb4T5JCNE502d4DQIQgAAEIGB6ArrBPfjmeqn/n/XgU/LIIcMagoHQZzWemgnagdp3Td8RGggBCEAAAhBIJ5DJ4HSjm/fH1+Qp516yUfMHm4OB4B1ut7sy/bM8hwAEIAABCJiWQFsGpxvdPS+ukRfMuHVrNBJvDofCT3sqPIebtkM0DAIQgAAEIKAI5GJwutE98Po6OX3RY/KQ/kc1hsOx96s91ee4XK69IAkBCEAAAhAwHYF8DE43OvU459G/yuNO/XmTFtDW+2v8M0kzMN3Q0iAIQAACzibQXoPTze6u5/4lz7x05uagFt4QCkaWeco8YWcTpfcQgAAEIGAKAh01ON3oSDMwxXDSCAhAAAIQ0AkUyuB0o1OPpBnodHmEAAQgAIGSESiGwelmR5pByYaVA0MAAhCAQDENTjc60gzQGQQgAAEIGE7ACIPTjY40A8OHlwNCAAIQcC4BIw1ONzr1SJqBczVHzyEAAQgYQqBUBqebHWkGhgwzB4EABCDgPAKlNjjd6EgzcJ726DEEIACBohIwi8HpRqceSTMo6pCzcwhAAALOIGBGg9PNrnWagcvlcjljVOglBCAAAQh0mICZDU43OtIMOjzM7AACEICA8whYweB0o9PTDPoNPHY91Qycp1V6DAEIQCAvAlYyON3o1CNpBnkNMxtDAAIQcB4BqxqcbnakGThPs/QYAhCAQE4ErG5wutGRZpDTcLMRBCAAAecQsIvB6UanHkkzcI5+6SkEIACBrATsaHC62ZFmkHXYeQMCEICA/QnY2eB0oyPNwP46pocQgAAEdiLgBIPTjY40g52GnxcgAAEI2JeAkwxONzr1SJqBfTVNzyAAAQgkCTjV4HSzI82AiQABCEDApgScbnC60ZFmYFOB0y0IQMC5BDC49VI3Of2RNAPnzgd6DgEI2IgABrezwelGR5qBjYROVyAAAecRwOCyG5xudKQZOG9e0GMIQMAGBDC4XRucbnSkGdhA8HQBAhBwDgEMLneD041OPZJm4Jw5Qk8hAAGLEsDg2mdwutmRZmBR4dNsCEDA/gQwuI4ZnG50pBnYf67QQwhAwGIEMLjCGJxudOqRNAOLTQKaCwEI2JMABld4g9PNjjQDe84ZegUBCFiEAAZXPIPTjY40A4tMBpoJAQjYiwAGV3yD042ONAN7zR16AwEImJwABmecwelGpx5JMzD5xKB5EICA9QlgcKUxON3sSDOw/hyiBxCAgEkJYHClNTjd6EgzMOkEoVkQgIB1CWBw5jA43ejUI2kG1p1PtBwCEDARAQzOfAanmx1pBiaaKDQFAhCwHgEMzrwGpxsdaQbWm1e0GAIQMAEBDM78BqcbHWkGJpgwNAECELAOAQzOOganG516JM3AOnOMlkIAAiUigMFZ0+B0syPNoEQTh8NCAALmJ4DBWdvgdKMjzcD8c40WQgACBhPA4OxhcLrRqUfSDAyeRBwOAhAwJwEMzn4Gp5sdaQbmnHO0CgIQMIgABmdfg9ONTk8ziERqm8Oh8NOeCs/hBsmLw0AAAhAoHQEMzv4GpxsdaQalm2ccGQIQKAEBDM45BqcbnXokzaAEk41DQgACxhLA4JxpcLrZkWZg7HzjaBCAgIEEMDhnG5xudKQZGDjpOBQEIGAMAQwOg9NNTn8kzcCYucdRIACBIhPA4DA43dhaP5JmUOTJx+4hAIHiEsDgMLjWxtb6b9IMijsH2TsEIFAkAhgcBtfa0LL9TZpBkSYhu4UABIpDAIPD4LIZWluvk2ZQnPnIXiEAgQISwOAwuLaMbFfvkWZQwMnIriAAgcISwOAwuF2ZWC7vk2ZQ2HnJ3iAAgQIQwOAwuFwMLJ9tdkgzcNdc4XK59i+AVNkFBCAAgfwIYHAYXD7mlc+2pBnkNxfZGgIQ6BiBCiHEYCFEQN8NBofB5WNa7dmWNAN9tvEIAQgUmsBsIcSbQogNQgjZ8v8Q/SAYHAbXHtNqz2dIM9BnHY8QgEAhCXxPCPF2i7k1CSH20HeOwWFw7TGrjn6GNAN9BvIIAQgUgsC/Wgzu8fSdYXAYXEfNqiOfJ80gfTbyHAIQaA+BrmmXJy9M3wEGh8F1xKAK9VnSDNJnJc8hAIF8CPwszeBC6R/E4DC4QplUofZDmkH6DOU5BCCwKwJLWgzuUyFEp/SNMTgMrlDGVOj9kGaQPlN5DgEIZCKgDO2TFoO7p/UGGBwGV2hjKvT+SDNoPWv5GwLOJfBjIcThQojjhBDq15PqkqSeHqAuVe7wD4PD4AptSMXan43TDDxCiCOFECcIIWI7TFD+gAAEkgT8Qoj7hRDv/u8y5DQhxKVCiKeFEJekGVxZa1YYHAZXLEMq5n5tkGbQWQhxthDiZSHEr/93leUsIcSZLfP3GSHEAa3nKn9DwKkE1OTYJIS4SwixVxoE9br63k2t4N5Kez31FIPD4IppRMXet0XTDGr+d4XlFSHEaiFEPDUZtz/5S8t8nd/qdf6EgCMJXNUyIVR+2w4/IBFCDEpbvd2aiQ4Gh8EV24SM2L+F0gy6CSG+EEKoGy6kbpnXMjf3TZuvyuj4BwFHE5jYMiHez3JJ49S0CaO+k9vpHwaHwRlhQEYew8RpBupesGtb5qSam5n+qaswanWnvkfnHwQcS0DdT3Jry2QZkoXC1Jb3vxZCfD/TNhgcBmek+Rh5LBOmGeiXH5WBtb7akml68hoEHEngO0KI91rMa0UbBJ5o2eapbNtgcBickaZTimOZJM1AXUHRf808Itt85HUIQECIC9ImS8ZLj0KI7wohmlu2m5QNGgaHwZXCdEpxzBKnGfypZS6qqyn7ZZuPvA4BpxNQlzbUd27qbHC9EGLPLEBOSzPBSJZtBAaHwZXCbEp9TIPTDNRP/pWxqTnLj0eyBSNeh4AQonuace10Z5IWQsoEX23Zbk1b1/sxOAyu1GZTyuMblGbQM23O/pIoBgEIZCcwPm2yqCTuTP/UNX79er/6VVbWfxgcBldKgzHLsYucZqDuUKLPxxuyTkbegAAExM1pk2VYBh6qNM7zaduckbZNddrz5FMMDoMzi8mYpR1FSDM4Om0+tnnC2XJ7vdbTlL8h4BgC16RNltNb9Vpd639UCHFR2jbqFl7q35X/M76jWp6nHjA4DM4sxmK2dhQwzUCddG5rmZNvtPGVwVghxJTU5OQJBBxIIP1yx2tCiIOEEOq+diox9AUhhLpTwvSWyaQmVWXLpLk4EysMDoMzm7GYrT0FSjN4OO2kc1yruajuYPJ/QojbWr3OnxBwHAH1AxKV16Zf0/9vy30oPxJC1LXQuDrtfZUMrr63y/gPg8PgzGYoZm1PB9MMDhRC/D1tXv75f5cjbxJC3CeEUHNX3XiZfxCAgBBibyGEupyxSAhxhxDinJbXdDgHt9yhfKEQIqq/mOkRg8PgzGooZm5XO9MMdhdCqO/N1UrtwZZVmzI28uIyBSdeg0BHCWBwGJyZjcTsbTMozaCj05zPQ8CZBDA4DM7sJmKF9hU5zcCZwYleQ6CjBDA4DM4KBmKlNqbSDLTgZzXumitcLtf+HZ2nfB4CEGgHAQwOg7OSeViprQVMM2jHzOYjEIAA96J8E4OzkmlYsa0FSjMgWkEAAvkSYAWHwVnRNKzY5g6mGeQ7tdkeAhDA4DA4K5qF1dvczjQDAhYEIJAPAQwOg7O6WVi5/aQZ5BOt2BYCeRLA4DA4KxuEXdpOmkGegYvNIZALAQwOg7OLSdilH6QZ5BK52AYCORDA4DA4uxiD3fpBmkEOAYxNINAWAQwOg7ObMditP6QZtBXBeA8CbRDA4DA4uxmCXftDmkEbgYy3IJCJAAaHwdnVEOzcL9IMMkUzXoNAKwIYHAZnZyOwe99IM2gV0PgTAukEMDgMzu4m4IT+kWaQHtV4DoEWAhgcBucEA3BSH0kzILxDAIOTTgp69NV5JzKkGRDmHU+AFZzzAh9m56wxJ83A8WHeuQAwOGcFO8zNueNNmoFz47xje47BOTfgYXbOHXvSDBwb8p3VcQzOuUEOg2PsSTNwVrx3XG8xOIIcRocGSDNwXOh3RocxOIIbBocG0jVAmoEzYr8jeonBEdzSgxvP0YOuAdIMHGEB9u4kBkdA0wMaj2ghkwZIM7C3B9i6dxgcQS1TUOM1dNFaA6QZ2NoK7Nk5DI5A1jqQ8Tea2JUGSDOwpx/YrlcYHMFsV8GM99FINg2QZmA7S7BXhzA4gle24MXraCNXDZBmYC9fsE1vMDiCWK5BjO3QSi4aIM3ANvZg/Y5gcAStXIIW26CTfDVAmoH1/cHyPcDgCFz5Bi62RzP5aIA0A8vbhHU7gMERrPIJVmyLXtqrAdIMrOsTlm05BkfAam/A4nNop70aIM3AspZhrYZjcASp9gYpPod2OqoB0gys5ReWay0GR5DqaJDi82iooxogzcBy1mGNBmNwBKeOBic+j4YKqQHSDKzhHZZoJQZHcCpkcGJf6KlQGpj/p5XylHMv2aj5g83BQPAOl8vlskRQpZHmIYDBEZAKFZDYD1oqhgZIMzCPX1iuJRgcQakYQYl9oqtCa4A0A8vZS+kbjMERiAodiNgfmiq2BkgzKL13WKIFGBzBqNjBiP2jsWJpgDQDS9hM6RqJwRF8ihV82C/aMkoDpBmUzkNMfWQMjiBkVBDiOGjNCA2QZmBqyzG2cRgcQceIoMMx0JnRGiDNwFgvMeXRMDgCj9GBh+OhOSM1QJqBKa3HmEZhcAQbI4MNx0JvpdIAaQbGeIqpjoLBEXBKFXA4LtorlQZIMzCVDRWvMRgcQaZUQYbjor1Sa4A0g+J5iyn2jMERZEodZDg+Giy1BkgzMIUdFb4RGBzBpdTBheOjQTNpgDSDwvtMyfaIwRFczBRcaAt6NIsGSDMomS0V7sAYHAHFLAGFdqBFM2qANIPC+Y3he8LgCCpmDCq0CV2aTQOkGRhuTx0/IAZnrkDywBtfynlPvi6nLnxELvjzW9Jsk5z2mEsvjEdpxoM0g457jyF7wOBKM0FaB6b+J46SLn9Y7rnX3lIIkfw/+zfPY3BvmmN8Wo8XfzMuSgOkGRhiU+0/CAZnjomqfqasVm5d3dVJczvgxz/B3DA3NGARDZBm0H4PKuonMThzGJy+Ijiwa3nS4A49bgTBzSLBTR87Hs01l0o1HqQZFNWy8ts5BmeeSXn70/9MXZ48/9oFGBwGhwYsrAHSDPLzoqJsjcGZx+CUqanv3zp16iSV2ZXqDJTjmkcTjIX1x4I0g6JYV247xeDMM4H6HPvTpMGVVwcwNwufuWNK5plTZhoL0gxy86SCboXBmWMyqvSAAw7skjS4Y04bi8FhcGjAxhogzaCgNpZ9ZxicOQzuhkeeS33/dtm8B1LBTf0666bHViTz4m7708rU62Y6M6Ut5tAQ42C9cSDNILs3FeQdDM4ck2LUJVcnDa7z7nvIe/7+UdLIxs68Tap0AT0vTn03py5j3vvypxidjc/uMSpzzEkjx4E0g4LY2c47weDMMZmivQckjSyQ6Jk0r2NHj5M1sXr5s0uvkaMvv04eVFmVMrqBI8ZgcBgcGrCpBkgz2Nmn2v2KMrj67oesV9eEO/L//pWfM+HaOeHu+8en8jt77ZU0sOHjrpDq/7BzJ0n1pbR+Fql+Vanf5WSP7+wpl7z0ceo9fRsezXGywjgwDoXQAGkG7ba1bz+oDC4aiW88/tQzZXv/9zp0gJxwPXlb7RW1uu+kfhly5ISr5KCRZ2U0r3DPw1Lbqe/l2ns8PkcARgPW0QBpBt/6Vd7PCnGJcuwvbpQXzLiFgNvOFdxxYy5MGtdunTtLrb63XPLyJxlZ1vUblDK4O595J+M2BC7rBC7GirHKRwOkGeRtb0JgcKWfZO5AJGVcl867P6tx6fep3Hvf70qVVpDP5GDb0o8zY8AYFEoDpBnkaHYYXGkn3Z3Pvis77bZb0uA8wVhW45q//I3UdoccMwxza+dquVABhv2Udt7Afzt/0gx2YXQYXGkn6oU3LEyt3sZdf0dW4xpx4dTUdpPveCjrdkz80o4n/OFfCg2QZpDF6DC40k7IfieMTBqXuuyY7bs3lff2o4PKktsFu/XB3Fi9oQE0kFUDpBmkmR0GV1qD+2GXrknj6jVoaFbBjrjoF8ltVCrBTY/+Let2pThz5Jil1Q/84Z9NA6QZCH5kkk0cRryuKnbr6QFnXjk7o3HN/e2LUq3u1HZtXcI0or0cg2CKBqynAUenGbCCK51gT7/s2pTBXffgUzsZ3N0vrpFlVb5k+Rx1Ky+CS+nGCvawt7oGHJlmgMGVbuImDh2YMrjW9d8WPrtK+mLd5F777CsvmHUn5sZ3LmgADRRMA45JM8DgSmdwY6bcKPfce5+kyalip+rHJLf+4RV52qQZcr8fHCi7HT5Yznvy9YKJ2upnoLS/dFqFvT3Z2z7NAIMrrXBVHtxZV82Rhx43QkZ79Zd9hwyXIydcKSmNU9pxIaDD30kasG2aAQbHRHbSRKav6B0NtK0BW6UZYHBtDzaTAT5oAA04UQO2SDPA4Ji8Tpy89Bndo4HcNGDpNAMMLrdBZjLACQ2gASdrwJJpBtUVFZ5gMPz1qPMnbW7v/8MHD916xJBhW9v7eT7Xfvawgx0aQANGa6DfwCFbqypd0lft+yoYDJycdnMscz09TIjdgzXVTReddbyceflp/IcBGkADaAANtKmBESf0l9Vu97ao5vvQV1XV21yu1qo1WnXVuIvOOqFZfv6g5D8M0AAaQANooLUGtv3nAbl82TQ5sF+3xngo8Jq3wn1sKysx559er3fPmOb/Ys1rCzA4TB4NoAE0gAZSGvjv2qSxbevfp64hEQm84HW5epjTydpoVai6+pJLx520obVr8zdncmgADaAB52lg66f3y4cXX7qtT49Yc31Ue8ZT7qlvw0LM/VbXrl33iWq+9Z+9eWfKuRG180TNmDPmaMDZGvj6k18lja1XXaQpHvI/5a2srDW3e+XYuoCvesrUiSNYxXF5gpMcNIAGHKaBLZ8slUvnT9xaHw1uiIcDT7hcLn+O1mGNzbQDte9GNV/D2rcXIm6HiZuzdmeftTP+zh3/TR/eK++aO25rXURrjgb9D3nKPNXWcKx2tDJUUzNz5uWjNiF45wqesWfs0YD9NbBh9RJ515xxWxLhQFMsHFhSVVVV3g7LsNZHPB7PflHN37hu1WJWcazi0AAaQAM208D6VYvl7OlnbImHA83xUOBOX3l5V2u5VAdbG9H8N95w1eivOIuz/1kcY8wYowFnaEAtWm6aNnpTVPM3hTXfApfL9ZMOWoU1P+4/+OAfRoP+psb37+bszWZnbwQzZwQzxplx1jXw+TuL5MzJp22MBHzNkaBvTkVFxQHWdKYCtjoWDNx28zVnbdYh8ciEQQNoAA1YRwMfrbxdTp148qaY5msI1Xhnulyu/QtoEdbeldvt7hIL+ZvUF5GI2jqiZqwYKzTgbA2oO1JNHj+8KarVrA9WV09ROc7WdqMitT4e8t214MaxXzNhnD1hGH/GHw2YXwOrXrhVnv/zIeqHI19oVTUTy8rK9i6SNdhjt96DvWW1oUDzpjX3sorjuzg0gAbQgAk18M8Vt8ixowc3RIP+tTUe73h1b2F7OJABvYiHtfsW3XzBVs7gzH8GxxgxRmjAORp4669z5ZiRRylj+8zn8ZyjSp8ZYAn2OoQqiFob1po3f7yUszcTnr0R0JwT0Bhrxlpp4KUnZ8lThw1orA0HVte4qn4mhOhsL9cxuDfxkP+h+xZM+IYJxgRDA2gADZRGA3//0yw5Ymj/dfGQ/32f2/tTIUQng63AnoerKqvydouFmtVdphF3acQNd7ijAWdq4LnfXiOPHtCzqT4aerulyCjGVmirrQ0FHv/1okn/ZZI5c5Ix7ow7GjBOA5atnl1o4zFqf96KCq1nItz0zaes4pjoxk10WMPaSRrQq2cP6FPXEAv5X62qrOxvVIx3/HFqw9qffnPv5ducJDj6SoBFA2ig2BpQxvbE0imp6tlut7ub4w3HaADeysr4Id3jjWowij3g7J+gggbQgN01oFfP7l2/vXp2VUVFwui4zvHSCCQi2rO/f3AqqzhSBjjJQQNooJ0aUMa2dMGEb1T17NqI/3fVlZWBtDDL01IR8LpcPfr3rmtUX4La/eyK/rGCQANooJAaUNWzF80dp4ytKR7yL/N4PDWliuUcNwuB2nDwxeUPT8Pg2nn2VsgJw74IwGjA/BrYuPreVPXsaND/kLe8vCpLeOXlUhPwulyHDezXvYGJZf6JxRgxRmigdBpo/mCJnHfd2anq2TVlZQeXOn5z/BwIJCKB1559fCarOFZxaAANoIFWGvhy1S/l7KvHbFYlx6Jaze2VlZUH5RBW2cQsBLwu18BjDu/ZyNlh6c4OYQ97NGAuDXzx7iJ5zRWjNunVs8vKyn5glphNO/IkkIgG33zxj9dz9tbq7I2gY66gw3gwHsXWwMev30H17Dz9w/Sbe8vdQ4Yd23d9scXD/glQaAANmFEDO1TP9lXP8Hq93zd94KaBORPoVBvWVqnyDWYUH20iKKIBNFAMDax+Zb68eOyJTap6dqi6+mKqZ+fsGdba0FvhPmnkiQP4RSWXKTnJQQO214Cqnn3emCFNsZD/P6p6tsvl2staEZvW5ktgt3gosHrlX2bbXtzFOBNkn6ww0ID5NfDW327Wq2evpXp2vhZh8e29bvepZ4w4il9UcgbPSQ4asJUGUtWzQ4EPqZ5tcaPqQPM7x4P+T9TynbNR85+NMkaMERpoWwOqevYpJ/T7UlXPbjG23ToQH/mo1QnUeN0/P/f0wU1MnLYnDnzggwbMqwFlbCcM6tNA9WyrO1KB259IJPaIBv1r33vpNlZxXKZCA2jAMhrQq2cP6tejORHRXvdWuI8tcHhkd3Yg4K+pOv+is45nFUdws0xwYzVl3tVUscdGr559eN96qmfbwYCK3Qev17tnTPN/oZIfiy1O9u/cwMTYM/Yd0UB69exEJPBCtcvVvdixkf3bhIBWXX3xpPOHbeiIAPksAQwNoIFCa2Drp/fLhxdfuk2vnu0p99TZJOzSDaMIqMTHqOb/Ut2brdACZX8EPTSABvLVgKqevWzRpG96JsJNVM82yglsfJxAdfXkKRNOZhXHd3Gc5KCBkmlAr57dLRZqTkQDj7jdbp+Nwy5dM4pApEuXfaOar2Ht2wtLJu58z/LYnpUBGrCHBvTq2XVhrUlVz64qq/IaFfs4jkMIhHy+GVdfPmojQcMeQYNxZBzNrgG9enYsGNgQCwWWeA/2ljkk3NJNowl4PJ79opq/cd2qxaziuEyFBtBA0TSQrJ49/YwtVM82Oso7/HgRzX/DrCtP/8rsZ360j9UJGrCeBlT17JumnbExqvmbIkHfHKpnO9xwjO6+/+CDfxgN+psa3ru7aGdvBCbrBSbGjDHriAb06tlxzd8Y1Wqudblc+xsd2zgeBJIEYkH//82deebmjgiazxIQ0QAaWLPydjl5wvCmqFazPuirnqG+BiHMQqCkBNxudxd1bXzD6iWs4vgeBg2ggbw18OGr26tnRwK+BpWC1LVr131KGtQ4OATSCcRDvoXzZ537NWfhnIWjATSQqwbeWXGrPH/MkGaqZ6dHU56bjoD6uW5tKNC0ac29eZ+95ToZ2I7AiQbsoQFVPXvs6MHro0H/Z1TPNl04p0GZCKi8lLtuHscqjktUnOSggYwaeHn5LHnqSQMaExFtjb+q6vTDhNg9UyzhNQiYjoDH46lIhLXmzR8vzShuzr7tcfbNODKO+WogVT076P93S/XszqYLYDQIArsiEA/6f33v/PFb850AbE/QRAP204AytqFH922oDWvveSvcJwkhOu0qhvA+BExLQN0TTt34VN3dm4Blv4DFmDKmuWjgud9eIwf179FE9WzThmoa1l4CtaHA4w8uvPi/uUwEtiFgogF7aKClerY88tD6xngo8JqnomJAe2MIn4OAaQl4Kyo0VZfpm09ZxRG87RG8Gcfs49i6erbX5eph2uBEwyBQCAKJcPCPjy25bBuBIXtggA1srKwBvXr2Id2iTbVh/9NUzy5E5GQfliBQ7XLFDukeb1Rnd0ZP4i0fL5WvPDVL/uvvtxp+bKP7yvEwSaM1kFY9uzEe8j/lrayMWyIo0UgIFJJAIqI987sHphiyiptxxcnyyH5R6fN2lXvs0VkKIeQjd1+CwZGPhQYKpIEtnyyVS+dP3Lq9erZG9exCBkv2ZT0C1S5X9/69E43b/lP8VZy6g8o7z98sQ4HypLl17rybXP8v6tQZfXbP8ey3okxWz547bmtdRGumerb14jAtLiKBuqj24vKHpxl2Fl0fr0oaXPdEtWHHJKjbL6gzpg9KdfP0ededvYXq2UUMkOza2gS8LtehAw/r1mBEwGj+4J7U5ckpE07E4Ap0acqIseMY5jlJaF0921de3tXaUYjWQ6CIBOKhwCvPPj6j6Ibz/351eXL1pr5/e+rRK4t+PIKyeYIyY9HxsVi3arG8adroTap6dljzLVBlsIoYFtg1BOxBwOt2H3nM4T0bix2Exp9zTNLg9tl7T7n54/swOFZwaCAHDXz+ziI5c/JpG9EegJkAABOtSURBVGNBX2M06L+2oqLiAHtEHnoBAYMIJKLamy/84bqiBhz9ByaDBsSLepxiGzX77/hqBIa7ZvjRytvl1Aknb4xpvoZQjXcm1bMNCoYcxn4EvBXuY08c3Hd9oQLP1k9/Jf+5Yq786xNXS5X39umbd8hOnTolV3A3ThuFweVw5l6osXD6fj5/566kDvW8y28+u1+ueW2+/NsTM2Qp8kB3NR4t1bObqZ5tvzhLj0pIoDasrXrpyVkdMh8VTC678HhZUfYjecYp/eQFZw6Sh/UOykW3nJv6/u3Vp2/o0DF2FSB4f9erAycweviXF0v1a93e3Xxy8vihcsTQ3vK04YfKBTeemdRiZfmBptLhu8/fIs//+ZDmWND/ud/rneByufYqYTjg0BCwFwFvhXvYKUMHtPsXlX/89RR5UJcD5IC+YfnZW3emgsfiW8dKd8WPk0Hlxz/aTxqRd+eEAE4fMxt5w3u/lMOP7yX3/M4ecsm8cSkdKl4Xn3es9Lp/ktTimJH9d3ivVDzfXvFt9ewaj3e81+vd016Rhd5AwBwEOtWGAqtX/mV23hP/3vnjpErero245Vcf7fgDkuf+39Wp1Zs6iy5VIOG4mQ3BTlzUzQOUBtXl8GWLJ+6ktceWTEppcentF+70vpEs3nxujhxzysCG2oj2EdWzzREAaYXNCXg9npGjTx6Y1y8qVSBR5nbA/vvK917a+f6Sj993aSqoLJx7TkmDipEBjGMZa6jqu96e9TVJralf7Gbir1+eVAaovhfOtE2xX1NFRk8dNqCxNhT4gOrZNg+odM90BDrHg/6P/7nilpwm/6oXb5Hf/97eyaBy2/VjMn5Gva5y39T/1a/My7hNsYMK+zfWbErBW11+VBpTl8kb3787o870bdQveo1uY7J69uC+62MhqmebLurRIOcQ8HndY8457ZhdruLUd2m96n3JoOKp7JL8tWSmoDHqp32T2wT9xgeVTO3hNfuZ3d//dG3qV7q3XDs6q3mFAxVJLV541tFZtym0PlT17KMH9Gyqi2pvqF8rOyeS0FMImJBAIpHYIxr0r33vpdvaDALq0qS+MlOXfjIFBvWT7K4/OSC5nTp7zrQNr9nPcIweU5VbqbT4ve/unXX19vbf5qT0qi6bF7ON6uRv+bJpqerZGJsJAx1Nci6BQI33vAvPPL65rSCgfoKtgooqf7Pu3UUZA8YfHpycCipPLpuacZu2jsF7mN+uNKAuk+snWio1Jdv2F529/U46u+/eOasJZvtsrq+rvLrly6Zt69+nriERCbxA9WznxlB6bmIC6qfKUc237oN/zM8YMNSPSfTE7aP6xzJuo4KCfmb93X33ynoJM9fgwXaYXSYNXP+LkSmDy1ZjUCVP77XnHsntilHJQq+e3adHrLk+qj3jKffUm3h60zQIQEAlm1583okZV3Eqt00/a778ohMyGtyzv52e2ubYgYmM22QKWLyGkeWjgSFH1aV0lp5/mb6P0SP6SXUPVKXZQn7/lqF6di2RAwIQsAABdSeFqOb/Ut0TLz1YqOdXXnJSKqjcMfvsnd5XtarUHUx0E1Rn2fo+1N1O9Oc8YmYd1YDKe1M6U4ndmW4i8MDC8ckEb30Fp+e/KXPa+OGSdmlRr55dFw1uiIcDT7hcLr8FpjRNhAAE0gloNTVXTJ4wfEPrIHT15cNT5jX/hh1/YKLykU49qY+cO/P01DZqNaf2cc9t58s75+xsiK33z98YX64aiIVcSZ2pS+at0wPe+uscecIx3eTyh3+R0qK6vK40qr6vU1Xmcz2O2m7Th/fKu9KqZ3vKPNXp84XnEICAhQhEunTZN6r5Gta+tXCHQPCbe79N3o6H3VLdQUIFgHdfuFkecVhEqvsA3jT9tFRQUTe3VWfS540ZuMN+8gkubIvpZdLAyGF9UjqbNO64pL7Ur3eV3pQWv3jnrpQW991nz+QPotRlzacfuypnLaorEnfNGbclEQ40xcKBJVVVVeUWmsY0FQIQyEYg7PNdPf2yUzemBxd1KUjdxFa/BKl+nq1y4dT3HPoX/ddOOSX1vro8dM7pR5jy7u3p/eK59Uz09WduSv2AROnxhz/4ntzv+/skb7Ss/7p36sQTU1pUJvfbpZflZG7rVy2Ws6efsSUeDjTHQ4E7qZ6dLUrwOgQsSkDVoYpq/kZVUTjdANRNba+adJJUv6JUv5ZUVQQ+eePb7+s++Mdtsk+PgBzYLyrVPQDTP8tz6xmJmcfszedmyzNHDZCH9tKSVQPULeFUySa9zW88e5McfGQiWU1g5TM3pl7X32/9qFfPVkVGVfVsl8v1E4tOX5oNAQjsikAkUD3r+l+M/qp1IOBvjMpOGtCrZ0cCvuZI0DeH6tm7igy8DwEbEPAffPAPo0F/U8N7me/xZ6cgR1+cZ9pUz7ZBkKILEOgIgWjIf8vcmWduxgCcZwB2HfM1ry2Qk8f/tCmq1awPVldP6dq16z4dmSN8FgIQsCgBt9vdJRbyN6lflNk14NEvZ5i3Xj07Hgp8oVXVTCwrK9vbotOSZkMAAoUiEA/57pw365yvMQJnGIHdxlmVgRo7enCDupk41bMLFRXYDwRsQqCysvIg9ZPpjavvZRX3vzu62M0A7Nqft/46V44ZeZQyts98Hs85hwmxu02mJN2AAAQKSSAeDNyzcO64rXYNhvTLPsadqp4dDqymenYhowD7goBNCXg8nopEWGv+6qP7WMGwijOlBpSxjRjaf1085H/f5/b+VAjRyabTkW5BAAKFJlAb1h5cMm88qzgMzlQGp1fP7hYLvdVSZBRjK/TkZ38QsDsBb3l5VX0s1KTuyM4lPftc0rPiWOrVswf269YYDwVeo3q23aMP/YOAAQRqQ9pvHrjz4v9aMSjSZuubsl49e0CfuoZY0P9qVWVlPwNkzyEgAAEnEKiurAz0TISbvkm75x/GYX3jMPsYKmN7YumUbXr1bLfb3c0J840+QgACBhNIhIN/ePSey7aZPSjSPusbr7oc/vDiS7f1ro80xUP+p6oqKhIGy53DQQACTiJQ7XLFDukeb1Rn1ZiI9U3EjGOYrJ69YMI39S3Vs9WVAyfNMfoKAQiUkEBdJPCX390/hVUcv6gs6EmOqp69aO44ZWxqxbbM4/HUlFDmHBoCEHAigWqXq3v/XolG9Ws2M64AaJO1Vpbp1bOjQf9D6he7TpxX9BkCEDAJgbqo9sLyZdMwOFZx7dZA8wdL5Lzrzk5Vz64pKzvYJPKmGRCAgJMJVFVW9jq8Tz2rOAwub4P7ctUv5eyrx2xWlSqiWs3t6n6nTp5L9B0CEDAhgXgo8Mozj8/IO8BxCdFalxALNV5fvLtIXnPFqE169eyysrIfmFDWNAkCEICAEO4K9xFHH96zsVABkP3Y0/g+fv0OOXXiyZtimq8hVOOd6XK59mf+QAACEDA9gbqo9sbzv7+WVRyXKnfSwPbq2cO3V8/2Vc/wer3fN72gaSAEIAABnYCnwjN46OC+61l92XP11Z5xXf3KfHnx2BObVPXsUHX1xVTP1mcLjxCAgOUI1EYC77705KydzuDbExz5jHWNUlXPPm/MkKZYyP8fVT3b5XLtZTkx02AIQAAC6QQ8lZUnjjihfwPmZF1z6sjYvfW3m/Xq2Wupnp0+M3gOAQjYgUCneCjwwcq/zGYV56Dv4tSq/dRhAxprqZ5thzlMHyAAgWwEvB7PyNNPPpJfVDrA4FT17FNO6Pelqp5d46r6mRBit2y64HUIQAACdiDQOR70f/z2iptZxdnU5JSxnTCoT0N9NPQ21bPtMGXpAwQgkDMBn9dzxtmnHdPUke9z+Ky5vsfTq2cP6tejORHRXqd6ds7TgQ0hAAE7EUgkEntEg/617710G6s4i6/idqieHUpWz+5vJ63SFwhAAAJ5E/B5PedeMGYIqziLGlyqenb3WHMiEnhBVY7IWwR8AAIQgIAdCahVXCzo//zfL89jFWchk9v66f1Uz7bjhKRPEIBAYQkEvN7xF489sZnv08z1fVqm8fj6k1/JZYsmfdMzEW6qjfh/R/Xsws4F9gYBCNiMgLqDRVTzr/to5e2s4ky6itOrZ3eLhZoT0cAjVM+22SSkOxCAQPEIaDU1l19x0fANmVYNvFa6ld3G1ffKu+aM25IIB5pU9eyqsipv8VTAniEAAQjYkECkS5d9o5pv/dq3FrKKM8EqTq+eHQsGNsRCgSVUz7bhpKNLEICAcQTCPt/06ZNGbmLFVroVW7J69vQztlA92zjdcyQIQMABBFT9r6jmb1y3ajGrOINXcap69k3TztgY1fxNkaBvDtWzHTDh6CIEIGAsgWig+vrrpp7+Fas4Y1ZxevXsuOZvjGo111I921i9czQIQMBBBNTKIRr0NzW8dzeruCKu4tasvF1OnkD1bAdNLboKAQiYgUA05L95zoyfb2YVV/hV3Ievbq+eHQn4GgLV1ZOpnm0GxdMGCEDAMQTcbncX9SOHDauXsIor0CrunRW3yvPHDGmmerZjphEdhQAEzEogFvTf/n/Xn72FVVzHVnGqevbY0YPXR4P+z6iebVa10y4IQMBRBCorKw+Kh/zNKtEYk8vf5F5ePkueetKAxkREW6OKjB4mxO6OEhCdhQAEIGBmAvFg4O6Fc877GoPL3eBS1bOD/n+3VM/ubOYxpm0QgAAEHEnA4/FUJMJa81cf3ccqbhffxSljG3p034basPaet8J9khCikyNFQ6chAAEIWIVAbVh7YMltF21lFZd5Fffcb6+Rg/r3aKJ6tlUUTTshAAEItBDwlpdX1cdCTapMCya33eRaqmfLI/p2a4yHAq95KioGIBgIQAACELAggdqw9tgDd0z8r9MNLlU9uwfVsy0oY5oMAQhAYGcCqqimKrD5zafOXMXp1bMP6RZtiof8T3nKPXU7U+IVCEAAAhCwJIFEOPiHR+++bJuTVnFp1bMblbF5Kyvjlhw8Gg0BCEAAAtkJuN3uaO9usUZ1mc7uJrflk6Vy6fyJW7dXz9YecbvdvuxkeAcCEIAABCxPoDYSePqJX03p8Cpu/b9+KR+/7wr5zWf3m8osk9Wz547bWhfRmqmebXm50gEIQAACuRNwu93d+vasbWrvKk7VPJt15emyZ11EHnloN/nYkstNYXDqnpvzrjt7i14923uwtyx3KmwJAQhAAAK2IFAbDqx48qGr8lrF6cbWozacNDi1gnvzuTlyYL/usr1mWYjLpK2rZ/vKy7vaYpDoBAQgAAEI5E+gqrKy1+F96hu3/WfX38WpYp7TLx0pD+kWlTfPPFM2vr9jjbkxpxwlf//AVMNXcdurZ4/epKpnh/2+Bap6Qv4k+AQEIAABCNiOQG048I9nHp+R1ZjWvLZgB2Nr/iBz2Z1X/nyjHHxEL5mLWRZixfb5O4vkzMmnbYwFfY3RoP/aioqKA2w3OHQIAhCAAATaT8BT4Tn86AE9GlubzupX5svJ44fLw3ol5OJbLpC53MNy1ElHyD8/Mi2rWbY+Rnv+VtWzp044eWNM8zWEarwzPR7Pfu3vPZ+EAAQgAAFbE1D3Xlzxu2uTxvTPFbfIiWOHyn69txvb5o+X5mxYz//+Wjn0mL45b5+PwbVUz27Wq2d37dp1H1sPCp2DAAQgAIGOE/BUVh5zVP+ezWeddrQ88rBu8uHFl8r23ulk+HGHyWcfn1kwk3v3+Vu2V88O+j/3e70TXC7XXh3vMXuAAAQgAAHHEIhovjW3XHNWh38Jqb7PO/n4fh02uLdXfFs9u8bjHe/1evd0zGDQUQhAAAIQKBwBT2Xl0JOP79+Qz2XDbNuecPQh8sU/Xt8uk1MpB2NOGdhQG9E+8ldVnU717MKNMXuCAAQg4FQCnWpDgQ9ee3p2u4wp3eyefOgq+bPhR+a1H1VkdOSwAQ2qDVTPdqoE6TcEIACBIhGo9nhO+dnwI3f6RWW6eeXyXKUKDBnYW768fNYuTS5ZPXtw3/WxENWzizSs7BYCEIAABIQQneNB/8fq+69cjKytbZ741RR55qmDsu6H6tnoDQIQgAAEDCXg83rOOGvU0U1tmVcu76nbdg0a0F2+/sy3lzzVa8uXTZNHHlqfrJ7trXAfa2jnOBgEIAABCDiagFrFfap+np+LkbW1zaN3Xy7PG31s8peZy5dN29a/T11DIhJ4wety9XA0YToPAQhAAAKlIeDzeM45f8yxHf4ubvNHS2XPRET2rotsqI9oz3jKPfWl6RFHhQAEIAABCAghEonEHrGg//N/vzyvXau4VtWz/+KtrKwFLAQgAAEIQMAUBAJe70UTxw5tbusSZOv39OrZddHghng48ITL5fKbojM0AgIQgAAEIKATULfEimr+dR+tvH2Xq7jW1bM9ZZ5qfT88QgACEIAABExHQKupueyKi4ZvaL1S0/9OVs++/pzt1bPDgSVUzzbdENIgCEAAAhDIRCDSpcu+Uc23fu1bC3dYxa1ftVjOnn7Glng40BwPBe6kenYmerwGAQhAAAKmJhD210ybNmnkJrVqW7dqsbxp2uhNqshoWPMtcLlcPzF142kcBCAAAQhAIBsBVVA0qvkbrxg/PGlsMc0/0+Vy7Z9te16HAAQgAAEIWIZAXSg0KuTzTfb5fN+zTKNpKAQgAAEIQAACEIAABCAAAQhAAAIQgAAEIAABCEAAAhCAAAQgAAEIQAACEIAABCAAAQhAAAIQgAAEIAABCEAAAhCAAAQgAAEIQAACEIAABCAAAQhAAAIQgIC9Cfx/AUuafKnS9k4AAAAASUVORK5CYII=" } }, "cell_type": "markdown", "id": "671fbf93", "metadata": {}, "source": [ "Ein weiteres zentrales Resultat der Zahlentheorie ist der Kleine Fermatsche Satz. Der französische Mathematiker Pierre de Fermat formulierte diesen bereits 1640, doch erst fast 100 Jahre später wurde er vollständig bewiesen, ebenfalls durch Leonard Euler.\n", "\n", "\n", "\n", "
\n", "\n", "Kleiner Fermatscher Satz\n", " \n", "Sei $n \\in \\mathbb{N}$ und $a\\in \\{1,\\dots,n\\}$ mit $\\gcd(n,a)=1$. Dann gilt $$a^{\\varphi(n)} \\equiv 1 \\mod n $$\n", "\n", "
\n", "\n", "\n", "Fermat entdeckte übrigens im Laufe seines Lebens eine ganze Reihe von bekannten Sätzen, die Beweise überließ er jedoch seinen Kollegen. vollständig selbst bewiesen hat Fermat nur ein einziges Theorem: Dieses besagt, dass keine zwei rechtwinklige Dreiecke mit ganzzahligen Kantenlängen existieren können, sodass die erste Kathete des Dreiecks $T_1$ kongruent zu einer Kathete des Dreiecks $T_2$ und die zweite Kathete von $T_1$ kongruent zur Hypothenuse von $T_2$ ist.\n", "\n", "\n", "
\n", " Abbildung 1: Fermats Dreiecke
\n", " By David Eppstein - Own work, CC0, https://commons.wikimedia.org/w/index.php?curid=57316802\n" ] }, { "cell_type": "markdown", "id": "757175b9", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "bd1bff47", "metadata": {}, "source": [ "## RSA-Kryptosystem" ] }, { "cell_type": "markdown", "id": "610537d7", "metadata": {}, "source": [ "Das RSA-Verschlüsselungssystem funktioniert folgendermaßen.\n", "\n", "Wir wählen den Nachrichten- und Chriffreraum $N= C=\\mathbb{N}$.\n", "\n", "1. Bob wählt zufällig zwei ungleiche Primzahlen $p,q\\in\\mathbb{P}$ und berechnet $m := p\\cdot q$, $\\varphi(m)=(p-1)(q-1)$.
\n", "Er wählt ein $e\\in (\\mathbb{Z}/\\varphi(m)\\mathbb{Z})^*$, also der Einheitengruppe von $\\mathbb{Z}/\\varphi(m)\\mathbb{Z}$ und berechnet sein Inverses $d:= e^{-1} \\mod \\varphi(m)$.
\n", "\n", "Privater Schlüssel von Bob: $d$
\n", "Öffentlicher Schlüssel: $(m,e)$\n", "\n", "2. Alice verschlüsselt ihre Nachricht $n\\in N$ durch potenzieren mit $a$: $$c := e(n,a)= n^e \\mod m$$ \n", "und schickt die verschlüsselte Nachricht $c$ an Bob.\n", "\n", "3. Bob erhält $c$ und entschlüsselt die Nachricht mit seinem privaten Schlüssel durch die Abbildung\n", "$$d(c,e)=c^d \\mod m$$" ] }, { "cell_type": "markdown", "id": "72736265", "metadata": {}, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "1. Beweisen Sie, dass die Entschlüsselung des RSA-Verfahrens funktioniert.\n", "2. Verschlüsseln Sie die Nachricht $n=9$ mit den Parametern $p= 11$, $q=13$, $a=7$.\n", "3. Implementieren Sie Julia-Funktionen zum Ver- und Entschlüsseln von Nachrichten nach dem RSA-Verfahren.\n", "
" ] }, { "cell_type": "markdown", "id": "f2c8df0f", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "af0b6805", "metadata": {}, "source": [ "Natürlich werden in der Realität deutlich größere Werte für $p,q,a$ gewählt als in der Aufgabe. Üblicherweise liegen die Primzahlen im Bereich von mehreren Hundert Dezimalstellen und es gilt $p,q \\gg n$.
\n", "Vor allem die Verwendung von kleinen Exponenten ist aus sicherheitstechnischen Gründen kritisch. Warum man beim RSA-Verfahren immer große Exponenten wählen sollte, sehen Sie in der nächsten Aufgabe." ] }, { "cell_type": "markdown", "id": "8b60c69f", "metadata": {}, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "Alice will die gleiche Nachricht an mehrere Personen verschicken. Dafür benutzt sie die RSA-Verschlüsselungen mit unterschiedlichen Werten für $m$, aber verwendet immer $e=3$.\n", "\n", "Zeigen Sie, dass sich mit diesen Informationen die Nachricht für Angreifer leicht entschlüsseln lässt. Veranschaulichen Sie Ihre Beweisidee an einem konkreten Zahlenbeispiel.\n", "\n", "Hinweis: Verwenden Sie den Chinesischen Restsatz.\n", "
" ] }, { "cell_type": "markdown", "id": "d9bedd3e", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "59cb582a", "metadata": {}, "source": [ "Wir sehen also, dass nicht alle Wahlen von Primzahlen für eine sichere Verschlüsselung geeignet sind.\n", "\n", "Aber auch im Fall, wenn alle Parameter geeignet gewählt sind, müssen Alice und Bob aufpassen:\n", "Denn sollte auch nur einer der geheimen Parameter $\\varphi(m), p, q, d$ zu Eve durchsickern, so ist die Chiffre direkt gebrochen. Es sollte also darauf geachtet werden, dass wirklich alle Parameter mit Ausnahme vom öffentlichen Schlüssel geheim gehalten werden." ] }, { "cell_type": "markdown", "id": "b5b32bef", "metadata": {}, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "Zeigen Sie, dass Eve alle Parameter des RSA-Kryptosystems effizient berechnen kann, sobald sie einen weiteren der Parameter $\\varphi(m),p,q$ kennt.\n", "
" ] }, { "cell_type": "markdown", "id": "d2bf67a6", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "d8c9b5b6", "metadata": {}, "source": [ "Eine weitere Sicherheitslücke stellt das folgende Szenario dar:
\n", "Eve kennt natürlich den öffentlichen Schlüssel $(m,e)$ und hat somit alle nötigen Informationen, um beliebige Nachrichten zu verschlüsseln. Sie kann also leicht eine Mitteilung an Bob schicken, in der sie sich als Alice ausgibt.\n", "\n", "Für dieses Problem wurde das Konzept von digitalen Signaturen entwickelt. \n", "Digitale Signaturen verwendet man um die Authentizität und Integrität einer Nachricht zu prüfen. Eine Nachricht ist authentisch, wenn sie wirklich vom angegebenen Absender stammt und integrär, wenn sie nicht nachträglich noch verfälscht oder abgeändert wurde.
\n", "\n", "im RSA-Verschlüsselungsverfahren lassen sich digitale Signaturen folgendermaßen umsetzen.\n", "\n", "1. Alice wählt erneut zwei verschiedene Primzahlen $p_A,q_A \\in \\mathbb{P}$ und berechnet $m_A=p_A\\cdot q_A$ und $\\varphi(m_A)=(p_A-1)(q_A-1)$. Sie wählt einen privaten Schlüssel $e_A$ mit Inversem $d_A:=e_A^{-1} \\mod \\varphi(m)$ und unterzeichnet die Nachricht $n$ durch potenzieren mit dem privaten Schlüssel $e_A$:\n", "$$n_A := n^{e_A} \\mod m_A$$\n", "Die unterzeichnete Nachricht $n_A$ kann sie nun mit dem öffentichen Schlüssel $(e,m)$ von oben wie gehabt verschlüsseln und schickt $$c:=n_A^e$$ zusammen mit $(m_A,d_A)$ an Bob.\n", "\n", "Privater Signaturschlüssel von Alice: $e_A$
\n", "Öffentlicher Signaturschlüssel: $(m_A,d_A)$\n", "\n", "2. Bob erhält die verschlüsselte Nachricht und entschlüsselt sie mit seinem privaten Schlüssel: $c^d = n_A \\mod m$. Ob die Nachricht wirklich von Alice stammt, kann er testen, indem er den öffentlichen Signaturschlüssel anwendet: $$n_A^{d_A}=n \\mod m_A$$\n", "Die entschlüsselte Nachricht ergibt nur Sinn, wenn sie wirklich mit Alices privatem Signaturschlüssel erzeugt wurde.\n", "\n", "Damit hat Eve deutlich größere Schwierigkeiten, Nachrichten zu fälschen. Eine Möglichkeit wäre es, den privaten Signaturschlüssel zu erraten, was bei Primzahlen von ausreichender Größe sehr schwierig ist." ] }, { "cell_type": "markdown", "id": "3f5fdfec", "metadata": {}, "source": [ "
\n", " \n", "### Recherche-Aufgabe\n", "***\n", "Sammeln Sie Informationen zum geschichtlichen Hintergrund des RSA-Kryptosystems. Wie hat es sich im Laufe der Zeit entwickelt? Welches waren/sind die Anwendungsbereiche des Kryptosystems?\n", "
" ] }, { "cell_type": "markdown", "id": "dbfc7425", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "2e8f1893", "metadata": {}, "source": [ "## Rabin-Kryptosysten" ] }, { "cell_type": "markdown", "id": "64bc5885", "metadata": {}, "source": [ "Ein Spezialfall des RSA-Kryptosystems ist das Rabin-Kryptosystem. Dieses funktioniert im Prinzip wie das RSA-Verschlüsselungssystem, mit der Ausnahme, dass der feste Paramater $e=2$ gewählt wird.\n", "\n", "1. Bob wählt zufällig zwei ungleiche Primzahlen $p,q\\in\\mathbb{P}$. \n", "\n", "Privater Schlüssel von Bob: $(p,q)$
\n", "Öffentlicher Schlüssel: $m$\n", "\n", "2. Alice verschlüsselt ihre Nachricht $n\\in N$ durch potenzieren mit $e$: $$c := e(n)= n^2 \\mod m$$ \n", "und schickt die verschlüsselte Nachricht $c$ an Bob.\n", "\n", "3. Bob erhält $c$ und entschlüsselt die Nachricht mit seinem privaten Schlüssel durch die Abbildung\n", "$$d(c)=\\sqrt{c} \\mod m$$\n", "\n", "Die Schwierigkeit besteht auch hier wieder dahin, eine Wurzel in der Gruppe $\\mathbb{Z} / m \\mathbb{Z}$ zu ziehen. Dafür gibt es aber inzwischen effiziente Algorithmen, z.b. den Tonelli-Shanks-Algorithmus." ] }, { "cell_type": "markdown", "id": "8d4eeca2", "metadata": {}, "source": [ "
\n", " \n", "### Aufgabe\n", "***\n", "1. Finden Sie heraus, wie der Tonelli-Shanks-Algorithmus zum lösen von Gleichungen der Form $$n^2 \\equiv\\mod m$$ funktioniert. Formulieren Sie in eigenen Worten einen Pseudoalgorithmus und beweisen Sie, dass dieser funktioniert.\n", "2. Lösen Sie mit dem Algorithmus per Hand die Gleichung $n^2 \\equiv 78 \\mod 91$ und geben Sie jeden Rechenschritt an.\n", "3. Programmieren Sie den Tonelli-Shanks-Algorithmus in Julia.\n", "
" ] }, { "cell_type": "markdown", "id": "1cf8a599", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "8111e8ea", "metadata": {}, "source": [ "
\n", " \n", "### Rückblick-Aufgabe\n", "***\n", "In diesem Notebook haben wir uns zuerst mit der rein theoretischen, formalen Definition von Kryptosystemen befasst. Weil monoalphabetische Chiffren wie die Caesar-Chiffre leicht zu brechen sind, sind vor allem polyalphabetische Chiffren für uns interessant. Das RSA-Verfahren bietet bei korrekter Implementierung eine höhere Sicherheit gegen Angriffe und erfordert keinen separaten Schlüsselaustausch.\n", "\n", "Fassen Sie rückblickend zusammen, auf welche Punkte man bei der Implementierung der RSA-Verschlüsselung besonders achten muss, um den Sicherheitsaspekt zu gewähren. Welche sind die Vorteile am RSA-Verfahren? Welche Schwachpunkte haben Sie kennegelernt?
\n", "Sammeln Sie Ideen, wie man das Verfahren in Zukunft weiter verbessern könnte.
\n", " \n", "
" ] }, { "cell_type": "markdown", "id": "a5c8c237", "metadata": {}, "source": [ "***" ] }, { "cell_type": "markdown", "id": "093ffb76", "metadata": {}, "source": [ "### Literaturhinweise\n", "- Euler's totient function. (2024). In Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/w/index.php?title=Euler%27s_totient_function&oldid=1237832475\n", "- Fermat's right triangle theorem. (2024). In Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/w/index.php?title=Fermat%27s_right_triangle_theorem&oldid=1217217241\n", "\n", "- RSA (cryptosystem). (2024). In Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/w/index.php?title=RSA_(cryptosystem)&oldid=1238185543\n", "\n" ] } ], "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.12.3" } }, "nbformat": 4, "nbformat_minor": 5 }