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

Beim letzten Update von F-Droid gab es Probleme. Updates wurden nicht mehr geladen und stattdessen zeigte das Telefon die Meldung »error getting index file« an. Nach einigem erfolglosen Herumprobieren stieß ich auf den Mastodon-Account von F-Droid. Laut der letzten Meldung versuchten die Entwickler einen anderen Fehler zu beheben. Dies löste dann dieses Problem aus.

Doch wie lässt sich das nun beheben? Ein Hinweis liefert der Blogbeitrag der Entwickler. Sie schreiben, man solle das alte Indexformat aktivieren. Dazu geht ihr im F-Droid auf Optionen. Recht weit unten in den Einstellungen müsst ihr den Expertenmodus aktivieren und dann findet ihr ganz unten den Menüeintrag «Altes Index-Format erzwingen«. Nun lassen sich, wie gewohnt, die Updates herunterladen und installieren.

Viel Spass mit aktueller freier Software auf euren Smartphones.

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

Als das Tor-Projekt den Tor-Browser entwarf, machten sie sich viele Gedanken zum Schutz der Privatsphäre. Sie versuchten jegliche Gefahren zu identifizieren und diese zu umschiffen. Daraus entstand das Design zum Tor-Browser. Seitdem versuchen die Entwickler, die Schwachstellen in Bezug auf die Privatsphäre im Mozilla Firefox im Griff zu behalten. Neben dem Tor-Button kommen viele individuelle Patches zum Einsatz. Die meisten davon wurden bisher von Mozilla nicht in den Firefox eingepflegt. Doch dies ändert sich jetzt.

Seit Anfang Mai gibt es im Wiki von Mozilla eine Seite, die sich Tor Uplift nennt. Mozilla fängt nämlich nun doch an, Patches vom Tor-Projekt in den Firefox wieder einzubauen. Auf der Wikiseite wird der Fortschritt festgehalten. Bisher kamen 26 Änderungen weiter und an sechs wird gerade aktiv gearbeitet. Sören Hentzschel beschreibt in seinem Blogbeitrag, welche neuen Optionen es im Firefox gibt und wie diese aktiviert werden können.

Insgesamt ist das ein guter Schritt der Entwickler, den Schutz der Privatsphäre im Firefox weiter zu erhöhen. Wie Sören in seinem Beitrag schreibt, engagiert sich Mozilla auch weiterhin stark im Tor-Projekt. Weiter so!

Vor vielen Jahren legte ich mir bei Amazon eine Wunschliste an. Diese war zum einen als Merkzettel für mich gedacht und zum anderen konnten andere darauf zugreifen, um mir einen Wunsch zu erfüllen.

Dort landete unter anderem auch das Buch »Privacy on the line« von Whitfield Diffie und Susan Landau (Sie ist u.a. auch Tor-Unterstützerin.). Die Beschreibung klang sehr interessant:

In Privacy on the Line, Whitfield Diffie and Susan Landau strip away the hype surrounding the policy debate over privacy to examine the national security, law enforcement, commercial, and civil liberties issues. They discuss the social function of privacy, how it underlies a democratic society, and what happens when it is lost. This updated and expanded edition revises their original—and prescient—discussions of both policy and technology in light of recent controversies over NSA spying and other government threats to communications privacy.

Aber weder kaufte ich das Buch noch kaufte es mir eine andere Person. Aber jetzt habe ich einen Grund, es zu lesen. Das Buch kann über die Webseite kostenlos heruntergeladen werden. Auf https://mitpress.mit.edu/books/privacy-line findet ihr einen Download-Link, der euch direkt zur PDF-Version bringt. Das Buch ist weiterhin im Handel erhältlich und vermutlich werde ich es nach einigem Schmökern, dann doch endlich kaufen.

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.