\mnb150ÿ{\rtf1\ansi\deff0\deftab720{\fonttbl{\f0\fswiss MS Sans Serif;}{\f1\froman\fcharset2 Symbol;}{\f2\fswiss\fprq2 System;}{\f3\fmodern\fprq1 Courier New;}{\f4\fswiss\fprq2 Arial;}{\f5\fswiss\fprq2 Helvetica;}{\f6\fswiss\fprq2\fcharset1 Arial;}{\f7\fmodern\fprq1\fcharset1 Courier New;}{\f8\froman\fcharset1 Times New Roman;}{\f9\froman\fprq2\fcharset1 Times New Roman;}}
{\colortbl\red0\green0\blue0;\red0\green128\blue0;\red255\green0\blue0;\red0\green0\blue255;\red0\green0\blue128;}
\deflang1031\pard\ri4\plain\f3\fs20\cf0\b ________________________________________________________________________________
\par
\par \plain\f3\fs20\cf0 Inhalt....: Verschl\'fcsselung externer Daten mittels RSA
\par Kategorie.: Arbeitsblatt
\par Mathematik: Kryptographie, Zahlentheorie
\par MuPAD.....: 3.0.0
\par Datum.....: 2002-10-27
\par Autoren...: Julia Faflek
\par Funktionen: fopen, fclose, readbytes, writebytes, powermod
\par \plain\f3\fs20\cf0\b ________________________________________________________________________________
\par \plain\f4\fs36\cf0\b
\par \plain\f4\fs40\cf0\b Ver- und Entschl\'fcsselung externer Daten mittels
\par RSA\plain\f4\fs36\cf0\b
\par \plain\f4\fs22\cf0
\par \plain\f4\fs24\cf1 RSA ist weltweiter Standard bei der Ver- und Entschl\'fcsselung von Daten. Hier wird gezeigt,
\par wie man externe Daten einliest, um sie mit RSA zu verschl\'fcsseln. Auf weitere zahlentheoretische
\par Hintergr\'fcnde wird nicht n\'e4her eingegangen.
\par \plain\f4\fs28\cf0
\par Wir wollen eine externe Datei in MuPAD einlesen, die nachher als Liste von
\par Zahlen dargestellt werden soll. Dazu definieren wir erst einmal den Ordner,
\par in dem sich die Datei befindet. \plain\f3\fs28\cf2 MeinOrdner\plain\f4\fs28\cf0 muss entsprechend angepasst
\par werden. Beachten Sie, dass am Ende der Pfadeingabe ein \plain\f3\fs28\cf2 /\plain\f4\fs28\cf0 stehen muss.
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf2 {\pntext\f1\'b7\tab}Ordner :=\plain\f4\fs28\cf2 \plain\f3\fs28\cf2 "C:/MeinOrdner/":
\par \pard\ri4\plain\f9\fs22\cf0
\par \plain\f6\fs28\cf0 Nun \'f6ffnen wir eine Bilddatei im .jpg Format mittels des Befehls \plain\f7\fs28\cf2 fopen\plain\f6\fs28\cf0 und
\par den Optionen \plain\f7\fs28\cf2 Read\plain\f6\fs28\cf0 und \plain\f7\fs28\cf2 Raw\plain\f6\fs28\cf0 , damit wir die Datei nachher mittels \plain\f7\fs28\cf2 readbytes\plain\f6\fs28\cf0
\par einlesen k\'f6nnen. Hier k\'f6nnen beliebige Dateiformate verschl\'fcsselt werden.
\par \plain\f8\fs22\cf0
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf2 {\pntext\f1\'b7\tab}IN := fopen(Ordner."cube.jpg", Read, Raw):
\par \pard\ri4\plain\f4\fs28\cf0
\par Wir werden die Datei "portionsweise" einlesen, da wir bei RSA nur mit Zahlen,
\par die kleiner sind als das Modul N rechnen k\'f6nnen. Die portionsweise ein-
\par gelesenen Daten werden dann als Liste von Bytes dargestellt, die dann noch in
\par eine ganze Zahl umgewandelt werden muss. Daher schreiben wir eine Prozedur,
\par die eine ganze Zahl x berechnet mit\plain\f3\fs22\cf2
\par \pard\li2500\ri4\plain\f3\fs22\cf3 {\pict\wmetafile8\picw5075\pich1932\picscalex99\picscaley99\picwgoal2879\pichgoal1103
0100090000033A0500000B001C0000000000050000000B0200000000050000000C028C07D31303
0000001E00050000000C029A07D713050000000B0200000000030000001E00050000000C02A107
0814050000000B0200000000050000000B0200000000030000001E00050000000C02AF070C1405
0000000B0200000000050000000B0200000000050000000B0200000000030000001E0005000000
0C02B6073E14050000000B0200000000050000000B0200000000050000000B0200000000050000
000B0200000000030000001E00050000000C02C5074114050000000B0200000000050000000B02
00000000050000000B0200000000050000000B0200000000050000000B0200000000030000001E
00050000000C02CC077414050000000B0200000000050000000B0200000000050000000B020000
0000050000000B0200000000050000000B0200000000050000000B0200000000030000001E0005
0000000C02DB077714050000000B0200000000050000000B0200000000050000000B0200000000
050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000
00030000001E00050000000C02D305610F050000000B0200000000050000000B02000000000500
00000B0200000000050000000B0200000000050000000B0200000000050000000B020000000005
0000000B0200000000050000000B0200000000030000001E00050000000C02E305880F05000000
0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000
000B0200000000050000000B0200000000050000000B0200000000050000000B02000000000500
00000B0200000000030000001E00050000000C02F305B30F050000000B0200000000050000000B
0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000
0B0200000000050000000B0200000000050000000B0200000000050000000B0200000000050000
000B0200000000030000001E00050000000C020306DC0F050000000B0200000000050000000B02
00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B
0200000000050000000B0200000000050000000B0200000000050000000B020000000005000000
0B0200000000050000000B0200000000030000001E00050000000C020406DE0F050000000B0200
000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B02
00000000050000000B0200000000050000000B0200000000050000000B0200000000050000000B
0200000000050000000B0200000000050000000B0200000000050000000B020000000003000000
1E00030000001E00050000000C026903FF08050000000B0200000000050000000B020000000005
0000000B0200000000050000000B0200000000050000000B0200000000050000000B0200000000
050000000B0200000000050000000B0200000000050000000B0200000000050000000B02000000
00050000000B0200000000050000000B0200000000050000000B020000000008000000FA020000
0000000000000000040000002D0100001C000000FB0238FF000000000000900100000001070000
00417269616C000000930A0A1D38E91200D89FF177E19FF1772020F377570F66D8040000002D01
010005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200
00000004000000080100001C000000FB0210FF0000000000009001000000010700000054696D65
73204E657720526F6D616E00D89FF177E19FF1772020F377570F66D8040000002D0102000B0000
0026060F000C004D61746854797065000022011C000000FB0210FF000000000000900101000001
0700000054696D6573204E657720526F6D616E00D89FF177E19FF1772020F377570F66D8040000
002D010300040000002D0102001C000000FB0256FF000000000000900101000001070000005469
6D6573204E657720526F6D616E00D89FF177E19FF1772020F377570F66D8040000002D0104001C
000000FB0256FF0000000000009001000000020700000053796D626F6C0000160F0A8C38E91200
D89FF177E19FF1772020F377570F66D8040000002D0105001C000000FB0256FF00000000000090
01000000010700000054696D6573204E657720526F6D616E00D89FF177E19FF1772020F377570F
66D8040000002D010600040000002D010200040000002D0104001C000000FB0210FF0000000000
009001000000020700000053796D626F6C0000220F0A0E38E91200D89FF177E19FF1772020F377
570F66D8040000002D010700040000002D010400040000002D010600040000002D010500040000
002D010400040000002D010600040000002D0105001C000000FB0210FF00000000000090010000
0002070000005346204D617468204578740038E91200D89FF177E19FF1772020F377570F66D804
0000002D010800040000002D010200040000002D010500040000002D010700040000002D010200
0500000009020000FF00040000002D01030007000000210501007802FE016B00040000002D0107
0007000000210501003D02FE011E01040000002D010500040000002D010800040000002D010200
040000002D010500040000002D010800040000002D010200040000002D010500040000002D0108
00070000002105010058020E01EA01040000002D01040007000000210501006902030325020400
00002D01050007000000210501003D0203036D02040000002D0106000700000021050100300203
03E402040000002D01040007000000210501006B02EF001302040000002D010500070000002105
01002D02EF007F02040000002D01060007000000210501003102EF00F602040000002D01070004
0000002D010200040000002D010600040000002D01020007000000210501004C02FE0175030700
0000210501006902FE01080407000000210501007302FE014B0407000000210501007402FE01A8
0407000000210501006502FE01EB04040000002D01040007000000210501006B02380256050400
00002D01050007000000210501002D023802C205040000002D0104000700000021050100690238
023906040000002D0107000700000021050100D702FE019806040000002D010200070000002105
01003202FE01040707000000210501003502FE017C0707000000210501003602FE01F407040000
002D0104000700000021050100690282016C0808000000FA020000000000000000000004000000
2D0109001C000000FB021000070000000000BC02000000000102022253797374656D00002B0F0A
B838E91200D89FF177E19FF1772020F377570F66D8040000002D010A00040000002701FFFF0400
0000F001000004000000F001010004000000F001020004000000F001030004000000F001040004
000000F001050004000000F001060004000000F001070004000000F0010800040000002701FFFF
040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FF
FF040000002701FFFF040000002701FFFF040000002701FFFF040000002701FFFF040000002701
FFFF040000002701FFFF040000002701FFFF030000000000
}\plain\f3\fs22\cf3
\par \pard\ri4\plain\f4\fs28\cf0 wobei k die Anzahl der Bytes in der Liste ist.\plain\f3\fs22\cf3
\par \plain\f4\fs22\cf0
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf2 {\pntext\f1\'b7\tab}Bytes2Int := proc(Liste)
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf2 local Zahl, i;
\par begin
\par Zahl := 0:
\par for i from 1 to nops(Liste) do
\par Zahl := 256 * Zahl + Liste[nops(Liste) + 1 - i]
\par end_for:
\par return(Zahl):
\par end_proc:
\par \pard\ri4\plain\f4\fs28\cf0
\par Die so erhaltene Zahl wird mittels RSA verschl\'fcsselt, dann wieder zur\'fcck in
\par Bytedarstellung konvertiert und in eine Datei geschriebenen. Wir brauchen
\par also eine Prozedur, die eine ganze Zahl in Bytedarstellung umwandelt:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf2 {\pntext\f1\'b7\tab}Int2Bytes := proc(Zahl, n)
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf2 local Liste, Quotient, Rest, i;
\par begin
\par Quotient := Zahl:
\par Liste := null():
\par for i from 1 to n do
\par Rest := modp(Quotient, 256):
\par Quotient := _div(Quotient, 256):
\par Liste := (Liste, Rest):
\par end_for:
\par if Quotient <> 0 then
\par print("Warnung: Informationsverlust! ", Quotient):
\par end_if:
\par [eval(Liste)]:
\par end_proc:
\par
\par \pard\ri4\plain\f4\fs28\cf0 Nun haben wir alles zur Hand, um eine Datei mit RSA verschl\'fcsseln zu
\par k\'f6nnen. Dazu brauchen wir noch eine geeignete Verschl\'fcsselungsprozedur,
\par die bei Eingabe des RSA-Moduls N, des \'f6ffentlichen Schl\'fcssels und der
\par Datei die verschl\'fcsselte Datei "irgendwo" speichert. Hier soll die Datei folgen-
\par derweise gespeichert werden:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf2 {\pntext\f1\'b7\tab}OUT := fopen(Ordner."cube.crypt", Write, Raw):
\par \pard\ri4\plain\f4\fs28\cf0
\par Die Option \plain\f3\fs28\cf2 Write\plain\f4\fs28\cf0 bedeutet, dass diese Datei angelegt wird und zum
\par Schreiben ge\'f6ffnet wird. Wir berechnen also zuerst n, die L\'e4nge des
\par Moduls in Bytedarstellung und wiederholen in einer Schleife folgendes:
\par
\par 1. Lese n-1 Bytes ein, da nicht mit Zahlen gr\'f6\'dfer als das Modul gerechnet
\par werden darf
\par
\par 2. Wandle diese Liste in eine ganze Zahl um
\par
\par 3. Verschl\'fcssle mit der RSA-Verschl\'fcsselungsfunktion
\par
\par 4. Wandle diese Zahl in eine Liste von n Bytes um
\par
\par 5. Schreibe diese Bytes in eine Datei
\par
\par Wenn nichts mehr gelesen wurde, wird die Schleife verlassen. Schliesslich
\par werden die ge\'f6ffneten Dateien wieder geschlossen.
\par \plain\f3\fs22\cf3
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf2 {\pntext\f1\'b7\tab}verschluesseln := proc(Modul, oeffentlich, IN, OUT)
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf2 local n, Part, Umwandlung1, Codierung, Umwandlung2;
\par begin
\par n := floor(log(256, Modul)) + 1:
\par repeat
\par Part := readbytes(IN, n-1):
\par Umwandlung1 := Bytes2Int(Part):
\par Codierung := powermod(Umwandlung1, oeffentlich, N):
\par Umwandlung2 := Int2Bytes(Codierung, n):
\par writebytes(OUT, Umwandlung2):
\par until Part = [] end:
\par fclose(IN):
\par fclose(OUT):
\par end_proc:
\par \pard\ri4\plain\f3\fs20\cf0\b
\par \plain\f4\fs28\cf0 Jetzt m\'fcssen wir uns nur noch Gedanken um die Entschl\'fcsselung machen,
\par dazu gehen wir "r\'fcckw\'e4rts". Nehmen wir an, wir haben eine verschl\'fcsselte
\par Datei erhalten, die wir entschl\'fcsseln wollen. Als erstes m\'fcssen wir diese
\par wieder portionsweise \'e0 n Bits einlesen und in eine ganze Zahl umwandeln.
\par Auf diese wenden wir dann die Entschl\'fcsselung an, indem wir den geheimen
\par Schl\'fcssel verwenden. Die so erhaltene Zahl muss nun in n-1 Bytes umge-
\par wandelt werden und in eine neue Datei geschrieben werden.
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf2 {\pntext\f1\'b7\tab}entschluesseln := proc(Modul, geheim, IN, OUT)
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf2 local n, Part, Umwandlung1, Decodierung, Umwandlung2;
\par begin
\par n := floor(log(256, Modul)) + 1:
\par repeat
\par Part := readbytes(IN, n):
\par Umwandlung1 := Bytes2Int(Part):
\par Decodierung := powermod(Umwandlung1, geheim, Modul):
\par Umwandlung2 := Int2Bytes(Decodierung, n-1):
\par writebytes(OUT, Umwandlung2):
\par until Part = [] end:
\par fclose(IN):
\par fclose(OUT):
\par end_proc:
\par \pard\ri4\plain\f4\fs28\cf0
\par Betrachten wir nun ein Beispiel. Zun\'e4chst legen wir folgende RSA-Parameter
\par fest:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf2 {\pntext\f1\'b7\tab}p := nextprime(2^64):
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf2 q := nextprime(p + 2^16):
\par N := p*q:
\par \pard\ri4\plain\f4\fs28\cf0
\par Folgenderweise erzeugen wir ein zuf\'e4lliges Schl\'fcsselpaar:
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf2 {\pntext\f1\'b7\tab}Schluesselerzeugung := proc(p, q)
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf2 local Phi_N;
\par begin
\par Phi_N := (p-1)*(q-1):
\par for i from 1 to Phi_N do
\par e := random(2..Phi_N-1)():
\par if igcd(e, Phi_N) = 1 then
\par print("oeffentlich = " .e):
\par break:
\par end_if:
\par end_for:
\par d := e^(-1) mod Phi_N:
\par print("geheim = " .d);
\par end:
\par \pard\ri4\plain\f4\fs28\cf0
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf2 {\pntext\f1\'b7\tab}Schluesselerzeugung(p,q)
\par \pard\ri4\plain\f4\fs28\cf0
\par Folgender Aufruf verschl\'fcsselt die oben angegebene Datei und erzeugt
\par eine verschl\'fcsselte Datei in \plain\f3\fs28\cf2 Ordner\plain\f4\fs28\cf0 .
\par \plain\f3\fs20\cf0
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf2 {\pntext\f1\'b7\tab}verschluesseln(N, e, IN, OUT)
\par \pard\ri4\plain\f4\fs28\cf0
\par Die so erhaltene Datei k\'f6nnen wir jetzt zum Beispiel per e-mail an einen
\par Bekannten schicken. Dieser benutzt dann seinen geheimen Schl\'fcssel
\par um die Datei folgenderweise zu entschl\'fcsseln:\plain\f3\fs20\cf0\b
\par
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs28\cf2 {\pntext\f1\'b7\tab}IN := fopen(Ordner."cube.crypt", Read, Raw):
\par \pard\li600\ri1\fi-300\plain\f3\fs28\cf2 OUT := fopen(Ordner."cubeneu.jpg", Write, Raw):
\par entschluesseln(N, d, IN, OUT)
\par \pard\ri4\plain\f3\fs20\cf0\b _______________________________________________________________________________
\par \plain\f3\fs22\cf3
\par \plain\f4\fs22\cf3\b \'dcbungen:
\par \plain\f4\fs20\cf3\b 1. \plain\f4\fs20\cf3 Entschl\'fcsseln Sie das Bild geheim.crypt mit dem Modul N = nextprime(2^64)*nextprime(p+2^16)
\par und dem geheimen Schl\'fcssel d = \plain\f4\fs22\cf3\protect 336306151939690575333302230623497162561\plain\f4\fs20\cf3\b .
\par 2.\plain\f4\fs20\cf3 Verschl\'fcsseln Sie beliebige Dateien ihrer Wahl. Achten Sie darauf, dass je gr\'f6\'dfer die Datei, desto l\'e4nger
\par dauert auch die Ver- und Entschl\'fcsselung.
\par \plain\f4\fs20\cf3\b 3.\plain\f4\fs20\cf3 Machen Sie sich mit den Funktion\plain\f4\fs20\cf4 \plain\f3\fs20\cf2 _div\plain\f4\fs20\cf4 \plain\f4\fs20\cf3 und\plain\f4\fs20\cf4 \plain\f3\fs20\cf2 modp\plain\f4\fs20\cf4 \plain\f4\fs20\cf3 vertraut. Wo liegt der Unterschied?
\par \plain\f4\fs20\cf3\b 4.\plain\f4\fs20\cf3 Besuchen Sie die Hilfeseiten zu ?fopen und ?readbytes.\plain\f4\fs20\cf4
\par \plain\f3\fs20\cf0\b _______________________________________________________________________________
\par \plain\f4\fs22\cf0
\par \plain\f4\fs22\cf1\b Anmerkungen:\plain\f4\fs22\cf1
\par \plain\f4\fs20\cf1\b 1. \plain\f4\fs20\cf1 Unter \plain\f4\fs20\cf2 www.mupad.de/schule+studium/material/\plain\f4\fs20\cf1 befinden sich weitere Notebooks, die sich mit dem Thema
\par RSA besch\'e4ftigen.
\par
\par \plain\f4\fs20\cf1\b 2.\plain\f4\fs20\cf1 Weitere Anregungen finden Sie in der Buchreihe \plain\f4\fs20\cf2 Mathematik 1 x anders\plain\f4\fs20\cf1 . In dieser Reihe
\par wird eine Vielzahl unterschiedlichster mathematischer Probleme mit MuPAD gel\'f6st. Die
\par B\'fccher k\'f6nnen unter \plain\f5\fs20\cf3 www.schule.mupad.de/literatur\plain\f4\fs20\cf1 kostenfrei kopiert werden.\plain\f4\fs20\cf2
\par \plain\f3\fs20\cf0\b _______________________________________________________________________________
\par
\par
\par }