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

Backblaze ist eine amerikanische Firma, die Speicher- und Backupplatz anbietet. In deren Servern sind über 2500 SSDs verbaut. Backblaze fing im Jahr 2018 an, diese Art von Speicher zu nutzen und ersetzt seither die drehenden Platten (HDDs). Nun fragt sich die Firma immer mal wieder, wie belastbar die SSDs im Vergleich zu den HDDs sind. Im letzten Review gibt es einige Antworten dazu.

Dazu vergleicht die Firma Speichermedien, die als so genannte Bootgeräte zum Einsatz kommen und in etwa gleich alt sind. Bootgerät heißt bei Backblaze, dass die Server hiervon gestartet werden. Weiterhin werden Logdateien und temporäre Dateien auf die Speicher geschrieben. Sowohl HDD wie auch SSD vollführen gleiche Aufgaben.

Bisher hatten die Fehlerraten in etwa den gleichen Verlauf. Die SSDs lagen von den Werten leicht unterhalb der HDDs. Dieses Jahr ist nun das fünfte Jahr der Betrachtungen und hier gingen die Zahlen deutlich auseinander. Während bei den HDDs ab dem 5. Jahr ein deutlicher Anstieg der Fehlerraten zu beobachten ist, bleibt der bei den SSDs in etwa gleich.

Auf der Speichertestseite von Backblaze könnt ihr die weitere Entwicklung verfolgen und auch die Rohdaten herunterladen. Die Firma geht derzeit davon aus, dass die Fehlerraten der SSDs zu einem späteren Zeitpunkt steigen und wollen solange einen Blick auf deren SMART-Werte werfen. Ich bin sehr gespannt, wie lange der Vorteil der SSDs anhält und werde hin und wieder mal die Seiten von Backblaze checken.

Die Nachrichten über die schlimmen Terroranschläge in Brüssel ziehen am Nachrichtenticker vorbei und schon beginnen wieder die üblichen Diskussionen. Die Innenpolitiker fordern mehr Überwachung, andere machen die Flüchtlinge oder Angela Merkel verantwortlich, wieder andere weisen darauf hin, dass Flüchtlinge gerade vor dem Terror geflohen sind etc. Es tauchen auch, wie bei anderen Anschlägen, Meldungen auf, dass die Kriminellen schon vorab den Behörden bekannt waren und es wird die Frage gestellt, warum nichts gemacht wurde. Einer der Gründe ist die Mathematik, die gegen die Behörden spielt. Warum ist das so?

Zu Anfang treffe ich ein paar Annahmen: Ich verwende Belgien als Beispiel. Das Land hat ca. 11 Millionen Einwohner. Weiterhin bräuchte ich eine Zahl potenzieller Terroristen. Jetzt nehme ich mal an, es gäbe nur islamistischen Terrorismus. In Deutschland meldet das Bundesamt für Verfassungsschutz ein islamistisches Personenpotenzial von knapp 44.000 Menschen. Angenommen die Zahl lässt sich 1:1 auf Belgien übertragen, so leben dort gerundet 5.500 Menschen mit einem islamistischen Personenpotenzial. Das Ziel der Behörden ist nun, diese Personen zuverlässig zu filtern und ggf. zu beobachten.

Dazu werden Überwachungs-, Datenauswerte- und Kontrollmaßnahmen installiert. Das System ist so leistungsfähig, dass es 99,9% aller Terroristen erkennt. Also nur in einem Tausendstel der Fälle wird ein Terrorist nicht als solcher erkannt. Aber es erkennt auch Normalbürger in einem Prozent der Fälle fälschlicherweise als Terroristen.

Das System ist in Betrieb und bringt einen Alarm, dass es einen Terroristen erkannt hat. Aber ist dies wirklich einer und wie hoch ist die Wahrscheinlichkeit? Geht mal in euch und versucht, eine Schätzung abzugeben.

Um die Frage zu beantworten, stellen wir uns vor, dass System würde ganz Belgien durchleuchten. Es würden also 5.495 Terroristen erkannt werden. Daneben erkennt das System auch 110.000 Einwohner als Terroristen, die keine sind. Das heißt, insgesamt wird 115.495 Mal Alarm geschlagen. Aber der Alarm war nur in 4,7 % der Fälle korrekt. Das heißt, das System schlägt in mehr als 95 % der Fälle falschen Alarm.

Das heißt, dass zwar viele Personen und besonders viele Terroristen von so einem System erkannt würden. Dennoch sind auch hier die Mehrzahl unbescholtene Bürger und die Strafverfolger haben die Arbeit, korrekt zu filtern. Diese Arbeit sieht im Nachhinein sehr einfach aus. Aber üblicherweise fehlen bei der Suche vor einem Anschlag viele konkrete Hinweise. Letztlich müssen wir akzeptieren, dass es perfekte Sicherheit nicht herstellbar ist. Ich bin der Meinung, dass nicht mehr Überwachung, Datenaustausch und Repression die Lösung ist, sondern die Politik (»wir«) sollte sich Gedanken machen, wo die Gründe liegen und diese beseitigen.

Heute gibt es eine Portion Hardware-Porn:

via Hardware-Pornographie: Festplatte, entblättert

Von Primzahlen geht für viele eine große Faszination aus das Thema wird aus verschiedenen Richtungen gern beleuchtet. Sehr alt ist dabei die Fragestellung, wie viele Primzahlen es denn gibt. Euklid fand neben anderen die Antwort auf diese Frage: Es gibt unendlich viele Primzahlen. Sein Beweis ist recht einleuchtend.

Stellen wir uns vor, es gäbe nur endlich fünf Primzahlen (In der Regel sagt man: endlich viele) p1, p2, p3, p4 und p5. Dann berechnet man eine neue Zahl z = p1*p2*p3*p4*p5+1, d.h. alle Primzahlen werden multipliziert und anschließend wird die Zahl 1 addiert. Keine der bisherigen Primzahlen teilt diese Zahl z. Da aber jede natürliche Zahl einen Primteiler besitzt, muss der außerhalb der bisher bekannten Primzahlen liegen, d.h. es gibt mindestens eine neue Primzahl p6. Die Aussage lässt sich dann wieder anwenden und so ergibt sich, dass die Zahl der Primzahlen nicht endlich sein kann.

Bei Mathoverflow wurden diverse Fehleinschätzungen diskutiert. Unter anderem zählte dazu, dass die oben konstruierte Zahl z eine Primzahl sei. Wenn man den Beweis oberflächlich liest (siehe auch die Skripte zu Algebra 1 oder Zahlentheorie), könnte man in der Tat zu dem Schluss kommen. Die Zahlen 2, 3, 5, 7, 11 und 13 liefern jedoch ein Gegenbeispiel.

Schlimm finde ich dann die in dem Posting angegebenen Beispiele von Leerern (sic!), die ihre Schülern unter Beschimpfungen vor die Tür stellen, weil sie auf den obigen Umstand hinweisen und den auch noch beweisen.

Falls ihr euch schon immer mal gefragt habt, wie man ein reguläres 17-Eck mit Zirkel und Lineal konstruiert. Hier ist die Lösung:

Ich komme gerade von der Kriminalpolizei, wo ich erkennungsdienstlich behandelt wurde. Wenn das so weitergeht, muss ich bald meine DNA abgeben und am Ende atme ich selbst gesiebte Luft. Was war passiert?

Es ist schon etwas länger her, da fragte mich eine Firma an, ob ich nicht eine Analyse ihrer IT-Infrastruktur vornehmen könne. Sie hatten den Verdacht, dass da etwas “nicht stimmt”. Es war anzunehmen, dass jemand aus der Mitarbeiterschaft Daten entwendet. Ich untersuchte also das Netzwerk und einige Rechner. Dabei stach ein Rechner besonders hervor. Dort baute ich mit dem Sysadmin die Festplatte aus und kopierte diese zur weiteren Untersuchung. Es stellte sich heraus, dass der Mitarbeiter in massivem Umfang Daten aus der Firma geschleust hatte. Im weiteren Verlauf schaltete die Firma die Staatsanwaltschaft ein. Diese hat mittlerweile die (Ermittlungs)fäden in der Hand. Im Rahmen dessen werden diverse Gegenstände untersucht und geschaut, wer diese angefasst hat. Als Tatortberechtigter durfte ich somit meine Fingerabdrücke abgeben.

Im Vorfeld habe ich lange gerätselt, ob das machen soll oder nicht. Denn es gibt nicht wenige Fälle, in denen die einmal erhobenen Daten irgendwo landen, so nach dem Motto: Könnte man vielleicht noch einmal gebauchen.. Meinen Anwalt konnte ich für einen fundierten Rat nicht erreichen also verließ ich mich auf meinen guten Glauben und Fragen. Ich hatte mir vorgenommen, den Beamten vorher über die befürchteten Konsequenzen auszuquetschen und, falls es unglaubwürdig wäre, die Abgabe zunächst zu verweigern. Aber dazu kam es gar nicht. Denn kaum war ich in seinem Büro angekommen, setzte er zu einer längeren Belehrung an. Demnach werden die Spuren nicht gespeichert, sondern nur mit den am Tatort vorgefundenen verglichen. Die Fingerabdrücke werden nach den Worten des Beamten nicht in Datenbanken gespeichert, sondern nach Abschluss des Falles (oder sagte er, nach Beendigung des Vergleichs?) gelöscht. Wahrscheinlich schaute ich immer noch skeptisch und er meinte zum Schluss, dass sie, selbst wenn sie die Abdrücke aufheben und später auswerten würden, dürften die nicht gegen mich verwendet werden. War da nicht was mit den Früchten des vergifteten Baumes? In der Tat scheint dies nicht so zu sein, wie ich dachte. Die Wikipedia weiß mehr im Artikel zum Beweisverbot. Schließlich bekam ich einmal einen Satz schwarze Hände. Dank eines Spezialwaschmittels sind die aber schon wieder sauber.

Ich fand den Besuch letztlich recht interessant. Denn der Beamte war sehr offen und wir unterhielten uns über einige Themen, u.a. natürlich auch über das Abnehmen von Abdrücken. Interessanterweise nutzt die Polizei dieselbe Methode wie der CCC. Der Unterschied besteht letztlich nur darin, dass es das Ganze für die Polizei als fertige Einheit gibt.

Spätestens wenn der Fall abgeschlossen ist, werde ich mal eine Auskunftsanfrage bei verschiedenen Behörden starten und hoffentlich herausfinden, dass keine Informationen über mich gespeichert sind.

Foto von TheRealGrudge