Lehrstuhl für Mathematik mit Schwerpunkt Symbolic Computation
Algebraische Kryptographie

Algebraische Kryptographie

Der Lehrstuhl in der Festschrift  "25 Jahre Fakultät für Informatik und Mathematik"

Was ist das denn schon wieder?

Eine der Hauptaufgaben der Kryptographie ist die verschlüsselte Übermittlung von Nachrichten über einen öffentlichen Kanal. Dabei soll ein unberechtigter Empfänger, also jemand der den Geheimschlüssel nicht besitzt, die Nachricht nicht dechiffrieren können.

Das wusste ich schon. Aber wo ist hier der Bezug zur Algebra und zu Symbolic Computation?

Wir beschäftigen uns mit zwei Bereichen der algebraischen Kryptographie. Der eine ist die Konstruktion neuer Kryptosysteme mit Hilfe von Gröbner- Basen in nichtkommutativen algebraischen Strukturen.

Aber gibt doch bereits hervorragende Verschlüsselungsmethoden wie das RSA System.

In der Tat, das RSA Kryptosystem ist das mit weitem Abstand in der Praxis am häufigsten angewandte. Aber wie alle anderen praxisrelevanten Kryptosysteme auch, hat es zwei gravierende Mankos: zum einen ist die genaue Komplexitätsklasse des zu Grunde liegenden zahlentheoretischen Problems nicht bekannt und zum anderen wurde bewiesen, dass man das RSA System mit einem Quantencomputer brechen kann. Es ist also nur noch eine Frage der Zeit bis die momentan gängigen Kryptosysteme alle unsicher sind.

Ein 16-bit Quantenprozessor

Verschlüsselungstechniken für Geschäfte im Internet

Heißt das, wenn ich auch weiterhin meine Bankgeschäfte und Einkäufe über das Internet abwickeln möchte, brauche ich neue Verschlüsselungstechniken? Dann erfinden Sie mal ganz schnell etwas. 

Wir werden unser Bestes tun. Aber bevor wir konkrete Vorschläge machen können, ist hier noch viel theoretische Grundlagenarbeit zu verrichten, da viele der Strukturen, die wir im Auge haben, bezüglich ihrer kryptographischen Verwendbarkeit noch unerforscht sind.

Sie sprachen von zwei Bereichen der algebraischen Kryptographie, in denen der Lehrstuhl aktiv ist.

Nun, es gibt natürlich noch die dunkle Seite der Macht. Hier tritt sie unter der Bezeichnung Kryptoanalyse auf. Man kann mit symbolischen Berechnungen auch versuchen, symmetrische Kryptosysteme zu knacken.

Wieder mit diesen Gröbner-Basen? Das klingt aber sehr verdächtig nach einem Allheilmittel.

Ob man am besten Gröbner-Basen, Randbasen oder andere Techniken verwenden sollte, wissen wir noch nicht. Auf jeden Fall entwickeln wir so genannte algebraische Angriffe. Das ist eine spezielle Form von Known-Plaintext-Angriffen, bei denen man die Berechnung des Geheimschlüssels zurückführt auf das Lösen eines algebraischen Gleichungssystems über einem endlichen Zahlbereich.

Und das funktioniert? Ist jetzt sogar der offizielle Advanced Encryption Standard (AES) unsicher?

So weit sind wir noch nicht. Aber es sind bereits bedeutende kryptographische Herausforderungen mit symbolischen Berechnungen gelöst worden und man sollte jedes neue symmetrische Kryptosystem erst einer Sicherheitsüberprüfung gegen algebraische Angriffe unterziehen.

Lösen von mathematischen Problemen mithilfe von „Symbolic Computation“ möglich?

Das ist ja alles kaum zu glauben. Ein Bekannter von mir hat in seiner Firma auch ein mathematisches Problem, bei dem er schon seit längerem nicht weiterkommt. Glauben Sie, dass Sie ihm mit Ihrer „Symbolic Computation“ helfen könnten?

Das weiß ich natürlich nicht. Aber wir hier am Lehrstuhl sind gegenüber Anwendungsmöglichkeiten unserer Theorien und Algorithmen immer sehr aufgeschlossen. Sagen Sie Ihrem Bekannten doch einfach, er soll sich bei uns melden.

Schematischer Ablauf eines algebraischen Angriffs