Qbi's Weblog

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:

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 ℝⁿ. (Ein n-dimensionales Gitter L ist eine diskrete additive Untergruppe von ℝⁿ.)

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

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

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 ℝⁿ gesprochen. Aus der Wikipedia-Seite zum euklidischen Raum wird schnell klar, dass ℝⁿ 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.
• ℝⁿ
  • ℝⁿ ist der n-dimensionale Raum der reellen Zahlen. Aus der Schule kennt man ℝ¹ (Zahlenstrahl), ℝ² (Zahlenebene) und ℝ³ (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:

• Implications of the Proposed Quantum Attack on LWE
• A quick post on Chen’s algorithm

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:

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.

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.

• Barbie™ Typewriter
• Neues zur verschlüsselnden Barbie-Schreibmaschine

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.

Heute gibt es wieder eine Veranstaltungsankündigung. Am morgigen Dienstag, dem 09. September 2014, werde ich zusammen mit Martina Renner einen Vortrag mit anschließender Podiumsdiskussion in Jena halten. In der Veranstaltung geht es um den NSA-Untersuchungsausschuss. Zu Anfang werden wir einige Details zur NSA, zu deren Überwachungsprogrammen und zu den Entwicklungen beim Untersuchungsausschuss erzählen. Anschließend stellen wir uns den Fragen aus dem Publikum.

Wer teilnehmen mag, sollte vor 18 Uhr im Hörsaal 8 im Unigebäude in der Carl-Zeiss-Str. 3 sein.

Die Podiumsdiskussion mit Hans-Christian Ströbele und Prof. Dr. Michael Dreyer wurde von Campus TV aufgezeichnet. Mittlerweile ist das Video bei YouTube verfügbar. Die Audioqualität ist verbesserungswürdig. Dennoch viel Spass beim Anhören und -sehen!

Die Räume der Friedrich-Schiller-Universität Jena hatte heute zu ungewöhnlicher Zeit ungewöhnliche Gäste. Zur Mittagszeit, wo sonst der Vorlesungsbetrieb in vollem Gange ist, trafen sich verschiedene Politiker, Wissenschaftler und interessiertes Publikum. Die Fraktion von Bündnis90/Grüne hatte zusammen mit der Heinrich-Böll-Stiftung Thüringen, den Politiker Hans-Christian Ströbele und den Politikwissenschaftler Prof. Dr. Michael Dreyer. Beide sollten gemeinsam eine Podiumsdiskussion zum Thema Snowden und NSA bestreiten.

Ströbele erzählte zu Beginn seines Vortrages von seinem Besuch in Moskau bei Edward Snowden. Währenddessen oder kurz danach hatte er sich vorgenommen, den Whistleblower zu unterstützen. Dies sollte zum einen durch die Errichtung eines Untersuchungsausschusses wie auch durch einen Aufenthalt Snowdens in Deutschland passieren.

Der NSA-Untersuchungsausschuss lag zu Beginn der Legislaturperiode in weiter Ferne. Die SPD, die vor der Wahl noch einen anderen Zungenschlag hatte, verlor mit Regierungsbeteiligung das Interesse an Snowden. Interessanterweise war es die CDU, die den Weg zu dem Untersuchungsausschuss ebnete. Ströbele machte hierfür den Druck aus den Reihen der Bevölkerung verantwortlich. Im Verlaufe des Vortrages versuchte er immer wieder klar zu machen, dass politischer Druck »von der Straße« durchaus in die Politik einwirkt. Die Schritte, die dann passieren, sind leider klein, manchmal zu klein.

Mittlerweile wurden erste Juristen im Untersuchungsausschuss angehört. Auch hier erwähnte Ströbele, dass alle drei Juristen einhellig meinten, dass die Überwachung des BND verfassungswidrig ist. Hier gilt es nun, die Gesetze und auch die Arbeit des parlamentarischen Kontrollgremiums anzupassen. Dies soll nach dem Vorbild des United States Senate Select Committee on Intelligence sowie ähnlicher Behörden passieren. Diese haben neben den eigentlichen Gremiumsmitgliedern eine Reihe von unterstützenden Mitarbeitern. Die Mitarbeiter helfen dann beispielsweise bei der Einschätzung technischer Fragen.

Ströbele erwähnte einige Male stolz das Unternehmen Posteo. Das kümmert sich um gute Verschlüsselung und sitzt in Kreuzberg. Ich war ja versucht, noch mailbox.org zu erwähnen. Auch das Unternehmen sitzt in Berlin und verschlüsselt die Daten auf dem Transportweg wie auch in der Inbox.

Insgesamt regte Ströbele an, dass sich US-Unternehmen, die Probleme wegen starker Verschlüsselung bekommen haben, in Deutschland ansiedeln.

Zum Abschluss seines Vortrages klebte er einen Ein-Bett-für-Snowden-Aufkleber in den Hörsaal und überließ Prof. Dreyer das Wort.

Dreyer bemühte sich um Gegenrede. Denn nach seinem Bekunden ist ein Podium mit gleichen Meinungen langweilig. Nachdem er einen Werbeblock für diverse andere Veranstaltungen abgespult hatte, fragte er das Publikum, wer denn Jonathan Pollard kenne. Erwartungsgemäß meldete sich (fast) niemand. Pollard gab Dokumente an den israelischen Geheimdienst (oder, wie die offizielle Bezeichnung lautete, das Büro für wissenschaftliche Verbindungen) weiter. Dafür wurde Pollard zu lebenlänglicher Haftstrafe verurteilt. Seit der Verurteilung setzte sich ziemlich jeder israelische Premier bei dem jeweiligen US-Präsident für die Freilassung ein. Bisher waren alle ohne Erfolg. Dreyer nahm dies als Beispiel oder Parallele für ein eventuelles Vorgehen gegen Snowden. Aus meiner Sicht hinkt dieser Vergleich jedoch. Denn Pollards Veröffentlichungen sorgten für die Enttarnung diverser CIA-Agenten und vermutlich sogar für Hinrichtungen einiger Agenten. Das Damage Assessment besteht aus diversen Dateien. Auf der anderen Seite versuchte Snowden Dokumente zu wählen, die niemandem einem Risiko aussetzen und die auch keine legitime nachrichtendienstliche Tätigkeit aufdeckt. Stattdessen versuchte er nur den ungesetzlichen Teil aufzudecken und mit Dokumenten zu belegen. Daher würde ich erwarten und hoffen, dass er im Falle eines Gerichtsverfahrens wenig streng bestraft wird.

Die anderen Argumente Dreyers bezogen sich auf die Auslieferungsabkommen, die Deutschland natürlich einhalten muss. Ströbele wandte ein, dass einerseits die Regierung sich gegen eine Auslieferung aussprechen kann und andererseits die Auslieferung für politische Vergehen verboten ist. Die Bundesregierung wurde angefragt, ob es sich bei Snowden um einen solchen handelt. Daraufhin fragte die Regierung in den USA nach deren Meinung. Das sorgte für einige Lacher im Publikum.

Dreyer schlug weiterhin vor, statt Snowdens lieber Glenn Greenwald oder Laura Poitras einzuladen. Hier stellte sich heraus, dass er diesen Aspekt nicht gut vorbereitet hatte. Denn beide sind bereits eingeladen. Allerdings werden sie wohl keine Aussage machen, sondern als Journalisten Quellen schützen.

Die Empfehlung von Dreyer war, dass sich alle umfassend Gedanken über Vor- und Nachteile machen sollten. Diese Gedanken sollten als Grundlage einer Entscheidung stehen und eventuelle Emotionen sollten zurücktreten.

Insgesamt fand ich die Veranstaltung sehr schön. Gerade dadurch, dass Prof. Dreyer versuchte, einen Kontrapunkt zu setzen, wurde die Diskussion interessanter und einige Argumente traten stärker zu Tage. Ich würde mir mehr solcher Veranstaltungen wünschen.