Die Minute hat geschlagen. Endspurt.

Jetzt von den vielen Hörern. Ich will jetzt noch eine Frage zu der Klausur oder Probeklausur. Die habe ich ja gestern vorgerechnet, aber da waren andere da. Also die könnten sie natürlich jetzt noch stellen, wenn da Fragen sind.

Oder danach. Ansonsten mache ich jetzt den letzten Abschnitt aus der Kryptographie, dieses RSA-Verschlüsselungssystem. Das ist ganz interessant und braucht, da werden genau hier unsere zahlentheoretischen Erkenntnisse benutzt.

Also das RSA-Verschlüsselungssystem.

Das ist von 1978. Also es gibt jetzt schon auch noch wieder sicherlich andere Verfahren, aber das gibt einen guten Einblick, was man so alles machen kann.

Sie sehen im Skript, das ist von drei Amerikanern, Rivest, Chamiere und Adelman. Daher die drei Buchstaben erfunden worden. Und das geht folgendermaßen.

Das habe ich hier auch schon so als eine Liste, aber da schreibe ich jetzt zumindest kurz die Schritte hin, um das dabei zu erklären. Wir haben einen Sender, der heißt A, und einen Empfänger, B.

Die haben A, möchte B was schicken und will, dass nur B das entschlüsseln kann. Und das geht folgendermaßen.

Also die beiden kennen sich zumindest irgendwie, sie wissen voneinander natürlich, sonst macht das keinen Sinn. Und hier ist die Idee, dass nicht einfach hier der A eine Verschlüsselung macht, sondern dem Empfänger B dann den Schlüssel gibt, sondern eigentlich kommt das Input von B.

B macht die Idee dabei ist, bei der Verschlüsselung braucht es Primzahlen. Das haben Sie sicherlich alle gehört. Irgendwie Primzahlen sind für Entschlüsselung gut.

Also B zur Verschlüsselung und zur Entschlüsselung. Also B sucht sich zwei Primzahlen. Zwei Primzahlen nennen wir hier P und Q, die müssen groß sein. Mindestens 100 Ziffern.

Also 100 Ziffern sind schon groß. Allein da braucht man Primzahlen für, aber Sie haben am Anfang der Vorlesung ja auch schon gehört, da gibt es dann solche Wellen von, oder solche Leute, die sich interessieren immer wieder neue Primzahlen zu finden. Für sowas hier sind die gut.

Dann zweitens, wenn man zwei Zahlen hat, ist es einfach mehr oder weniger das Produkt zu bilden. Das nennen wir hier N. Das weiß Peter natürlich auch, weil er die Primzahlen kennt.

Jetzt brauchen wir die Eulerse Zahl. Die Eulerse Zahl von N, das war ja die, oder Eulerse Funktion, das war die, die alle zu der Zahl, die gegebenen Zahl hier, abzählt, die Teile fremden Zahlen.

Also da haben wir aber ja so ein paar, wenn das eine Primzahl ist, das hatten wir noch gesehen, überlegt, dass das dann gerade N-1 ist. Jetzt ist es keine Primzahl, sondern ein Produkt auszahlen, aber das ist eine algebraische Funktion, sowas wie Sie von linearen Funktionen kennen, wo die Linearität irgendwie rausgezogen werden kann. Hier kann man das Produkt rausziehen.

Das steht auch weiter vorne im Skript bei den Sätzen, die ich nicht alle bewiesen habe am Ende von diesen, weiß nicht mehr von welchem Kapitel, da wo ich die Funktion eingeführt hatte und hinter dem chinesischen Rechtssatz steht Folgendes.

Also wenn phi das Produkt von solchen Zahlen ist, dann können wir das auch, ja nicht linear, sondern diese Multiplikativ auseinander ziehen und dann, weil das Primzahlen sind, ist das hier einmal p-1 mal q-1.

Das kann man hier jetzt in diesem Fall bestimmen. Viertens, man sucht eine teilerfremde Zahl, also suche S, eine Zahl S, die soll die Eigenschaft haben 1 kleiner gleich S kleiner phi von N.

Die soll teilerfremd sein zu phi von N, also der Giget von S und phi von N sei gleich 1.

Da steht hier drunter noch, zum Beispiel wird es eine Primzahl tun, die größer ist als das Maximum der beiden.

Dann vergleicht man wieder hier die ganzen Zahlen, denn die kann weder das noch das teilen, also wir kennen jetzt hier auch diese Zahl, also steht da drunter, also das ist jetzt nicht ganz so ein Problem, das schreibe ich jetzt nicht extra an die Tafel.

Also jetzt haben wir p, wir haben q, wir haben N und wir haben phi von N. Jetzt brauchen wir ein Verses 5.

Wir brauchen finde oder bestimme, ich würde es noch genauer sagen, das macht ja alles B, B bestimmt.

Im Moment läuft alles bei B ab, der sucht sich diese Zahlen, dann klar, wenn er die Zahlen hat, das Produktbilden, macht sein Computer, das schreibt er auf, das S sucht er sich raus und jetzt sucht er noch das inverse von S.

Also S quer hoch minus 1, will er bestimmen, das ist sowas, was wir gestern auch vorgerechnet haben, sowas müssen Sie nächste Woche auch machen.

Das ist jetzt die Erstklasse, also das ist sozusagen das inverse von S und zwar wo, also äquivalent dazu meine ich, man will die Lösung haben von der Kongruenz, S mal T sei Kongruenz zu 1 und zwar Modulo phi von N,

also auch hier wäre das im Z Modulo phi von N, Z. Also das steht jetzt nur auf verschiedene Weisen da, also ich kann auch sagen B bestimmt T, sodass entweder können Sie das so schreiben,

das ist das inverse, also die Restklasse von T ist das inverse von dieser Zahl S in Z Modulo phi von N, Z, die gibt es, weil hier ja der ggt gleich 1 ist.

Oder man kann das äquivalent so hinschreiben und ich will natürlich, es soll auch verlangt und es sei natürlich ein vernünftiger Repräsentant, es sei 0 kleiner T kleiner phi von N,

also nicht irgendwie ein beliebig großer, nein es ist ein beliebig, schon ziemlich groß wahrscheinlich, weil wir uns hier mit sehr sehr großen Zahlen beschäftigen. Also das kann man alles nicht von Hand machen, das sind ja hier schon Zahlen mit mehr als 100 Zirken.

Aber theoretisch aufschreiben, so mit Buchstaben kann man es und dann muss man das eben nur mit einem Computer, der dann aber auch seine Zeit braucht zu rechnen. Also das wissen wir auch wie das geht.

Jetzt im nächsten Punkt, im sechsten, da ist jetzt auch ein ganz am Anfang ein Tippfehler zu folgenden, also zur folgenden Fer und Entschlussung, also das zu soll ein zur sein, da habe ich das ruhig mal hin,

zur, dass es R fehlt, folgenden Fer und Entschlussung werden nur die Zahlen S und T,

also S, T und N auch noch. Also wir haben jetzt, wir haben P und Q, haben wir angefangen, aus P und Q ist definiert sofort N und phi von N,

S wird wieder gesucht, das ist sozusagen frei, also mehr oder weniger frei, weil die natürlich ein paar Bedingungen haben, T ist wieder fest und dann vergisst man aber wieder einige davon

und B veröffentlicht, das kann er ruhig irgendwie ganz oft allen möglichen Leuten sagen, er gibt frei die Zahlen S und N.

Mit den allein kann man aber nicht so ohne weiters hier die anderen wieder herholen.

T wird geheim gehalten. Ja und P und P, Q und phi von N können vernichtet werden.

Die waren nur technisch, wurden nur technisch gebraucht, um das ganze System zu machen, bisher stehen hier nur irgendwelche Zahlen,

also die zum Teil zusammenhängen, mehr oder weniger und was, also dann schmeißt man die wieder weg, wir haben im Hinterkopf natürlich noch, wie das alles zusammenhängt

und das ist öffentlich und das ist geheim, aber das sind jetzt nur noch drei Zahlen. Jetzt geht es um die Verschlüsselung.

Da fangen wir an, jetzt kommen wir zu A, der Sender, der hat den Text, den will er verschlüsseln, der hat den Klartext, der verwandelt den Klartext

samt Satzzeichen, also alles samt Satzzeichen. Damit hat er natürlich ein Alphabet, was mehr als 26 Zeichen hat, also alle Satzzeichen dabei und so weiter,

aber das soll jetzt in irgendeinen Zeichensatz gemacht werden und zwar hier in einer Ziffernfolge und da ist zum Beispiel dieser ASCII Code praktisch,

aber man könnte auch was anderes machen, da steht hier nochmal, also dieser ASCII weiß man immer irgendwie, damit Computern zu tun hat, ASCII Codes, da hatten das gehört,

nicht jeder weiß genau, was es ist, aber das ist irgendwie sowas, da macht man halt irgendwie aus all den Buchstaben und Satzzeichen, die wir haben,

einen Zahlencode, mit dem kann dann der Rechner arbeiten, also klare Satzzeichen in eine Ziffernfolge. Also im ASCII Code ist ein 7 oder 8 wie Zeichencode,

also das ist ganz klar, wie viele Ziffern dann zu einem Zeichen gehören und darum kann man das dann, das kann dann jeder Rechner wieder zu dem Klartext machen,

also das ist noch keine Verschlüsselung, das ist nur eine Umschreibung in Zeichen, in Zahlen, in Ziffern. Und diese Ziffernfolge, die nennen wir jetzt Z,

die hat ganz ganz ganz gut mit den Ziffern, je nachdem wie lang der Satz ist natürlich der Klartext länger, aber das sind jetzt wirklich nur Ziffern.