Ich wollte heute eine Schnupper-Vorlesung quasi halten, die ein
Ausschnitt ist, also ein total realer Ausschnitt aus dem Stammmodul
Sicherheit.
Trotzdem müssen wir das heute nicht so ernst sehen, weil das ist weder
prüfungsrelevant, noch müssen Sie das jetzt können.
Das können Sie sich ja im Stammmodul Sicherheit wieder anhören, wenn
Sie wollen.
Auf jeden Fall würde ich mich freuen, wenn es beispielsweise Fragen
gibt, denn ich habe mir ein, ich sage jetzt mal, anspruchsvolles,
schönes Thema rausgesucht.
Wir wollen asymmetrische Verschlüsselung besprechen.
Das heißt, was Sie vielleicht kennen, ist diese Verschlüsselung, wie
sie beispielsweise bei einer Enigma-Maschine funktioniert.
Da haben Sie irgendwie einen Schlüssel bei Alice und einen Schlüssel
bei Bob.
Die stellen dann ihre Walzen so ein, dass sie sozusagen die gleiche
geheime Einstellung haben und dann kann man auf Alice Seite Klartext
in ein Schiffrat verwandeln und dieses Schiffrat eben auf Bobs Seite
wieder entschlüsseln, indem man dieses Schiffrat eingibt, bei
identischer Walzenstellung und dann wird sozusagen daraus wieder ein
Klartext.
Es ist allerdings so, dass das eigentliche, das eigentlich
Interessante ist nicht, was die Kryptografie drei, vier tausend Jahre
lang getan hat, denn drei, vier tausend Jahre lang war das Thema
tatsächlich, wie schaffe ich es, wenn Alice und Bob einen Schlüssel
haben, diesen Schlüssel zu benutzen.
Das ist inzwischen gar nicht mehr so das Thema, sondern die Frage ist
eher, wie kommen Alice und Bob dazu, einen gemeinsamen Schlüssel zu
haben.
Haben die sich mal getroffen?
Kann man das im Internet von heute auch sich ständig treffen, um einen
Schlüssel auszutauschen?
Nein.
Was es da gibt, was sozusagen das eigentliche Wunder ist, von dem ich
heute berichten will, ist, inzwischen gibt es sogenannte asymmetrische
Verschlüsselung.
Das heißt, Alice und Bob haben nicht mehr denselben Schlüssel, sondern
es gibt für ein Verschlüsselungsverfahren zwei Schlüssel.
Ein Schlüssel, der öffentlich bekannt sein darf und einen Schlüssel,
den man geheim hält.
Der öffentlich bekannte Schlüssel dient der Verschlüsselung.
Das heißt, jeder kann verschlüsseln und dem legitimen Empfänger dann
die verschlüsselte Nachricht schicken und nur der kann entschlüsseln,
weil nur er den geheimen Schlüssel hat.
Und als ich das erste Mal davon gehört habe, dass es sowas gibt, habe
ich gedacht, so ein Quatsch.
Und jetzt möchte ich sozusagen versuchen, Ihnen plausibel zu machen,
dass das tatsächlich funktioniert.
Und wir werden da ein bisschen auch Mathematik machen müssen.
Wenn wir es wirklich verstehen wollen, müssen wir heute nicht.
Sie können gerne auch Zwischenfragen stellen.
So, das Ziel ist ein sicherer Nachrichtenübermittlungskanal.
Also wir haben einen Kanal, der ist unsicher im Sinne von, da hängt
ein Lauscher dran.
Da muss ich schon mal sagen, im Vorgriff auf später, man kann sich
unsichere Kanäle auf zwei Arten vorstellen und es macht auch einen
großen Unterschied.
Einmal, dass da jemand lauscht und zum anderen, dass jemand vielleicht
Nachrichten abfängt und verfälscht weiterleitet.
Letzteres ist natürlich noch viel schwieriger zu schützen.
Wir werden heute wahrscheinlich hauptsächlich nur betrachten, dass
jemand am Kanal lauscht.
Also wir haben einen Kanal, da lauscht jemand dran und wir wollen
trotzdem sicher kommunizieren.
Das heißt, Bob schickt Alice ein Chiffrat C statt einer Nachricht.
Und jetzt, was wollen wir?
Wir wollen, dass Bob dieses Chiffrat aus der Nachricht berechnen kann.
Alice kann wieder die Nachricht aus dem Chiffrat zurückgewinnen.
Und jetzt kommt so ein bisschen Wischiwaschi und ich glaube, es war
auch 4000 Jahre lang nicht klar, was das eigentlich bedeutet.
Wir wollen irgendwie, dass ein Außenstehender aus dem Chiffrat keinen
Hinweis auf die Nachricht kriegt.
Und es war ein Riesendurchbruch für die Kryptografie, als man das
überhaupt erstmal formal gefasst hat.
Also bei dem Entwickler der Enigma, der wusste nicht, was er
eigentlich will und hat es auch nicht geschafft.
Ja, asymmetrische Verschlüsselung ist jetzt etwas, was wir eigentlich
haben wollen, denn wie bei der Enigma hätten wir jetzt Alice hat einen
Schlüssel K im Index geschrieben, Bob hat einen Schlüssel K im Index
geschrieben, das ist derselbe Schlüssel und jetzt verschlüsselt man
dann mit diesem Schlüssel K die Nachricht M, erhält das Chiffrat.
Das heißt, um aus der Nachricht das Chiffrat zu berechnen und um aus
dem Chiffrat die Nachricht zurückzugewinnen, brauche ich dieses
Geheimnis.
Das ist aber in zweierlei Hinsicht problematisch.
Die eine problematische Situation ist die, wenn ich viele, viele Leute
im großen, weiten Internet habe, dann braucht jedes Paar von Leuten so
einen Schlüssel.
Das heißt, ich brauche quadratisch viele Schlüsselpaare, damit das
überhaupt funktioniert, aber das finde ich noch nicht mal das
Schlimme, weil Speicher kostet ja nichts.
Das eigentlich Problematische ist, dass die Schlüsselverteilung
problematisch ist.
Das heißt, sie müssten sich persönlich treffen oder sie brauchen
irgendeinen sicheren Kanal, um den Schlüssel zu übertragen.
Dabei wollen sie ja einen sicheren Kanal mit dem Schlüssel
realisieren.
Das beißt sich irgendwie ein bisschen.
Es beißt sich nicht ganz.
Es ist eigentlich ein Verlagern in der Zeit.
Das heißt, wenn sie jetzt einen sicheren Kanal haben, weil sie sich
jetzt gerade treffen, können sie einen Schlüssel vereinbaren, den sie
später benutzen können, um einen unsicheren Kanal sicher zu machen.
Trotzdem, wenn sie jetzt mit irgendeinem Webshop oder einer Webseite
verschlüsselt kommunizieren wollen, wollen sie nicht erst hinfahren
müssen.
Und da, tata, Merkel und Diffie und Hermann haben tatsächlich sich
dieses Problems angenommen.
Merkel war der Erste, der eine Lösung vorgeschlagen hat, ganz links
der Herr.
Der hatte folgende Idee und ich sehe schon, wenn ich Anekdoten
erzähle, kommen wir mit dem Stoff gar nicht durch.
Macht aber nichts.
Wissen wir ja nicht.
Merkel hatte folgende Idee.
Wir verschicken Rätsel.
Und zwar Rätsel der Form, dass die Lösung eines Rätsels uns eine
eindeutige Nummer gibt.
Das ist Teil der Lösung.
Und einen geheimen Schlüssel, auch Teil der Lösung.
Aber man muss dieses Rätsel echt knacken, um an diese Nummer, um
diesen Schlüssel zu kommen.
Und jetzt war die Idee von Merkel, ich schicke Bob hunderttausend
Rätsel.
Der wählt irgendeins zufällig aus, löst es und schickt mir zurück,
welche Nummer er herausgekriegt hat.
Dann weiß ich, welches Rätsel er gelöst hat und kann den zugehörigen
Schlüssel sozusagen verwenden, um mit Bob zu kommunizieren.
Jeder, der aber an der Leitung gelauscht hat, muss fast alle Rätsel
lösen, um diese Nummer und diesen Schlüssel zu finden.
Das heißt, wir haben so einen kleinen Vorteil gegenüber dem Angreifer.
Der ist noch nicht groß genug, um irgendwas draus zu machen, was
sicher ist.
Aber es war das erste Mal, dass überhaupt jemand gesagt hat, hey, da
könnte prinzipiell was gehen.
Wir könnten Rätsel stellen auf eine Art und Weise, dass das Rätsel das
Bob lösen muss, um den richtigen Schlüssel rauszukriegen, substanziell
einfacher ist als das Rätsel, das ein Externer, ein Außenseiter lösen
muss, um rauszufinden, welches der Schlüssel ist, der verwendet wurde.
Leider trägt das nicht sehr weit, aber es war trotzdem eine tolle Idee
und es war auch in der richtigen Zeit, so in der Mitte der 70er.
Diffie und Hellman haben dann die Idee tatsächlich auf den Punkt
gebracht und haben gesagt, was wir eigentlich bräuchten, wäre ein
Verschlüsselungsverfahren mit zwei Schlüsseln, einem Schlüssel zum
Verschlüsseln und einem Schlüssel zum Entschlüsseln.
Und das war sozusagen, wie sie sich das vorgestellt haben, die
asymmetrische oder die sogenannte Public Key Verschlüsselung.
Jeder darf im Prinzip den Public Key kennen, den stellen wir uns vor,
der steht in so einer Art Telefonbuch.
Und Bob benutzt jetzt den Public Key von Alice, um zu verschlüsseln.
Er benutzt einen Verschlüsselungsalgorithmus, der nur diesen Public
Key und die Nachricht M verwendet.
Daraus kommt das Schiffrat, das schicken wir an Alice und Alice hat
einen Secret Key SK und kann damit tatsächlich entschlüsseln, aber
hoffentlich niemand sonst.
Also, verschlüsseln nur mit dem Public Key und der Nachricht,
entschlüsseln nur mit dem Secret Key.
Public Key und Secret Key werden von Alice irgendwie gleichzeitig
generiert, denn es sollte auf jeden Fall schwierig sein, aus einem
Public Key ein Secret Key zu gewinnen, sonst wäre das nicht sicher.
Das heißt, Alice wählt irgendwie Zufall und generiert daraus einen
Public Key und einen Secret Key.
Und wenn Sie sich jetzt fragen, was dieses 1 hoch K da soll, das macht
man, das ist eine unäre Codierung der 1.
Das macht man nur, damit dieser Algorithmus, der eigentlich gar keinen
Input hat, trotzdem ein formal, ein Polynomialzeitalgorithmus ist.
Niemand macht das wirklich so, das macht man nur so, damit man
leichter sprechen kann, dass der Polynomialzeit ist.
Sonst wäre das ja gar nicht definiert, ein Algorithmus, der keinen
Input hat, in was soll der denn polynomiell sein?
Und da sagen wir, im Sicherheitsparameter.
Ja, im Sicherheitsparameter oder in der Codierung des
Sicherheitsparameters, im Sicherheitsparameter.
Deshalb geben wir, um es formal klar zu machen, immer den
Sicherheitsparameter K unäher noch zusätzlich dazu, damit wir sagen
können, der Key Generation Algorithmus, der sozusagen den Public Key
und den Secret Key gleichzeitig generiert, der ist ein
Polynomialzeitalgorithmus.
Und der Public Key darf dann veröffentlicht werden und der Secret Key
muss bitte geheim bleiben.
Jawohl.
Es gibt auf einmal keine geheime Schlüsselverteilung mehr, für die man
sich treffen muss, sondern der Public Key ist öffentlich.
Was ich dazu sagen muss, es ist noch unheimlich wichtig, dass Sie
wissen, wem welcher Public Key gehört.
Das ist auch im Internet vielleicht ein Problem, wenn Sie jemanden
nicht kennen.
Aber prinzipiell, wenn es ein vertrauenswürdiges Telefonbuch gibt,
dann wäre dieses Problem gelöst und dann könnten Sie auf die geheime
Schlüsselverteilung verzichten.
Bei N Benutzern haben wir nicht mehr quadratisch viele Schlüssel, die
wir vorhalten müssen, sondern ich kann mir im Prinzip, muss ich mir
für jeden, mit dem ich rede, nur einen Public Key merken.
Und wenn es so ein öffentliches Telefonbuch gibt mit den Public Keys
drin, dann muss ich mir vielleicht gar nicht viel merken, sondern kann
immer danach schauen.
Aber das Problem war, Diffie und Herman hatten zwar diese Idee, aber
sie wussten nicht, wie es geht.
Das ist jetzt ein bisschen unfair, die haben ein
Schlüsselaustauschverfahren erfunden, das es heute noch gibt.
Und dieses Schlüsselaustauschverfahren ist aber nicht ein Public Key
Verfahren, denn es gehen mehrere Nachrichten hin und her.
Das heißt, es war nicht so, dass Bob einfach unter Kenntnis von
Alice's Public Key eine Nachricht verschlüsseln kann und ihr schicken
kann, sozusagen nicht interaktiv übersenden, sondern es war so, man
musste ein paar Nachrichten hin und her schicken und danach hatte man
auf einmal einen gemeinsamen Schlüssel, den man für die Kryptografie
verwenden kann.
Und die Tatsache ist, das Diffie-Herman-Schlüsselaustauschverfahren
wird heute noch im Internet verwendet, ist ganz wichtig, aber die
Public Key Kryptografie, das sozusagen so ein Public Key genug ist, um
jemandem eine Nachricht verschlüsseln zu schicken, das war in ihrem
Paper, wo sie diesen Schlüsselaustausch erfunden haben, das auch New
Directions in Cryptography heißt, ein ganz wichtiges Papier ist.
Diese Public Key Kryptografie war nur so eine Vision.
Die hatten diese Vision, sie wussten aber nicht, wie es geht.
Und da kamen Rivest, Charmier und Edelmann und haben das Verfahren RSA
erfunden.
Und jetzt fragen Sie sich vielleicht, warum ist RSA nicht in
alphabetischer Reihenfolge?
Ist da vielleicht die Contribution nicht ganz gleich von allen?
Und genau so ist es.
Rivest und Charmier haben ein Verfahren erfunden und Edelmann hat es
gebrochen.
Und daraufhin haben Rivest und Charmier noch ein Verfahren erfunden
und danach konnte Edelmann es nicht mehr brechen.
Und deshalb fanden die drei wohl, dass Edelmanns Contribution nicht so
hoch war wie die von Rivest und Charmier.
Und deshalb heißt es RSA das Verfahren.
Und ich glaube, die eigentliche Anekdote ist, dass, glaube ich, Rivest
es erfunden hat.
Es ist ein riesiges Aha-Erlebnis beim Skifahren.
Dann hat es ihn hingebrezelt und dann hat Charmier ihm geholfen, die
Idee zu rekonstruieren, die er da hatte, bevor er hingefallen war.
So, wir werden jetzt das RSA-Verfahren besprechen.
Das ist so ein Public Key-Verfahren.
Das wird ein bisschen mathematisch sein.
Ich werde versuchen, es gleichzeitig mathematisch und anekdotisch zu
erklären, damit Sie auf jeden Fall was mitnehmen.
Beim RSA-Verfahren hat man einen Public Key und einen Secret Key.
Der Public Key ist eine große Zahl N, ein Modulus, weil wir Modulo
dieser Zahl rechnen.
Ich weiß nicht, ob Sie Modulo-Rechnen schon ausreichend gewürdigt
haben im zweiten Semester.
Das macht man ständig.
Das ist im Prinzip so, wie Sie die Uhrzeiten betrachten.
Die Uhrzeiten betrachten Sie Modulo 12.
Das heißt, immer wenn es 13 schlägt, rechnen Sie Modulo 12.
Das heißt, Sie ziehen die 12 so lange ab, bis Sie wieder in dem
Bereich zwischen 0 und 12 sind.
Das heißt, Sie sagen dann, es ist ein Uhr.
Und dieses Rechnen wie auf der Uhr, das kann man auch mit anderen
Zahlen machen, irgendwie Modulo 17 und sowas.
Und hier rechnen wir Modulo einen sehr großen Modulus N.
Das heißt, wir rechnen nicht mit den ganzen Zahlen, sondern wir
rechnen mit den ganzen Zahlen, solange sie klein genug sind.
Und wenn sie größer werden als der Modulus, dann ziehen wir den
Modulus so lange ab, bis wir wieder kleiner sind als der Modulus.
Und außerdem gibt es einen öffentlichen Exponenten E und einen
geheimen Secret Key, einen geheimen Exponenten D.
Ja, dieser öffentliche Modulus ist das Produkt von zwei hinreichend
großen Primzahlen.
Und das ist auch immer der Grund, warum man hört, dass Primzahlen so
wichtig sind in der Kryptografie.
Das liegt hauptsächlich an dem RSA-Verfahren, wo das tatsächlich eine
wesentliche Rolle spielt.
Dass, wenn Sie einen solchen Modulus gegeben haben und der ist
wirklich groß genug, dass das Zurückgewinnen der Zahlen P und Q, also
das Faktorisieren in die beiden Primzahlen, dass das sehr, sehr, sehr,
sehr, sehr schwierig ist.
Dazu muss ich sagen, wenn Sie faktorisieren können, dann haben Sie RSA
gebrochen.
Klar, ob RSA brechen schon so schwierig ist, dass Sie mit einem
Algorithmus, der RSA brechen kann, auch faktorisieren könnten, das ist
tatsächlich noch ein offenes Problem.
Deshalb wird sozusagen häufig leider vereinfacht, also wenn jemand zu
Ihnen kommt und sagt, ja RSA ist sicher, weil faktorisieren schwierig
ist, dann weiß er entweder was, was die Community nicht weiß oder er
vereinfacht unzulässig.
Man hört es leider trotzdem häufig.
So, die Rechnungen sind in Zn.
Zn ist definiert als Z-Modulo nZ, das heißt wir rechnen Modulo dieser
Zahl n, das heißt wir rechnen in den Restklassen.
Das ist aber nichts anderes, als dass wir sozusagen nur die Zahlen
benutzen, die kleiner sind als n und immer wenn wir beim Rechnen
rausfallen, zum Beispiel zu groß werden, dann ziehen wir n ab, so
häufig, bis wir wieder im richtigen Bereich sind oder wenn wir zu
klein werden, weil negativ, dann addieren wir halt n so häufig, bis
wir wieder im richtigen Bereich sind.
Dass das tatsächlich eine Art zu rechnen ist, die die Rechenregeln
erhält, muss man sich vielleicht mal überlegen.
Die Abbildung von den ganzen Zahlen auf die ganzen Zahlen Modulo n ist
ein Homomorphismus, also es ist eine Abbildung, die die Rechenregeln
erhält.
Und da können wir eben auch sehr schön rechnen und das werden wir
gleich.
E und D sind Exponenten und die sind in einem gewissen Sinne
zueinander in Verv, sodass eben hoch E nehmen und danach hoch D
nehmen, das soll sich irgendwie wegheben.
Werden wir gleich etwas konkreter machen, was das bedeutet.
Genauer, wir wollen, dass E mal D kongruent zu 1 ist Modulo V von n.
Also nicht Modulo n, Modulo V von n.
Wenn wir Modulo n rechnen, dann rechnen wir im Exponenten Modulo V von
n, das werde ich gleich noch versuchen, etwas klarer zu machen.
Und der Grund ist der, für die Experten gleich, Z Modulo nZ, also Zn,
wenn wir da drinnen exponenzieren, dann rechnen wir mit der
Multiplikation.
Das heißt, dass man da drinnen auch addieren kann, das ignorieren wir
mal für einen Moment.
Wir multiplizieren die ganze Zeit.
Und multiplikativ bilden einige Zahlen daraus eine Gruppe, die meisten
sogar.
Das heißt, es gibt multiplikative Inverse dazu.
Nicht zu allen, zum Null zum Beispiel nicht.
Die Null hat keine multiplikative Inverse.
Und jetzt ist es so, die Anzahl der Gruppenelemente, also die Anzahl
der Elemente da drinnen, die Inverses haben, ist genau V von n.
Und deshalb werden wir später sehen, dass wir, wenn wir multiplizieren
in der Gruppe, dass sozusagen V von n die Gruppenordnung ist.
Und das wird der Grund sein, warum E mal D ist 1 Modulo
Gruppenordnung.
Sowas bedeutet, wie diese E und D sind zueinander Inverse Exponenten.
Der Nachrichtenraum selber sind die Zahlen Modulo n.
Und wenn sich jetzt jemand fragt, wie man dann einen langen Roman mit
RSA verschlüsselt, dem sage ich unter uns, das macht man gar nicht.
Es ist dafür ein bisschen zu langsam, sondern man nimmt dann immer
sogenannte Hybridverfahren.
Das heißt, sie nehmen ein symmetrisches Verfahren und schicken mit RSA
nur noch den symmetrischen Schlüssel, den sie vorhaben zu verwenden.
Das heißt, sie würden sozusagen RSA nur benutzen, um einen Schlüssel
zu schicken, verschlüsselt mit RSA, einen symmetrischen Schlüssel.
Und mit dem symmetrischen Schlüssel würden sie dann ein ganz schnelles
symmetrisches Verfahren verwenden.
Ja, das Verschlüsseln mit dem Public Key alleine ist das Exponenzieren
mit diesem öffentlichen E Modulo n.
Das heißt, wir rechnen in diesem Zn.
Und das Entschlüsseln wird sein, das Chiffrat hoch D nehmen Modulo n.
Und wenn die eben geeignet zueinander inverse sind, dann sollte da
wieder die Nachricht M rauskommen.
So, jetzt wollen wir so ein Public Key und ein Secret Key generieren.
Das heißt, das allererste, was wir beim Public Key Verfahren machen
müssen, ist erstmal ein Public Key und ein Secret Key finden.
Die wollten wir ja irgendwie gemeinsam generieren, dann den Public Key
veröffentlichen und den Secret Key für uns geheim halten.
Wie wählt man Primzahlen?
Primzahlen haben eine sehr, sehr hohe Dichte in den Zahlen.
Also der Primzahlensatz ist irgendwie n durch log n ist die Dichte.
Der Primzahlensatz ist viel genauer als das, aber das ist jetzt so
Hörsaalversion davon, ganz schnell, ist etwa die Dichte.
Das heißt, wenn wir eine zufällige Zahl ziehen, ist die
Wahrscheinlichkeit, dass das eine Primzahl ist, gar nicht mal so
schlecht.
Und das ist auch genau, wie man Primzahlen wählt.
Wir wählen gleich verteilt eine ungerade Zahl.
Wie machen wir das, dass es die richtige Länge hat?
Damit sie die richtige Länge hat, fängt sie mit einer 1 an.
Ja, sonst hätte sie vielleicht führende Nullen und wäre viel kürzer.
Und damit sie ungerade ist, hört sie mit einer 1 auf.
Das heißt, wir schreiben mal zwei Einsen hin und dazwischen einfach
zufällig 0,1 mit Münzwurf.
Also mit thermischem Rauschen oder wo immer ihr Rechner Zufall
herbekommt.
Und dann gucken wir, ob das eine Primzahl ist und wenn nicht, machen
wir es nochmal.
Und die Primzahl dicht ist tatsächlich so hoch, dass man relativ
schnell Erfolg hat.
Und das deshalb im Mittel nicht sehr lange dauert.
Dafür muss man sehr, sehr schnell testen können, ob eine Zahl prim
ist.
Und dafür gibt es den Miller-Rabin oder auch Rabin-Miller, weiß nicht,
wie der die Contribution ist, Primzahl-Test, der eben ratzfatz schnell
ist.
Aber probabilistisch,
es gibt auch inzwischen deterministische Algorithmen, um zu erkennen,
ob eine Zahl eine Primzahl ist oder nicht.
Allerdings sind die deutlich langsamer und da in der Kryptografie
sowieso wir uns so ein bisschen auf den Zufall verlassen, wie zum
Beispiel, dass der Angreifer den Schlüssel nicht zufällig rät oder
sowas, sind wir meistens bereit, so eine ganz kleine Unsicherheit zu
akzeptieren.
Und dann nehmen wir einfach probabilistische Primzahl-Tests.
Gut.
Genauso machen wir das für Q.
Und dann haben wir sozusagen zwei Primzahlen vorgegebener Länge
gefunden, indem wir eben zwei Einzelschreiben dazwischen Zufall
einfüllen, solange bis Miller und Rabin sagen, super, das ist eine
Primzahl.
Und dann hätten wir gerne noch E und D, dass sie auf diese geschickte
Weise zueinander invers sind.
Dazu wählen wir erstmal E zwischen 3 und V von N minus 1,
solange bis E und V von N GGT 1 haben.
Da ich P und Q gewählt habe, kenne ich P minus 1 mal Q minus 1, kann
ich leicht ausrechnen.
Dadurch kenne ich V von N, das war nämlich genau V von N.
Und ich kann dann einfach da Zahlen zufällig wählen, bis mal endlich
eine Teiler fremd ist.
Das geht sogar sehr schnell, weil die Wahrscheinlichkeit, damit einen
gemeinsamen Teiler zu haben, sehr gering ist.
Und dann berechnen wir D als E hoch minus 1 Modulo V von N.
Und das machen wir mit dem sogenannten erweiterten Euklid.
Ich weiß nicht, ob Sie den hatten.
Es gibt den euklidischen Algorithmus, den hatten Sie hoffentlich im
allerersten Semester schon.
Das ist einer der ältesten Algorithmen überhaupt, wie der Name Euklid
schon verbirgt.
Also der euklidische Algorithmus, mit dem man den GGT ausrechnet.
Und jetzt kann man aber nicht nur den GGT ausrechnen mit dem
euklidischen Algorithmus, sondern es gibt eine Variante des
euklidischen Algorithmus, der auch Euklid-Lagrange-Sperlekampf
-Algorithmus genannt wird, bei dem man nicht nur den GGT rauskriegt,
sondern auch eine lineare Kombination des GGT.
Ja, das ist lebenswichtig, dass man das kann.
Denn wenn irgendjemand Sie bedroht und sagt, Sie haben einen 3-Liter
-Eimer und einen 5-Liter-Eimer und wenn Sie jetzt nicht zwei Liter
Wasser abliefern oder einen Liter oder was auch immer, dann erschieße
ich Sie oder sowas.
Ja, das ist erweitert der euklidische Algorithmus.
Sie wollen im Prinzip eine lineare Kombination machen, um eben diese
genaue Zahl an Wasser zu erreichen.
Und der erweiterte Euklid von E und V von N, der wird als GGT 1
ausgeben.
Klar, weil 1 ist der GGT, so haben wir das Ding gewählt.
Aber er gibt außerdem noch zwei Zahlen aus, um den GGT linear zu
kombinieren.
Ein Alpha und ein Beta.
Mit Alpha mal E plus Beta mal V von N ist eben genau dieser GGT, ist
eben dieser 1.
Und jetzt sehen wir, wir wollten ja die Inverse von E Modulo V von N.
Was machen wir jetzt?
Wir nehmen die Gleichung, wie sie da steht, einfach auf beiden Seiten
Modulo V von N und dann steht da Alpha mal E plus 0.
Ja, irgendwas mal V von N Modulo V von N ist 0.
Also Alpha mal E ist 1.
Aha, Modulo V von N ist Alpha mal E sowas wie die 1.
Das heißt, das Alpha ist tatsächlich die multiplikative Inverse von E
Modulo V von N.
Und so wählen wir unser D.
D ist dieses Alpha.
Und dann haben wir E und D, sodass E mal D Modulo V von N die 1 ist.
Erweiterte Euclid.
Genau.
So.
Für die Korrektheit von RFA, was sozusagen erst Verschlüsseln und dann
Entschlüsseln dieselbe Nachricht gibt, das wäre nämlich ziemlich doof,
wenn nicht, da könnte es zu Missverständnissen kommen, wollen wir also
haben, M hoch E hoch D, also was nach Potenzgesetzen M hoch E mal D
ist, soll wieder M sein, wenn wir Modulo N rechnen.
Das werden wir kurz versuchen einzusehen.
Und zwar, was eine Nebengeschichte wert wäre, aber heute keine wird,
der kleine Satz von Fermat.
Der kleine Satz von Fermat, nicht der große Satz von Fermat, sondern
der kleine Satz von Fermat sagt, für eine Primzahl P und irgendein M
zwischen 1 und P minus 1 gilt, M hoch P minus 1 ist 1 Modulo P.
Das bedeutet eigentlich nur, dass wenn wir multiplikativ rechnen
Modulo P, dann bewegen wir uns in einer Gruppe mit P minus 1 Elementen
und ein Element hoch Gruppenordnung ist 1 in der Gruppe.
Egal, kleinen Fermat können Sie, wenn Sie wollen, nachschauen.
Wir werden ihn hier einfach als Werkzeug benutzen.
Das ist der kleine Fermat, das schlucken wir jetzt für einen Moment
und werden dann damit kurz beweisen, dass das RSA korrekt ist.
Also, insbesondere gilt für alle M aus ZP und Alpha aus Z, dass M hoch
P minus 1 hoch Alpha mal M wieder M ist Modulo P. Was haben wir
gemacht?
M hoch P minus 1 Modulo P ist 1.
1 hoch Alpha ist immer noch 1.
Einmal M ist M, solange wir alles Modulo P machen.
Das heißt, diese Gleichung dürfen wir ableiten aus dem kleinen Fermat.
Die zweite Zutat, die wir brauchen, ist der sogenannte chinesische
Restsatz.
Der chinesische Restsatz sagt, dass wenn Sie eine Zahl haben, die zwei
Primfaktoren hat, also zwei verschiedene Primfaktoren, so etwas wie 15
gleich 3 mal 5, dann ist die Abbildung, die von den Zahlen Modulo 15
abbildet auf Zahlenpärchen, wobei das eine Pärchen Modulo 3 und das
andere Modulo 5 gerechnet wird.
Dass diese Abbildung eine 1 zu 1 Abbildung ist und die Rechenregeln
erhält.
Das heißt, ob Sie mit Zahlenpärchen rechnen, auf der einen Seite
Modulo P, auf der anderen Seite Modulo Q oder ob Sie Modulo N rechnen.
Das ist von den Rechenregeln her dasselbe, sagt der chinesische
Restsatz.
Das ist im Prinzip nur eine Umbenennung.
Es ist aber eine Umbenennung, die, wenn Sie die Faktorisierung nicht
kennen, sehr, sehr schwer zu berechnen ist.
Sonst wäre RSA nicht sicher.
Aber wenn Sie die Faktorisierung kennen, dann ist der chinesische
Restsatz sehr leicht zu berechnen.
Und Sie können sozusagen zu einem Zahlenpärchen die Zahl, von der Sie
kamen, ausgehen.
Oder Sie können von der Zahl Modulo 15 auf das Zahlenpärchen kommen,
indem Sie die Zahl auf der einen Seite Modulo 3 und auf der anderen
Seite Modulo 5 rechnen.
Das heißt, das ist eine 1 zu 1 Abbildung, die die Rechenregeln erhält.
Mehr brauchen wir nicht.
Insbesondere gilt, wenn x gleich y Modulo p ist und x gleich y Modulo
q, dann gilt x gleich y Modulo n.
Das heißt, wenn zwei Zahlen gleich sind, dann sind die Zahlenpärchen
nach der Abbildung auch gleich.
Und wenn Sie Pärchen vergleichen oder Zahlen vergleichen, ist
dasselbe, weil das sozusagen eine 1 zu 1 Abbildung ist, die die
Rechenregeln erhält.
Das werden wir gleich verwenden.
So und jetzt kommen wir gleich durch mit der Mathe von RSA.
Wir haben n ist p mal q und e und d wie oben.
Dann ist m hoch e mal d gleich m Modulo n für alle möglichen
Nachrichten, also in unserem Nachrichtenraum.
So, Beweis.
Es gilt e mal d ist 1 Modulo phi von n, also Modulo p minus 1 mal q
minus 1.
So haben wir das gewählt.
Deshalb gilt p minus 1 mal q minus 1, also phi von n, teilt e mal d
minus 1.
Das ist einfach nur umgeschrieben.
Wenn etwas kongruent zu 1 ist, Modulo phi von n, dann ist die
Differenz davon mit 1 etwas, was von phi von n geteilt wird.
Wenn phi von n e mal d minus 1 teilt, dann teilt insbesondere p minus
1 e mal d minus 1.
Warum?
Wenn a mal b etwas teilt, dann teilt a es erst recht.
Das ist eine transitive Relation.
Wir könnten auch hinschreiben, p minus 1 teilt p minus 1 mal q minus
1.
Trivial.
Und das teilt e mal d minus 1.
Also gilt p minus 1 teilt e mal d minus 1.
Daraus folgt, e mal d lässt sich irgendwie schreiben als ein Faktor
alpha mal p minus 1 plus 1.
Wir haben es jetzt umgeschrieben.
Statt das teilt haben wir oben hingeschrieben alpha mal p minus 1 ist
eben e mal d minus 1 und kurz umgeformt und dann kamen wir auf diese
Gleichung.
E mal d ist also alpha mal p minus 1 plus 1 für irgendein alpha.
Und jetzt ist m hoch e mal d gleich m hoch p minus 1 hoch alpha.
Das ist einfach oben im Exponenten alpha mal p minus 1 mal m.
Das ist jetzt m hoch 1.
Wir haben einfach die Gleichung da oben in den Exponenten geschrieben
und das plus 1 am Ende war dann einfach ein mal m.
Okay, Gleichung in den Exponenten geschrieben.
Und jetzt ist es so, nach Fermat, das haben wir ja vorhin genau
hergeleitet, ist das m modulo p.
Das ist genau die Gleichung von der letzten Folie.
Wir haben m hoch e d ist m modulo p.
Die gleiche Argumentationskette hätten wir für q machen können.
Das heißt, wir wissen jetzt m hoch e d ist m modulo p und m hoch e d
ist m modulo q.
Also modulo p ist das gleiche, modulo q ist das gleiche.
Ach, dann ist es auch modulo n das gleiche, wegen chinesischer
Restsatz.
Das heißt, RSA ist korrekt, bedeutet Verschlüsseln und Endschlüsseln,
da kommt immer dasselbe raus.
Also Verschlüsseln und Endschlüsseln gibt wieder dieselbe Nachricht.
Ja, das war aber eigentlich gar nicht die wichtige Frage, sondern die
wichtige Frage ist eigentlich, ist RSA jetzt sicher?
Können wir das jetzt so verwenden?
Und dazu muss man sich auch mal fragen, was sicher überhaupt bedeutet,
was erwarten wir überhaupt?
Ja, was wollen wir eigentlich?
Und damit wir jetzt nicht übermäßig übers Ziel hinausschießen in
dieser einen Schnupper-Vorlesung, schränken wir uns jetzt mal auf
passive Sicherheit ein.
Passive Sicherheit bedeutet, jemand lauscht am Kanal.
Bedeutet nicht, jemand nimmt die Nachrichten, verändert sie und
schickt sie verändert weiter, was zusätzliche Angriffsmöglichkeiten
bietet, sondern wir stellen uns jetzt einfach vor, jemand lauscht am
Kanal.
Das heißt, wir wollen jetzt Sicherheit gegen jemanden, der das
Schiffrat erfährt.
So, das sieht jetzt kompliziert aus.
Ich werde es aber versuchen, ganz anschaulich zu machen, deshalb zeige
ich es Ihnen gar nicht.
Ich mache erst das Anschauliche.
Also, die naive Vorstellung ist, dass wer das Schiffrat erfährt,
erfährt nichts über die Nachricht.
Das ist aber die naive Vorstellung.
Es könnte ja sein, dass der Angreifer die Nachricht zur Hälfte kennt.
Dann gebe ich ihm das Schiffrat und er kennt die Hälfte der Nachricht.
Aber das hat er jetzt ja gar nicht aus dem Schiffrat und die kannte er
ja sowieso.
Das heißt, man muss sich überlegen, dass der Angreifer unter Umständen
Vorkenntnisse hat.
Und deshalb ist die Idee der sogenannten semantischen Sicherheit von
Public Key Verschlüsselungsverfahren, dass egal welche Vorkenntnis der
Angreifer hat, wenn wir ihm zusätzlich noch das Schiffrat geben, lernt
er nichts hinzu.
Ich gebe mal ein Beispiel, wo das schief geht und ein historisch
interessantes.
Die Enigma-Maschine war eine elektromechanische Maschine, die hat so
Walzen gehabt, die hat sie mit jedem Tastendruck gedreht.
Das heißt, der Schlüssel, der die Walzenstellung war, hat sich mit
jedem Tastendruck verändert.
Die war sehr, sehr kompliziert, aber weil die Sparfüchse statt acht
Walzen, wie im Originalentwurf, nur drei Walzen und eine Umkehrwalze
verwenden wollten, haben die sich überlegt, wir könnten ja den
Stromfluss so machen, dass es durch die drei Walzen fließt.
Durch die Umkehrwalze und wieder rückwärts durch die drei Walzen.
Das ist dann wie sieben, fast acht.
Super.
Diese Konstruktion hat allerdings bedingt, dass, weil Strom nicht
vorwärts und rückwärts im selben Kabel fließen kann, niemals ein A in
ein A verschlüsselt werden konnte.
Ein A in ein B, kein Problem.
Ein A in ein F kam auch vor.
Alles immer abhängig von der Walzenstellung.
Bei entsprechender Walzenstellung vielleicht auch ein A in ein D.
Aber niemals ein A in ein A.
Das erzähle ich vielleicht ein andermal, was das dann für Konsequenzen
hatte für die Engländer und warum das denen beim Brechen enorm
geholfen hat.
Aber ich wollte jetzt eigentlich auf die semantische Sicherheit
hinaus.
Dies ist ein Verschlüsselungsverfahren, das nicht semantisch sicher
ist.
Es stimmt zwar vielleicht intuitiv, dass man sagt, wer das Schiffrat
kriegt, der weiß nichts über den Klartext.
Aber das stimmt nicht mehr, sobald sie Vorkenntnisse haben.
Das heißt, wenn sie zum Beispiel wissen, dass der Klartext ein reiner
Testtext ist, der nur aus Es besteht oder nicht.
Das könnte auch die geheime Botschaft sein.
Das wissen sie jetzt nicht so genau.
Ob das jetzt diese Testnachricht war, bei der wissen wir aber, dass
die nur aus Es besteht oder war das jetzt die wahre Botschaft, wo wir
eigentlich wissen wollen, was drin steht.
Und jetzt ist es so, das ist meine Vorkenntnis.
Jetzt kriege ich zusätzlich das Schiffrat und jetzt gucke ich mir das
Schiffrat an.
Und wenn in dem Schiffrat irgendwo, sieht aus wie zufällige
Buchstaben, irgendwo ein E drin vorkommt, sage ich ja, das war nicht
der Testtext.
Das wäre nie passiert.
Das heißt, wenn ich weiß, dass der Testtext nur Es enthält, weiß ich,
dass das Schiffrat kein E enthalten darf.
Und deshalb lerne ich tatsächlich etwas, wenn ich Vorkenntnisse habe,
aus dem Schiffrat.
Und das will man nicht.
Und deshalb hat man die semantische Sicherheit erfunden.
1982, das heißt die Kryptografische Blindflug für 4000 Jahre.
Und dann, dass eigentlich man sagen muss, egal welche Vorkenntnis man
hat, das Schiffrat darf einem nichts zusätzlich verraten.
Und jetzt, das sind alles nur Worte, was ich da mache, jetzt muss man
gucken, wie formalisiert man das.
Und das macht man so.
Ein Public Key Verschlüsselungsschema ist semantisch sicher, wenn es
für jede Verteilung von Nachrichten gleicher Länge, bitte gleicher
Länge, weil sonst unterscheiden Sie das Schiffrat, zwei Schiffrate,
daran, dass sie unterschiedlich lang sind.
Also, wenn für jede Verteilung auf den Nachrichten gleicher Länge jede
Funktion F und jeden probabilistisch-polynomialzeit-Angreifer A es
einen Polynomialzeit-Algorithmus B gibt, was machen wir jetzt?
Ganz genau hinschauen.
A werden wir das Schiffrat verraten.
B verraten wir das Schiffrat gar nicht.
Und wenn jetzt A irgendwas kann, was B nicht kann, dann sagen wir, das
Verschlüsselungsverfahren ist einfach unsicher.
Wir wollen, dass alles, was A kann, obwohl es das Schiffrat kennt,
soll auch B können, ohne das Schiffrat zu kennen, dann erst sind wir
zufrieden.
Das ist ein ganz starker Sicherheitsbegriff.
Das heißt, wir sagen, wir haben eine Funktion F, irgendeine Funktion
F, das gilt für jede Funktion F und diese Funktion F werten wir aus
auf dem Klartext.
Die Funktion F könnte zum Beispiel uns verraten, ob überhaupt ein E im
Klartext ist oder ob der Klartext nur aus Es besteht oder die Anzahl
der Es vom Klartext oder es könnte einfach die Quersumme der
Binärdarstellung sein oder F könnte uns den häufigsten Buchstaben der
Nachrichten...
Sie können sich was beliebiges ausdenken.
Das heißt, F gibt uns irgendeine Information über den Klartext und es
gilt für alle F, also für jede Information, die man überhaupt aus dem
Klartext rausziehen kann.
Und jetzt wollen wir, dass es zu jedem Angreifer A, der F mit einer
gewissen Wahrscheinlichkeit aus dem Schiffrat gewinnen kann, es einen
Angreifer B gibt, der mit quasi derselben Wahrscheinlichkeit F
bestimmen kann, ohne das Schiffrat überhaupt zu kennen.
Und dann sagen wir, ist das Verfahren semantisch sicher, weil nichts,
was Bedeutung haben könnte, F von Nachricht könnte ja irgendwas
Bedeutungstragendes sein.
Nichts, was Bedeutung haben kann, kann man aus dem Schiffrat besser,
substanziell besser generieren als aus dem hohlen Bauch.
So, das heißt, der Angreifer A bekommt 1 hoch K, das ist der
unäherkodierte Sicherheitsparameter, damit wir auf jeden Fall
sicherstellen, dass das Ding, wenn es ein Polyzeit-Algorithmus ist,
auch die Polyzeit zur Verfügung hat und nicht irgendjemand kommt und
sagt, ah, der Input, wer weiß, wie der kodiert ist und wer weiß, ob
das dann noch poly ist, ist uns alles egal.
Ja,
der Kollege hat recht, er sagt, er schlägt vor, wir verschlüsseln
nicht die Nachricht, sondern was anderes, was völlig Unkorreliertes.
Ja, was die Sicherheit angeht, super, was die Korrektheit angeht, mäh.
Also, die Korrektheit ist diese Forderung, dass das, was ich
verschlüssele, nach dem Entschlüsseln auch wieder da ist.
Das heißt genau, das spricht aber dafür, dass wir hier die Formel
schon richtig deuten, also der eine Angreifer kriegt sozusagen den
Public Key, das Schiffrat und soll F von M vorhersagen und die
Wahrscheinlichkeit, dass er, also er kriegt den Public Key und das
Schiffrat und die Wahrscheinlichkeit, dass er F von M ableiten kann,
minus der Wahrscheinlichkeit, dass das der Angreifer B auch kann, dem
wir das Schiffrat gar nicht sagen, das soll eine sehr, sehr kleine
Zahl sein.
Wir sagen, die ist vernachlässigbar.
Vernachlässigbar bedeutet, geht sehr schnell gegen null, wenn der
Sicherheitsparameter wächst.
Ist eine asymptotische Aussage, ist jetzt nicht so wichtig.
Für das Verständnis ist wichtig.
Ein Verschlüsselungsverfahren ist sicher im Sinne der semantischen
Sicherheit, wenn alles, was sich über den Klartext aussagen lässt, aus
dem Schiffrat, lässt sich auch über den Klartext aussagen, ohne das
Schiffrat überhaupt zu kennen.
Das heißt, die Wahrscheinlichkeit, dass meine Vorhersage besser wird,
dadurch, dass ich das Schiffrat kenne, ist winzig und geht rapide
gegen null, wenn der Sicherheitsparameter wächst.
Warum brauche ich das überhaupt?
Warum kann ich nicht sagen, dass die gleich ist, die
Wahrscheinlichkeit?
Ganz einfach, es könnte ja sein, dass der Angreifer den Schlüssel rät.
Das ist zwar absolut unwahrscheinlich, aber er könnte ja einfach raten
und dann kann er nachgucken, wenn er das Schiffrat hat und wenn er das
Schiffrat nicht hat, kann er nicht nachgucken.
Deshalb muss da ein Unterschied sein.
Das heißt, es kann nicht sein, in einem mathematisch präzisen Sinne,
dass die genau gleich sind, aber wir können diesen Unterschied
beliebig klein machen, indem wir den Sicherheitsparameter skalieren.
So, Intuition dahinter, wie ich schon sagte.
Alles, was mit dem Schiffrat über die Nachricht berechnet werden kann,
kann auch ohne das Schiffrat berechnet werden.
Leider ist diese Definition technisch sehr unhandlich.
Ja, da sind zu viele Quantoren drin, zum Beispiel für alle F.
Ja, das hätte man lieber praktischer.
Und es gibt tatsächlich einen beweisbar äquivalenten Begriff, der viel
einfacher ist, wo man sich aber vielleicht eher fragt, warum rein
intuitiv, warum ist das Sicherheit?
Und wenn Sie das jetzt gleich fragen, wenn ich den anderen Begriff
vorstelle, dann sage ich, weil er äquivalent dazu ist.
So, und der heißt Int-CPA.
Ja, das ist so eine Abkürzung.
In der Kryptographie gibt es zig Sicherheitsbegriffe.
Das ist einer davon.
Dieser ist äquivalent zur semantischen Sicherheit, bezieht sich damit
auf passive Angriffe, also aufs reine Lauschen.
Es gibt auch welche, die richten sich gegen aktive Angreifer.
Und es richtet sich manchmal auch gegen andere Angriffsarten.
Und um all diesem Zoo der Sicherheitsbegriffe besser sich merken zu
können, haben diese Abkürzungen immer ein Schema.
Und zwar wird die Sicherheit definiert über ein Spiel, das der
Angreifer nicht gewinnen können soll.
Und die ersten drei Buchstaben bezeichnen das Spiel.
Das ist in diesem Fall das Indistinguishability Game.
Ja, Int bezieht sich auf das Indistinguishability Game, das soll der
Angreifer bitte nicht gewinnen können.
Und CPA bezieht sich darauf, welche Angreifer wir zulassen.
Das sind Angreifer, die einen chosen plaintext Angriff machen dürfen.
Das heißt, die dürfen sich Chiffrate geben lassen zu einem gegebenen
Klartext.
Das ist übrigens bei Public Key Verfahren gar nichts besonderes, weil
ich selber den Public Key habe, kann ich mir zu beliebigen Klartexten
Chiffrate selber berechnen.
Das heißt, dieses CPA ist nichts wirklich sehr besonderes, kein sehr
starker Angreifer.
Wie gesagt, es ist mehr so einer, der nur lauschen kann.
Ja, aber es geht jetzt darum, ein CPA Angreifer, der also nicht sehr
stark ist, sondern mehr so aufs Lauschen ausgerichtet ist, wird dieses
Indistinguishability Game nicht gewinnen dürfen.
Das ist die Definition und dieses Definitionsequivalent zur
semantischen Sicherheit und wird einfacher sein, wenn man später mit
arbeitet.
So, das Spiel, das der Angreifer nicht gewinnen soll, geht wie folgt.
Wir geben dem Angreifer den Public Key.
Nachdem der Angreifer damit Polynomialzeit lange rumgespielt hat und
sich genau angeguckt hat oder sowas, gibt der Angreifer zwei
Nachrichten gleicher Länge raus.
M1 und M2.
Ihr glaubt vielleicht, dass diese Nachrichten die Schwäche des
Verschlüssungsverfahrens besonders auf den Punkt bringen.
Dann erhält A ein Chiffrat und dieses Chiffrat ist entweder M1 oder
M2, zufällig gewählt, sagen wir ihm aber nicht.
Das heißt, ein Challenger, ein Spielleiter nimmt vom Angreifer M1 und
M2, wählt zufällig eins davon aus, verschlüsselt das und gibt es dem
Angreifer zurück.
Und A gewinnt, wenn er B richtig rät.
Jetzt ist es so, natürlich kann A mit Wahrscheinlichkeit 50% auf jeden
Fall gewinnen, indem er einfach rät.
Und die Sicherheitsdefinition in CPA sagt jetzt im Wesentlichen, dass
er es auch nicht viel besser kann.
Also er kann auch noch versuchen den Schlüssel zu raten oder sowas,
aber das soll wieder sowas Vernachlässigbares sein, was schnell gegen
Null geht.
Aber im Wesentlichen soll jeder Angreifer höchstens vernachlässigbar
besser sein als raten.
Also für alle A soll gelten, die Wahrscheinlichkeit, dass A gewinnt
und davon ein Halb abgezogen, weil das ist trivial, die soll klein
sein.
Und dann sagen wir, das Schema ist in CPA sicher.
Die Idee dahinter ist, die Chiffrate sind ununterscheidbar, da man
insbesondere M1 oder M2 auch zufällig hätte wählen können.
Der Angreifer kann ja sagen, ich interessiere mich, ob ich ein nur E
-Chiffrat von einem zufälligen Chiffrat unterscheiden kann.
Kann man auch sagen, dass sie ununterscheidbar von Zufallsschiffraten
sind.
Ist ein äquivalenter Begriff wieder.
So.
Ohne Beweis wiederhole ich nur nochmal, ein symmetrisches
Verschlüsselungsverfahren ist genau dann semantisch sicher, wenn es in
CPA sicher ist.
Und das gilt auch für asymmetrische Verschlüsselungsverfahren.
Die Symmetrischen sind ein bisschen interessanter in diesem
Zusammenhang, weil dort das CPA tatsächlich einen Unterschied macht,
weil es einen Unterschied macht, ob ich verschlüsseln kann auf Befehl,
ob ich Chosen-Plain-Text-Angriffe durchführen kann.
RSA ist jetzt aber nicht semantisch sicher, so wie ich das vorgestellt
habe.
Beispiel.
Nehmen wir mal an, wir haben nur zwei Nachrichten.
Das ist ein Public-Key-Verfahren, wir haben nur zwei Nachrichten.
Jetzt gebe ich M1 und M2 aus, kriege ein Chiffrat zurück.
Da ich aber selber den Public-Key habe, kann ich die beiden
Nachrichten auch selber verschlüsseln und kann einfach gucken, welche
von den beiden ist es denn.
Bedeutet, ein Verschlüsselungsverfahren, das nicht randomisiert, ein
Verschlüsselungsverfahren, das immer wieder denselben Output gibt, das
deterministisch ist, das kann nicht semantisch sicher sein.
Das war 1982 eine riesige Erkenntnis und davor hatten es falsch
gemacht.
Das heißt, es war eine große Erkenntnis, dass wenn man schon Public
-Key -Kryptografie machen will, dann muss man randomisieren, sonst
erkenne ich Dinge wieder.
Und Dinge wiederzuerkennen bedeutet, mit der entsprechenden
Vorkenntnis, dass ich Dinge unterscheiden kann, bedeutet, dass ich das
Int -CPA-Spiel gewinnen kann.
Gar nicht gut.
Also, grundsätzliches Problem, RSA ist deterministisch und damit kann
es nicht Int-CPA-sicher sein.
Wir müssen uns was Neues überlegen.
Es gibt weitere Angriffe auf RSA, aber die werde ich jetzt nicht
weiter ausbreiten, weil das passiert nur, wenn man es doof benutzt.
Also, wenn man beispielsweise RSA so benutzt wie im Lehrbuch, also
Textbook RSA und nicht randomisiert, dann kann es auch sehr gefährlich
sein, wenn überall der Exponent derselbe ist.
Denn man stelle sich vor, ich verschlüssele dieselbe Nachricht an
viele Empfänger.
Dann weiß ich, dass dieselbe Nachricht hoch drei genommen Modulo dem
einen Modulus vom Fred und Modulo dem Modulus vom Karl und Modulo dem
Modulus vom Sepp, bis ich genug Moduli habe, um den chinesischen
Restsatz anwenden zu können.
Dann kann ich M hoch drei rekonstruieren als ganze Zahl und dann kann
ich eine dritte Wurzel ziehen mit dem Taschenrechner und habe die
Nachricht.
Also, Problem, wenn wir die Nachricht an viele Benutzer senden.
Der Angreifer kennt jetzt die Schiffrate, die alle der Form sind, M
hoch drei Modulo der verschiedenen Moduli.
Problem, chinesischer Restsatz, aha, wir können M hoch drei
rekonstruieren Modulo einem Modulus, der größer ist als M hoch drei
und dann kenne ich es als ganze Zahl.
Ja, weil N1 mal N2 mal N3 größer ist, kenne ich es sozusagen, kenne
ich M hoch drei als ganze Zahl, nichts anderes steht da.
Und Taschenrechner liefert M, also Wurzel ziehen ist schnell, dann
nehmen sie das Newton-Verfahren, das irrt sich so ein bisschen, aber
die nächstliegende ganze Zahl ist es.
Ja, dies könnten wir mit einem probabilistischen Verschlüsseln
beheben, dann würde das Problem nicht mehr da sein und damit haben wir
einen zweiten Grund, warum wir unbedingt probabilistisch verschlüsseln
müssen.
Einmal, deterministisches Verschlüsseln kann überhaupt nicht
semantisch sicher sein und das da mögen wir auch nicht.
Ach und eine weitere schlechte Idee ist, das gleiche, den gleichen
Modulus für viele Benutzer zu verwenden.
So, ein anderes Problem ist, RSA ist Homomorph, das heißt, wenn sie
zwei RSA-Verschlüsselungen haben, also M hoch E und M Strich hoch E,
beides Modulo N, Modulo demselben Modulus, dann können sie die beiden
Schiffrate miteinander multiplizieren und das ist tatsächlich ein
Schiffrat für das Produkt der beiden Klartexte.
Da kann man sich vielleicht eine Anwendung ausdenken, wo man das will,
meistens will man das aber nicht.
Das ist zum Beispiel bei Auktionen problematisch.
Der Auktionator A veröffentlicht den Public Key, behält den Secret Key
und denkt, jetzt bin ich sicher, weil jetzt werden alle Gebote an mich
verschlüsselt geschickt und niemand kann das ablauschen und sein Gebot
irgendwie vom Gebot eines anderen abhängig machen.
Das geht aber trotzdem, denn wenn wir zwei Bieter haben, dann kann
folgendes passieren.
Beide schicken verschlüsselt ihre Gebote, klar, so ist die Spielregel.
A entschlüsselt und der Bieter mit dem höheren Gebot erhält die Ware.
Und der Angriff ist jetzt, B2 wartet, bis B1 sein Gebot geschickt hat
und dann nimmt er einfach das Gebot von B1, keine Ahnung was drin
steht, multipliziert es mit einer Verschlüsselung der zwei und kriegt
ein eigenes Gebot, das doppelt so hoch ist.
Keine Ahnung, was drin war, jetzt haben wir ihn klar überboten.
Das will man auch nicht.
Das haben wir aber bisher nicht betrachtet, im Sinne von, das ist kein
Lauschangriff, das ist ein aktiver Angriff.
Das heißt, der Int-CPA-Sicherheitsbegriff sagt darüber nichts.
Dafür muss man die Schraube noch etwas weiter drehen, um das zu
verhindern.
Ja, und wie macht man jetzt RSA sicher?
Wie könnte man es reparieren?
Der erste Ansatz ist, dass man einfach Zufall an die Nachricht
anhängt, ein Random Padding macht.
Das heißt, wir werden jetzt verschlüsseln, indem wir erstmal die
Nachricht vorverarbeiten mit einer Zufallszahl R und dann obendruf RSA
verschlüsseln.
Und diese Vorverarbeitung nennen wir Padding.
Und beim Entschlüsseln überprüfen wir, ob das Padding die richtige
Form hat.
Wenn nicht, hat wohl jemand daran rumgenestelt.
Und erst wenn wir erkennen, dass das Padding die richtige Form hat,
extrahieren wir die Nachricht M und schmeißen den Zufall weg.
Der ist ja nicht Teil des Klartextes.
So, und ein Beispiel wäre, wir nehmen die Nachricht, hängen genau L
Nullen dran und dann eine Zufallszahl R mit M und R so, dass die sehr
viel kleiner sind als der Modulus.
Das ist aber problematisch.
Erstens, es gibt keinen Sicherheitsbeweis.
Es gibt aber Leute, die sich darüber nicht aufregen.
Nicht-Kryptografen, sogenannte, regen sich da häufig gar nicht auf.
Aber es gibt auch Probleme.
Das heißt, dass es keinen Sicherheitsbeweis gibt, zeigt auch, dass es
Probleme gibt.
Und zwar wissen wir ja, dass RSA homomorph ist.
Und wenn wir jetzt die Homomorphie ausnutzen, können wir eventuell die
Nachricht verändern.
Ja, da muss man so ein bisschen drauf pokern, dass diese L Nullen in
der Mitte erhalten bleiben mit den Operationen, die wir machen.
Aber es gibt tatsächlich subtile Änderungen, die man hinbekommt.
Und dann hat man die Nachricht verändert.
Jetzt sagen Sie, wir wollten doch nur Int-CPA erreichen.
Wir wollten doch nur Sicherheit gegen Lauschen.
Jetzt sagen Sie, Sie nutzen die Homomorphie, um uns zu sagen, dass
PKCS1 1,5 nicht gut ist.
Ja, stimmt.
Aber wir haben trotzdem noch keinen Sicherheitsbeweis, auch nicht für
semantische Sicherheit.
PKCS1 in der Version 2,0 nutzt RSA-UAEP.
Das ist ein viel besseres Padding.
Dafür gibt es einen Sicherheitsbeweis, den Kryptografen nicht
sonderlich mögen, weil da kryptographische Hash-Funktionen verwendet
werden, um das Padding zu berechnen.
Und dieser Beweis benutzt, dass diese Hash-Funktion eine zufällige
Abbildung ist.
Hash-Funktionen sind keine zufälligen Abbildungen, ja.
Es gibt ja einen Algorithmus, der hasht.
Wenn es irgendeine zufällige Abbildung wäre, dann gäbe es vielleicht
keinen Algorithmus, der das macht.
Und deshalb ist es auch nicht ganz klar, inwieweit dieser Beweis in
dem sogenannten Random Oracle Model, also in dem Modell, wo Hash
-Funktionen sowas sind wie Zufallsabbildungen, ob der überhaupt etwas
über die Wirklichkeit sagt.
Bisher ist es aber so, dass niemand RSA UAEP gebrochen hat und das
wird tatsächlich im Internet massenhaft verwendet.
So, wie funktioniert das?
UAEP macht folgendes, wir nehmen die Nachricht M, wir nehmen ein paar
Nullen und wir nehmen eine Zufallszahl R.
Dann hashen wir die Zufallszahl R mit einer Hash-Funktion G, XORen das
auf die Nachricht und diese paar Nullen.
Was da rauskommt, hashen wir mit der Hash-Funktion H, XORen es auf die
Zufallszahl und rauskommt dieses XY und das wird danach normal RSA
verschlüsselt.
Und wie gesagt, wenn Sie sich vorstellen, G und H wären echte
Zufallsabbildungen, sogenannte Random Oracles, dann hat das einen
Sicherheitsbeweis, der sogar soweit geht, dass er gegen alle aktiven
Angriffe auch noch sicher ist.
Das heißt, jegliche Form der Homomorphie wird auch zerstört, aber es
gibt leider keinen Sicherheitsbeweis, der die Hash-Funktionen als Hash
-Funktionen modelliert.
Ja, also heuristisch so sicher wie RSA-Funktionen invertieren.
Heuristisch, weil die Aussage mit dem Beweis in dem Random Oracle
Model ist und jetzt gibt es eine Heuristik, die sagt, was im Random
Oracle Model sicher ist, das ist in der Praxis meistens auch sicher.
Und im Sinne dieser Heuristik ist das sozusagen als sicher gezeigt.
Und RSA-OIP ist sogar sicher gegen aktive Angriffe und tatsächlich ist
der beste bekannte Angriff N zu faktorisieren.
Das heißt, der beste bekannte Angriff ist, wir faktorisieren N, dann
kennen wir P und Q, dann kennen wir Phi von N, das ist nämlich P-1 mal
Q -1 und dann können wir aus dem E das D berechnen mit erweitertem
Euklid und haben den geheimen Schlüssel.
Das heißt, das ist der beste bekannte Angriff.
Der beste bekannte Faktorisierungsalgorithmus ist das sogenannte
Zahlkörpersieb.
An dem entlang schätzt man im Moment, wie groß RSA-Zahlen sein müssen,
um die nächsten circa sechs Jahre sicher zu sein.
Das heißt, empfehlen würde ich nichts, was weniger ist als 2048 Bit
und natürlich, wenn Quantencomputer realisierbar werden in der
entsprechenden Größe, dann ging das noch schneller, weil für
Quantencomputer ist faktorisieren ein relativ einfaches Problem.
Dann müsste man sich völlig neue Verfahren ausdenken, die es auch
schon gibt und im Kontext von RSA eine offene Forschungsfrage ist, ist
N faktorisieren, das ist der beste Angriff, den wir kennen, ist es
tatsächlich notwendig, um RSA oder RSA-OIP zu brechen?
Das wissen wir nicht.
Ja, Nachteil, es ist rechenaufwendig.
Man verwendet da einen naiven Algorithmus.
Es existieren zwar asymptotisch bessere Algorithmen, aber mal unter
uns.
Für alle realistischen Parameter, die wir bisher haben, also sowas wie
2048 Bit, sind diese ganzen asymptotischen Algorithmen von den
Konstanten her noch viel zu aufwendig, um schneller zu sein.
Und RSA-OIP wird benutzt, weil es einfach zu implementieren ist.
Es hat eine einfache Arithmetik und die Ver- und Entschlüsselung ist
sehr, sehr ähnlich.
Also da geht man beim Entschlüsseln, invertiert man erst RSA mit dem
Secret Key und dann geht man im Prinzip rückwärts durch das Diagramm
und checkt, ob da, wo die Nullen stehen, müssen die Nullen auch
stehen.
Dann hält man das Padding für richtig und extrahiert die Nachricht M.
Mit Optimierungen, also zum Beispiel, dass man E gleich 3 wählt und
dem chinesischen Restesatz nutzen bei der Entschlüsselung, ist es
trotzdem ziemlich schnell.
Chinesischen Restesatz verwenden bei der Entschlüsselung Vorsicht.
Das kann zu Seitenkanälen führen.
Tatsächlich, wenn man sich verrechnet und kriegt unterschiedliche
Ergebnisse raus, kann es sein, dass man dann auf einmal mit einem
einfachen GGT und den falschen Ergebnissen tatsächlich den RSA
-Schlüssel brechen kann.
Das ist ein echtes Thema, wenn man RSA-Signaturen auf Chipkarten
realisiert, weil dann gibt man ja die Hardware dem Angreifer in die
Hand und der kann die in den Kühlschrank legen, ein bisschen britzeln,
aufätzen und anblitzen und keine Ahnung was.
Und dann so ein bisschen gucken, was passiert.
Und da hat es sich erwiesen, dass dann den chinesischen Restesatz zu
nutzen keine so gute Idee ist, weil es die Hardware angreifbarer
macht.
Auf jeden Fall ist RSA eine sogenannte Trapdoor-One-Way-Permutation.
Das heißt, es ist eine Abbildung, also hoch E Modulo N ist eine
Abbildung, die schwer zu invertieren ist, es sei denn, man kennt ein
Hintertürchen, das dieser Secret Key ist und es gibt sehr viele
kryptographische Verfahren, die solche Trapdoor-One-Way-Permutations
als Basisprimitive verwenden.
Ja, andere Verfahren, da gehe ich jetzt nicht drauf ein.
Ich erzähle lieber was anderes.
Und zwar dieses ElGamal-Verfahren, mit dem ich sie jetzt fast
belästigt hätte.
Da ist dem Herrn ElGamal Folgendes aufgefallen.
Dieser Schlüsselaustausch von Diffie und Hellman.
Diffie und Hellman waren die beiden, die Public-Key-Verschlüsselung
nicht erfunden haben.
Die hatten nur diesen Schlüsselaustausch, haben aber Public-Key
-Verschlüsselung als Ideal vor Augen gehabt.
Und da hat dieser Herr ElGamal gesagt, sagt mal, guckt euch doch mal
den Schlüsselaustausch genau an.
Nehmt die erste Nachricht und sagt, die wähle ich für jeden gleich.
Das ist mein Public-Key.
Und die zweite Nachricht ist sozusagen die Nachricht, mit der ich dann
den Schlüssel generieren kann.
Und da ich den Schlüssel schon kenne als Sender, benutze ich den
Schlüssel, um die Nachricht symmetrisch zu verschlüsseln und habe ein
Public -Key-Verfahren.
Da gibt es den öffentlichen Schlüssel.
Ich überlege mir die Antwort, die ich gesendet hätte, wenn es ein
Schlüsselaustausch wäre.
Da wäre ein Schlüssel K rausgekommen.
Den Schlüssel K verwende ich symmetrisch.
Und jetzt sende ich die zweite Nachricht des Schlüsselaustauschs und
das Schiffrat in einem Pack.
Public-Key-Verschlüsselung.
Hat Elgamal erfunden.
Diffie und Hellman haben das nicht gesehen.
Interessant.
Ja, was ich vielleicht noch erzählen will, ist, dass wenn es
Quantencomputer gäbe, dann gibt es andere Verschlüsselungsverfahren,
die auf einmal interessant werden.
Eins davon ist Mac-Elise.
Das ist ein ganz spannendes Verfahren.
Das benutzt sogenannte fehlerkorrigierende Codes.
Das kennen Sie vielleicht von der CD oder Sie sind vielleicht alle zu
jung, um CDs zu kennen.
Das sind die Dinger, auf denen man so ein bisschen rumkratzen kann.
Und die spielen immer noch.
Und wie funktioniert das?
Das benutzt sogenannte fehlerkorrigierende Codes.
Das heißt, da werden die Bits redundant verteilt, so gespeichert, dass
selbst wenn einige fehlen oder verfälscht sind, man trotzdem die
Nachricht noch rekonstruieren kann.
Jetzt ist es so, Claude Shannon hat bewiesen, dass jeder zufällige
Code, jeder zufällige lineare Code sogar, jeder zufällige lineare Code
gute Fehlerkorrektur-Eigenschaften hat.
Später hat sich leider herausgestellt, dass das Fehlerkorrigieren mit
zufälligen linearen Codes NP-schwierig ist.
Und das war der Moment, wo McLeese gedacht hat, da mache ich doch ein
Public Key-Verfahren draus.
Das heißt, ich nehme einen fehlerkorrigierenden Code, den verfremde
ich so, dass ich mir merke, was ich gemacht habe, aber jetzt sieht er
aus wie ein zufälliger Code, den veröffentliche ich als meinen Public
Key.
Wenn mir danach jemand eine Nachricht senden will, dann nimmt er die
Nachricht, codiert die Nachricht mit dem fehlerkorrigierenden Code,
träufelt Fehler drauf, sodass dieses Fehlerkorrigieren für alle schwer
ist, außer für den, der sich den Code ausgedacht hat, schickt das.
Jeder, der an der Leitung lauscht, sieht ein verrauschtes Codewort und
kann das nicht dekodieren.
Aber der, der sozusagen den Code verfremdet hat, kann diese
Verfremdung rückgängig machen, Fehlerkorrektur machen und kriegt die
originale Nachricht wieder.
Und das ist ein Verfahren, Mac-Lease, wo man Goppa-Codes verwendet.
Das sind Codes, die, wenn sie verfremdet werden, tatsächlich nach
allem, was wir wissen, so aussehen wie zufällige Codes.
Das ist die Mac-Lease-Annahme.
Und wir glauben, dass Mac-Lease auch sicher bleibt, wenn
Quantencomputer kommen.
Also sie können ruhig kommen.
Dann werden unsere Public-Key-Verfahren etwas ineffizienter, denn der
Grund, warum wir Mac-Lease im Moment nicht verwenden, sondern RSA ist,
dass RSA irgendwie 2048-Bit-Schlüssel hat und nicht irgendwie Megabyte
als Schlüssel oder so.
Das ist etwas, was wir vielleicht akzeptieren müssen, wenn diese
fehlerkorrigierenden Code-Matrizen mal die Public-Keys sind.
Aber in Zeiten, wo man sich ganze Videos runterladen kann, ist es dann
vielleicht auch nicht mehr so schlimm.
Das heißt, das ist so eine der Forschungsrichtungen, die es im Moment
gibt, die sogenannte Post-Quantum-Public-Key-Kryptographie, also für
die Zeit, wo Quantentechnologien selbstverständlich sind und man sich
gegen Quantencomputer absichern muss.
Andere Dinge, die man heute macht, ist, man interessiert sich
tatsächlich für Verschlüsselungsverfahren, wo man mit den Chiffraten
rechnen kann.
Idealerweise hätte man gerne, dass man im Prinzip Daten verschlüsselt
in der Cloud ablegen kann.
Der Cloud-Provider kann darauf rechnen, weiß aber nicht, was er tut.
Und wir können das Ergebnis entschlüsseln und mussten aber nicht
selber rechnen.
Leider tut das so noch nicht, weil der Aufwand für diese sogenannte
Vollhomomorphe Verschlüsselung, die es tatsächlich gibt, aber der
Aufwand ist dafür noch so groß, dass sie in der Zeit wahrscheinlich
die Sache schneller mit ihrem eigenen Taschenrechner gemacht haben,
als verschlüsselt in der Cloud zu rechnen.
Weil da einzelne Bits irgendwie so Chiffrate sind, damit das überhaupt
geht, das Wunder.
Trotzdem ist das eine sehr interessante Forschungsrichtung, weil man
mit Vollhomomorphe Verschlüsselung, also Chiffraten, auf denen man
rechnen kann, noch einen Schritt weiter gehen kann und damit bin ich
bei einem ganz aktuellen Thema der Kryptografie, der sogenannten Code
Obfuscation.
Was man gerne hätte, wäre, dass man ein Programm so verfremden kann,
dass man dem Programm nicht mehr ansieht, was es tut.
Da muss man sich auch erstmal überlegen, was bedeutet das eigentlich?
Also Code Obfuscation.
Und da war es so, dass der erste Wunsch, den die Menschheit hatte,
war, so wie bei semantischer Sicherheit, so wollen wir es machen.
Das heißt, es gibt den Angreifer, dem geben wir den Code und dem
anderen Angreifer geben wir den Code nicht und die sollen nichts
unterschiedliches können.
Das ist ja blöd.
Der, der den Code hat, kann ja den Code laufen lassen und tolle Sachen
ausrechnen.
Der, der den Code nicht hat, kann das nicht.
Na gut, dann machen wir es wie folgt.
Der eine kriegt den Code und der andere kriegt nur so eine Art
Blackbox -Cloud-Zugriff auf die Funktionalität, aber kriegt den Code
nicht.
Und jetzt, wenn der eine Angreifer was Erstaunliches machen kann, was
der andere Angreifer nicht machen kann, dann ist das keine gute Code
Obfuscation.
Das war lange Zeit der Wunsch, wie man Code Obfuscation gerne
hinbekommen würde, bis in den Jahren um 2000 herum ein Herr Barrack
bewiesen hat, dass das prinzipiell unmöglich ist mit theoretischer
Informatik.
Was er nämlich gemacht hat, ist, er hat ein Programm konstruiert, das
erkennt, ob seine Eingabe ein Programm mit der gleichen Funktionalität
ist, wie es selber.
Und wenn sie jetzt den Code haben, egal wie er verfremdet wurde, die
Funktionalität ist ja noch dieselbe, dann können sie das Programm mit
sich selber füttern, das Ding sagt Aha und führt einen Stepptanz, also
macht irgendwas Erstaunliches, gibt irgendwas mit einer schrägen
Wahrscheinlichkeit aus.
Während wenn sie nur Blackbox-Cloud-Zugriff haben, sie wissen nicht,
was sie da eingeben müssen, um mit der gleichen schrägen
Wahrscheinlichkeit ein Ergebnis zu bekommen.
Das heißt, er hat bewiesen, dass es prinzipiell nicht obfuszierbare
Programme gibt, Programme, die sich selber erkennen, zumindest ihre
eigene Funktionalität.
Und daraufhin ist man einen Schritt zurückgegangen und hat gesagt, was
könnte Code Obfuscation dann sein?
Und dann kam man auf folgende Idee.
Wir machen es nicht wie semantische Sicherheit, wir machen es so wie
Int -CPA.
Das heißt, der Angreifer darf zwei Programme wählen, die dasselbe
machen.
Ich obfusziere eins der beiden davon und gebe ihm das und er soll
nicht sagen können, welches von beiden das war.
Jetzt denkt man, was ist denn das für eine komische Definition?
Ist das wirklich, impliziert das irgendwelche Sicherheit?
Und tatsächlich, das impliziert ein ganz großes Versprechen, aber nur
wenn es wirklich gute Obfuscation überhaupt gibt.
Selbst wenn wir den Begriff erfüllen würden, wüssten wir nicht, ob
Obfuscation gut ist.
Wenn wir aber uns mal ganz kurz überlegen, es gäbe gute Obfuszierung,
dann hat dieser Begriff ein enormes Versprechen.
Und zwar, das hier ist zum Beispiel das Programm, das schon obfusziert
ist und das ist das Programm im Klartext.
Und jetzt obfusziere ich und jetzt weiß der Angreifer nicht mehr, ob
das das Programm war, das er schon mal obfusziert hatte oder das im
Klartext.
Und das gilt für jedes Obfuszierungsverfahren.
Bedeutet, es ist eine Art Best Possible Obfuscation.
Egal wie gut wir obfuszieren können, ein Obfuskationsverfahren, das
diesen Ununterscheidbarkeitsbegriff erfüllt, ist besser oder genauso
gut.
Und da sind im Moment viele Leute hinterher, weil damit könnte man
echt fast alle Probleme der Kryptographie zumindest in der Theorie
lösen.
Leider sind alle bisher vorgeschlagenen Verfahren sehr, sehr langsam.
Mal sehen, was als nächstes passiert.