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

Netzpolitik schreibt über ein Projekt, dass eine Weltkarte der Videoüberwachung erstellen will. Das Projekt mit dem Namen »Surveillance under Surveillance« nutzt die Karte von OpenStreetMap.

Ich habe vor vielen Jahren für die Kartierung der Kameras in Jena noch GMaps verwendet. Damals habe ich versucht, mit Farbcodes zu arbeiten. Bei dem jetzigen Projekt kann man die Art der Kameras und den Öffnungswinkel einstellen. Damit gibt es einen guten Überblick über den Zustand der Überwachungskameras. Wenn viele mitmachen, ergibt sich wirklich eine Weltkarte.

Für mich ist das eine gute Gelegenheit im Rahmen unserer Junghackingtage mit den Kindern eine Kamerasafari zu machen und die Daten zu Jena zu aktualisieren.

Der Thüringer Landesbeauftragte für den Datenschutz und die Informationsfreiheit (TLfDI), Dr. Lutz Hasse, stellte heute seinen Tätigkeitsbericht für 2014 und 2015 vor. Ich war zu der Veranstaltung mit eingeladen und will die Veranstaltung aus meiner Sicht zusammenfassen.

Derzeit arbeiten im TLfDI 20 Personen und zwei, die von anderen Ämtern abgeordnet wurden. Bei den beiden handelt es sich um einen Lehrer und eine Polizistin. Herr Dr. Hasse ist Vorsitzender des Arbeitskreises Datenschutz und Bildung der Datenschutzbeauftragten. In diesem Rahmen hilft der abgeordnete Lehrer. Insbesondere das Thema Medienkompetenz liegt dem TLfDi am Herzen. Auch die Hauptkommisarin ist in die tägliche Arbeit der Behörde eingebunden. Somit gewinnt sie einen Einblick und kann das später in der Polizei den dortigen Kollegen weitergeben.

Der Tätigkeitsbericht ist über die Jahre immer weiter gewachsen. Als Herr Hasse in das Amt gewählt wurde, gab es lediglich einen fingerdicken Bericht. Die heutige Ausgabe kam in zwei Bänden mit über 1300 Seiten Umfang. Die Bücher sind in den Bericht zum nicht-öffentlichen Bereich (private Firmen, Vereine etc.) und zum öffentlichen Bereich (Behörden, Gemeinden etc.) getrennt.

Im nicht-öffentlichen Bereich hat das TLfDI die Möglichkeit, Beanstandungen und Bußgelder auszusprechen. Davon machte die Behörde reichlich Gebrauch. Die Zahl der Beanstandungen verdreifachte sich im Vergleich zum vorigen Zeitraum und aus ursprünglich weniger als 500 € Bußgeldern wurden im neuen Zeitraum 5.300 € Bußgeld. Aufgrund der hohen Arbeitsbelastung fanden weniger Kontrollen bei Firmen statt.

Insgesamt versucht das TLfDI einen Blick auf zukünftige Gefährdungen zu haben. So spielten in der Veranstaltung SmartTV, Spielzeugpuppen mit eingebautem Mikrofon und WLAN wie auch Datenschutz in (selbstfahrenden) Autos eine Rolle. Die Datenschützer sind an diesen Themen dran und versuchen sich dazu eine Meinung zu verschaffen.

Wie schon im letzten Bericht spielt die Videoüberwachung in verschiedener Form eine große Rolle. Der aktuelle Bericht enthält mindestens 84 Fälle zur Videoüberwachung. Auch in Zukunft wird der Bereich eine große Rolle spielen. Nach einem Urteil des europäischen Gerichtshofs fallen wohl nahezu alle Kameras (auch privat betriebene) unter das Bundesdatenschutzgesetz. Damit sind diese beim TLfDI zu melden. Die Behörde versucht, ein Register einzurichten und dann sollen Kamerabetreiber deren Kameras dorthin melden. Weiterhin sind Dashcams (Kameras in Autos), Helmkameras und Kameradrohnen im Blick. Auch hier könnte es zu einer Registrierungspflicht kommen.

Weiterhin kam das Aktenlager in Immelborn zur Sprache. Dort wurde ein Berg von zum Teil sensiblen Akten in einer Fabrikhalle gefunden. Der ursprüngliche Betreiber des Lagers war nicht mehr aufzufinden und eigentlich hätten die Akten an die Besitzer zurückgehen müssen. Herr Hasse bat damals die Polizei um Amtshilfe, die aber nicht gewährt wurde. Das TLfDI klagte daraufhin. Später fand sich dann doch eine Firma, die die Räumung des Lagers übernahm. Der ganze Vorfall wird mittlerweile von einem Untersuchungsausschuss im Landtag betrachtet. Herr Hasse erzählte heute, dass im Rahmen des Ausschusses festgestellt wurde, dass der Polizeipräsident in der Tat Unterstützung leisten wollte. Das Amt hatte 10 Leute für ca. zehn Tage beantragt. Das Innenministerium fragte jedoch bei der Polizei 100 Leute für einen Monat an. Ein Schelm, wer Böses denkt. Dennoch war die Polizei zur Unterstützung bereit. Aber das Innenministerium pfiff die Polizei dann wohl zurück.

Im Bereich Gesundheit wurde auf ein Forum verwiesen, an das sich Krankenhäuser wenden können. Die Idee ist, dass ein Krankenhaus eine Datenschutzfrage stellen kann. Diese ist anonymisiert und das TLfDI beantwortet diese, ohne auf das Haus schließen zu können. Das Angebot wird gut angenommen und hat viele Abrufe.

Daneben erzählte Herr Dr. Hasse noch die Geschichte von Krankenakten, die an seine Heimadresse geschickt wurden. Als er den Brief öffnete, waren Krankenakten enthalten. Einen Tag später gab es eine weitere »Lieferung«. Daraufhin wandten sie sich an das betreffende Krankenhaus. Dort gab es eine Mitarbeiterin, die nach dem Namen eines Arztes im Internet suchte und auf die Adresse des Datenschützers stieß. Sie schickte die Akten dann ohne weitere Prüfung an den Datenschützer.

Im öffentlichen Bereich scheinen öffentliche Sitzungen von Stadt- und Gemeinderäten ein Dauerbrenner zu sein. Dort werden immer wieder personenbezogene Daten genannt, obwohl diese in nicht-öffentlicher Sitzung diskutiert werden sollen.

Insgesamt war dies eine sehr interessante und aufschlussreiche Veranstaltung. Ich habe jetzt Lesestoff für die nächste Zeit in der Hand.

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.

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.