Kryptologie – kurz gefasst

Eine kleine Begriffskunde

Ein Beitrag von Prof. Dr.-Ing. Georg Sigl

Was unter asymmetrischer Kryptographie zu verstehen ist, wie Hashfunktionen das signieren umfangreicher Datenmengen erleichtern und welche mathematischen Probleme sich in Gittern ergeben - im folgenden Beitrag werden kryprografische Begriffe und ihre Bedeutung in der Kryptografie näher erläutert. 

Public Key Kryptographie

Sicherheit durch Faktorisierungsproblem

Die heute meist genutzte asymmetrische Kryptographie, nach ihren Erfindern Rivest, Shamir und Adleman RSA genannt, benutzt sowohl private als auch öffentliche Schlüssel, daher auch die Bezeichnung „Public Key Kryptographie“.

Im Kern beruht ihre Sicherheit darauf, dass man zwar große Primzahlen durch geeignete Algorithmen leicht generieren und auch leicht das Produkt aus zwei Primzahlen bilden kann. Zum Entschlüsseln einer Nachricht muss man aber die beiden Primfaktoren selbst kennen, denn es gibt bis heute kein effektives Verfahren, um sie „rückwärts“ aus dem Produkt zu berechnen - ein Problem, das schon Euklid bekannt war.

Diese Faktorisierung kann man beispielsweise für 119 = 7 *17 noch unschwer erraten, für große Zahlen mit etwa 3000 bit, wie sie heute zur Verschlüsselung verwendet werden, geht das jedoch nicht mehr. Der Quantencomputer wird diese Situation aber ändern.

Hashfunktionen

Schnelle digitale Signatur mit Hashwerten

Da RSA-Berechnungen sehr aufwändig sind, dauert es sehr lange bis man eine umfangreiche Datenmenge, z.B. einen Vertragstext oder ein Software Update, verschlüsselt bzw. signiert hat.

Deshalb hat man Hashfunktionen in die Kryptographie eingeführt. Eine Hashfunktion generiert aus einer langen Datei einen kurzen heute meist 256 bit langen Hashwert, der als „Fingerabdruck“ der Datei bezeichnet werden kann und anstelle der gesamten Nachricht signiert wird.

Ändert man die Datei auch nur ein wenig, dann verändert sich der Hashwert drastisch. Verwendet man kryptographische Hashfunktionen, so haben unterschiedliche Dateien auch unterschiedliche Hashwerte.

Ist dies nicht der Fall, so spricht man von einer Kollision die nicht erwünscht ist, weil dann Änderungen der Datei nicht mehr erkannt werden können. Dann kann ein Hacker beispielsweise Malware einschleusen unter Missbrauch einer Signatur eines Softwareherstellers.

Beispiel einer sicheren Hashfunktion

Die heute meist eingesetzte kryptographische Hashfunktion SHA-2 erfüllt die Kriterien für eine sichere Hashfunktion:

  • Einwegfunktion, d.h. es ist leicht y= h(x) aber extrem aufwändig und somit praktisch unmöglich die Umkehrfunktion x=h-1(y) zu berechnen
  • Kollisionsresistenz, d.h. es ist sowohl praktisch unmöglich zu einem Paar y1 = h(x1) ein zweites Paar y2 = h(x2) = h(x1) zu bestimmen als auch zwei beliebige Dateien x1 und x2 die den gleichen Hashwert liefern.

Einsatzgebiete von Hashfunktionen

Hashfunktionen haben vielfältige Einsatzgebiete. Die Speicherung von Passwörtern in Form von Hashwerten ist vermutlich der bekannteste.

Aufgrund der oben beschriebenen Einwegeigenschaft kann aus einer gestohlenen Passwortdatei das Passwort aus dem Hashwert nicht ermittelt werden.  Auf dem gleichen Prinzip der Einwegfunktion beruht die Sicherheit der Postquantum sicheren Einmalsignaturen.

Gitter

Mathematische Probleme in Gittern

Gitter (engl. Lattice) sind Unterräume von reellen kontinuierlichen mehrdimensionalen Räumen. Sie entstehen durch Addieren von reellen Basisvektoren, die mit ganzen Zahlen skaliert werden. Das erzeugt einen Raum von Punkten, die wie ein Gitter angeordnet sind. In Gittern gibt es mathematisch schwierig zu lösende, sog. NP-vollständige Probleme.

Dazu gehören das Finden des kürzesten Vektors im Gitter (SVP: Shortest Vector Problem) und das Finden des nächsten Gitterpunktes zu einem beliebigen Punkt im Raum der nicht auf dem Gitter liegt (CVP: Closest Vector Problem), siehe dazu Abbildung 1.

Gitter bestehen aus den ganzzahligen Linearkombinationen linear unabhängiger Vektoren, den Vektoren einer sog. Gitterbasis.

Wie findet man Gittervektoren, die möglichst nahe zu einem vorgegebenen Vektor liegen, der nicht zur Basis gehört, also z.B. der blaue Punkt in der Skizze (Abb. 1)?

Was im Zweidimensionalen trivial erscheint, wird in Räumen mit vielen Dimensionen ein äußerst schwer lösbares mathematisches Problem, das durch diese Eigenschaft die Sicherheit entsprechender Verschlüsselungen garantiert.

Literaturempfehlung

Die TiB Redaktion empfiehlt als Einführung zur Kryptologie: Ertl/Löhmann „Angewandte Krytografie“.