{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Kryptographie – Notebook\n",
    "\n",
    "**Informatik 12 · Kryptologie**\n",
    "\n",
    "Kryptographie ist Rechnen mit Resten. Dieses Notebook geht den Weg des Kapitels\n",
    "nach: von der Cäsar-Chiffre, die eine Häufigkeitsanalyse nicht übersteht, über den\n",
    "Schlüsseltausch von Diffie und Hellman bis zu RSA mit kleinen Zahlen.\n",
    "\n",
    "Den Angriff auf Vigenère haben Sie in einem eigenen Notebook — hier geht es um\n",
    "alles, was davor und danach kommt.\n",
    "\n",
    "Führen Sie zuerst die nächste Zelle aus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ALPHABET = \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\"\n",
    "\n",
    "# Buchstabenhaeufigkeit im Deutschen in Prozent (Abschnitt 8.3.4)\n",
    "DEUTSCH = {\"A\": 6.51, \"B\": 1.89, \"C\": 3.06, \"D\": 5.08, \"E\": 17.40, \"F\": 1.66,\n",
    "           \"G\": 3.01, \"H\": 4.76, \"I\": 7.55, \"J\": 0.27, \"K\": 1.21, \"L\": 3.44,\n",
    "           \"M\": 2.53, \"N\": 9.78, \"O\": 2.51, \"P\": 0.79, \"Q\": 0.02, \"R\": 7.00,\n",
    "           \"S\": 7.27, \"T\": 6.15, \"U\": 4.35, \"V\": 0.67, \"W\": 1.89, \"X\": 0.03,\n",
    "           \"Y\": 0.04, \"Z\": 1.13}\n",
    "\n",
    "\n",
    "def saeubere(text):\n",
    "    \"\"\"Grossbuchstaben, Umlaute ersetzen, alles andere entfernen.\"\"\"\n",
    "    text = text.upper()\n",
    "    for alt, neu in ((\"Ä\", \"AE\"), (\"Ö\", \"OE\"), (\"Ü\", \"UE\"), (\"ß\", \"SS\")):\n",
    "        text = text.replace(alt, neu)\n",
    "    return \"\".join(z for z in text if z in ALPHABET)\n",
    "\n",
    "\n",
    "def zeile(*teile):\n",
    "    print(\"  \".join(str(t).ljust(14) for t in teile))\n",
    "\n",
    "\n",
    "KLARTEXT = saeubere(\"\"\"\n",
    "Die Sicherheit eines Verfahrens darf niemals davon abhaengen, dass der\n",
    "Algorithmus geheim bleibt. Sie darf allein vom Schluessel abhaengen. Dieser\n",
    "Grundsatz stammt von Auguste Kerckhoffs und ist bis heute gueltig.\n",
    "\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 1 · Cäsar\n",
    "\n",
    "Schreiben Sie `caesar(text, k)`, das jeden Buchstaben um $k$ Stellen verschiebt.\n",
    "Entschlüsselt wird mit $-k$.\n",
    "\n",
    "Prüfen Sie, dass `caesar(caesar(text, 7), -7)` wieder den Ausgangstext liefert.\n",
    "\n",
    "**Frage:** Wie viele Schlüssel gibt es? Reicht das gegen einen Angreifer mit Rechner — und was folgt daraus für die Mindestgröße eines Schlüsselraums?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def caesar(text, k):\n",
    "    # TODO: jeden Buchstaben um k verschieben, Rest unveraendert lassen\n",
    "    return text\n",
    "\n",
    "\n",
    "# geheim = caesar(KLARTEXT, 7)\n",
    "# print(geheim[:60])\n",
    "# print(caesar(geheim, -7) == KLARTEXT)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 2 · Brute Force und Häufigkeitsanalyse\n",
    "\n",
    "Zwei Angriffe auf dieselbe Chiffre.\n",
    "\n",
    "Zuerst stumpf: alle 26 Verschiebungen ausgeben und hinsehen. Dann klüger: den\n",
    "häufigsten Buchstaben im Geheimtext suchen und annehmen, er sei das E.\n",
    "\n",
    "**Frage:** Der kluge Angriff braucht nur eine Rechnung statt 26 Versuchen. Ab welcher Textlänge funktioniert er zuverlässig? Probieren Sie es mit den ersten 20, 50 und 200 Zeichen von `geheim`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def haeufigster(text):\n",
    "    # TODO: haeufigsten Buchstaben zurueckgeben\n",
    "    return \"E\"\n",
    "\n",
    "\n",
    "def schluessel_raten(geheimtext):\n",
    "    \"\"\"Nimmt an, der haeufigste Buchstabe sei das verschluesselte E.\"\"\"\n",
    "    # TODO: k = (Position des haeufigsten - Position von E) mod 26\n",
    "    return 0\n",
    "\n",
    "\n",
    "# for laenge in [20, 50, 200, len(geheim)]:\n",
    "#     k = schluessel_raten(geheim[:laenge])\n",
    "#     zeile(laenge, k, caesar(geheim[:laenge], -k)[:30])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 3 · Rechnen mit Resten\n",
    "\n",
    "Alles Weitere braucht drei Werkzeuge: schnelle Potenzen modulo $m$, den\n",
    "erweiterten euklidischen Algorithmus und das Inverse.\n",
    "\n",
    "Python kann `pow(a, b, m)` selbst — schreiben Sie es trotzdem einmal mit\n",
    "*square and multiply*, damit Sie sehen, warum es schnell ist.\n",
    "\n",
    "**Frage:** Wie viele Multiplikationen braucht Ihr `potenz` für einen Exponenten mit 600 Stellen? Zählen Sie mit — und vergleichen Sie mit der naiven Schleife."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def potenz(basis, exponent, modul):\n",
    "    \"\"\"square and multiply: Gibt (ergebnis, multiplikationen) zurueck.\"\"\"\n",
    "    ergebnis, zaehler = 1, 0\n",
    "    # TODO: Exponent bitweise abarbeiten\n",
    "    return ergebnis, zaehler\n",
    "\n",
    "\n",
    "def inverses(a, m):\n",
    "    \"\"\"Kleinstes x > 0 mit a * x mod m == 1, oder None.\"\"\"\n",
    "    # TODO: ausprobieren reicht fuer kleine m\n",
    "    return None\n",
    "\n",
    "\n",
    "# print(potenz(7, 128, 1000), pow(7, 128, 1000))\n",
    "# print(inverses(7, 40))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 4 · Diffie-Hellman\n",
    "\n",
    "Alice und Bob einigen sich öffentlich auf $p$ und $g$, würfeln je eine geheime\n",
    "Zahl und tauschen $g^a \\bmod p$ beziehungsweise $g^b \\bmod p$.\n",
    "\n",
    "Zeigen Sie durch Rechnung, dass beide denselben Schlüssel erhalten.\n",
    "\n",
    "**Frage:** Eve kennt $p$, $g$ und beide öffentlichen Werte. Schreiben Sie einen Angriff, der $a$ durch Ausprobieren findet, und messen Sie, wie lange er für $p = 2\\,147\\,483\\,647$ bräuchte. Warum hilft ein größeres $p$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "p, g = 2_147_483_647, 7\n",
    "\n",
    "a = random.randrange(2, 10 ** 6)        # Alice, geheim\n",
    "b = random.randrange(2, 10 ** 6)        # Bob, geheim\n",
    "\n",
    "# TODO: oeffentliche Werte berechnen, dann beide Seiten den Schluessel"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 5 · RSA mit kleinen Zahlen\n",
    "\n",
    "Erzeugen Sie ein Schlüsselpaar: zwei Primzahlen $p$ und $q$, $n = pq$,\n",
    "$\\varphi(n) = (p-1)(q-1)$, ein $e$ teilerfremd zu $\\varphi$, und $d$ als Inverses\n",
    "von $e$.\n",
    "\n",
    "Verschlüsseln Sie dann eine Zahl und entschlüsseln Sie sie wieder.\n",
    "\n",
    "**Frage:** Faktorisieren Sie $n$ durch Ausprobieren und berechnen Sie daraus $d$. Wie groß müsste $n$ sein, damit das aussichtslos wird? Der Lehrplan verlangt die Berechnung von $d$ im Grundkurs ausdrücklich **nicht** — warum ist sie für das Verständnis trotzdem nützlich?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import gcd\n",
    "\n",
    "p_rsa, q_rsa = 61, 53\n",
    "\n",
    "\n",
    "def schluesselpaar(p, q, e=None):\n",
    "    \"\"\"Gibt (n, e, d) zurueck.\"\"\"\n",
    "    n = p * q\n",
    "    phi = (p - 1) * (q - 1)\n",
    "    # TODO: e waehlen (teilerfremd zu phi), d als Inverses bestimmen\n",
    "    return n, 0, 0\n",
    "\n",
    "\n",
    "# n, e, d = schluesselpaar(p_rsa, q_rsa)\n",
    "# print(\"oeffentlich:\", (n, e), \" geheim:\", d)\n",
    "# m = 1234\n",
    "# c = pow(m, e, n)\n",
    "# print(m, \"->\", c, \"->\", pow(c, d, n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Aufgabe 6 · Eine Hashfunktion und warum sie wehtut\n",
    "\n",
    "Hashfunktionen sollen jede noch so kleine Änderung sichtbar machen. Bauen Sie eine\n",
    "sehr einfache (und unsichere) Hashfunktion und prüfen Sie den Lawineneffekt:\n",
    "Ändern Sie **ein** Zeichen und zählen Sie, wie viele Bits sich ändern.\n",
    "\n",
    "**Frage:** Suchen Sie zwei verschiedene Texte mit demselben Hash — bei 16 Bit geht das schnell. Wie viele Versuche haben Sie gebraucht, und wie viele hätten Sie erwartet? (Stichwort Geburtstagsparadoxon.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hashwert(text, bits=16):\n",
    "    \"\"\"Sehr einfache Hashfunktion - nicht fuer echte Anwendungen!\"\"\"\n",
    "    h = 7\n",
    "    # TODO: ueber die Zeichen laufen, mischen, auf bits beschraenken\n",
    "    return h\n",
    "\n",
    "\n",
    "# a = hashwert(\"Guten Morgen\")\n",
    "# b = hashwert(\"Guten Morgon\")\n",
    "# print(format(a, \"016b\"), format(b, \"016b\"))\n",
    "# print(\"geaenderte Bits:\", bin(a ^ b).count(\"1\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "### Abgabe\n",
    "\n",
    "Fertig ist das Notebook, wenn Cäsar hin und zurück denselben Text liefert, der\n",
    "geratene Schlüssel für den vollen Text stimmt, Diffie-Hellman bei beiden Seiten\n",
    "denselben Wert ergibt, RSA die 1234 unverändert zurückgibt und Sie eine Kollision\n",
    "Ihrer Hashfunktion gefunden haben.\n",
    "\n",
    "Notieren Sie am Ende in zwei Sätzen, was Diffie-Hellman leistet und was es\n",
    "**nicht** leistet."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
