Diese Vorlesung greift das beim letzten Mal skizzierte RSA-Verfahren wieder auf. Wir schauen uns die verwendeten mathematischen Mechanismen an und werfen einen Blick auf einige fundamentale Attacken.
Die Schlüsselparameter n, e, p, q, d werden als öffentlich und privat unterschieden. Wenn n ein öffentlicher Schlüssel ist und p, q geheim sind, dann funktioniert das nur, wenn das Zerlegen von ganzen Zahlen in ihre Primfaktoren ein schweres Problem ist. In der Tat gibt es dafür keinen Beweis. Es gibt nur den Anhaltspunkt, nämlich dass sich Mathematiker viele Jahrzehnte an diesem Problem versucht haben (ernsthaft etwa ab Mitte der 1970er Jahre) und es bisher keinen effizienten Algorithmus gibt.
Beachten Sie die extrem einfachen Formeln zum Verschlüsseln und zum Entschlüsseln unten rechts.
m^e mod n ergibt den verschlüsselten Text m'
(m')^d mod n ergibt wieder den Klartext m
Diese Einfachheit ist auch ein Grund dafür, warum RSA sich als Public Key Verfahren so schnell durchgesetzt hat.
Wir benötigen eine Funktion phi(n), diese gibt die Anzahl der zu n teilerfremden Zahlen kleiner als n. Um dies einordnen zu können, probieren wir ein paar Beispiele: phi(12), phi(7), phi(9). Diese Werte werden durch Aufschreiben der Menge dieser teilerfremden Zahlen bestimmt. Beispielsweise sind 1, 5, 7, 11 die einzigen zu 12 teilerfremden Zahlen, die < 12 sind. Daher ist phi(12)=4. Für Primzahlen sind viel mehr Zahlen teilerfremd. Eigentlich alle. Daher ist phi(p)=p-1, im Beispiel sehen wir das an p=7.
Die beiden Formeln für phi(p^n) und phi(p*q) verdienen auf der nächsten Folie nähere Aufmerksamkeit.
Anstatt die zu p^n teilerfremden Zahlen zu zählen, zählen wir das Gegenteil, diejenigen, die mit p^n einen gemeinsamen Faktor haben. Offenbar sind das genau die, die einen Faktor p in ihrer Zerlegung haben. Anders ausgedrückt, das sind alle Vielfachen von p. Preisfrage ist, wieviele Vielfache von p gibt es, die < p^n sind?
Nachdenken.
Nochmal lesen.
Nachdenken.
Okay, es gibt die Vielfachen 1*p, 2*p, 3*p,...,p^(n-1)*p.
Das letztere Vielfache ist aber schon p^n. Also ist die richtige Antwort: ein Vielfaches weniger als diese Liste. Das sind p^(n-1)-1 Stück.
Da wir mit dem Gegenteil gerechnet haben, ist die uns interessierende Größe
(alle Zahlen < p^n) - (berechnete Anzahl)
und es kommt p^n - p^(n-1) heraus.
Die gleiche Betrachtung geschieht für n=p*q mit Primzahlen p, q.
Die Vielfachen von p sind wieder 1*p, 2*p, 3*p,... und die Vielfachen von q sind 1*q, 2*q, 3*p,...diese beiden Mengen muss man aus 1,2,3,...,p*q herausnehmen und es ergibt sich die Formel im roten Kasten.
Warum funktioniert RSA, d.h. warum ist die Entschlüsselung der Verschlüsselung wieder der Klartext?
Die Folie dürfte selbsterklärend sein.
Zwei Beschleunigungen von RSA werden gezeigt.
Kleine Exponenten bedeuten wenige Multiplikationen. Es ist unklar, ob kleine Exponenten eine Sicherheitslücke darstellen. Schon seit langer Zeit wird e=65537 empfohlen, das ist e=2^16+1.
Der Chinesische Restsatz (CRT) erlaubt dem Besitzer des geheimen Schlüssels, die Entschlüsselungsformel (Folie 1) mod p und mod q auszuführen und das Ergebnis zusammenzusetzen. Insgesamt hat man das Verfahren durch CRT um den Faktor 4 beschleunigt.
Der Status der Attacken auf RSA ist für e und d durch schlechte Parameterwahl wie viel zu kleines e<=5 oder d (siehe Folie) gegeben. Die für den Angreifer unbekannte Faktorisierung von n kann mit subexponentiellen Algorithmen erzielt werden. Subexponentiell wird durch den exp(...)-Ausdruck dargestellt und liegt damit zwischen L(0,b) polynomiell und L(1,b) exponentiell.
Der Faktorisierungsrekord mit dem schnellsten dieser Algorithmen (Number Field Sieve) liegt bei 829 Bits.
Der Foliensatz schließt mit einer Betrachtung, welche Attacken auf welche empfohlenen Schlüssellängen führen.
Habe ich eine Attacke mit polynomieller Laufzeit (d.h. effizient), dann ist das Verfahren kryptographisch unbrauchbar, denn die geheimen Schlüssel können schnell ausgerechnet werden.
Habe ich nur Attacken mit subexponentieller Laufzeit oder schlechter, dann ist die Empfehlung für die geheimen Schlüssel bei 2048 Bits und höher.
Habe ich nur Attacken mit exponentieller Laufzeit, dann ist die Empfehlung für die geheimen Schlüssel bei 128 Bits oder 256 Bits.