Skip to content

Mathematik verstehen am Beispiel einer Defintion

Kürzlich ging eine Erschütterung durch die Welt der Kryptografie. Das Paper Quantum Algorithms for Lattice Problems versprach einen neuen Angriff gegen bestimmte Algorithmen. Diese heißen Learning-With-Errors (LWE) und bilden eine Grundlage für Algorithmen, die gegen Quantencomputer sicher sein sollen. Hier spielt eine Menge Mathematik mit hinein. Als Beispiel seht ihr eine halbe Seite aus dem Paper:

Seite 22 des Papers
Seite 22 des Papers

Das Thema klang hinreichend interessant und ich wollte mich ein wenig einlesen. Zum konkreten Paper muss man sagen, dass mittlerweile ein Fehler im Algorithmus gefunden wurde und die Autoren schreiben:

Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold.

Beim Lesen fiel mir wieder etwas auf, was mir schon früher auffiel. Es gibt Sätze, die kommen recht unschuldig daher und klingen leicht verständlich. Dennoch steckt soviel Theorie dahinter, dass es eine Weile dauern könnte, um diese zu durchdringen.

Gleich in der Einführung findet sich ein Beispiel: An n-dimensional lattice L is a discrete additive subgroup of ℝn. (Ein n-dimensionales Gitter L ist eine diskrete additive Untergruppe von ℝn.)

Welche Begriffe muss man verstehen oder interpretieren können, um die Definition zu verstehen?

  1. n-dimensional
  2. diskrete additive Untergruppe
  3. n

Das heißt, nahezu jedes Wort ist erklärungsbedürftig und mit Schulwissen kaum zu durchdringen. Wenn wir jetzt die Wikipedia konsultieren, kommen wir ein Stück weiter. Dort findet sich auch eine Definition des Gitters als diskrete Untergruppe eines euklidischen Raums sowie einige Beispiele. Wenn wir beide Definitionen vergleichen, steht in dem Paper zusätzlich das Wort additiv und anstatt euklidischer Raum wird von ℝn gesprochen. Aus der Wikipedia-Seite zum euklidischen Raum wird schnell klar, dass ℝn ein euklidischer Raum ist. Also sind beide Definitionen ähnlich. Das heißt, mit kleinen Einschränkungen können wir mit der Wikipedia-Definition weiterarbeiten.

Um den Satz nun zu verstehen, sollten wir uns dem zweiten Begriff, der diskreten additiven Untergruppe, zuwenden. Beim Aufdröseln ergeben sich neue Begriffe, die man entweder kennen oder lernen muss.

  • Untergruppe
    • Eine Untergruppe hat eine Verknüpfung (Addition, Multiplikation etc.) und bildet eine Gruppe.
      • Eine Gruppe ist eine Menge mit einer Verknüpfung (Addition, Multiplikation etc.). Bei der Verknüpfung ist es egal, wie man Klammern setzt (Assoziativgesetz), es gibt ein so genanntes neutrales Element und ein inverses Element. Wenn man ein neutrales Element verknüpft, ändert sich nichts, so wie bei einer Addition mit 0. Wenn man ein Element der Menge mit dessem inversen Element verknüpft, erhält man das neutrale Element (12-12=0 bei der Addition, -12 ist das inverse Element).
  • Additive Untergruppe
    • Das ist eine Untergruppe, wo die Verknüpfung Addition heißt.
  • Diskrete Untergruppe
    • Eigentlich geht es hier um diskrete Teilmengen eines Raumes mit der zusätzlichen Eigenschaft, dass diese Teilmenge eine Untergruppe bildet.
    • Eine Teilmenge ist, wie der Name schon sagt, ein Teil der Menge.
    • Diskret bedeutet nun, dass jedes Element der Menge eine Umgebung hat, dass kein weiteres Element der Teilmenge enthält. Das heißt, die einzelnen Elemente der Menge sind isolierte Punkte.
    • Die ganzen Zahlen …, -2, -1, 0, 1, 2, … sind als Teilmenge der reellen Zahlen eine solche Menge. Denn bei jeder Zahl gibt es nach links und rechts einen Abstand, wo sich keine andere Zahl drin findet. Bei den Brüchen (rationale Zahlen) ist das anders. Dort finden sich keine zwei Zahlen mit einem kleinen Abstand, dass keine andere rationale drin läge. Daher ist das keine diskrete Teilmenge.
  • n
    • n ist der n-dimensionale Raum der reellen Zahlen. Aus der Schule kennt man ℝ1 (Zahlenstrahl), ℝ2 (Zahlenebene) und ℝ3 (dreidimensionaler Raum).

Damit haben wir alle Bauteile zusammen, um den obigen Satz zu verstehen. Wobei ich zugeben, muss, dass ich oben einige Abkürzungen genommen habe und auf intuitives Verständnis gesetzt habe. Dennoch reicht das in der Mathematik oftmals nicht. Es ist sinnvoll, sich Beispiele auszudenken. Diese sollten sowohl den positiven Fall abdecken (erfüllt die Definition), aber auch den negativen Fall (erfüllt die Definition nicht). Das sorgt dann wirklich für ein Verständnis des Ganzen.

Das war es auch, was ich am Anfang meinte, als ich von dem kleinen unschuldig klingenden Satz schrieb. Um den zu verstehen, muss man entweder tief im irgendwann mal Erlernten graben oder neues lernen und es dauert eine längere Zeit, bis man ein Paper einmal durchgearbeitet hat. Noch viel länger dauert es, bis man es verstanden hat. :-)

Der obige Satz war der Einstieg in das Paper und nur die Einleitung. Später geht es um gaussche Funktionen und Fouriertransformationen. Das sind Konzepte über die es semesterlange Vorlesungen gibt. Das heißt, um das zu verstehen, kann man wirklich aus den Tiefen der Mathematik schöpfen. Ich wünsche euch viel Spaß bei der Lektüre. :-)

Mit dem Paper haben sich einige andere auseinandergesetzt. Hier findet ihr interessante Lektüre dazu:

Aufruf: Schickt mir eine mit Minilock verschlüsselte Datei

Kürzlich rief ich euch auf, mir eine verschlüsselte Datei zuzusenden. Die Ergebnisse des Experiments waren recht durchmischt. Weniger als die Hälfte der Einsendungen hatte enthielt eine verschlüsselte Datei. Knapp die Hälfte dieser Dateien waren mit OpenPGP verschlüsselt. Insgesamt fand ich einige der Ergebnisse ziemlich unerwartet.

Unter anderem erwartete ich, dass auch Minilock für die Aufgabe genutzt werden würde. Dennoch nutzte niemand diese Möglichkeit. Aus meiner Sicht ist das eine recht einfache Möglichkeit, um eine Datei zu verschlüsseln. Daher will ich dies unten vorstellen und bitte euch, mir eine Datei mit Minilock zu verschlüsseln und zukommen zu lassen. Dabei interessiert mich natürlich, was euer Eindruck von der Software ist. Also schreibt ruhig ein paar bewertende Worte dazu.

Minilock-ID-Erzeugung
E-Mail-Adresse und Passwort angeben, um eine Minilock ID zu erzeugen

Minilock ist eine Erweiterung für den Google Chrome oder die freie Alternative Chromium. Bei anderen Lösungen ist meist das Betriebssystem die Einschränkung und hier ist es der Browser. Um die zu installieren, besucht ihr die Minilock-Seite im Web Store und klickt rechts oben auf den blauen Button (zu Chrome hinfügen, add to chrome). Wenn ihr die Anwendung zum Browser hinzugefügt habt, öffnet sich ein neuer Tab und ihr seht das Icon für die Anwendung. Jetzt kann es losgehen.

Zu Anfang erzeugt Minilock eine ID. Dieses Kennzeichen wird später benutzt, um Dateien für euch zu verschlüsseln bzw. könnt ihr die Minilock IDs anderer nutzen, um Dateien für diese Leute zu verschlüsseln. Gebt in das Feld eine E-Mail-Adresse sowie ein Passwort ein. Minilock prüft zunächst die Komplexität des Passworts. Sollte dies zu schwach sein, erscheint eine Warnung sowie eine Empfehlung für ein sichereres Passwort. Gebt hier als ein langes und komplexes Passwort ein. Merkt euch beide Merkmale. Ihr benötigt die später, um euch bei der Anwendung “einzuloggen”.

Meine Minilock ID für dieses Experiment ist

MkUrFQM6NDPpYgd813BZub5cLaW1K2Sk5zF3SnG5RBXKm
Dateiauswahl und Minilock ID
Ansicht mit Dateiauswahl und Minilock ID

Nun könnt ihr Dateien verschlüsseln. Wenn ihr auf dem Bild rechts, in die obere Hälfte klickt, öffnet sich eine Dateiauswahl. Sucht dort eine oder mehrere Dateien aus und bestätigt eure Auswahl. Danach müsst ihr die oben angesprochenen Minilock IDs als Empfänger eingeben und Minilock erzeugt eine Datei mit der Endung .minilock. Diese ladet ihr auf den Rechner (Klick auf Dateiname) und könnt diese anschließend versenden. Der Empfänger kann die dann wiederum in sein Minilock laden und hoffentlich entschlüsseln.

Versucht mal, die obige Anleitung umzusetzen und verschlüsselt mir an die obige ID eine Datei. Wie einfach oder schwierig fühlte sich das für euch an?

Mit minilock verschlüsselte Datei
Mit minilock verschlüsselte Datei

Ergebnis des Verschlüsselungsexperiments

Anfang Februar 2018 rief ich dazu auf, mir eine verschlüsselte Datei zukommen zu lassen. Ich bekam fast 50 Zusendungen und war überwältigt. Vielen Dank für eure Mitarbeit!

Viele reden heute in meiner Umgebung über Verschlüsselung. Es gibt Messenger, die verschlüsseln, Webseiten werden verschlüsselt übertragen und Festplatten können verschlüsselt werden. Eine der einfacheren Aufgaben sollte die Verschlüsselung einer Datei sein. Aus meiner Sicht ist dies eine grundlegende Aufgabe, die einfach zu bewältigen sein müsste. Meine Annahme war, dass dies in der Praxis nicht der Fall ist.

Zum Vergleich: Stellt euch vor, ihr fragt beliebige Personen euch einen Text zu schreiben und das Ergebnis zukommen zu lassen. Meine Annahme ist, dass ein Großteil der Menschen dieses Problem lösen können. So ähnlich sollte es sich auch mit der Verschlüsselung einer beliebigen Datei verhalten. Die Betonung liegt jedoch auf sollte.

Im Vorfeld hätte ich erwartet, dass die meisten Dateien als gezippte (oder sonstwie gepackte) und verschlüsselte Datei kommen, dicht gefolgt von Officedateien mit Passwort. Am Ende kamen drei gezippte Dateien (entspricht 6% aller Dateien und 14% der verschlüsselten Dateien) und  keine Oficedatei. Das war eine Überraschung.

Die überaus meisten Dateien etwa ein Drittel aller Dateien und 64% der verschlüsselten Dateien waren gegen meinen OpenPGP-Schlüssel verschlüsselt. Auch dies fand ich überraschend, denn ich hätte vermutlich ein symmetrisches Verfahren gewählt und das Passwort auf einem anderen Weg übertragen. Allerdings ist die hohe Zahl für mich ein eindeutiges Zeichen der Filterblase in der mein Aufruf gelandet ist. Denn kann mir schwer vorstellen, dass die breite Masse der Menschen so oft und viel OpenPGP auf- und einsetzt.

Leider bekam ich nahezu keine Rückmeldung über fehlgeschlagene Versuche oder von Leuten, die gar keine Idee hatten, wie sie das Problem angehen können. Jedoch würde ich mehr als die Hälfte der Versuche, die mich erreichen als gescheitert betrachten. Diese enthielten entweder eine Datei im Klartext oder gar keine Datei. Das ist für mich schon ein deutliches Zeichen, dass die Aufgabe schwierig ist.

Aber wie geht es einfacher? Eine Lösung sind die oben angesprochenen gezipten Dateien. Hier müsste man natürlich über die Art der Verschlüsselung und deren Sicherheit reden. Ein ebensolches Problem steht bei Office-Dateien. LibreOffice bietet in der letzten Version auch die Benutzung von OpenPGP an. Aber dies muss erstmal eingerichtet werden.

Eine recht einfache, wenn auch unbekannte Lösung ist Minilock. Dies ist eine Erweiterung für Google Chrome und Chromium. Damit lässt sich die Aufgabe aus meiner Sicht recht bequem erledigen. Ich werde später eine kleine Anleitung schreiben und mal zu einem Praxistest aufrufen.

Zahlen zum Verschlüsselungsexperiment

Ich hatte euch gebeten, mir eine verschlüsselte Datei zu schicken. Die An- und Vielzahl der Antworten war überwältigend. Vielen Dank an alle, die mitmachten! Doch was kam dabei heraus? Unten findet ihr eine Auswertung in Zahlen:

Insgesamt erhielt ich knapp 50 Dateien. Diese kamen überwiegend per E-Mail (37). Daneben schickten mir Leute Hinweise über Quitter (3), Twitter (2), Slack (1), XMPP (1), Wire (1) und als Kommentar (2) zum Blogbeitrag.

Jemand hatte sich den Spass erlaubt, einen PGP-Schlüssel für die betreffende E-Mail-Adresse zu erstellen. Ich erhielt drei E-Mails, die einen falschen Schlüssel nutzten. Ich hatte im Beitrag auf meinen Schlüssel verwiesen und gehofft, dieser würde benutzt werden. Aber einige arbeiten offensichtlich anders, als ich das erwartet habe. ;-)

Insgesamt 22 Dateien oder weniger als die Hälfte der Versuche waren verschlüsselt:

  • Die meisten davon (11) waren mit OpenPGP gegen meinen Schlüssel verschlüsselt.
  • Vier Dateien nutzten AES zur Verschlüsselung. Das Passwort lag der E-Mail bei.
  • Dreimal erhielt ich eine gepackte (Zip) Datei mit Passwort in der E-Mail.
  • Zwei Dateien nutzten das TLS-Zertifikat und waren gegen dieses verschlüsselt. Ich bin natürlich im Besitz des privaten Schlüssels und konnte diese entschlüsseln.
  • Ein Link führte auf einen Pastebin mit einer OpenPGP-verschlüsselten Nachricht.
  • Schließlich kam noch ein Veracrypt-Container.

Auf der anderen Seite heißt das eben auch, dass ein Großteil der Dateien nicht verschlüsselt war. Insgesamt kamen fünf E-Mails mit einem Klartext-Anhang an. Ebenso erhielt ich eine klartextliche Datei über Keybase, drei Dateien über send.firefox.com, eine über Tutanota. Die Dateien, die über XMPP und Wire kamen, waren ebenso unverschlüsselt. Allerdings war hier die Leitung selbst verschlüsselt.

Schließlich erhielt ich noch Nachrichten, die keine Datei enthielten. Eine Mail verwies auf Peersm. Dies konnte ich in keinem Browser zum Laufen bekommen. Ein Kommentar im Blog enthielt eine Base64-kodierte Datei. Dies ist keine Verschlüsselung, sondern kann immer dekodiert werden.

Alles in allem ist das Ergebnis etwas anders als ich im Vorfeld erwartet hatte. Zu meinen Erwartungen und meiner Bewertung werde ich einen separaten Beitrag verfassen.

Falscher Schlüssel für enc2018@kubieziel.de

Ich bin bisher hocherfreut über die Rückmeldungen zu meinem Aufruf. Hier gibt es bereits jetzt viel Stoff für weitere Blogbeiträge. Allerdings hat sich jemand den Scherz erlaubt und einen PGP-Schlüssel für die E-Mail-Adresse enc2018@kubieziel.de erstellt. Einige Leute haben diesen Schlüssel schon genutzt, um mir Dateien zuzusenden. Ich habe hier nicht den privaten Schlüssel. Damit kann ich die Dateien nicht entschlüsseln. Falls ihr mir verschlüsselte Dateien zukommen lassen wollt, nutzt bitte den Schlüssel von der Kontaktseite. Der Fingerprint ist 60D8 5B8D 9A1C D2D1 355E BE9F 65B3 F094 EA3E 4D61.

Falls der Erzeuger des obigen Schlüssels mir den privaten Teil für das Experiment zukommen lassen will, freue ich mich natürlich auch. :-)

Aufruf: Schick mir eine verschlüsselte Datei

tl;dr: Bitte verschlüsselt eine Datei und schickt mir diese zusammen mit einer (kurzen) Beschreibung, wie ich die lesbar mache.

Alle Welt redet von Verschlüsselung und keiner macht es. So könnte man meine These kurz zusammenfassen. Habt ihr schonmal versucht, eine Datei zu verschlüsseln und diese jemand anderem zuzusenden? Wie habt ihr dies angestellt?

Aus meiner Sicht ist das eine einfache, grundlegende Aufgabe, die man in jedem Anfängerkurs stellen könnte:

Stelle dir vor, dein Gegenüber nutzt einen öffentlichen Computer (Internetcafe, Bibliothek etc.). Du möchtest mit diesem eine Datei austauschen, deren Inhalt nur ihr beide kennt. Verschlüssele eine Datei auf deinem Rechner und übermittle diese an dein Gegenüber.

Ich frage mich nun, wie ihr das machen würdet. Daher habe ich mich zu einem kleinen Experiment entschlossen: Liebe Leserinnen und Leser, bitte verschlüsselt eine (nicht allzugroße) Datei und schickt mir diese zu (per E-Mail an enc2018@kubieziel.de, hinterlasst einen Kommentar oder kontaktiert mich anderweitig) . Legt ein paar Informationen bei, wie ich die wieder entschlüsseln kann. Ihr wisst nicht, wie ihr das machen könnt? Schreibt mir bitte unbedingt eine Mail an enc2018@kubieziel.de oder hinterlasst unten einen Kommentar und erzählt mir davon. Ihr habt es probiert und seid daran gescheitert? Schreibt mir bitte unbedingt eine Mail an enc2018@kubieziel.de oder hinterlasst unten einen Kommentar und erzählt mir davon. Ich würde gern wissen, wie einfach oder schwierig dies für euch ist.

Ich plane, die Umfrage später anonymisiert auszuwerten und ggf. in weiteren Beiträgen verschiedene Werkzeuge vorzustellen.

 

cronjob