In das folgende Mathematica-Notebook sind die ausfuehrbaren Mathematica-Befehle fett und in Schreibmaschinenschrift geschrieben. Man fuehrt sie aus, indem man in die entsprechende Zeile geht (in eine von den Zeilen, wenn es mehrere sind) und gleichzeitig Shift und Return drueckt. Durch das gleichzeitige druecken, teilt man dem System mit, dass man die Zeile ausfuehren moechte. Drueckt man nur Shift, erzeugt man einen Mathematica-Befehl, der aus zwei Zeilen besteht. Dies kann sinnvoll sein, um die Eingabe zwecks besserer Lesbarkeit zu strukturieren.

RSA mit Mathematica

Zunaechst waehlen wir eine kleine Zahl e. Ueblicher Weise wird e als Primzahl gewaehlt
(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 sind. Dies ist sicher genau dann der Fall, wenn (p-1) und (q-1) mit e teilerfremd ist.

Der folgende Befehl ueberprueft, 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 fuer das Computeralgebra-System Mathematica.

Ein Beispiel:

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 erfuellt:

(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[3, NextPrime[n + 1]];

Zwei Beispiele:

GoodPrime[3,  6]

p  = 
      GoodPrime[5,  374563465789687324659636789672578639563645]

Wir ueberpruefen:

PrimeQ[p]

GCD[p - 1,  5]

GCD steht fuer 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=pq den oeffentlichen Schluessel. Dabei ist wichtig, dass nur n bekannt gegeben wird,
nicht aber p und q.
Fuer sehr grosse Primzahlen p und q dauert das Faktorisieren von pq (auch mit schnellen Rechnern und sehr guten Algorithmen) sehr lange.
Versuchen Sie einmal:

p  =  GoodPrime[3,  12^100]

q  =  GoodPrime[3,  13^100]

<< NumberTheory`

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). Der Befehl ist im Paket NumberTheory implementiert, welches mit <<NumberTheory' geladen wird.

Mit dem oeffentlichen Schluessel {e, n} sind wir bereits in der Lage, eine Botschaft zu verschluesseln. Eine Botschaft ist eine Zahl m, die  m <n aber  m^e >n erfuellen sollte.
Etwa:

m  =  
      n  -  34562567834785656378566754678687345687687326456834658

Diese Zahl wird verschluesselt, indem man sie mit e potenziert und dann modulo n reduziert. Da das Reduzieren modulo n nicht nach dem potenzieren erfolgen sollte, sondern waehrend des Potenzierens, gibt es hierfuer einen speziellen Befehl:

w  =  PowerMod[m, e, n]

w enhaelt jetzt die verschluesselte Botschaft.

Nun erzeugen wir den privaten Schluessen, denn wir wollen die Botschaft auch wieder entschluesseln.
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 groessten 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 groesste gemeinsame Teile, x =5 und y = -4 erfuellen:

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)
2.) y eine modulare Inverse von b modulo a ist ( b y = (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=136eine solche modulare Inverse:

x := 136

Mod[a x,  b]

Wir erzeugen jetzt den privaten Schluessel d:

Der private Schluesse 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 fuer unseren privaten Schluessel. Wir koennten ihn tatsaechlich dafuer nehmen. Aus aesthetischen Gruenden bevorzugen wir eine positive Zahl d, welche wir wie oben berechnen.

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

Nun koennen wir endlich unser Chiffrat w von oben wieder dechiffrieren. Dabei gehen wir wie beim verschluesseln vor. Wir ersetzen lediglich den Bestandteil e des oeffentlichen Schluessels durch den privaten Schluessel d.

m2  =  PowerMod[w, d, n]

Wir machen die Probe:

m2  ===  m

Wir erhalten die urspruengliche Zahl tatsaechlich zurueck.

Der folgende Befehl ueber nimmt die Erzeugung der Schluessel:

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 oeffentlichen Schluessels und dem privaten Schluessel.

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