Cryptography Reference
In-Depth Information
11.1.2
Einwegfunktionen und Falltürfunktionen
Der Grund, warum die im letzten Kapitel beschriebene Modulo-Rechnung in der
Kryptografie so wichtig ist, ist folgender: Einige der Modulo-Rechenarten sind
sehr einfach durchführbar, ihre Umkehrung ist dagegen recht aufwendig. Dies
lässt sich in der Kryptografie hervorragend nutzen, wenn man eine einfache
Rechnung als Verschlüsselung und die komplizierte Umkehrung als Entschlüsse-
lung verwendet. Voraussetzung ist jedoch, dass es bei der komplizierten Umkeh-
rung eine »versteckte Abkürzung« gibt, die als Schlüssel verwendet wird. Eine
Funktion, die einfach zu berechnen ist, deren Umkehrung jedoch nur mit großem
Aufwand berechnet werden kann, nennt man
Einwegfunktion
. Existiert dagegen
eine »versteckte Abkürzung« also eine Zusatzinformation, mit der die ansonsten
schwierige Umkehrung einfach gemacht wird, dann spricht man von einer
Fall-
türfunktion
.
Der diskrete Logarithmus
Mit einem geeigneten Computerprogramm ist das Ergebnis der Formel
a
b
(mod
n
)
selbst für sehr große Werte von
a
,
b
und
n
relativ leicht berechenbar. Selbst für
über hundert Bit lange Zahlen ist bei geschickter Implementierung eine Sekunde
auf einem PC ausreichend. Vollkommen anders sieht es mit der Umkehrung, dem
diskreten Logarithmus, aus. Selbst mit größtem Hardwareaufwand und den bes-
ten bekannten Algorithmen erreicht man bei mehreren Tausend Bit schnell
Berechnungszeiten, die über die Lebensdauer unseres Universums hinausgehen.
Damit haben wir das erste Beispiel für eine Einwegfunktion:
f
(
x
)=
a
x
(mod
n
)
ist nach heutigem Kenntnisstand eine solche. Einen mathematischen Beweis dafür
gibt es allerdings nicht. Es ist daher theoretisch möglich, dass eines Tages ein
schnelles Verfahren zur Berechnung des diskreten Logarithmus entdeckt wird. Da
dies jedoch schon seit längerem erfolglos versucht wird, können wir davon ausge-
hen, dass dieser Fall nie eintreten wird.
Leider ist die Erkenntnis, dass die Modulo-Exponentiation eine Einwegfunk-
tion ist, zunächst einmal recht nutzlos. Denn Alice kann einen Klartext durch
eine Modulo-Exponentiation (wir stellen uns den Klartext in diesem Kapitel als
Zahl vor) zwar gut verschlüsseln - Empfänger Bob kann den Text jedoch nicht
mehr entschlüsseln, da es sich ja um eine Einwegfunktion handelt. Trotzdem gilt
die Modulo-Exponentiation als wichtigste Einwegfunktion der Kryptografie.
Was Alice und Bob damit machen können, werden Sie in späteren Kapiteln sehen.
Das Faktorisierungsproblem
Eine weitere wichtige Einwegfunktion ist das Multiplizieren zweier Primzahlen
(in diesem Fall ist zur Abwechslung nicht die Modulo-Multiplikation gemeint).
Eine solche Primzahl-Multiplikation ist heutzutage mit Computerunterstützung
einfach realisierbar, auch bei größeren Zahlen entstehen so schnell keine Prob-
