Geheimschriften und Computeralgebra:
Das RSA-Verfahren

Caesars Geheimschrift

nachricht = "DIES IST MEINE NACHRICHT"

ToCharacterCode["A"]

\(\(\(CaesarE[nachricht_, e_] := 
      Module[{liste, L}, 
		liste = 
          ToCharacterCode[nachricht]; 
		liste = 
          liste /. {32 -> L}; 
		liste = liste - 65; 
		liste = 
          liste + e; 
		liste = Mod[liste, 26]; 
		liste = 
          liste /. {Mod[x_, y_] -> L}; 
		liste = 
          liste + 65; 
		liste = 
          liste /. {L + 65 -> 32}; 
\ \ \ \ \ FromCharacterCode[
          liste]
	]\)\(
\)
    \)\)
CaesarE[nachricht_] := 
      CaesarE[nachricht, 3]

    
\(\(\(CaesarD[nachricht_, e_] := CaesarE[nachricht, \(-e\)]\)\(
\)
    \)\)
CaesarD[nachricht_] := CaesarD[nachricht, 3]

resultat = CaesarE[nachricht]

CaesarE["ABCDEFGHIJKLMNOPQRSTUVWXYZ"]

CaesarE["ABCDEFGHIJKLMNOPQRSTUVWXYZ", 14]

CaesarD[resultat]

CaesarE["CAESAR IST DOOF"]

CaesarD[CaesarE["CAESAR IST DOOF"]]

Text zum Entziffern

test = "QXIIT TCIOXUUTGC"

Entschlüsselung

Do[Print[CaesarD[test, n]], {n, 1, 26}]

CaesarD[test, 15]

Schnelles Potenzieren

powermod[a_, 0, p_] := 1

    
powermod[a_, n_, p_] := 
      Mod[powermod[a, (n/2), p]^2, p] /; EvenQ[n]

    
powermod[a_, n_, p_] := 
      Mod[powermod[a, n - 1, p]*a, p] /; OddQ[n]

    
$RecursionLimit = ∞;

powermod[6283678638721638126538126378162312, 
      34236472364862378462384632784628, 1253762153761536721573]

PowerMod[6283678638721638126538126378162312, 
      34236472364862378462384632784628, 1253762153761536721573]

a = Random[Integer, {(10^999), (10^1000)}]

n = Random[Integer, {(10^999), (10^1000)}]

p = Random[Integer, {(10^999), (10^1000)}]

Timing[powermod[a, n, p]]

Timing[PowerMod[a, n, p]]

Modulares Inverses

e = 1234567

p = 7654321

d = PowerMod[e, -1, p]

e*d

Mod[e*d, p]

e = Random[Integer, {(10^999), (10^1000)}]

p = Random[Integer, {(10^999), (10^1000)}]

d = PowerMod[e, -1, p]

Mod[e*d, p]

ASCII-Liste

Partition[Table[FromCharacterCode[n], {n, 0, 127}], 16]

Partition[Table[FromCharacterCode[n], {n, 0, 129}], 10]

Hilfsfunktionen

ToCharacterCode["TEXT"]

\(\(\(Combine[liste_] := First[liste]\  /; \ Length[liste] == 1\)\(
\)
    \)\)
Combine[liste_] := 
      1000*Combine[Reverse[Rest[Reverse[liste]]]] + 
        Last[liste]

    
Convert[string_] :=   Combine[ToCharacterCode[string]]

zahl = Convert["TEXT"]

\(\(\(makelist[zahl_] := {zahl}\  /; \ zahl < 1000\)\(
\)
    \)\)
\(\(\(makelist[zahl_] := 
      Append[makelist[\((zahl - Mod[zahl, 1000])\)/1000], 
        Mod[zahl, 1000]
		]\)\(
\)
    \)\)
ConvertBack[zahl_] := FromCharacterCode[makelist[zahl]]

ConvertBack[zahl]

Erzeugung von Primzahlen

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

n = Random[Integer, {(10^499), (10^500)}]

Timing[NextPrime[n]]

Das  RSA-Verfahren

VerschlüsseleRSA[nachricht_] := 
      PowerMod[Convert[nachricht], e, m]

    
EntschlüsseleRSA[zahl_] := 
      ConvertBack[PowerMod[zahl, d, m]]

InitialisiereRSA := 
      Module[{}, 
p = 
          NextPrime[
            Random[Integer, {(10^199), (10^200)}]]; 
q = 
          NextPrime[
            Random[Integer, {(10^199), (10^200)}]]; 
m = 
          p*q; 
φ = (p - 1)*(q - 
                1); 
e = φ; 
While[
          Not[GCD[φ, e] === 1], 
e = 
            NextPrime[
              Random[Integer, {(10^39), (10^40)}]]]; 
d = 
          PowerMod[e, -1, φ];
]

Erzeugung der Schlüssel

InitialisiereRSA

öffentlicher Schlüssel

{e, m}

privater Schlüssel

d

Verschlüsselung nach RSA

nachricht = "Dies ist meine Nachricht"

resultat = VerschlüsseleRSA[nachricht]

EntschlüsseleRSA[resultat]

EntschlüsseleRSA[resultat + 1]

Ein paar andere Nachrichten:

resultat = 
      VerschlüsseleRSA["Wie ist es mit dieser Meldung?"]

EntschlüsseleRSA[resultat]

resultat = 
      VerschlüsseleRSA["Keiner hat ne Idee!"]

EntschlüsseleRSA[resultat]

Schließlich eine wirklich geheime Nachricht:

<< "Eigene \
Dateien/Koepf/Vorträge/Schülervortrag2004-RSA/\
nachricht"

resultat = VerschlüsseleRSA[nachricht]

EntschlüsseleRSA[resultat]