Skip to content

Mathematik verstehen am Beispiel einer Definition

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:

TLS-Bingo -- Wer bietet mehr?

Ich hatte heute den verwegenen Plan und wollte die Webseite des sächsischen Landtages per HTTPS aufrufen. Der Browser stoppte mich und zeigte eine schöne Fehlermeldung:

Edas
Fehlermeldung zum Zertifikat von edas.landtag.sachsen.de

Also dem Zertifikat traut der Browser nicht. Außerdem fehlen dem weitere Bestandteile. Das Zertifikat ist eigentlich für eine andere Domain und schon längst abgelaufen.

Hier frage ich mich, ob jemand schon mal eine Liste von Zertifikatsfehlern gesehen hat, die länger ist, als die obige. :-)

Kryptografie mit Barbie

Das wunderbare Projekt »Chaos macht Schule« des CCC versucht, Medienkompetenz und Technikverständnis von Kindern und Jugendlichen zu fördern. Verschlüsselung gehört mit in diesen Bereich und Bruce Schneier wies kürzlich auf ein Gerät hin, das in jedes Kinderzimmer gehört. ;-)

Von Mattel gibt es eine Schreibmaschine für Kinder, die eine einfache Verschlüsselung beherrscht. Das Modell E-118 wird von der slowenischen Firma Mehano hergestellt. Mittels der Tastenkombination Shift-Lock und 1, 2, 3 oder 4 wird die Verschlüsselung aktiviert. Die Nachricht kann dann über die Tastatur eingegeben werden und die Maschine druckt den Geheimtext aus. Die Schreibmaschine führt dabei eine einfache Ersetzung (Substitution) aus. Aber für einen Einstieg in die Welt der geheimen Kommunikation ist das sicher sehr gut.

Kryptografie auf einem Schwert

Was hat der Text NDXOXCHWDRGHDXORVI zu bedeuten? Diese Frage stellt das British Museum sich und der Allgemeinheit.

Ein etwa 700 Jahre altes Schwert wird derzeit ausgestellt. Auf der Klinge findet sich die obige Inschrift. Laut der Webseite des Museums vermutet man, dass es die Initialen einer religiösen Handlung darstellt. So steht die Abkürzung ND für Nostrum Dominus (unser Herr) und das X könnte für Christus stehen.

Das Museum ist an weiteren Deutungen sehr interessiert. Wenn ihr etwas wisst oder ahnt, wendet euch an das Museum.

via Ancient Origins: Medieval Sword contains Cryptic Code. British Library appeals for help to crack it.

Cypherpunks reloaded

Mehr als zwanzig Jahre ist es nun her, als sich eine Gruppe von Leuten auf einer Mailingliste »traf«. Die Cypherpunks diskutierten in den folgenden Jahren Kryptografie, Anonymität und andere Techniken zum Schutz der Privatsphäre. Letztlich ist über verschiedene Ecken auch Bitcoin ein Produkt der Cypherpunks-Zeit. Allerdings diskutierten die Teilnehmer nicht nur, sondern viel wichtiger, sie programmierten. Ein Spruch aus den Zeiten lautet: »Cypherpunks write code.«

Nun fand ich eine E-Mail in meiner Inbox, die das erneute Aufleben der Mailingliste ankündigte. Und prompt trudelten hier einige E-Mails ein. Wer also an den Themen Kryptografie, Politik und Privatsphäre interessiert ist, kann sich dort eintragen. Allerdings kamen früher recht viele E-Mails über die Liste und auch in den letzten Tagen erhielt ich recht viele Nachrichten. Ihr solltet also mit eurem E-Mail-Client gut filtern. :-)

Ich bin gespannt, ob die Liste neuen Drive gewinnt. Immerhin habe ich durch die Diskussion der letzten Tage ein paar Zufallszahlenerzeuger für den Rechner kennengelernt und habe nun was zum Testen.

ACM Turing Award für Goldwasser und Micali

Die beiden Kryptografen Shafrira »Shafi« Goldwasser und Silvio Micali erhalten den ACM Turing Award. Das ist so eine Art Nobelpreis in der Informatik. Goldwasser und Micali sind vermutlich nur Insidern bekannt. Sie lieferten allerdings wesentliche Beiträge zur Kryptografie. Die Begriffe der Semantic Security und Ununterscheidbarkeit eines Algorithmus’ vom Zufall gehen auf die Forscher zurück. Sie legten damit die Grundlagen für eine Formalisierung des Wissenschaftszweiges. Ich gratuliere beiden Wissenschaftlern für die Auszeichnung!

Pressemitteilung der ACM

Artikelserie "Mein digitaler Schutzschild" in der ZEIT

Patrick Beuth hat für die ZEIT ein Experiment gemacht. Er stellte sich die Frage, wie schwierig es für Laien ist, sich anonym und sicher zu bewegen. Diese Erfahrungen schrieb Beutch in der Serie »Mein digitaler Schutzschild« nieder. Für das Experiment kaufte er sich einen neuen Rechner und installierte Ubuntu. Später machte er sich Gedanken zu sicheren Verbindungen über VPN und Tor, nutzte E-Mail-Verschlüsselung mit OpenPGP und verschlüsselte die Festplatte. Die Artikel sind aus der Sicht eines neuen Benutzers geschrieben und sehr interessant zu lesen.

ZEIT Online macht sogar den Sprung vom Artikel in die Praxis und organisiert am 26. Februar eine CryptoParty. Dort zeigen Patrick Beuth und die Organisatoren der CryptoPartys in Berlin, wie die verschiedenen Werkzeuge zu benutzen sind. So wird die anfängliche Hürde, derartige Werkzeuge zu benutzen sicher kleiner.

cronjob