________________________________________________________________________________
Inhalt....: Wiener Attacke
Kategorie.: Arbeitsblatt
Mathematik: Kryptographie, Zahlentheorie
MuPAD.....: 3.0.0
Datum.....: 2003-06-23
Autoren...: Julia Faflek <faflek@mupad.de>
Funktionen: contfrac, numlib::contfrac::rational, random, nextprime, igcd, mod
________________________________________________________________________________
Der Angriff von Wiener
RSA ist weltweiter Standard bei der Ver- und Entschlüsselung von Daten. Hier wird der Angriff
von Wiener vorgestellt, der auf Kettenbrüchen basiert. Mit diesem Angriff kann RSA erfolgreich
gebrochen, wenn
Zunächst beschäftigen wir uns mit dem Begriff der Kettenbruchentwicklung.
Dieser stellt eine rationale Zahl a dar. Mit dem Befehl contfrac(a) erhalten
wir die gewünschte Darstellung:
contfrac(5/3)
contfrac(123/1234)
Folgender Aufruf
op(contfrac(123/1234), 1)
liefert eine geordnete Liste der Koeffizienten. Damit lässt sich m/n darstell-
ten als [a0, a1, …, an]. Definieren wir nun die i-te Konvergente einer Ketten-
bruchentwicklung: Sei [a0, a1, …, an] = m/n, so ist u/v = [a0, a1, …, ai] die i-te
Konvergente der Kettenbruchentwicklung von m/n.
In MuPAD können wir das wie folgt umsetzen: Wir berechnen die 3-te Kon-
vergente der Kettenbruchentwicklung von 123/1234.
contfrac(123/1234, 3)
numlib::contfrac::rational(contfrac(123/1234), 3)
Für m/n und u/v gelte
Dann ist u/v eine Konvergente der Kettenbruchentwicklung von m/n.
Diese Tatsache wird nun auf den folgenden Satz angewandt:
Sei N = pq, wobei p und q Primzahlen mit q < p < 2q. Weiter seien e, d
teilerfremd zu Phi(N), wobei Phi die Eulersche Phi-Funktion bezeichnet,
mit ed = 1 mod Phi(N). Daraus folgt: ed - 1 = kPhi(N) für eine ganze Zahl k.
Schließlich sei
.
Dann gilt:
Damit ist k/d eine Konvergente der Kettenbruchentwicklung von e/N.
Nun haben wir alles an der Hand, um RSA erfolgreich zu brechen, falls
der private Schlüssel d entsprechend klein ist.
Wir erzeugen zunächst zwei große Primzahlen p und q, so dass q<p<2q:
q1 := random(10^20..10^21):
q := nextprime(q1())
p1 := random(q..2*q):
p := nextprime(p1())
Nun berechnen wir den Modul N und Phi(N):
N := p * q;
Phi_N := (p-1) * (q-1);
Jetzt suchen wir einen geheimen Schlüssel d im Intervall von 3 bis
1/3N^(1/4):
d1 := random(3..floor(float((1/3) * N^(1/4)))):
for i from 1 to 1000 do
d := d1():
if igcd(d, Phi_N) = 1 then break end_if;
end_for:
print(Unquoted, "d = " .expr2text(d))
d = 11109390589
Schließlich wird der öffentliche Schlüssel e berechnet:
e := 1/d mod Phi_N
und eine zufällige Nachricht x generiert, um nachher den Wert von d zu
verifizieren:
x1 := random(10^30..10^40):
x := x1()
Nun machen wir uns Gedanken um den Angriff. Wir benutzen, dazu den
obigen Satz und berechnen alle Konvergenten der Kettenbruchentwicklung
von e/N. Für jede Konvergente überprüfen wir ob der Nenner das gesuchte
d ist, indem wir den Wert x^e mit dem Nenner potenzieren und überprüfen,
ob das Ergebnis gleich x ist.
Wiener := proc(e, N, x)
local i, d_ber;
begin
for i from 1 to nops(op(contfrac(e/N), 1)) do
d_ber := denom(numlib::contfrac::rational(
contfrac(e/N), i)):
if powermod(x, (e * d_ber), N) = x then
break
end_if:
end_for:
print(Unquoted, "Berechnetes d ist ".expr2text(d_ber)):
end_proc:
Wir überprüfen, ob die Attacke funktioniert:
Wiener(e, N, x), d
Berechnetes d ist 11109390589
Es hat geklappt!!!
_______________________________________________________________________________
Übungen:
1. Testen Sie die Wiener Attacke 3mal, wobei jedes Mal neue p, q, d, e und x generiert werden.
2. Machen Sie sich mit der Funktion time bekannt (s. ?time) und bestimmen Sie die Laufzeiten des
ssAngriffes von Wiener.
3. Versuchen Sie N mit Hilfe der Funktion ifactor zu faktorisieren.
_______________________________________________________________________________
Anmerkungen:
1. Unter www.mupad.de/schule+studium/material/ befinden sich weitere Notebooks, die sich mit dem Thema
ssRSA beschäftigen.
2. Weitere Anregungen finden Sie in der Buchreihe Mathematik 1 x anders. In dieser Reihe wird eine Vielzahl
ssunterschiedlichster mathematischer Probleme mit MuPAD gelöst. Die Bücher können unter
sswww.schule.mupad.de/literatur kostenfrei kopiert werden.
_______________________________________________________________________________