Dieser Foliensatz besteht aus vier Teilen.
Der erste Teil enthält ein weiteres Beispiel für Ihre Pollard-Rho Implementierung mit 30 Bits. Rechnen Sie es mit Ihrer Implementierung nach (Folie 1).
Der zweite Teil enthält eine Parallelisierung bzw. eine verteilte Berechnung der Pollard-Folge.
Der dritte Teil erklärt, wie man mit dem Potenzieren mod p verschlüsseln kann (ElGamal).
Der vierte Teil erklärt, wie man mit dem Potenzieren mod n verschlüsseln kann (RSA). Hierbei ist n keine Primzahl, sondern das Produkt zweier Primzahlen n=pq.
Viele Jahre hat man darüber gerätselt, wie man die Berechnung der Pollard-Folge, bei der y(i) aus y(i-1) berechnet wird, parallelisieren kann. Halten Sie einen Augenblick inne, um sich vorzustellen, wie man das mit z.B. 100 Prozessoren machen könnte.
Das Problem ist, dass y(i-1) erst kurz vor der Berechnung von y(i) bekannt ist. Also mit 100 Prozessoren schneller bei y(10000000) zu sein als mit einem Prozessor ist nicht vorstellbar. Oorschot und Wiener hatten 1994 die Idee, mehrere verschiedene Folgen gleichzeitig zu berechnen. Irgendwann treffen zwei von diesen zusammen, das ergibt das Bild eines griechischen Lambda. Das Zusammentreffen könnte man erkennen, indem sich alle Prozessoren in jedem Schritt austauschen.
Wenn man dies tun würde, bräuchte man eine große Bandbreite, sagen wir 10.000.000 mal pro Sekunde 300 Bits, also 3 GBits pro Sekunde. Wenn man es stattdessen bewerkstelligt, dass im Schnitt nur zehnmal pro Sekunde ausgetauscht wird, hat man einen Faktor 1.000.000 in der Bandbreite gespart. Der Trick: (y,k,l) wird nur ausgetauscht, wenn y von einer bestimmten Form ist. Ein passendes Kriterium wäre, wenn die Binärdarstellung von y in den low-order Bits 20 Nullen enthält.
Man nennt diese speziellen Werte "distinguished points". Sie sind im Lambda mit Kästchen gekennzeichnet. Bei den Kreisen wird nur gerechnet und nichts gesendet. Bei den Kästchen wurde gerechnet, ein distinguished point erkannt und dieses Zwischenergebnis (y,k,l) gesendet.
Die Prozessoren tauschen sich allerdings nicht untereinander aus, man betreibt für diese Zwecke einen zentralen Server. Dieser sammelt distinguished points (y,k,l) bis er ein Tripel (y',k',l') erhält mit y=y'. Dann kann der Server mit k, l, k', l' eine Lösung ausgeben und die rechnenden Prozessoren zum Anhalten zwingen.
Das Verfahren von ElGamal wird erklärt. Es ist ein Public Key Verfahren. Die Bedeutung dieses Begriffs ist der Electronic Frontier Foundation sehr anschaulich und doch recht präzise gelungen, siehe unter eff.org.
Wir versetzen uns in die Lage einer Teilnehmerin Alice des Kommunikationsnetzwerks.
Alice hat einen öffentlichen Schlüssel (p,g,y). Geheim ist a. Typischerweise hat jeder Teilnehmer ein anderes p, g, y und a. Für die Sicherheit spielt es keine Rolle, ob zwei Teilnehmer zufällig das gleiche p haben, solange sie ein anderes a haben.
Die Parameter von Alice, die hier zu sehen sind, sind also (p,g,y,a).
Von der Wahl der Primzahl p hängt die Sicherheit des Verfahrens ab. Damit wegen der früher angesprochenen Reduktion des Problems keine Schwächen auftreten können (siehe Folie 2 vom 15.04.), werden sichere Primzahlen benutzt. Zur Erinnerung: die Attacke via Reduktion funktioniert, wenn alle Primzahl-Teiler von p-1 klein sind. Eine simple Methode dies zu vermeiden, ist es, darauf zu achten, dass der Wert q=(p-1)/2 eine Primzahl ist. Finden Sie einige Beispiele für solche Paare (p,q). Es ist unbekannt, ob es unendlich viele davon gibt. Wer darüber mehr lesen möchte, solche q heißen Sophie-Germain-Primzahlen.
Jeder der Alice eine Nachricht schicken möchte, führt für seine Message m die Schritte 1)-3) unter "Nachricht an den Teilnehmer senden" aus. Alice führt die Schritte 1) und 2) unter Entschlüsselung aus.
Verinnerlichen Sie die Logik dieses Verfahrens durch Implementierung.
Eine sichere 2048-Bit-Primzahl ist diese hier
p=16750331664182990874029696098074132587055230868866355471205981592769668400410929080145251807914116630575424564968565756429425077053697765941419791294368328988444506598961602958555174031728271584496618401768164691938327994233685083814133199713151647174398634948882680007059407523534099543985258151634256770077906742473373796503614987161731571380707948766230709542778469397317729996963765804212585363206201773385764592552607079268543895326833554722831176561278204984206036672554262689038632734675122842491796592700330649708501167965346232689703004471806748640023604592108026215325091492657313002880937145514539663301259
ein zugehöriger Erzeuger g=2.
Hier wird erklärt, warum nach der Entschlüsselung der Verschlüsselung eines Klartextes m wieder der Klartext herauskommt. Dahinter steckt eine einfache Rechnung mod p unter Beachtung des kleinen Fermat'schen Satzes Fermat's little theorem.
Das Verfahren von Rivest, Shamir und Adleman wird skizziert.
Wenn Alice ihre Schlüssel erzeugt, wählt sie zunächst zwei etwa gleich große aber verschiedene Primzahlen p,q und multipliziert diese (n=p*q). Desweiteren wählt sie einen zufälligen Exponenten e mit ggT(e,(p-1)*(q-1))=1 und bildet dann d=1/e mod (p-1)*(q-1).
Sie publiziert n, e als öffentlichen Schlüssel und hält p, q, n geheim.