Joachim Mohr   Mathematik Musik Delphi
≡
Verschlüsselungsalgorithmen

Ein Beispiel zur RSA-Verschlüsselung

y = xe mod n

Gerechnet mit dem Programm RSA

Vorbereitung:
Wähle zwei Primzahlen zum Beispiel p=491 und q=223.

Nun beginnt Deiner Rechnung:
n=p*q=109493 und n0=(p-1)·(q-1)=108780.

Suche nun eine Zahl e mit ggT(e,n0)=1. Davon gibt es genügend. Zum Beispiel e=19

Dein Partner soll dir mit den Zahlen n=109493 und e=19 einen streng geheimen Tipp mitteilen:

Die Rechnung Deines Partners ist dann:

Folgender Text wird verschlüsselt
Heißer Tipp: Morgen gewinnt der HSV
1. Schritt: Den Buchstaben wird der ASCII-Code zugeordnet:
H=72 e=101 i=105 ß=223 e=101 r=114 =32 T=84 i=105 p=112 p=112 :=58 =32 M=77 o=111 r=114 g=103 e=101 n=110 =32 g=103 e=101 w=119 i=105 n=110 n=110 t=116 =32 d=100 e=101 r=114 =32 H=72 S=83 V=86 =32

2. Schritt: Zweierblöcke werden zusammen gefasst:
72+256*101=25928; 105+256*223=57193; 101+256*114=29285; 32+256*84=21536; 105+256*112=28777; 112+256*58=14960; 32+256*77=19744; 111+256*114=29295; 103+256*101=25959; 110+256*32=8302; 103+256*101=25959; 119+256*105=26999; 110+256*110=28270; 116+256*32=8308; 100+256*101=25956; 114+256*32=8306; 72+256*83=21320; 86+256*32=8278;

Nun wird auf die folgenden Zahlen x die Verschlüsselung y = x^e mod n angewendet ("^"="hoch"):
25928 57193 29285 21536 28777 14960 19744 29295 25959 8302 25959 26999 28270 8308 25956 8306 21320 8278

3. Schritt
y=xe mod n
e=19 und n=109493

(Die Verschlüsselung): Rechnung y := x^e (mod n) mit e=19:
25928^19=22496; 57193^19=88882; 29285^19=2065; 21536^19=29333; 28777^19=104161; 14960^19=31130; 19744^19=52000; 29295^19=35075; 25959^19=59509; 8302^19=42638; 25959^19=59509; 26999^19=54862; 28270^19=57266; 8308^19=18807; 25956^19=104903; 8306^19=30570; 21320^19=35810; 8278^19=72907; (alles Modulo n gerechnet)

Wir haben nun den verschlüsselten Text als Zahlenkolonne der y-Werte:
22496 88882 2065 29333 104161 31130 52000 35075 59509 42638 59509 54862 57266 18807 104903 30570 35810 72907
Wenn es ein längerer Text wäre, könnte man diese Zahlenkolonne noch leicht zu einem Binären File komprimieren, um Übertragungszeit zu sparen.
Nebenrechnung:
Die eigentliche Rechnung sind die hohen Potenzen.
Diese können folgendermaßen rekursiv berechnet werden: 
     / 1, falls e=0
     |
     |
 e   |    e-1
x  = | x·x   , falls e ungerade
     |
     |      e
     |      -
     |   2  2
     \ (x )    "Wiederholtes Quadrieren"

                      19
In unserem Fall wird x  für x=  25928 (die erste Potenz im 3.Schritt)

rekursiv mit nur 6 Multiplikationen folgendermaßen berechnet:

 19      18      9        8        4        2
x   = x·x  = x·x   =x·x ·x = x·x ·x = x·x ·x = x·x ·x
                1      1  1     1  2     1  3     1  4
                                                                       n
                  2       2   4        2   8       2   4             (2 )
Bezeichnung: x = x ; x = x = x ; x = x  = x ; x = x = x ; ... ; x = x    .
              1       2   1       3   2        4   3             n

Wie dies mit dem Zweiersystem zusammenhängt, sieht man an der Zerlegung:

                  4     19   1  2  16
19 = 1 + 1·2 + 1·2  => x  = x ·x ·x
Rechnung (da wir modulo n=109493 rechnen, werden vom Ergebnis Vielfache von n so lange abgezogen, bis das Ergebnis kleiner als n ist. Man kann also alles sogar mit einem Taschenrechner rechnen. 
x=25928

    2
x1=x =x*x=672261184

                                            2
x1/n = 6139 Rest 83657, wir dürfen also x1=x = 83657 setzen.

      4   2
x2 = x =x1 =6998493=63917·n + 29568 = 29568 (mod n)

     8    2
x3 =x = x2 =874266624=7984·n + 74512 = 74512 (mod n)

      16    2
x4 =x  = x3 =5552038144=50706·n+86086 = 86086 (mod n)


x·x1 =2169058696 = 19810·n + 2366 = 2366 (mod n)


x·x1·x4 = 203679476 = 1860·n + 22496 = 22496 (mod n)


   19      9         4         2
=>x  = x·x1 = x·x1·x2 = x·x1·x3  =x·x1·x4 = 22496 (mod n)


(Dies ist das erste Ergebnis beim 3. Schritt)


Dir ist also eine Zahlenkolonne mitgeteilt worden, aus der du wieder den Klartext finden musst.
Zahlenkolonne der y-Werte:
22496 88882 2065 29333 104161 31130 52000 35075 59509 42638 59509 54862 57266 18807 104903 30570 35810 72907
Dies gelingt dir - und nur dir, falls die Primzahlen groß genug sind - durch Kenntnis der Zahl d, die du berechnen kannst.

Um d berechnen zu können, benötigt man die Zerlegung der Zahl n=109493 in ihre Primfaktoren:
n=p·q mit p=491 und q=223

Aus den Primfaktoren kann mit einem mathematischen Verfahren (Erweiteter euklidischer Algorithmus) d leicht berechnet werden. Das Produkt mit e*d muss ein Vielfaches von n0=(p-1)·(q-1)=108780 um eins übertreffen.

Genauer: Bestimme d so, dass e*d=19*d=x*108 780+1=1 mod 108 780 für ein passendes x ist.

Du kennst p und q und damit auch n0=(p-1)·(q-1)=108780. (Diese Zahl kennt der Angreifer nicht.)

Das Problem für einen Angreifer ist: Wenn er n und den verschlüsselten Text kennt, kennt er immer noch nicht die beiden Primfaktoren von n. Bei großen Primfaktoren würde der schnellste Computer Milliarden von Jahren benötigen, um diese zu finden. (Stand: 2003)
Ein mathematischer Satz besagt: Wenn e·d = 1 mod n0, dann ist yd = (xe)d = xe·d = x mod n für alle x.
Wir müssen also ein passende d suchen.
Der erweiterte Euklidische Algorithmus liefert d=85 879.
Ist jetzt wirklich e*d=1 mod n0?
Ist wirklich 19*19*85879 = 1 mod 108 780?

Wir rechnen:
e*d = 19*85879 = 1631701 und
1631701=1 mod 108 780, denn ziehen wir von 1631701 mehrmals, genau 15 mal 108 780 ab, so ist das Ergebnis 1.

Der Beweis findet sich zum Beispiel in Johannes Buchmann: "Einführung in die Kryptologie". Springer-Lehrbuch 1999. Im wesentlichen beruht er auf dem kleinen Fermatschen Satz, der sich in Lehrbüchern über Restklassengruppen befindet.

Damit hat man die "Umkehrfunktion", um den Text zu entschlüsseln. Die Aufgabe von Kryptologen ist - wie man hier sieht - Funktionen zu finden, deren Umkehrfunktion ein Angreifer zu Lebzeiten nicht finden kann.

Ein Angreifer kann dann trotz Kenntnis der Verschlüsselung ("öffentlicher Schlüssel") und des verschlüsselten Textes, den Text nicht entschlüsseln, da er nicht in der Lage ist, die Umkehrfunktion (den "privaten Schlüssel") zu finden.

x=yd mod n
d=85879 und n=109493


Rechnung: (3. Schritt rückgängig)
22496^85879=25928; 88882^85879=57193; 2065^85879=29285; 29333^85879=21536; 104161^85879=28777; 31130^85879=14960; 52000^85879=19744; 35075^85879=29295; 59509^85879=25959; 42638^85879=8302; 59509^85879=25959; 54862^85879=26999; 57266^85879=28270; 18807^85879=8308; 104903^85879=25956; 30570^85879=8306; 35810^85879=21320; 72907^85879=8278; (Alles Modulo n gerechnet)

Wir erhalten also die folgende Zahlenkolonne:
25928 57193 29285 21536 28777 14960 19744 29295 25959 8302 25959 26999 28270 8308 25956 8306 21320 8278

Diese steht für Zahlenzweierblöcke, die sich folgendermaßen berechnen lassen:(2. Schritt rückgängig):
25928/256=101 Rest 72
57193/256=223 Rest 105
...
Anders ausgedrückt gilt:
25928=72+256*101; 57193=105+256*223; 29285=101+256*114; 21536=32+256*84; 28777=105+256*112; 14960=112+256*58; 19744=32+256*77; 29295=111+256*114; 25959=103+256*101; 8302=110+256*32; 25959=103+256*101; 26999=119+256*105; 28270=110+256*110; 8308=116+256*32; 25956=100+256*101; 8306=114+256*32; 21320=72+256*83; 8278=86+256*32;

Nun müssen wir noch den erhaltenen (ASCII-)Zahlen ihren Buchstaben zuordnen (1. Schritt rückgängig):
72=H; 101=e; 105=i; 223=ß; 101=e; 114=r; 32= ; 84=T; 105=i; 112=p; 112=p; 58=:; 32= ; 77=M; 111=o; 114=r; 103=g; 101=e; 110=n; 32= ; 103=g; 101=e; 119=w; 105=i; 110=n; 110=n; 116=t; 32= ; 100=d; 101=e; 114=r; 32= ; 72=H; 83=S; 86=V; 32= ;

Damit ist - vorausgesetzt d war richtig - der Text entschlüsselt:
Heißer Tipp: Morgen gewinnt der HSV
Nebenrechnung: Selbst eine Potenz wie x 85879 läßt sich mit "nur" 27 Multiplikationen durchführen: 

 85879      42939        21469           10734           5367
x     = x·x1     =x·x1*x2     =x·x1·x2·x3     =x·x1·x2·x4      |x1=x*x, x2=x1*x1.
                                                               |
                     2683                  1341                |x3*x2*x2 u.s.w.
      = x·x1·x2·x4·x5    = x·x1·x2·x4·x5*x6                    |
                                                               |"Wiederholtes Quadrieren"
                           670                    335
      = x·x1·x2·x4·x5*x6*x7   =x·x1·x2·x4·x5·x6*x8

                              167                            83
      = x·x1·x2·x4·x5·x6*x8*x9   = x·x1·x2·x4·x5·x6*x8*x9*x10

                                      41
      = x·x1·x2·x4·x5·x6·x8·x9·x10·x11

                                          20
      = x·x1·x2·x4·x5·x6·x8·x9·x10·x11·x12

                                          10
      = x·x1·x2·x4·x5·x6·x8·x9·x10·x11·x13

                                          5
      = x·x1·x2·x4·x5·x6·x8·x9·x10·x11·x14

                                              2
      = x·x1·x2·x4·x5·x6·x8·x9·x10·x11·x14·x15


     = x·x1·x2·x4·x5·x6·x8·x9·x10·x11·x14·x16


Dass dies mit dem Zweiersystem zusammenhängt, sieht man an der Zerlegung:

               2   4   5   6   8   9   10   11   14   16
85879=1 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2  + 2  + 2  + 2


Man benötigt als hier weniger als [2·lb(85879)] = 32 Multiplikationen.

                             d
Allgmenein benötigt man für x   weniger als [2·lb(d)] Multiplikationen, wobei

        log(d)
lb(d) = —————— der Zweierlogarithmus
        log(2)

und [y] = "größte ganze Zahl kleiner gleich y" ist.



Man sagt: Die Anzahl der Multiplikationen für die d-te Potenz ist von der Ordnung lb(d).
Mit TTMathe (oder auch dem Taschenrechner) vorgerechnet: 
         Rechenblatt mod n=109493
x=22496                         22 496
x1=x·x                          102 863
x2=x1·x1                        50 207
x3=x2·x2                        104 496
x4=x3·x3                        5605
x5=x4·x4                        101 027
x6=x5·x5                        64 734
x7=x6·x6                        84 153
x8=x7·x7                        48 648
x9=x8·x8                        46 202
x10=x9*x9                       58 769
x11=x10*x10                     57 662
x12=x11*x11                     41 806
x13=x12*x12                     14 370
x14=x13*x13                     102 595
x15=x14*x14                     62 442
x16=x15*x15                     67 127
y=x*x1                          90 479
y=y*x2                          33 569
y=y*x4                          45 271
y=y*x5                          70 707
y=y*x6                          11 059
y=y*x8                          59 123
y=y*x9                          78 975
y=y*x10                         92 491
y=y*x11                         30 998
y=y*x14                         15 625
y=y*y16                         25 928