Ein Mathematica-Notebook

Eine kurze Gebrauchsanweisung

In das folgende Mathematica-Notebook sind die ausführbaren Mathematica-Befehle fett und in Schreibmaschinenschrift geschrieben und zusätzlich eingerückt und gelb unterlegt. 
Man führt die Befehle aus, indem man mit dem Cursor in die entsprechende Zeile geht (bzw. in eine von den Zeilen, wenn es mehrere sind) und gleichzeitig Shift und Return drückt. 
Durch das gleichzeitige Drücken dieser beiden Tasten, teilt man dem System mit, dass man die Zeile ausführen möchte. Drückt man die Taste Shift allein, erzeugt man eine Mathematica-Eingabe, der aus zwei Zeilen besteht. Der Zeilenumbruch wird dabei wie ein Leerzeichen behandelt. Dies kann sinnvoll sein, um die Eingabe zwecks besserer Lesbarkeit zu strukturieren. 
Die nicht eingrückten Text sind nur Kommentare und können nicht ausgeführt werden.

RSA mit Mathematica

Die Erzeugung geeigneter Primzahlen

Zunächst wählen wir eine kleine Zahl e. Üblicherweise wird e als Primzahl gewählt (e = 3,5,7). Dies ist aber nicht unbedingt notwendig.

Dann brauchen wir zwei Primzahlen p, q, welche die Eigenschaft haben, dass φ(pq) = (p-1)(q-1) mit e teilerfremd ist. Dies ist sicher genau dann der Fall, wenn (p-1) und (q-1) mit e teilerfremd sind.

Der folgende Befehl überprueft, ob eine Zahl eine Primzahl ist:

PrimeQ[7]

PrimeQ[8]

Im Folgenden definieren wir einen Befehl, welcher zu einer gegeben Zahl n, die kleinste Primzahl bestimmt, die kleiner oder gleich n ist:

NextPrime[n_] := n /; PrimeQ[n];
NextPrime[n_] := NextPrime[n + 1];

Diese rekursive Definiton von Befehlen ist typisch für das Computeralgebra-System Mathematica.

Ein Beispiel:

{ NextPrime[ 9 ],  NextPrime[15],  
      NextPrime[345324523752] }

Der folgende Befehl  verwendet den Befehl NextPrime, um zu zwei gegebenen Zahlen  e  und  n  diejenige kleinste Zahl   p  zu finden, die die folgenden drei Bedingungen erfüllt:

(i)   p  ≥  n,      (ii)   p  ist Primzahl,       (iii)   p -1  und  e  sind teilerfremd.

GoodPrime[e_, n_] := 
        n /; ((GCD[n - 1, e] === 1) && 
              PrimeQ[n]);
GoodPrime[e_, n_] := GoodPrime[e, NextPrime[n + 1]];

Zwei Beispiele:

Verschlüsseln mit RSA

GoodPrime[3,  6]

p  = 
      GoodPrime[5,  374563465789687324659636789672578639563645]

Wir überprüfen:

PrimeQ[p]

GCD[p - 1,  5]

GCD steht für Greatest Common Divisor und ist ein eingebauter Mathematica-Befehl.

Haben wir drei Zahlen  e,  p,  q  mit den oben genannten Eigenschaften gefunden, so bilden  e  und  n  :=  p q  den öffentlichen Schlüssel. Für RSA ist dabei wichtig, dass nur  n  bekannt gegeben wird, nicht aber  p  und  q.
Fuer sehr große Primzahlen  p  und  q  dauert das Faktorisieren von  p q  (auch mit schnellen Rechnern und sehr guten Algorithmen) sehr lange.
Versuchen Sie es einmal:

p  =  GoodPrime[3,  12^100]

q  =  GoodPrime[3,  13^100]

Wir laden ein Mathematica-Paket ein, welches den schnellsten verfügbaren Faktorisierungsbefehl (in Mathematica) enthält:

<< NumberTheory`

Wir bilden das Produkt der Primzahlen.

n  =  p q

Jetzt versuchen wir diese Zahl wieder zu faktorisieren. Man sollte sich aber vorher informieren, wie man einen laufenden Prozess wieder abbricht. (Etwa, indem man die Zelle des Befehls - die blaue Klammer rechts - mit der blauen Maustaste anklickt, d.h. markiert, und dann unter Kernel in der Menueleiste auf Abort Evaluation geht.)

FactorIntegerECM[n]

Keine Chance! Dabei ist der Befehl FactorIntegerECM schon das schnellste, was Mathematica an der Faktorisierungsfront zu bieten hat (andere Programme sind jedoch schneller - und wir verwenden hier noch keine Parallelisierung).

Mit dem öffentlichen Schlüssel  {e, n }  sind wir bereits in der Lage, eine Botschaft zu verschlüsseln. Eine Botschaft ist eine Zahl m, die   m  < n  aber   m^e >n  erfüllen sollte.
Etwa:

m  = 
      n  -  34562567834785656378566754678687345687687326456834658

Diese Zahl wird verschlüsselt, indem man sie mit  e  potenziert und dann modulo n  reduziert. Da das Reduzieren modulo  n  nicht nach dem potenzieren erfolgen sollte, sondern während des Potenzierens, gibt es hierfür einen speziellen Mathematica-Befehl:

w  =  PowerMod[m, e, n]

w  enhält jetzt die verschlüsselte Botschaft.

Erzeugung des privaten Schlüssels und Entschlüsseln der Botschaft

Nun erzeugen wir den privaten Schluessen, denn wir wollen die Botschaft auch wieder entschlüsseln.
Dazu suchen wir zunaechst eine modulare Inverse von  e  modulo  φ(n)  =  (p-1)(q-1).  Hierzu verwenden wir den erweiterten euklidischen Algorithmus: Haben zwei Zahlen  a  und  b  den größten gemeinsamen Teiler  g,  so gibt es zwei Zahlen  x  und  y  mit

g = a x  + b y.

Der erweiterte euklidische Algorithmus liefert diese beiden Zahlen:

{a, b}  =  { 119,  147 }

{g,  {x,  y}} = ExtendedGCD[a, b]

g = 7  ist hier der größte gemeinsame Teile,  x  = 5  und  y  =  -4  erfüllen:

g  ===  x*a  +  y*b

(Der sonderbare Operator === sigmalisiert Mathematica, dass er eine Gleichung auf ihren Wahrheitsgehalt untersuchen soll.) True bedeutet, dass die Aussage wahr ist.)

Sind  a  und  b  teilerfremd, so gilt:

a x  + b  y  = 1

Dies bedeutet, dass 
1.)    x  eine modulare Inverse von  a  modulo  b   (  a x = 1  (mod  b) )  und
2.)    y  eine modulare Inverse von  b  modulo  a   ist ( b y = 1 (mod  a) ).

{a, b}  =  {187,  147}

{g,  {x,  y}}  =  ExtendedGCD[a, b]

Mod[ a x,  b]

Mod[b y,  a]

x = -11  ist Inverse von  a  modulo  b.  Wegen  -11 = 136 (mod  b) . Ist auch  x = 136  eine solche modulare Inverse:

x := 136

Mod[a x,  b]

Wir erzeugen jetzt den privaten Schlüssel  d:

Der private Schlüssel ist eine modulare Inverse von  e  modulo  φ(n) = (p-1)(q-1).  Er ergibt sich somit (wie oben gesehen) durch:

{eins,  {d1,  muell}}  =  
      ExtendedGCD[3,  (p - 1) (q - 1)]

d1  ist der Kandidat für unseren privaten Schlüssel. Wir könnten ihn tatsächlich dafür nehmen. Aus ästhetischen Gründen bevorzugen wir eine positive Zahl  d,  welche wir wie oben berechnen.

d  =  Mod[d1,  (p - 1) (q - 1)]

Nun können wir endlich unser Chiffrat  w  von oben wieder dechiffrieren. Dabei gehen wir wie beim verschlüsseln vor. Wir ersetzen lediglich den Bestandteil  e  des öffentlichen Schluessels durch den privaten Schluessel  d.

m2  =  PowerMod[w, d, n]

Wir machen die Probe:

m2  ===  m

Wir erhalten die ursprüngliche Zahl tatsächlich zurück.

Der folgende Befehl übernimmt die Erzeugung der Schlüssel:

MakeKey[e_, p_, q_] := {
e, 
          p*q, 
Mod[ExtendedGCD[
                e, (p - 1) (q - 1)][[2, 
                1]], (p - 1) (q - 
                  1)]
};

Aus den Zahlen  e,  p,  q  erzeugt MakeKey eine Liste bestehend aus den beiden Bestandteilen des öffentlichen Schlüssels und dem privaten Schlüssel.

{e,  n,  d}  =  MakeKey[3,  p,  q]

Die oben verwendeten Befehle in einem Mathematica-Paket

Die oben genannten Befehle   NextPrime, GoodPrime  und    MakeKey  sind in dem Mathematica-Paket rsa.m   zusammengefasst, welches mit

<< rsa.m

eingelesen wird. Dazu machen sie am besten ein neues Arbeitsfenster auf. Dies geschieht, indem sie im Menuepunkt "File" auf "new" klicken. Dann stehen Ihnen die drei oben genannten Befehle zur Verfügung.

Dieses Mathematica-Paket finden sie unter
http://www.mathematik.uni-kassel.de/~project/lehrerfortbildung/material/rsa.m