________________________________________________________________________________
Inhalt....: Verschlüsselung beliebig langer Texte mittels RSA
Kategorie.: Arbeitsblatt
Mathematik: Kryptographie, Zahlentheorie
MuPAD.....: 3.0.0
Datum.....: 2002-08-05
Autoren...: Julia Faflek <faflek@mupad.de>
Funktionen: numlib::toAscii, modp, powermod, floor, nextprime, random, igcd
________________________________________________________________________________
Ver- und Entschlüsselung beliebig langer Texte
mittels RSA
RSA ist weltweiter Standard bei der Ver- und Entschlüsselung von Daten. Hier wird gezeigt,
wie man einen Text aufbereitet, um ihn mit RSA zu verschlüsseln. Auf weitere zahlentheoretische
Hintergründe wird nicht näher eingegangen. Eine Einführung in das RSA Verfahren bietet das
Notebook "RSA.mnb", welches unter www.mupad.de/schule/material zum Download zur
Verfügung steht.
Wir wollen einen Textstring eingeben, der dann in das ASCII-Format umgewandelt
wird.
Nachricht:= "MuPAD ist toll!"
numlib::toAscii(Nachricht)
Die nun vorliegende Liste wird als 128-adische Darstellung einer ganzen Zahl
aufgefasst. Da in RSA mit ganzen Zahlen gerechnet wird, wandeln wir diese Liste
in eine ganze Zahl um.
Dazu schreiben wir eine Prozedur, die eine ganze Zahl x berechnet mit
wobei k die Länge der Liste darstellt.
Ascii2Int:= proc(Liste)
local Zahl, i;
begin
Zahl:= 0:
for i from 1 to nops(Liste) do
Zahl:= 128 * Zahl + Liste[nops(Liste) + 1 - i]
end_for:
return(Zahl):
end:
Das Problem, das sich nun stellt, ist, dass mit RSA nur Nachrichten verschüsselt
werden können, deren Wert in obiger Codierung einer ganzen Zahl kleiner als N
entspricht. Dabei ist N = p * q der RSA-Modul. Daher müssen wir die Liste der
ASCII-Darstellung in Blöcke der Länge n - 1 zerlegen, wobei n die Länge der Zahl
N in 128-adischer Darstellung ist. Dazu müssen wir uns überlegen, wie viele solcher
Blöcke gebildet werden müssen, falls die Länge der Liste größer als n - 1 ist.
Dazu betrachten wir den Ausdruck
Ist r = 0, so müssen wir s Blöcke bilden, andernfalls s+1. Nun schreiben wir eine
Prozedur, die bei Eingabe eines Strings, je nach Länge entweder eine ganze Zahl
oder eine Liste von Zahlen ausgibt.
Text2Int:= proc(Text, n)
local Liste, Quotient, Rest, Block, Zahl, i;
begin
Liste:= numlib::toAscii(Text):
if nops(Liste) > n-1 then
Quotient:= _div(nops(Liste), n-1):
Rest:= modp(nops(Liste), n-1):
Block:= null():
Zahl:= null():
for i from 1 to Quotient do
Block:= op(Liste, (i-1)*n-i+2..i*(n-1)):
Zahl:= (Zahl, Ascii2Int([Block])):
end_for:
if Rest = 0 then
return([Zahl]):
else
Block:= op(Liste, Quotient*n-(Quotient+1)+2..nops(Liste)):
Zahl:= (Zahl, Ascii2Int([Block])):
return([Zahl])
end_if:
else
return([Ascii2Int(Liste)]):
end_if:
end:
Nun haben wir den Text so aufbereitet, dass wir ihn mit RSA verschlüsseln
können. Dazu benötigen wir noch eine geeignete Verschlüsselungsprozedur,
die bei Eingabe des RSA-Moduls N, des öffentlichen Schlüssels und der
Nachricht verschlüsselte Zahlen ausgibt.
verschluesseln:= proc(Modul, oeffentlich, Nachricht)
local n, Umwandlung, Codierung;
begin
n:= floor(log(128, Modul)) + 1:
Umwandlung:= Text2Int(Nachricht, n):
Codierung:= [powermod(Umwandlung[i], oeffentlich, Modul)
$ i = 1..nops(Umwandlung)]:
end:
Jetzt müssen wir uns nur noch Gedanken um die Entschlüsselung machen,
dazu gehen wir "rückwärts" vor: Nehmen wir an, wir haben eine Liste von Zahlen
erhalten, die wir entschlüsseln wollen. Als erstes wenden wir auf jede dieser
Zahlen die RSA-Entschlüsselung an, indem wir den geheimen Schlüssel ver-
wenden. Die so erhaltenen Zahlen müssen nun ins ASCII-Format umgewandelt
werden.
Zunächst brauchen wir also eine Prozedur, die uns aus einer ganzen Zahl kleiner
als N eine Darstellung im ASCII-Format liefert:
Int2Ascii:= proc(Zahl, n)
local Liste, Quotient, Rest, i;
begin
Quotient:= Zahl:
Liste:= null():
for i from 1 to n-1 do
Rest:= modp(Quotient, 128):
Quotient:= _div(Quotient, 128):
Liste:= (Liste, Rest):
end_for:
return(Liste):
end:
Diese Prozedur muss also auf jede entschlüsselte Zahl angewandt werden.
Die so erhaltenen Listen müssen aneinandergesetzt werden und dann in
einen Textstring umgewandelt werden. Dies leistet die folgende Prozedur:
Int2Text:= proc(Zahlliste, n)
local Liste, i, Text;
begin
Liste:= null():
for i from 1 to nops(Zahlliste) do
Liste:= (Liste, Int2Ascii(Zahlliste[i], n)):
end_for:
Text:= numlib::fromAscii([Liste]):
return(Text):
end:
Jetzt fehlt nur noch die Entschlüsselungsprozedur, in der wir die Prozedur
Int2Text verwenden:
entschluesseln:= proc(Modul, geheim, GeheimeNachricht)
local n, Umwandlun, Decodierung;
begin
n:= floor(log(128, Modul)) + 1:
Decodierung:= [powermod(GeheimeNachricht[i], geheim, Modul)
$ i = 1..nops(GeheimeNachricht)]:
Umwandlung:= Int2Text(Decodierung, n):
end:
Betrachten wir nun ein Beispiel. Zunächst legen wir folgende RSA-Parameter fest:
p:= nextprime(2^64):
q:= nextprime(p + 2^16):
N:= p*q:
und erzeugen wir ein zufälliges Schlüsselpaar:
Schluesselerzeugung:= proc(p, q)
local Phi_N;
begin
Phi_N:= (p-1)*(q-1):
for i from 1 to Phi_N do
e:= random(2..Phi_N-1)():
if igcd(e, Phi_N) = 1 then
print("oeffentlich = " .e):
break:
end_if:
end_for:
d:= e^(-1) mod Phi_N:
print("geheim = " .d);
end:
Schluesselerzeugung(p, q)
"oeffentlich = 20107169056314830892607910405588105153"
"geheim = 336306151939690575333302230623497162561"
Folgenden Text wollen wir mit dem öffentlichen Schlüssel e verschlüsseln und
verschicken:
Mitteilung := "Hallo liebe MuPAD-Freunde! ".
"Nun koennen wir beliebig lange ".
"Texte verschluesseln. Wir muessen ".
"nur darauf achten, dass die verwendeten ".
"Zeichen auch im Ascii-Format vorliegen. ".
"Also Umlaute und einige Sonderzeichen vermeiden! ".
"Daher sind auch keine Zeilenumbrueche per ".
"Shift+Return erlaubt. Einige Zeichen, wie ".
"@, *, ~ und ^ sind dagegen erlaubt."
GeheimeMitteilung := verschluesseln(N, e, Mitteilung)
Nehmen wir an, wir hätten jetzt obige geheime Botschaft empfangen. Wir verwenden
nun den geheimen Schlüssel d, um zu entschlüsseln:
entschluesseln(N, d, GeheimeMitteilung)
__________________________________________________________________________
Übungen:
1. Verwenden Sie andere RSA-Parameter und verschlüsseln Sie immer die gleiche Nachricht. Welches
Verhalten bzgl. der Länge der verschlüsselten Nachricht können Sie feststellen?
2. Machen Sie sich mit den Funktionen _div und modp vertraut. Wo liegt der Unterschied?
________________________________________________________________________________
Anmerkungen:
1. Weitere Erläuterungen finden Sie in unserem Newsletter #3 August 2002.
2. Unter www.schule.mupad.de/material/ befinden sich Notebooks, die sich ebenfalls mit dem
Thema RSA beschäftigen. Dort steht u.a. auch ein Notebook bereit, das eine kurze Einführung in das
RSA-Verfahren gibt.
3. Weitere Anregungen finden Sie in der Buchreihe Mathematik 1 x anders. In dieser Reihe
wird eine Vielzahl unterschiedlichster mathematischer Probleme mit MuPAD gelöst. Die
Bücher können unter www.schule.mupad.de/literatur kostenfrei kopiert werden.
_______________________________________________________________________________