________________________________________________________________________________
Inhalt....: Verschlüsselung externer Daten mittels RSA
Kategorie.: Arbeitsblatt
Mathematik: Kryptographie, Zahlentheorie
MuPAD.....: 3.0.0
Datum.....: 2002-10-27
Autoren...: Julia Faflek <faflek@mupad.de>
Funktionen: fopen, fclose, readbytes, writebytes, powermod
________________________________________________________________________________
Ver- und Entschlüsselung externer Daten mittels
RSA
RSA ist weltweiter Standard bei der Ver- und Entschlüsselung von Daten. Hier wird gezeigt,
wie man externe Daten einliest, um sie mit RSA zu verschlüsseln. Auf weitere zahlentheoretische
Hintergründe wird nicht näher eingegangen.
Wir wollen eine externe Datei in MuPAD einlesen, die nachher als Liste von
Zahlen dargestellt werden soll. Dazu definieren wir erst einmal den Ordner,
in dem sich die Datei befindet. MeinOrdner muss entsprechend angepasst
werden. Beachten Sie, dass am Ende der Pfadeingabe ein / stehen muss.
Ordner := "C:/MeinOrdner/":
Nun öffnen wir eine Bilddatei im .jpg Format mittels des Befehls fopen und
den Optionen Read und Raw, damit wir die Datei nachher mittels readbytes
einlesen können. Hier können beliebige Dateiformate verschlüsselt werden.
IN := fopen(Ordner."cube.jpg", Read, Raw):
Wir werden die Datei "portionsweise" einlesen, da wir bei RSA nur mit Zahlen,
die kleiner sind als das Modul N rechnen können. Die portionsweise ein-
gelesenen Daten werden dann als Liste von Bytes dargestellt, die dann noch in
eine ganze Zahl umgewandelt werden muss. Daher schreiben wir eine Prozedur,
die eine ganze Zahl x berechnet mit
wobei k die Anzahl der Bytes in der Liste ist.
Bytes2Int := proc(Liste)
local Zahl, i;
begin
Zahl := 0:
for i from 1 to nops(Liste) do
Zahl := 256 * Zahl + Liste[nops(Liste) + 1 - i]
end_for:
return(Zahl):
end_proc:
Die so erhaltene Zahl wird mittels RSA verschlüsselt, dann wieder zurück in
Bytedarstellung konvertiert und in eine Datei geschriebenen. Wir brauchen
also eine Prozedur, die eine ganze Zahl in Bytedarstellung umwandelt:
Int2Bytes := proc(Zahl, n)
local Liste, Quotient, Rest, i;
begin
Quotient := Zahl:
Liste := null():
for i from 1 to n do
Rest := modp(Quotient, 256):
Quotient := _div(Quotient, 256):
Liste := (Liste, Rest):
end_for:
if Quotient <> 0 then
print("Warnung: Informationsverlust! ", Quotient):
end_if:
[eval(Liste)]:
end_proc:
Nun haben wir alles zur Hand, um eine Datei mit RSA verschlüsseln zu
können. Dazu brauchen wir noch eine geeignete Verschlüsselungsprozedur,
die bei Eingabe des RSA-Moduls N, des öffentlichen Schlüssels und der
Datei die verschlüsselte Datei "irgendwo" speichert. Hier soll die Datei folgen-
derweise gespeichert werden:
OUT := fopen(Ordner."cube.crypt", Write, Raw):
Die Option Write bedeutet, dass diese Datei angelegt wird und zum
Schreiben geöffnet wird. Wir berechnen also zuerst n, die Länge des
Moduls in Bytedarstellung und wiederholen in einer Schleife folgendes:
1. Lese n-1 Bytes ein, da nicht mit Zahlen größer als das Modul gerechnet
werden darf
2. Wandle diese Liste in eine ganze Zahl um
3. Verschlüssle mit der RSA-Verschlüsselungsfunktion
4. Wandle diese Zahl in eine Liste von n Bytes um
5. Schreibe diese Bytes in eine Datei
Wenn nichts mehr gelesen wurde, wird die Schleife verlassen. Schliesslich
werden die geöffneten Dateien wieder geschlossen.
verschluesseln := proc(Modul, oeffentlich, IN, OUT)
local n, Part, Umwandlung1, Codierung, Umwandlung2;
begin
n := floor(log(256, Modul)) + 1:
repeat
Part := readbytes(IN, n-1):
Umwandlung1 := Bytes2Int(Part):
Codierung := powermod(Umwandlung1, oeffentlich, N):
Umwandlung2 := Int2Bytes(Codierung, n):
writebytes(OUT, Umwandlung2):
until Part = [] end:
fclose(IN):
fclose(OUT):
end_proc:
Jetzt müssen wir uns nur noch Gedanken um die Entschlüsselung machen,
dazu gehen wir "rückwärts". Nehmen wir an, wir haben eine verschlüsselte
Datei erhalten, die wir entschlüsseln wollen. Als erstes müssen wir diese
wieder portionsweise à n Bits einlesen und in eine ganze Zahl umwandeln.
Auf diese wenden wir dann die Entschlüsselung an, indem wir den geheimen
Schlüssel verwenden. Die so erhaltene Zahl muss nun in n-1 Bytes umge-
wandelt werden und in eine neue Datei geschrieben werden.
entschluesseln := proc(Modul, geheim, IN, OUT)
local n, Part, Umwandlung1, Decodierung, Umwandlung2;
begin
n := floor(log(256, Modul)) + 1:
repeat
Part := readbytes(IN, n):
Umwandlung1 := Bytes2Int(Part):
Decodierung := powermod(Umwandlung1, geheim, Modul):
Umwandlung2 := Int2Bytes(Decodierung, n-1):
writebytes(OUT, Umwandlung2):
until Part = [] end:
fclose(IN):
fclose(OUT):
end_proc:
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:
Folgenderweise 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"
Folgender Aufruf verschlüsselt die oben angegebene Datei und erzeugt
eine verschlüsselte Datei in Ordner.
verschluesseln(N, e, IN, OUT)
Error: Illegal argument [readbytes]
Die so erhaltene Datei können wir jetzt zum Beispiel per e-mail an einen
Bekannten schicken. Dieser benutzt dann seinen geheimen Schlüssel
um die Datei folgenderweise zu entschlüsseln:
IN := fopen(Ordner."cube.crypt", Read, Raw):
OUT := fopen(Ordner."cubeneu.jpg", Write, Raw):
entschluesseln(N, d, IN, OUT)
_______________________________________________________________________________
Übungen:
1. Entschlüsseln Sie das Bild geheim.crypt mit dem Modul N = nextprime(2^64)*nextprime(p+2^16)
und dem geheimen Schlüssel d = 336306151939690575333302230623497162561.
2. Verschlüsseln Sie beliebige Dateien ihrer Wahl. Achten Sie darauf, dass je größer die Datei, desto länger
dauert auch die Ver- und Entschlüsselung.
3. Machen Sie sich mit den Funktion _div und modp vertraut. Wo liegt der Unterschied?
4. Besuchen Sie die Hilfeseiten zu ?fopen und ?readbytes.
_______________________________________________________________________________
Anmerkungen:
1. Unter www.mupad.de/schule+studium/material/ befinden sich weitere Notebooks, die sich mit dem Thema
RSA beschäftigen.
2. 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.
_______________________________________________________________________________