Cryptography Reference
In-Depth Information
Faktorisierung
Eine weitere Einwegfunktion ist die Faktorisierung einer großen Zahl in ihre Primfaktoren.
Wenn diese Primzahlen bekannt sind, dann ist es leicht, diese zu multiplizieren. Dagegen ist es
praktisch nicht durchführbar, eine große Zahl in ihre Primfaktoren zu zerlegen.
Das Faktorisierungsproblem wird bei RSA (Kap. 4.2) und bei der Authentifikation nach Fiat-
Shamir (Kap. 5.4) benutzt, um für das asymmetrische Schlüsselpaar den privaten Schlüssel zu
schützen. Ohne Kenntnis der Primfaktoren kann er aus dem öffentlichen Schlüssel praktisch
nicht ermittelt werden.
1.3.5.3
Falltür-Mechanismen
Eine Falltür gibt den Weg in verborgene Räume frei, falls man ihren Riegel öffnet. Der Riegel
kann geheim sein. Man kann dann die Falltür nur öffnen, falls man dieses Geheimnis kennt. Im
übertragenen Sinn werden Falltür-Mechanismen mit einem Geheimnis auch in der Kryptogra-
phie verwendet. Jede Entschlüsselung einer verschlüsselten Nachricht kann man als Falltür
auffassen. Die Entschlüsselung ist nur dann einfach, wenn man ein Geheimnis, nämlich den
Schlüssel kennt.
Weitere Beispiele sind die asymmetrischen Schlüssel bei RSA (Kap. 4.2) und bei der Authenti-
fikation nach Fiat-Shamir (Kap. 5.4). Der private (geheime) Schlüssel kann aus dem öffentli-
chen Schlüssel nur dann ermittelt werden, wenn man ein Geheimnis kennt. Dieses besteht in
der Kenntnis der Primfaktoren p und q eines Moduls n=p·q. (Dagegen ist die Ermittlung der
Primfaktoren aus dem öffentlich bekannten Modul n ein Einwegproblem.) Bei RSA ist mit
Kenntnis von p und q der Wert der Eulerfunktion (n) bekannt, über den der private Schlüssel
berechnet werden kann. Bei Fiat-Shamir kann nur mit Kenntnis von p und q die diskrete Quad-
ratwurzel, und damit der private Schlüssel berechnet werden.
Wenn bei einem asymmetrischen Schlüssel der öffentliche Schlüssel aus dem privaten Schlüs-
sel durch diskrete Exponentiation ermittelt wurde (ElGamal, ECC, siehe oben), dann ist das
keine Falltür sondern ein Einwegproblem: Es gibt kein Geheimnis, mit dessen Kenntnis man
den diskreten Logarithmus leichter lösen könnte.
1.3.5.4
Datenkompression
Durch Datenkompression wird der Bedarf an Speicher oder Übertragungszeit vermindert,
indem die Daten in einer kürzeren Form dargestellt werden. Die komprimierte Form enthält
weniger Redundanz. Wir beziehen uns hier auf verlustfreie Datenkompression, bei der nach
einer De-Kompression die originalen Daten exakt wieder hergestellt werden (Beispiel: ZIP-
Dateiformat).
Wenn Daten zunächst verschlüsselt und anschließend komprimiert werden, dann vermindert
diese Datenkompression die Datenmenge nur wenig. Der Grund dafür ist, dass verschlüsselte
Daten mehr einem Zufallsmuster ähneln und die Redundanz bei der Kompression nicht er-
kennbar ist. Eine Kompression sollte deshalb
vor
einer Verschlüsselung angewendet werden.
Eine Kompression vor einer Verschlüsselung ist auch im Hinblick auf die Sicherheit vor kryp-
tographischen Angriffen nützlich: Die Zufalls-ähnliche Form von komprimierten Daten er-
