\chapter [Implementierung der Rechenbibliothek] {Implementierung der Rechenbibliothek} \thispagestyle{empty} Da Modula2 in Bezug auf die L"ange der darstellbaren ganzen Zahlen beschr"ankt ist, mu\3te eine Ausweichl"osung f"ur dieses Problem gefunden werden. Die meisten Zahlendarstellungen bewegen sich im Bereich von -32768 bis 32767 oder von -2147483648 bis 2147483647, je nach dem welche Datenbusbreite die verwendete CPU besitzt. Diese Zahlenbereiche sind f"ur das RSA-Verfahren aber bei weitem nicht ausreichend, weil hier Zahlen von ca. 200 Dezimalstellen gebraucht werden, um eine ausreichende Sicherheit zu gew"ahrleisten.\\ Um ein Problem wie das RSA-Verfahren angehen zu k"onnen, mu\3te ein Modul implementiert werden, das mit solch langen Zahlen umgehen kann. Die dabei auftretenden Probleme sollen in diesem Kapitel erl"autert werden. \section [Die interne Zahlendarstellung] {Die interne Zahlendarstellung} Die einfachste Methode w"are ein ARRAY OF CHAR zu vereinbaren und darin die Zahl als ASCII-Zeichenketten darzustellen. Dies h"atte auch den Vorteil, da\3 man keine Umwandlungsprobleme von String nach LONG-Zahl und zur"uck h"atte. Nebenbei w"are es einfach die Grundrechenarten zu programmieren, weil sie ja den vertrauten Rechenoperationen entsprechen w"urden.\\ Bei genauerer Untersuchung dieses Problems entpuppt sich diese Darstellung aber als unbrauchbar, weil "Ubertr"age nur durch den Vergleich einzelner Komponenten abpr"ufbar w"aren. Dies ist sehr zeitaufwendig, weil die elementaren Vergleichsoperatoren zur Abbildung der Grundrechenarten h"aufig gebraucht werden.\\ Die bin"are Darstellung hingegen k"onnte jeden "Ubertrag nur durch Abfragen eines einzelnen Bits erkennen. Dabei stellt die LONG-Zahl ein sehr langes Bit-ARRAY dar. Einen weiteren Vorteil stellt die bessere Speicherausnutzung durch die bin"are Darstellung dar.\\ Es stellt sich nun die Frage ''Wie bildet man die Grundrechenarten auf ein langes Bit-ARRAY ab {?} ``.\\ Dazu mu\3 man erst einmal einige grunds"atzliche "Uberlegungen anstellen. Weil Modula2 keinen beliebig langen SET-Typ\footnote{Beschr"ankung auf die Breite des Datenbusses des verwendeten Systems} kennt, mu\3 ein ARRAY OF INTEGER verwendet werden.\\ W"ahrend der Rechenoperationen kann es vorkommen, da\3 nicht alle Komponenten des Integerarrays mit g"ultigen Daten gef"ullt sind. Wenn man sich die Anzahl der aktuell g"ultigen Komponenten nicht merkt, m"ussen alle unbenutzen Teile der LONG-Zahl mit 0 vorbesetzt werden. Weiterhin h"atte diese L"osung den Nachteil, da\3 man die Operationen auch mit unbenutzten Teilen der LONG-Zahl durchf"uhren m"u\3te, was eine wesentliche Verlangsamung der Berechnungen verursachen w"urde. Aus diesem Grund habe ich mich dazu entschieden im ersten Element die Anzahl der g"ultigen Komponenten abzulegen.\\ Jetzt mu\3 nur noch die Erkennung des "Uberlaufs bei einer Teiloperation realisiert werden. Die erste Idee einfach das Carry-Bit abzufragen scheitert daran, da\3 Modula2 keine M"oglichkeit zur Verf"ugung stellt das Carry-Bit direkt abzufragen. Deshalb habe ich einen kleinen Trick verwendet. Bei meiner Zahlendarstellung wird das Vorzeichenbit als Pseudo-Carrybit verwendet. Dies hat den Vorteil, da\3 der Compiler effizienten Code zur "Uberlaufabfrage erzeugen kann, weil ja nur das Negativbit abgefragt werden mu\3. Dies kann mit so einfachen Konstrukten geschehen wie ``IF $i<0$ THEN \ldots''. Solch eine Abfrage kann direkt in Maschinensprache ( BMI oder BPL beim MC 68000 ) "ubersetzt werden.\\ Das n"achste Bild soll die verwendete Zahlendarstellung noch einmal verdeutlichen. \begin{center} \unitlength1cm \begin{picture}(12,1) \newsavebox{\first} \savebox{\first}(2.0,1.0) { \put(0.1,0.05) {\scriptsize 0} \put(0.8,0.05) {\scriptsize 7} \put(1.1,0.05) {\scriptsize 8} \put(1.65,0.05) {\scriptsize 15} \put(0.0,0.0) {\line(1,0) {2.0}} \put(0.0,0.0) {\line(0,1) {0.55}} \put(1.0,0.0) {\line(0,1) {0.4}} \put(2.0,0.0) {\line(0,1) {0.55}} } \newsavebox{\second} \savebox{\second}(2.0,1.0) { \put(0.1,0.05) {\scriptsize 0} \put(1.65,0.05) {\scriptsize 15} \put(0.0,0.0) {\line(1,0) {2.0}} \put(0.0,0.0) {\line(0,1) {0.55}} \put(1.0,0.0) {\line(0,1) {0.4}} \put(2.0,0.0) {\line(0,1) {0.55}} } \newsavebox{\third} \savebox{\third}(2.0,1.0) { \put(0.1,0.05) {\scriptsize \ldots \dots \ldots} \put(0.0,0.0) {\line(1,0) {2.0}} \put(0.0,0.0) {\line(0,1) {0.55}} \put(2.0,0.0) {\line(0,1) {0.55}} } \newsavebox{\fourth} \savebox{\fourth}(2.0,1.0) { \put(0.1,0.05) {\scriptsize L"ange} \put(0.0,0.0) {\line(1,0) {2.0}} \put(0.0,0.0) {\line(0,1) {0.55}} \put(2.0,0.0) {\line(0,1) {0.55}} } \put(-1.0,0.0){\usebox{\fourth}} \put(1.0,0.0){\usebox{\first}} \put(3.0,0.0){\usebox{\second}} \put(5.0,0.0){\usebox{\second}} \put(7.0,0.0){\usebox{\third}} \put(9.0,0.0){\usebox{\second}} \end{picture} \end{center} Dabei sind das LSB\footnote{Least Significant Bit = Bit 0} und das MSB\footnote{Most Significant Bit = Bit 15} von besonderer Bedeutung.\\ Das MSB wird wie schon oben beschrieben, als Pseudocarrybit verwendet. Durch Testen des LSB kann entschieden werden, ob die vorliegende LONG-Zahl gerade oder ungerade ist. Dies ist bei einigen unten beschriebenen Algorithmen von besonderer Bedeutung. \section [Implementation der Grundrechenarten] {Implementation der Grundrechenarten} \subsection [Addition] {Addition} Die erste und wohl einer der wichtigsten Grundrechenarten ist die Addition. Diese Operation wird zwar nicht direkt vom RSA-Verfahren ben"otigt, aber viele Operationen wie die Multiplikation verwenden diese Verk"upfung intern. Um die Addition auf die LONG-Zahlen abzubilden sind einige "Uberlegungen notwendig, denn es sind 3 F"alle zu unterscheiden. Im ersten Fall sind beide Zahlen gleich lang. Hier kann einfach Komponente mit Komponente addiert werden.\\ Sollte bei einer solchen Teiloperation ein "Uberlauf auftreten, so mu\3 im n"achsten Schritt ein "Ubertrag ber"ucksichtigt werden. Sollte in der letzten Komponente noch ein "Uberlauf auftreten, so mu\3 in das n"achste Element eine Eins eingetragen werden, und die L"ange im Feld 0 erh"oht werden. Ist die maximale L"ange erreicht, so wird eine BOOLEAN-Variable Carry auf TRUE gesetzt, um den "Uberlauf bei der Gesamtoperation anzuzeigen. Dies kann, nachdem diese Variable importiert wurde, abgefragt werden. Die zwei anderen F"alle, in denen die LONG-Zahlen ungleichlang sind, sind etwas aufwendiger zu behandeln. Leider treten sie auch in der Mehrzahl der F"alle auf, was die Gesamtleistung der Algorithmus erniedrigt. Es bieten sich zwei M"oglichkeiten an: \begin{enumerate} \item {Man bearbeitet die Zahlen nur bis zu der L"ange der k"urzesten Zahl und "ubertr"agt dann die weiteren Komponenten der l"angeren Zahl in das Ergebnis. Dabei m"u\3en nat"urlich immer noch eventuell auftretende "Ubertr"age, die bei der Addition der einzelnen Komponenten entstehen, ber"ucksichtigt werden. In einem solchen Fall mu\3 die n"achste Komponente inkrementiert werden.} % \item{Man verl"angert die k"urzere Zahl k"unstlich in dem man vorne Komponenten mit 0 anf"ugt bis beide Zahlen gleich lang sind. Dann f"uhrt man den Algorithmus f"ur gleich lange Zahlen durch.} \end{enumerate} Ich habe mich bei der vorliegenden Implementierung f"ur den Fall 2 entschieden, weil zum einen der Programmierungsaufwand wesentlich niedriger ist, und zum anderen die Unterschiede bei den Zahlenl"angen nicht besonders ausschlaggebend sind. Der Algorithmus ist als Struktogramm im Anhang wiedergegeben. \subsection [Subtraktion] {Subtraktion} Bei der Subtraktion treten im Wesentlichen die gleichen Probleme wie bei der Addition auf. Deshalb unterscheiden sich die beiden Algorithmen nur unwesentlich. Der einzige Unterschied ist die Abpr"ufung, ob der erste Operand kleiner als der zweite ist, weil dann n"amlich die Carryvariable auf TRUE gesetzt werden mu\3. Dies ist notwendig, weil das vorliegende Modul keine negativen Zahlen unterst"utzt. \subsection [Multiplikation] {Multiplikation} Im Gegensatz zu den oben beschriebenen Operationen ist die Multiplikation etwas schwerer "uberschaubar. Ein erster naiver Versuch ergibt sich durch folgende "Uberlegung: $$5*4=5+5+5+5$$ oder allgemein: $$n*m=m*n=\underbrace{n+\ldots+n}_{genau\ m\ mal}$$ Bei dieser Vorgehensweise ist ein sehr hoher Aufwand notwendig, weil eine Additionschleife sehr oft durchlaufen werden mu\3, wenn m gro\3 ist. Weil dies im vorliegenden Modul der Fall ist und beim RSA-Verfahren die oft ben"otigte Potenzierung auch auf diese Multiplikation zur"uckgreift, ist diese Art der Implementierung nicht sinnvoll und wird hier nicht verwendet.\\ Statt dessen wird ein Algorithmus, der schon in der Assemblervorlesung im 4. Semester vorgestellt wurde, verwendet, um das Produkt $a*b$ zu berechnen. Bei diesem Algorithmus wird die Zahl b solange rechts rotiert, d.h. die Zahl wird fortgesetzt durch 2 geteilt, bis man die Null erreicht. Sollte w"ahrend der Ausf"uhrung des Algorithmus b ungerade sein, was durch Abfragen des LSB getestet werden kann, so wird eine dritte Variable um den Wert der Zahl a inkrementiert. W"ahrend des Schleifendurchlaufs wird die Zahl a mit 2 multipliziert, was einer Linksrotation entspricht. Dieser Algorithmus hat dann nur noch einen Aufwand von ld(b). D.h. bei einer Wortbreite von n sind nur n Additionen und $2*n$ Rotationen notwendig um das Ergebnis zu berechnen. Dies ist schon ein gro\3er Fortschritt gegen"uber dem weiter oben vorgeschlagen Algorithmus.\\ Der Aufwand in dieser Implementation ist leicht abzusch"atzen:\\ Wenn die Zahl b 3 INTEGER-Komponenten\footnote{Dies ist im L"angenfeld notiert} lang ist m"ussen maximal $3*15=45$ Rotationen\footnote{Bei dem von uns verwendeten MODULA2-Compiler wird ein 16-Bit INTEGER Typ bereitgestellt} durchgef"uhrt werden, die die ganze LONG-Zahl betreffen. Hier sieht man schon, da\3 dieses Verfahren bei langen Zahlen immer noch sehr aufwendig ist. Mir ist aber leider kein Algorithmus bekannt, der einen Aufwand von weniger als ld(b) hat. Das Struktogramm dieses Algorithmus ist im Anhang wiedergegeben. % \subsubsection[Restklassenmultiplikation] {Restklassenmultiplikation} Da beim RSA-Verfahren nur eine Multiplikation mit Abbildung in den verwendeten Restklassenring ben"otigt wird, habe ich einen modifizierten Multiplikationsalgorithmus implementiert, der dies leistet.\\ Die erste Idee nach einer normalen Multiplikation eine MOD-Operation durchzuf"uhren scheitert an dem zu hohen Rechenzeitbedarf, weil eine Modulofunktion Schiebe- und Subtraktionsoperationen ben"otigt. Weiterhin kann das Produkt zweier gro\3er Zahlen u.U. Werte erreichen, die nicht mehr darstellbar sind.\\ Der hier verwendete Multiplikationsalgorithmus ben"otigt ein Links-Shift und eventuell eine Addition. Bei beiden Funktionen k"onnen die verwendeten Variablen die Ordnung des Restklassenrings "uberschreiten. Bei n"aherer "Uberlegung zeigt sich aber, da\3 sie immer kleiner als $2*Ordnung$ des Restklassenrings ${{\cal Z}_n}$ sind. Deshalb mu\3 im Fall der "Uberschreitung nur eine Subtraktion durchgef"uhrt werden, um das Ergebnis wieder in den Bereich des Restklassenrings abzubilden, was eine erhebliche Rechenzeitersparnis ergibt. Ein weiterer Vorteil dieses Verfahrens ist, da\3 der Betrag der gr"o\3ten auftretende Zahl nur $2*Ordnung$ des Restklassenrings sein kann, wodurch u.U. erheblich Speicherplatz gespart wird. \subsection [Division] {Division} Obwohl die Division beim RSA-Verfahren nicht als einzelne Operation ben"otigt wird, habe ich sie der Vollst"andigkeit halber im Modul MathLong implementiert.\\ Die Division von $\frac{a}{b}$ unterscheidet sich im Wesentlichen nicht von der Multiplikation. Der einzige wesentliche Unterschied ist der Beginn des Algorithmus. Hier mu\3 die kleinere Zahl b solange mit 2 multipliziert werden, bis sie gr"o\3er oder gleich der Zahl a ist. Dies hat schwerwiegende Auswirkungen auf die Umwandlung von LONG-Zahlen in ASCII-Strings, weil hier fortgesetzt durch 10 geteilt werden mu\3. Da aber 10 klein gegen"uber der zu teilenen Zahl ist, sind sehr viele Schiebeoperationen notwendig. D.h. Divisionen bei denen die Zahl $b \ll a$ k"onnen nur relativ langsam berechnet werden. Auch zu dieser Funktion existiert ein Struktogramm im Anhang. \section[Die erweiterten Rechenoperationen]{Die erweiterten Rechenoperationen} \subsection [Modulofunktion] {Die Modulofunktion} Da die Modulofunktion f"ur das RSA-Verfahren von gro\3er Bedeutung ist, mu\3te auch diese Funktion implementiert werden.\\ Sie existiert in zwei Varianten. Einmal als normale einzelne Modulofunktion und zum andern als mit der Division kombinierte ModDiv-Funktion. Diese Funktion bietet einen Vorteil:\\ An mehreren Stellen ist gleichzeitig eine Zahl durch eine andere zu teilen und der Rest der Division zu bestimmen. Da sich diese Operationen im Algorithmus nur durch die R"uckgabe unterschiedlicher Variablen unterscheiden, wurden sie in einer Funktion zusammengefa\3t um so erheblich Rechenzeit zu sparen. \subsection [Potenzierung] {Potenzierung} Diesem Algorithmus f"allt ein zentrale Bedeutung beim RSA-Verfahren zu, weil sowohl die Verschl"usselung als auch die Entschl"usselung durch die Potenzierung geschieht\\ Da die Verschl"usselungsgeschwindigkeit ein wesentlicher Faktor bei einem Public-Key Cryptosystem ist, wurde bei der Implementierung besonders auf die Effizienz geachtet.\\ Eine erste naive "Uberlegung ergibt folgendes Ergebnis: \begin{displaymath} a^b=\underbrace{a*a*\dots*a}_{genau\ b\ mal} \end{displaymath} Wie man sieht werden hier sehr viele Multiplikationen ben"otigt, wenn b eine gro\3e Zahl ist. Da dies beim RSA-Verfahren aber der Fall ist, kann diese Methode nicht verwendet werden.\\ Ein "ahnliche Idee wie bei der Multiplikation f"uhrt dann zur Methode ''Repea\-ted Square and Multiply``, die nur noch einen Aufwand von ld(b) hat, was eine wesentliche Verbesserung darstellt.\\ Zur Potenzierung $x^y$ wird eine mit 1 initialisierte Variable r immer dann mit $x$ multipliziert, wenn x ungerade ist. Sodann wird $x$ durch $x^2$ ersetzt und y um ein Bit nach rechts rotiert. Diese Routine ist die iterative Formulierung des folgenden rekursiven Ansatzes: \begin{displaymath} a^b = \left\{ \begin{array}{l} a^{\frac{b}{2}}*a^{\frac{b}{2}},\mbox{ falls b gerade}\\ a^{\frac{b}{2}}*a^{\frac{b}{2}}*a,\mbox{ falls b ungerade} \end{array} \right. \end{displaymath} Die Aufspaltung von $a^b$ in $a^\frac{b}{2}$ wird rekursiv so lange fortgef"uhrt, bis $\frac{b}{2}$ gleich 1 ist. Die iterative Formulierung verwendet dazu die Bin"ardarstellung der Zahl $b$, die durch Schiebeoperationen gewonnen wird.\\ Jetzt wird auch klar warum eine Multiplikation mit anschlie\3ender MOD-Operation implementiert wurde. Durch diese Routine kann leicht eine Restklassenpotenzierung formuliert werden, mit der die Ver- bzw. Entschl"usselung einer Nachricht berechnet wird.\\ Um den Algorithmus zu veranschaulichen ist im Anhang ein entsprechendes Struktogamm wiedergegeben. % \section[Typwandlungsfunktionen]{Typwandlungsfunktionen} Da wir eine Zahlendarstellung verwenden, die nicht von Computern mit der INTEL-CPU 80386 unterst"utzt wird, sind die Typwandlungsfunktionen von elementarer Bedeutung. Deshalb wurden mehrere Varianten implementiert.\\ Um die Verwendung von LONG-Zahlen zu vereinfachen wurden h"aufig verwendete Zahlen als ''Konstanten`` im Definitionsmodul vereinbart.\\ Sollten andere Zahlen verwendet werden, so existiert je eine Routinen zur Wandlung von Strings in LONG-Zahlen und eine zur Umwandlung von positiven Integerzahlen.\\ Auch der umgekehrte Weg der Umwandlung ist vorhanden. Mit der Routine LONG2Str kann eine LONG-Zahl in einen String umgerechnet werden.\\ F"ur die Wandlungsfunktionen von Strings nach LONG-Zahlen beziehungsweise umgekehrt wurden Standardalgorithmen verwendet.\\ Um einen String in eine LONG-Zahl zu verwandeln wird das Hornerschema verwendet.\\ Die Ergebnisvariable mu"s mit 0 initialisiert werden. Dann wird das erste Zeichen im Eingabestring in seine Integerzahl umgewandelt. Die Ergebnisvariable wird dann mit 10 multipliziert \footnote{Hier wurde als Basis das vertraute Dezimalsystem verwendet}. Dannach wird noch die oben ermittelte Integerzahl zu der Ergebnisvariable dazuaddiert. Dieser Vorgang wird so lange wiederholt, bis das Ende des Eingabestrings erreicht ist.\\ Bei der Wandlung LONG-Zahl in String wird immer der Rest bez"uglich der Division mit 10 bestimmt. Dieser Rest wird in sein CHAR-"Aquivalent umgewandelt und in einen String eingetragen. Nach der Beendigung dieses Vorgangs wird der String noch umgedreht, damit die niedrigen Potenzen der Zahl am rechten Ende stehen.\\ Um die Umwandlung in eine LONG-Zahl zu vereinfachen wurde auch eine Wandlungsfunktion f"ur positive Integerzahlen in LONG-Zahlen vorgesehen. Die Wandlung geschieht dadurch, da\3 in Komponente 0 der LONG-Zahl die L"ange 1 eingetragen wird. In die erste Komponente wird dann nur noch die "ubergebene Zahl eingetragen. Diese Routine wird z.B. besonders oft vom Miller-Rabin-Test verwendet. % \section[Die Vergleichoperationen]{Die Vergleichoperationen} Bei allen Algorithmen werden arithmetische Vergleichsoperationen ben"otigt. Mit diesen Operationen k"onnen z.B. die Gleichheit oder Ungleichheit zweier LONG-Zahlen ermittelt werden. Alle diese Routinen liefern eine Variable vom BOOLEAN-Typ zur"uck.\\ In Anlehnung an die bekannte FORTRAN-77-Syntax wurden Namen wie ''LE`` Less Equal oder ''EQ`` {Equal} vergeben. Alle Vergleichsoperationen haben die gleiche Bedeutung wie ihre FORTRAN-77-"Aquivalente und bed"urfen deshalb keiner weiteren Erl"auterung.\\ Ich m"ochte hier noch auf eine Besonderheit eingehen. Von J"urgen Wei\-nelt wurde vorgeschlagen Vergleichsoperationen wie ''LT`` durch den Aufruf von ''NOT(GE)`` zu realisieren. Dies w"urde eine Verk"urzung des Programmcodes bewirken, aber auch gleichzeitig eine Verlangsamung der Routinen, weil die Parameter 2 mal "uber den Stack "ubergeben werden m"u\3ten. Da bei der vorliegenden Implementierung mehr auf Laufzeiteffizienz als auf Speichereffizienz geachtet werden mu\3te, habe ich mich daf"ur entschieden jede einzelne Operationen vollst"andig zu programmieren. % \section[Hilfsfunktionen]{Hilfsfunktionen} In diesem Abschnitt sollen die Hilfsfunktionen des Modules MathLong erw"ahnt werden. % \subsection[Speicherfunktionen]{Speicherfunktionen} Das wichtigste Funktionenpaar d"urften die Funktionen AllocNum und FreeNum sein, die Speicher f"ur LONG-Zahlen anfordern und freigeben. Da LONG einen opaquen Typ darstellt, ist er nach MODULA2 Konvention ein Zeiger. Deshalb mu\3 nicht nur eine Variable von Typ LONG vereinbart werden, sondern es mu\3 auch noch der entsprechende Speicherbereich mit AllocNum reserviert werden. Bei Programmende mu\3 dieser Speicher mit FreeNum wieder freigegeben werden. Um LONG-Zahlen zuweisen zu k"onnen wurde noch eine Zuweisungsfunktion Trans implementiert. Dies ist n"otig, weil die Zuweisung eines Zeigers auf einen anderen den Speicherbereich auf den der Quellzeiger deutet nicht kopiert. Folgende Anweisungen sollen dies verdeutlichen:\\ VAR a,b:LONG\\ \vdots\\ (* Falsche Zuweisung *)\\ a:=b\\ \vdots\\ (* Richtige Zuweisung *)\\ MathLong.Trans(a,b)\\ \vdots % \subsection[Allgemeine Hilfsfunktionen]{Allgemeine Hilfsfunktionen} Um den Zahlenbereich und die Anzahl der verwendeten Bits der LONG Zahlen abfragen zu k"onnen wurden mehrere Funktionen implementiert. \begin{enumerate} \item MaxLong: Diese Funktion gibt "ahnlich der MODULA2-Funktion MAX die gr"o\3te verf"ugbare LONG-Zahl zur"uck. Intern werden alle Komponenten der "ubergebenen Zahl mit -1 belegt. Dann wird das MSB gel"oscht um eine g"ultige LONG-Zahl zu erzeugen. Zuletzt wird noch die entsprechende L"ange in die nullte Komponente eingetragen. \item NStellen: Diese Routinen ermittelt die Anzahl der frei verf"ugbaren Dezimalstellen und gibt sie als Integerergebnis zur"uck. Die Berechnung ergibt sich durch folgende Gleichung: \begin{displaymath} \begin{array}{rrrl} &Stellen&=&log_{10}(2^{Verwendete\_Bits})\\ \Leftrightarrow &Stellen&=&{Verwendete\_Bits}*ln(2)/ln(10)\\ \end{array} \end{displaymath} \item AktStellen: Diese Funktion gibt die Anzahl der verwendeten Dezimalstellen der "ubergebenen Zahl zur"uck. \item NumBits: Das Ergebnis dieser Routine ist die Anzahl der verwendeten Bits. In der vorliegenden Implementierung ist dieses Ergebnis immer durch 15 teilbar, weil 15 Bits pro Integerkomponente verwendet werden. \end{enumerate} % \section[Spezialroutinen f"ur das RSA-Verfahren] {Spezialroutinen f"ur das RSA-Verfahren} % In diesem Abschnitt gehe ich auf die Teile der MathLong Bibliothek ein, die f"ur das RSA-Verfahren von Bedeutung sind. Da versucht wurde dieses Modul objektorientiert zu programmieren, mu\3ten alle Wandlungsfunktionen, die die Schl"usselverteilzentrale ben"otigt auch in MathLong implementiert werden. % \subsection[Fileoperationen]{Fileoperationen} Die wohl wichtigste Funktion f"ur das RSA-Verfahren ist die Verschl"usselungsfunktion f"ur Files.\\ Das im Labor vorhandene Netzwerk arbeitet nach dem Prinzip der verteilten Speichermedien, d.h. ein Rechner ''sieht`` das Netz als Festplatte oder Diskettenlaufwerk. Deshalb braucht keine Unterscheidung zwischen File- und Netzwerkzugriffen gemacht werden.\\ F"ur die Kodierung eines Files wurde eine Routine RSACode implementiert. Diese Routine erwartet die Deskriptoren eines ge"offneten Eingabe- und Ausgabefiles. Weiterhin mu\3 das "offentliche Schl"usselpaar "ubergeben werden. Als Besonderheit wird noch eine Prozedurvariable "ubergeben, die die Routine iden\-ti\-fi\-ziert, mit der eine ver"anderte Quellkodierung erzeugt werden kann. Im vorliegenden Projekt wird bei einem "ubergebenen Buchstaben nur abgefragt, ob das MSB gesetzt ist und dieses gegebenenfalls gel"oscht.\\ Das Gegenst"uck dieser Routine stellt RSADeCode dar. Der Aufruf dieser Routine ist mit RSACode vergleichbar. Der einzige Unterschied zeigt sich darin, da\3 man des geheime Schl"usselpaar "ubergeben mu\3. Auch eine Prozedurvariable zur Dekodierung der ge"anderten Quellkodierung ist vorhanden. Diese wird aber in der vorliegenden Implementierung nicht genutzt. % \subsection[Blockkodierungsroutinen]{Blockkodierungsroutinen} Die Schl"usselverteilzentrale mu\3 bei der Herstellung von digitalen Unterschriften manche Datenbl"ocke zweimal verschl"usseln. Da man dies nur schlecht mit den oben beschriebenen Fileoperationen erreichen kann, wurden spezielle Blockoperationen implementiert. Diese Funktionen k"onnen Bytebl"ocke Ver- und Entschl"usseln um so digitale Unterschriften zu erzeugen.\\ Zur Verarbeitung von Bytebl"ocken sind die zwei Prozeduren CodeByteBlock und DeCodeByteBlock vorgesehen. Dabei stellt DeCodeByteBlock das Gegenst"uck zu CodeByteBlock dar. Beiden Routinen ist entweder das "offentliche oder das geheime Schl"usselpaar zu "ubergeben. Als Besonderheit ist zu erw"ahnen, da\3 als Quelle bzw. Ziel ein Zeiger verwendet wird. Dies ist notwendig, weil durch die Verschl"usselung Bytebl"ocke l"anger werden k"onnen und MODULA2 keine dynamischen Felder kennt. Bei beiden Routinen wurde keine Prozedurvariable f"ur eine alternative Quellkodierung vorgesehen, weil diese Routinen ausschlie\3lich f"ur die internen Aufgaben der Schl"usselverteilzentrale vorgesehen sind. % \subsection[Blockwandlungsfunktionen]{Blockwandlungsfunktionen} Da auch Schl"ussel verschickt werden\footnote{z.B wenn ein Netzteilnehmer den "offenlichen Schl"ussel eines anderen Teilnehmers von der Schl"usselverteilzentrale erfragen will}, wurde ein Routinenpaar implementiert, da\3 eine Umwandlung von LONG-Zahlen in Bytebl"ocke und umgekehrt erm"oglicht. Diesen Routinen ist ein fest definiertes Bytefeld zu "ubergeben, indem eine Kopie der LONG-Zahl abgelegt wird.\\ Zus"atzlich wurden noch M"oglichkeiten vorgesehen, LONG-Zahlen in Files zu schreiben bzw. zu lesen. Diese M"oglichkeiten werden nicht ausgenutzt und wurden nur der Vollst"andigkeit halber implementiert. % \section[Das RSA-Kernmodul]{Das RSA-Kernmodul} Um eine einheitliche Oberfl"ache f"ur Anwendungsprogramme zu schaffen wurde ein separates Modul RSA geschaffen. In diesem Modul sind alle Routinen die das RSA-Verfahren ben"otigt zusammengefa\3t und in ihrer Bedienung m"oglichst vereinfacht. So finden sich in diesem Modul die schon oben beschriebenen Routinen sowie Funktionen zur Schl"usselgenerierung und zur Umwandlung von LONG-Zahlenpaaren in Bytebl"ocke definierter L"ange. Die letztgenannte Funktion wird wie schon erw"ahnt f"ur die Schl"usselverteilzentrale ben"otigt.\\ Zur Schl"usselgenerierung wird der Miller-Rabin-Test verwendet, der von Oliver Stock implementiert wurde. Desweiteren werden die Routinen aus dem Modul LongMathLib verwendet, die die Eulersche ${\cal \varphi}$-Funktion berechnen sowie den Berlekampalgorithmus durchf"uhren. % \section[Besonderheiten der Implementierung]{Besonderheiten der Implementierung} In diesem Abschnitt will ich auf die Besonderheiten eingehen, die sich durch die MODULA2-Implementierung ergeben.\\ Die wohl gr"o\3ten Schwierigkeiten ergaben sich durch die Zahlendarstellung. Da sowohl arithmetische Operationen wie $+$ und $*$ als auch logische wie AND, OR und NOT auf die einzelnen Komponenten angewendet werden wurden, mu\3te ein Weg gefunden werden, dies effizient zu l"osen.\\ Deshalb wurde ein Feld deklariert, das aus BITSET-Elementen besteht und durch Pointerhandling an der gleichen Address liegt wie das weiter oben beschriebene INTEGER-Array. Je nachdem welche Operationen durchgef"uhrt werden sollen, kann die eine oder die andere Darstellungsform gew"ahlt werden.\\ Obwohl dies nicht den Grundgedanken der strukturierten Programmierung entspricht, habe ich mich wegen des zu erzielenden Geschwindigkeitsvorteil f"ur diese L"osung entschieden. Dabei wurden alle M"oglichkeiten ausgesch"opft, Programmierungsfehler zu vermeiden, die MODULA2 zur Verf"ugung stellt, und die betroffenen Codeteile m"oglichst klein zu halten.\\ Ein weiterer Trick war das Abschalten der Compileroption, die die Bereichs"uberpr"ufung steuert. Dies war notwendig, weil bei komponentenweisen Addieren ein "Uberlauf einteten kann, der das Laufzeitsystem normalerweise zu einem Programmabbruch zwingt. Das Erkennen eines "Uberlaufs wird in dieser Implementierung durch das Abtesten des MSB\footnote{Wenn das MSB gesetzt ist dann ist die entsprechende Zahl negativ} erreicht.