Hallo zusammen,

über Facebook bin ich auf einen Wettbewerb gestoßen, den ich euch nicht vorenthalten möchte:

Deine Aufgabe ist es, ein Programm zu realisieren, mit dessen Hilfe es möglich ist, ausgewählte Dateien (und Verzeichnisse?) zu verschlüsseln und später wieder zu entschlüsseln.

[…]

• Verschlüsselung von Daten über die Konsole oder ein GUI
• Implementierung eines Verschlüsselungsalgorithmus (gerne auch ein eigens entwickelter Algorithmus!)
• Entschlüsselung der Daten über gleiches Programm

[…]

Quelle: Code Competition: Sicher ist Sicher. https://www.it-talents.de/cms/aktionen/code-competition/code-competition-04-2016

Bereits in den Kommentaren auf Facebook wurde dem Betreiber von dieser Idee abgeraten. Verschlüsselungsverfahren sollten nur von dafür qualifizierten Personen konzipiert werden. Fehler können bei der Anwendung selbiger ohnehin noch genug gemacht werden. Natürlich ist es eine gute Sache, junge Menschen für die Programmierung zu begeistern. Allerdings werden auf diese Weise die Security Audit Findings von morgen generiert. Ich stelle mir das in 5-7 Jahren so vor:

Chef: Wir brauchen in unserer Software dringend noch eine Verschlüsselungslösung um die sensiblen Daten der Kunden zu schützen.
Talentierter Mitarbeiter: Ich habe da im Studium mal etwas gebaut, ist aber vermutlich nicht ganz si…
Chef: Perfekt!

Trotzdem hat mich dieser Ausschreibungstext inspiriert, was man wohl alles an „billigen Lösungen“ einreichen könnte, um die 222 € zu gewinnen (oder den Raspberry Pi 3). Mal von einfachen Substitutions- und Permutationslösungen abgesehen, könnte man sich einfach einer Feistelchiffren-Konstruktion bedienen (wie in DES/3DES oder Blowfish). Es hat den Vorteil, dass man sich über die Entschlüsselung keine Gedanken machen muss.

Noch einfacher wäre es, eine Stromchiffre zu konstruieren. Für den Schlüsselstrom könnte man einfach einen PRNG (Pseudozufallsgenerator) mit einem Seed initialisieren und auf den Klartext auf-XOR-en. Das wäre nur eine Zeile – und sogar die gleiche für Ver- und Entschlüsselung.  Das fiese daran ist, dass das Ergebnis recht zufällig aussieht und ein Blackbox-Audit vermutlich sogar bestehen würde. Hier exemplarisch in Python und nur für Text, aber das geht mit einer Datei natürlich genauso gut:

>>> import random

>>> text = "hier kann ein beliebig langer Klartext geschrieben werden"

### Verschlüsselung ###
>>> random.seed("hier den Schlüssel!"); text="".join([chr(ord(e)^random.getrandbits(8)) for e in text])
>>> text
'\xeb\xbdP~0v\xa3\xb8[c\x0f\xb7\xaa\xbe\xaf\x1f\x15#\xd2:\x17\xbeU\xfesJ\x1d\x18\xcbmb\xe256*\x9ct\xc2\rl0\xbb\x9e\xbc0GV\xc5\xadG\xa89\xa0_"\x9f\xaa'

### Entschlüsselung ###
>>> random.seed("hier den Schlüssel!"); text="".join([chr(ord(e)^random.getrandbits(8)) for e in text])
>>> text
'hier kann ein beliebig langer Klartext geschrieben werden'

Anstelle des PRNG könnte man auch ein Hash-Verfahren nehmen und mit einem Schlüssel initiieren. Sicher ist daran jedoch nur das Lachen der Auditoren.

Mich würden die Einreichungen sehr interessieren. Vermutlich wird am Ende die ausgefallenste Lösung gewinnen und die Sicherheit eher auf der Strecke bleiben.

Hallo zusammen,

heute möchte ich präsentieren, welche „Alltagsprobleme“ sich in der Kryptologie wiederfinden.

Vor kurzem hat mich jemand angeschrieben, er säße vor einem kleinen mathematischen Problem. In seinem Dorf ist ein so genanntes Kuhfladen-Bingo geplant. Dafür muss ein Feld von fester Größe, in eine dynamische Anzahl kleinerer unterteilt werden. Nochmal langsam:

Wir haben zunächst das große Feld bzw. die Wiese. Diese hat eine konstante Größe bzw. im Falle, dass sie rechteckig ist, eine Länge und eine Breite. Jetzt haben wir x Lose verkauft und wollen dieses Feld in x-viele gleichgroße „kleine“ Felder aufteilen. Die Summe aller kleinen Flächen entspricht der Gesamtgröße – also wir wollen stets einen Gewinner und keine „unbesetzten“ Felder. Es soll also ein Schachbrettmuster auf dieses Feld gelegt werden, wobei in diesem Fall die kleinen Felder nicht quadratisch sein müssen.

Mathematisch ausgedrückt, suchen wir zwei ganzzahlige n und m, wobei n*m = x und x die Anzahl der verkauften Lose ist. Kennen wir n und m, können wir die Länge bzw. Breites des Feldes durch n bzw. m teilen und erhalten die Größe der „kleinen“ Rechtecke. Ein Beispiel:

Das Feld ist L=8 x B=16 Meter groß. Es wurden zufällig 1024 Lose verkauft. Also suchen wir:

n * m = 1024

Eine Lösung ist: n = 4, m=256. Demnach teilen wir die Länge L=8m durch 4 und erhalten l=2m – außerdem die Breite B=16m durch 256 und erhalten b=0,0625m. Ein kleines Feld hat also die Ausmaße l=4m und b=6,25cm. Wie wir allerdings schnell erkennen, gibt es bei dieser Gleichung mehrere Lösungen. Ebenso wären n=8, m=128 und sogar die triviale Lösung n=1 und m=1024 in der Lösungsmenge enthalten.

Einen naiven Lösungsalgorithmus finden wir also schnell: wir suchen einen Teiler von x im Intervall [2, sqrt(x)] also zwischen 2 und der Wurzel von x. Bei x=1024 ist das die 2, die 4, die 8, die 16 und die 32. Das lässt sich relativ einfach mit einer Schleife realisieren.

Daraufhin ergab sich die Frage, ob dafür nicht auch eine bessere bzw. effizientere Lösung existiert. Das Beste wäre eine Formel, in welcher nur die Variablen einzutragen sind und dann ein brauchbares (nichttriviales) Ergebnis präsentiert. An dieser Stelle möchte ich dem Leser Zeit geben um darüber nachzudenken. Auch bezüglich der Frage, warum sich dieses Problem in einem Blog über Kryptologie wiederfindet.

~

Ich habe eben gezeigt, dass wir bei diesem Problem zwei ganzzahlige Teiler suchen: n und m bzw. n*m=x. Ich ändere nun mal die Namen der Variablen: p*q=m. Sei also m ein RSA-Modul, also das Produkt zweier Primzahlen, so sind p und q ganzzahlige Teiler von m. Wir haben also „mehr oder weniger“ nach einem effizienten Algorithmus bzw. einer Formel gesucht, die RSA-Verschlüsselung zu brechen. Wären wir an jenem Abend erfolgreich gewesen, würde ich diesen Blogeintrag an einem Strand in der Karibik zu Ende schreiben.

Wie schon oft erwähnt, ist die „schwierige“ Suche nach den Primzahlen p und q genau das, was die RSA-Verschlüsselung ausmacht. Und die Tatsache, dass für p*q=m (p,q prim) bisher noch kein effizienter Algorithmus gefunden wurde, bietet uns Schutz bei Online Banking, Zertifikaten (PKI), VPN-Tunneln und vielem mehr.

Moooooooment. Da steht doch p*q=m (p,q prim) – also wir suchen zwei Primzahlen dessen Produkt m ergibt. Bei unserem Problem oben war jedoch die Rede von einem beliebigen Teiler! Stimmt. Es folgt ein Ausflug in die Zahlentheorie und theoretische Informatik.

Angenommen wir hätten das oben beschriebene Feldaufteilungsproblem effizient gelöst, dann wären wir im Besitz einer Formel oder eines Algorithmus, den wir einfach F nennen – F für Feld. Wir übergeben dem Algorithmus F also die Anzahl der Lose und selbiges generiert uns zwei ganzzahlige Teiler n und m. Auf der anderen Seite haben wir das RSA-Problem – wir besitzen also einen „langsamen“ Algorithmus für dieses Problem und nennen diesen R. Wir übergeben R ein RSA-Modul (also das Produkt zweier Primzahlen) und es liefert uns das entsprechende p und q.

Damit sind F und R also informell definiert. Nun übergeben wir, nur aus Spaß, unserem Feldproblem F ein RSA-Modul, sagen wir r(=p*q). Warum auch nicht – es ist ja auch nur eine Zahl. F liefert uns nun also zwei ganzzahlige Teiler n und m wobei gilt: n*m=r. Jetzt wird’s spannend: nach dem Fundamentalsatz der Arithmetik ist die Primfaktorzerlegung eindeutig und stets existent. D.h. das, was wir hier zurückbekommen, müssen p und q sein. Warum? Angenommen es gäbe noch eine andere Aufteilung z.B. a*b=r, dann hätte sowohl a, als auch b eine Primfaktorzerlegung (Existenz!) welche nicht mit p*q übereinstimmt. Das ist ein Widerspruch zur Eindeutigkeit – somit haben wir indirekt p=n und m=q bewiesen. #

Dieser Teil muss nun nicht unbedingt verstanden worden sein. Wichtig ist nur, dass wir das Problem R, also die Zerlegung eines RSA-Moduls, mit Hilfe von F lösen können. In der Informatik spricht man hier auch von Turingreduzierbarkeit. Wenn wir wissen, dass wir R mittels F lösen können, dann muss R „leichter“ sein als F, bzw. „R ist turingreduzierbar auf F“ oder „F ist Orakel für R“. So lassen sich Probleme in Klassen einteilen, was relativ komfortabel ist: sobald wir einen guten Algorithmus für F gefunden haben, ist auch effizient R gelöst. So müssen wir also nur nach einer Lösung für F suchen, wobei diese auch schwieriger sein könnte als R. Äquivalenz liegt vor, wenn eine Reduktion in beiden Richtungen möglich ist. Um die Frage vorweg zu nehmen: dies ist hier der Fall; F und R sind Turing-Äquivalent (ohne Beweis).

So sind wir von den Kühen, über die Kryptologie, zur theoretischen Informatik gekommen.

Hallo,

zunächst eine Warnung: dieser Beitrag ist relativ schwierig und ohne Vorkenntnisse in theoretischer Informatik nicht zu verstehen.

Im Laufe einer Lehrveranstaltung hat sich die Frage gestellt, ob die Primfaktorzerlegung (genauer: RSA – also 2 Primfaktoren) in NP liegt bzw. sogar NP-vollständig ist – ums populärer auszudrücken: wie viel Ärger bekommen wir, falls P=NP gilt.

Wir haben allerdings an dieser Stelle jedoch das Problem, dass die Komplexitätsklasse NP bzw. die Laufzeitfunktion NTIME auf Sprachprobleme – also Entscheidungen definiert ist. Innerhalb der Literatur finden sich wenig und vor allem sehr oberflächliche Aussagen darüber („es ist leicht einzusehen dass dieses Problem in NP liegt…“). Die letzten Wochen habe ich intensiver darüber nachgedacht und ich denke, eine brauchbare Lösung anbieten zu können.

Zunächst wichtige Vorarbeit:  die Frage, ob eine natürliche Zahl eine Primzahl ist oder nicht, liegt in P (also deterministischer Polynomialzeit). Erreicht wird dies durch den AKS-Primzahltest. Damit ist auch die Frage, ob eine Zahl n (ungleich 1) Primteiler besitzt in P feststellbar, da dies immer der Fall ist, sofern es sich um keine Primzahl handelt (Hauptsatz der Zahlentheorie).

Im nächsten Schritt prüfen wir, ob die Zerlegung des RSA-Moduls in NP liegt.

Nehmen wir hierzu beispielhaft die Primzahlen p=7 und q=11 also M=p*q = 7*11=77, binär dargestellt 1001101. Mittels eines naiven Nichtdeterministischen Algorithmus, können wir von 1 bis sqrt(M) alle möglichen Teiler durchprobieren. Dass dies in NP liegt, soll mittels der Abbildung gezeigt werden. Die Baumtiefe entspricht n/2, also die halbe Eingabelänge n(=7). Der Übersicht halber hier nur die Tiefe 3 anstelle 4.

Durch diese Verzweigung erhalten wir also alle Lösungskandidaten h.

Im blauen Kasten prüfen wir nun, ob h ein Primteiler von M ist. Sowohl der Primzahltest „ist h eine Primzahl?“ liegt in P (wie oben erwähnt), als auch die Division „ist h ein Teiler von M“. Auch würde der Primzahltest des zweiten Divisors in P liegen. Dementsprechend liefert der skizzierte Nichtdeterministische Algorithmus am Ende ein „ja“, da 111 (=7) sowohl Primzahl, als auch Teiler von M (77) ist.

Wir haben also nun festgestellt, dass die Frage nach der Primfaktorzerlegung in NP liegt. Das hilft uns allerdings nur bedingt, da diese Antwort schon vorher bekannt war. Per Definition besitzt ein RSA-Modul zwei Primteiler, daher würde der Algorithmus natürlich stets ein ja liefern. Wir müssen also dieses Entscheidungsproblem (1)  nutzen, um effizient das Optimierungsproblem (2) zu lösen.

Aus diesem Grund definieren also das Problem in folgender Weise neu:

Eingabe: (M,k) wobei m das RSA-Modul (bestehen aus dem Produkt zweier Primzahlen), und k eine beliebige Zahl k<=M.

Zulässige Lösung: ja/nein

Frage: liegt ein Primfaktor des RSA-Moduls M unterhalb von k.

Wir übergeben also das Modul M=(p*q) und fragen, ob sich der kleinere Primfaktor unterhalb von k befindet. Dieses Entscheidungsproblem ändert am oben skizzierten Algorithmus die Laufzeit nur um einen konstanten Faktor, welche in der polynomiellen Unschärfe sowieso verschwindet. Wir sind inder Lage, wie in der nächsten Abbildung zu sehen, mittels einer binären Suche den Primfaktor exakt zu bestimmen:

Können wir also das Entscheidungsproblem (1) als Orakel verwenden, so lässt sich auch dieses Optimierungsproblem (2) sehr effizient (logarithmisch) lösen. Die binäre Suche geht in der polynomiellen Unschärfe verloren, womit wir informell bewiesen haben: bei P=NP liegt die Faktorisierung auch in P.

Welche Auswirkungen hätte P=NP auf den Alltag? Diese Frage lässt sich leider nicht beantworten, da nicht jeder Algorithmus in P auch effizient ist. Wäre der Exponent jedoch niedrig, wären die Folgen schwerwiegend: die PKI würde zusammenbrechen, wodurch sicheres Online Banking unmöglich wäre. Jedes asymmetrische und damit auch jedes hybride Verschlüsselungssystem wäre hinfällig. Die Quantenkryptographie, die hiervon nicht betroffen wäre, liefert keinen adäquaten Ersatz.

Hoffen wir also, dass P != NP gilt.