Joachim Mohr   Mathematik Musik

Verschlüsselungen

Bei vielen Beispielen hier wird wegen der besseren Demonstrierfähigkeit ASCII-Code zu ASCII-Code (und nicht zu Binärcode) verschlüsselt. (Genauer: der ASCII-Bereich 0 bis 31 bleibt unverschlüsselt.) Daher ist die Basis nicht 256 sondern 256 - 32 = 224.

I Cäsarverschlüsselung

Downloadseite
Bei dieser Verschlüsselung wird einfach der Buchstabe im Alphabet um n Stellen verschoben.
Im Programm wird dies folgendermaßen bewerkstelligt:
Einem Buchstaben c wird zunächst eine Zahl i:=char(c)-32 zugeordnet. D.h. dem ASCII-Vorrat #0 bis #255 ohne Steuerzeichen #0 bis #31 entspricht eine Zahl von 0 bis 223 (Das entspricht 224 Zeichen).

Die Abbildung Zeichen ——> {0,..,223} ist bijektiv (umkehrbar)
                 c    ——> i:=char(c)-32
Die Cäsarverschlüsselung ist dann nicht anderes als i+n mod 224.

Bsp.: n=10 
0——>10
1——>11
...
213——>223
214——>0 (da 224=0 mod 224)
215——>1 (da 225=1 mod 224)
216——>2 (da 226=2 mod 224)
223——>9 (da 233=9 mod 224)

Ein verschlüsselter Text sieht zunächst unleserlich aus, kann aber mit der Kenntnis eines Zeichens und seiner Verschlüsselung gebrochen werden.

Die wissenschaftliche Kryptoanalyse geht davon aus, dass der Angreifer das Verschlüsselungsverfahren kennt. Nur der verwendete Schlüssel und die verschlüsselten Klartexte werden als geheim angenommen.

Mit jeder anderen bijektiven Abbildung von {0,..223} auf {0,..,223} lässt sich eine Verschlüsselung durchführen. Die Entschlüsselung ist mit Hilfe der Umkehrfunktion möglich.

Ein Angreifer hat aber auch hier leichtes Spiel. Mit einer Ciphertext-Only-Attacke(Der Angreifer kennt nur den verschlüsselten Text) kann er den Text folgendermaßen entschlüsseln:Bei einem etwa deutschsprachigen Text wird er am häufigsten Buchstaben beim verschlüsselten Text das "e" erkennen und mit weiteren statistischen Eigenschaften auch den Rest.

II Verschlüsselung mit Passwort: XOR- und Verwirbelungsverschlüsselung

Verschiebeverschlüsselung

Die Verschiebeverschlüsselung wird auch Vigenèrechiffre genannt. (Blaise Vigenère lebte im 16. Jahrhundert.)

Downloadseite

Ein nach dem Cäsarcode verschlüsselter Text ist einfach zu knacken. ("Analysire den Text nach der Häufigkeit der Buchstaben!"). Bei der (Ring-)Verschlüsselung mit Passwort ist das schon schwieriger.

Mit Hilfe eines Passwortes, wird der erste Buchstabe des zu verschlüsselnden Textes um so viel Stellen verschoben, wie der erste Buchstabe des Passwortes angibt (bei "A" z.B. um 65, bei "B" um 66 u. s. w), der zweite Buchstabe des zu verschlüsselnden Textes um so viel Stellen, wie der zweite Buchstabe des Passwortes angibt u.s.w. Ist das Passwort erschöpft, fängt man wieder mit dem ersten Buchstaben an.

Eine kurze Bemerkung zur Kryptoanalyse des Vigenèrechiffre:
Um das Passwort herauszufinden, muß man als erstes seine Länge bestimmen. Ist dies gelungen, lassen sich Buchstaben, die die gleiche Verschiebung erfahren haben, zusammenfassen, und auf die einfache Cäsarverschlüsselung zurückführen.

Das Programm ist im Vergleich zur Cäsarverschlüsselung nur leicht abzuändern. Die Prozeduren sind folgende:


{Verschiebt Buchstabe für Buchstabe positiv}
function VerschiebeVerschlpos(const s: String):String;
  //Damit ein Textfile wieder ein Textfile wird, werden
  //Steuerzeichen wie #13#10 nicht verschlüsselt, sondern bleiben erhalten.
  const Passwort ='245abx988GHIVZ'; //oder Benutzer gibt es ein
        B{Basis = Zahl der Buchstaben ohne Steuerzeichen} = 224;
  var i,q,nr :integer;
begin
  result := s;
  q:=1;
  for i:=1 to Length(result) do  Begin
    if result[i] >= ' ' then BEgin
      nr := (Ord(result[i]) - 32) + (Ord(Passwort[q]) - 32);
      if nr > B then nr := nr - B;
      result[i]:=Chr(nr+32);
    ENd;
    inc(q);
   if q > length(Passwort) then q:=1;
  end;
end;
{Verschiebt Buchstabe für Buchstabe negativ}
function VerschiebeVerschlneg(const s: String):String;
  {Damit ein Textfile wieder ein Textfile wird, werden
   Steuerzeichen wie #13#10 nicht verschlüsselt, sondern bleiben erhalten.}
  const Passwort ='245abx988GHIVZ'; //oder Benutzer gibt es ein
        B{Basis} = 224;
  var i,q,nr :integer;
begin
  result := s;
  q:=1;
  for i:=1 to Length(result) do  Begin
    if result[i] >= ' ' then BEgin
      nr := (Ord(result[i]) - 32) - (Ord(Passwort[q]) - 32);
      if nr < 0 then nr := nr + B;
      result[i]:=Chr(nr+32);
    ENd;
    inc(q);
   if q > length(Passwort) then q:=1; //"Ring"verschlüsselung
  end;
end;

Diese Verschlüsselung ist nur in Kombination mit einem einfachen "Wirbel" (siehe unten) brauchbar.

XOR-Verschlüsselung

Eine gern verwendete, jedoch nicht sehr sichere, Verschlüsselung ist die XOR-Verschlüsselung.

Jeder Buchstabe hat seinen ASCII-Code (eine Zahl zwischen 32 und 256. Die Zahlen zwischen 0 und 31 sind Steuerzeichen wie zum Beispiel "Neue Zeile"). In der Dualdarstellung entspricht das 8 Bit (Ein Bit ist 0 oder 1). Mit einem Buchstaben des Passwort wird dieser ASCII-Code nun mit XOR ("exclusives OR", lateinisch "aut" im Gegensatz zu "vel") verknüpft.

XOR bedeutet: Entweder - oder. Auf Bits angewandt


  1 XOR 0 = 1
  0 XOR 1 = 1
  1 XOR 1 = 0
  0 XOR 0 = 0
Zum Beispiel:
  ASCII(D) = 68,  Binär(68) = 1000100
  ASCII(b) = 98,  Binär(98) = 1100010
        1000100 XOR 1100010 = 0100110
  Dezimal(0100110) = 38, BuchstabeAusAscii(38) = &
  Kurz: D xor b =  &
  Die Entschlüsselung ist dieselbe Funktion:
        & xor b = D

In Delphi wandelt ord(c) den Charakter c in seinen Asciicode um. Zum Beispiel ord('D') = 68. Die Umkehrfunktion ist char. Zum Beispiel char(68) = 'D'.

Zum Verschlüsseln und Entschlüsseln benötigen wir nur eine Funktion:


function XORverschl(const s: String):String;
  //Damit ein Textfile wieder ein Textfile wird, werden
  //Steuerzeichen wie #13#10 nicht verschlüsselt, sondern bleiben erhalten.
  const Passwort ='245abx988GHIVZ'; //oder Benutzer gibt es ein
  var i,q,nr :integer;
begin
  result := s;
  q:=1;
  for i:=1 to Length(result) do  Begin
    if result[i] >= ' ' then BEgin
      nr := Ord(result[i]) XOR Ord(Passwort[q]);
      if nr >= 32 then result[i]:=Chr(nr);
    ENd;
    inc(q);
   if q > length(Passwort) then q:=1;
  end;
end;
Verwirbelung

Viele einfachen Verschlüsselungen sind sehr unsicher. (Vor allem, wenn ein Text gleiche Zeichen hintereinander hat.) Wesentlich sicherer wird er, wenn man die Buchstaben des Textes vorher "Durcheinanderwirbelt". (Es ist der Spezialfall eines Permutationchiffres.) Man vertauscht die Buchstaben des Textes.

Bevor ich das allgeneine Verfahren beschreibe, zeige ich es zunächst für n = 2 und n = 4: ("u <-> v" bedeutet der u-te und v-te Buchstaben wird vertauscht)

n=2
     1<->3 5<->7 9<->11  13<->15 ...  (Ungerade Zahlen um 2 verschieben)
     2<->6 4<->8 10<->14 12<->16 ...  (Gerade Zahlen um 4 verschieben)
Fälle: Wenn (k mod 4 = 1)  dann k <-> k + 2
       Wenn (k mod 8) = 2) oder (k mod 8=4) dann k <-> k + 4
In diesem einfachsten Fall wird der Text schon total unleserlich. Man macht
es noch unleserlicher, wenn man noch um einen Block weiter verschiebt.
(z.B. Block = halbe Länge des Textes)
     1<->3+block 5<->7+block 9<->11+block  13<->15+block ...
     2<->6+block 4<->8+block 10<->14+block 12<->16+block ...
n=4   ("block" lasse ich der besseren Lesbarkeit noch weg)
     mod 4=1:  1<->5  5(-)   9 <->13  13(-)   17<->21 21(-)    25<->29
     mod 4=2:  2<->10 6<->14 10(-)    14(-)   18<->26 22<->30  26(-)
     mod 4=3:  3<->15 7<->19 11<->23  15(-)   19(-)   23(-)    27<->39
     mod 4=0:  4<->20 8<->24 12<->28  16<->32 20(-)   24(-)    28(-)
Fälle:
mod 4 =1 und mod 8=1 k<->k + 4
mod 4 =2 und (mod 16=2) oder (mod 16=6) k<->k+8
mod 4 =3 und (mod 24=3) oder (mod 24=7) oder (mod 24=11) k<->k+12
mod 4 =0 und (mod 32=4) oder (mod 32=8) oder
             (mod 32=12) oder (mod 32=16) k<->k+16
Als Programm geschrieben:

procedure tausche(const L:integer; var s: string; const j: integer; k:integer);
var c: char;  //x:integer;
begin
  while k > L do dec(k,L);
  while k < 1 do inc(k,L);
  if (s[j] < #32) or (s[k] < #32) then exit; //keine Steuerzeichen
  c := s[j];
  s[j] := s[k];
  s[k] := c;
end;
procedure vertausche4(var s: string; vor:boolean);
    var k, L, L4: integer;
  procedure Fallunterscheidung; {einfachere Version: siehe unten}
    begin
      if k mod 8 = 1 then tauschesij(L,s,k,L4 + k + 4) else
        if (k mod 16 = 2) or (k mod 16 = 6) then tauschesij(L,s,k,L4+ k + 8) else
          if (k mod 24 = 3) or (k mod 24 = 7) or  (k mod 24 = 11)
            then  tauschesij(L,s,k,L4+ k + 12) else
               if (k mod 32 = 4) or (k mod 32 = 8) or  (k mod 32 = 12) or  (k mod 32 = 16)
                 then  tauschesij(L,s,k,L4+ k + 16)
    end;
begin
  L := length(s);
  L4 := L div 4;
  if vor then for k := 1 to L do Fallunterscheidung
    else for k := L downto 1 do Fallunterscheidung
end;

Im folgenden Programm wird dieses Verfahren mehrmals hintereinander angewendet. Für jeden Buchstaben des Passwortes eine andere Verwirbelung.




procedure tauscheBuchstaben(const L:integer; var s: string; const j: integer; k:integer);
var c: char;
begin
  while k "> L do dec(k,L);
  if (s[j] "< #32) or (s[k] "< #32) then exit; //keine Steuerzeichen
  c := s[j];
  s[j] := s[k];
  s[k] := c;
end;
procedure vertauschen(const passwort: string; var s: string; vor:boolean);
    var k, L, block, n, m: integer;
  procedure Fallunterscheidung;
       var j, h, u: integer;
    begin
      for j := 1 to n do Begin
        h := 2*j*n;
        for u := 0 to j - 1 do
        if (k mod h) = (j + u*n) then tauscheBuchstaben(L,s,k,block + k + j*n);
      End;
    end;
begin
  L := length(s);
  for m := 1 to length(passwort) do Begin
    if vor then n := ord(passwort[m]) - 31 else
      n:=ord(passwort[length(passwort) - m + 1]) -31;
    if n "< 2 then inc(n,31);
    block := L div n;
    if vor then for k := 1 to L do Fallunterscheidung
      else for k := L downto 1 do Fallunterscheidung
 End;
end;
function VerschldurchTausch(const s: String; vor:boolean):String;
  const passwort = 'Bk25J14';
begin
  result := s;
  vertauschen(passwort,result,vor);
end;
procedure TForm1.Vreschluesseln1Click(Sender: TObject);
begin
  memo1.Text := VerschldurchTausch(memo1.text,true);//vorwärts
end;
procedure TForm1.Entschluesseln1Click(Sender: TObject);
begin
  memo1.Text := VerschldurchTausch(memo1.text,false);//rückwärts
end;
Mit folgendem Programm kann man die Verschlüsselungen vergleichen:
Passwortverschlüsselung mit Verschieben, XOR und Wirbel

Alle diese Verschlüsselungen, auch beliebig viele Kombinationen verschiedener Verschlüsselungen, lassen sich mittels einer Known-Plaintext-Attackebrechen. (Der Angreifer kennt genügend viele Klartexte und die zugehörigen Chiffretexte. So konnten im 2. Weltkrieg die Engländer die deutsche "Enigma" erfolgreich angreifen.) Heute im Computerzeitalter kommen für wichtige Verschlüsselungen derartige Verfahren nicht mehr in Betracht.

III Blockverschlüsselung

Downloadseite
Hier: Basis=224 kurz B=224 und BB=B*B=50176

Da jede Verschlüsselung, die nur einzelne Buchstaben verschlüsselt, leicht zu knacken ist (das häufigste Vorkommen ist "e" u.s.w.), werden ganze Blöcke verschlüsselt. Im Programm hier sind es Zweierblöcke.

Lassen wird die Zuordnung Zeichen auf Zahl einmal außen vor, kann man das Verfahren folgendermaßen erklären.

Die Zuordnung (m,n)——>y:=m+n*B ordnet jedem Zahlenpaar aus der Produktmenge {0,1,2,..., B-1}*{0,1,2,..., B-1} eine eindeutig bestimmte Zahl der Menge {0,1,2,..., BB-1} zu.

Der Mathematiker schreibt für {0, 1, ..., B-1} kurz Z B.

Die Umkehrabbildung y——>(m,n) ist folgende:
n:=y div B (Bei Division Rest weglassen)
m:=y mod B (Der Rest bei Division durch B)
Also y:=m+n*B

f:(m,n)->m+n*B ist also eine umkehrbare Abbildung von Z B* Z Bauf Z BB.

Verschlüsselung und Entschlüsselung wird durch eine umkehrbare
Abbildung g der Menge Z BBauf sich bewerkstelligt.
Im Beispiel hier ist es g : x——>x+n mod BB
Umkehrabbildung: g_: x——>x-n mod BB


      Die wesentlichen Delphiprozeduren sind dann:  
Verschlüsseln mit 0 < n < BB.
Entschlüsseln mit - n. const B =224; // Globale Variablen ... BB=B*B; // ...Zeilen stehen über ... var //von Delphi geschrieben Form1: TForm1; //... implementation //... {$R *.DFM} //... function fPlusNmodBB(x,n:integer):integer; //Hier könnte auch eine beliebige umkehrbare Funktion //mit dem Definitionsbereich {0,1,2,...,BB-1} stehen //z.B. der RSA-Algorithmus x -"> x^n mod BB // die Umkehrfunktion ist dann aber nicht mehr mit -n zu bewerkstelligen // sondern nur wenn die Zerlegung A=P1*P2 einer gewissen Zahl in // ihre Primfaktoren P1 und P2 gelingt begin result := x+n; if result >= BB then result:=result-BB; if result < 0 then result:=result+BB; end; procedure VerschlZweierBlock(var c1,c2:char; n:integer); var i:integer; begin i:=fPlusNmodBB(ord(c1)-32+(ord(c2)-32)*B,n); //Funktion angewandt auf i von der Form i=a+b*B c1:=char(i mod B + 32); //mod wie Punkt- vor Strichrechnung c2:=char(i div B + 32); //div ist Punktrechnung: Keine Klammer nötig end; Procedure VerschlZeile(var s:string; n:integer); var k:integer; begin if length(s) mod 2 <> 0 then s:=s+' '; //Länge gerade Zahl for k:=1 to length(s) div 2 do VerschlZweierBlock(s[2*k-1],s[2*k],n); //Für k=1 s[1],s[2], für k=2 s[3],s[4], ... end;

IV RSA-Verschlüsselung

y = x emod n


Mit dem Programm RSA vorgerechnetes Beispiel

Bild
Bitte hier klicken

Ronald Rivest,
Adi Shamir und
Leonard Adleman
stellten 1978 den
RSA-Algorithmus vor


Downloadseite (mit einem schönen Programm von Hannes Nützmann)    Bildschirmaufnahme
Die Verschlüsselung nach Ron Rivest, Adi Shamir und Len Adleman beruht auf einem mathematischen Verfahren.
Ist n=p*q das Produkt zweier Primzahlen und e eine zu n 0=(p-1)·(q-1) teilerfremde Zahl, d.h. ggT(e,n 0)=1, dann ist
x->x e mod n eine umkehrbare Abbildung von Z nauf Z n.
Zu e kann man, wenn man die Primfaktoren p und q kennt, eine Zahl d finden mit e*d=1 mod n 0, d.h. es gibt eine Zahl q so, dass e*d=q*n 0+1 (siehe Der erweiterte euklidische Algorithmus )

f:x——>x d ist dann die Umkehrfunktion zum Entschlüsseln.

Der Beweis benötigt aus der höheren Mathematik den Satz von Fermat.

Einfaches Zahlenbeispiel:
   Bekannt: e = 63 und n = 4141
   gesucht: d so, dass d·63 = 1 mod (p-1)·(q-1), wobei n=p·q
Lösung:
   I  (Bei großen Zahlen praktisch unmöglich)
      Zerlege n in seine Primfaktoren: n = p·q = 41·101
   II (Routine)
      Bestimme mit Hilfe des erweiterten euklidischen Algorithmus
      d = 127 so, dass d·63 = 1 mod 40·100
      Probe: 127·63 = 8001 = 1 mod 4000
Schon etwas aufwendiger ist folgendes Beispiel:
   Bekannt e = 446263 und n=199151197093
   gesucht: d so, dass d·446263 = 1 mod (p-1)·(q-1), wobei n=p·q
Lösung: I  n = 199151197093 = p·q =479909·414977
        II d = 118246537863
           Probe: d·446263
                  = 118246537863·446263
                  = 52769054726355969
                  = 264971·(479908·414976) + 1
                  = 1 mod (p-1)·(q-1)

Bei großen Primzahlen p und q sind die einzelnen Faktoren von n=p·q praktisch nicht zu ermitteln ( Beispiel ) und deshalb die Umkehrfunktion, die Entschlüsselung, in diesem Jahrzehnt wohl unmöglich. Man kann deshalb die Parameter n und e der Verschlüsselung öffentlich machen. Jeder kann dem Empfänger eine verschlüsselte Botschaft zukommen lassen. Den Parameter d zum Entschlüsseln der Nachricht kennt nur der Empfänger, d.h. mit der verschlüsselte Botschaft kann ein Dritter nichts anfangen, selbst wenn er weiß, wie sie verschlüsselt wurde.

Im Beispiel hier werden wieder Zweierblöcke verschlüsselt. Da f keine Abbildung von Z BBauf Z BBist, werden die verschlüsselten Blöcke nur als Zahl dargestellt.

Anhang I hohe Potenzen: "Wiederholtes Quadrieren"

Siehe auch Hohe Potenzen, rekursiv

Beim RSA-Verfahren muss die Berechnung hoher Potenzen effektiv durchgeführt werden. Dies sei an folgendem Beispiel erläutert.

Beispiel: y=m efür m=2 und e=21. Also y=2 21

Algorithmus:
Anfangswert y:=1
Wiederhole den folgenden Befehl solange, bis e=0 ist:
Wenn e ungerade, dann y:=y·m und e:=e-1 (m ungeändert), sonst m:=m2 und e:=e/2 (y ungeändert)
Rechnung
y=1 m=2 e=21 (Algorithmus liefert y=2 21)
y=2 m=2 e=20
y=2 m=22 e=10
y=2 m=(22)2=2 4e=5
y=2·2 4=2 5m=2 4e=4
y=2 5m=(2 4)2=2 8e=2
y=2 5m=(2 8)2=2 16e=1
y=2 5·2 16=2 21e=0
[fertig! Statt 20 Multiplikationen nur 7. Effizienz = O(lb e)]
Die Funktion in Delphi lautet:

function h(m:extended; e:integer):extended;
begin
  result := 1;
  while e > 0 do
    if odd(e) then Begin
      result := result*m;
      e := e -1;
    End else Begin
      m :=m*m;
      e := e div 2
    End;
end;
Die rekursive Funktion h(m,e)=m eist leicht durchschaut. (Rekursiv ist doch einfacher als iterativ.)


function h(m:extended; e:integer):extended;
  begin
    if e = 0 then result := 1 else
      if odd(e) then result := m*h(m,e-1)//da me=m*m(e-1)
        else result := h(m*m,e div 2)    //da me=(m*m)(e/2)
  end;
Aufgabe: Anfang 2002 hat Michael Cameron die 39. Mersennsche Primzahl gefunden. Sie lautet c=2 13466917-1.
a) Wieviel Dezimalstellen hat diese Zahl?
b) Wieviel Multiplikationen sind nach dem ober beschriebenen Verfahren notwendig?
Lösung

Anhang II der erweiterte euklidische Algorithmus

Bei der RSA-Verschlüsselung benötigt man die zu e inverse Zahl d so dass gilt: e·d = 1 mod m (wobei m = n0 = (p-1)·(q-1) ist). Anders ausgedrückt. Es werden zwei ganze Zahlen d=u und v ermittelt für die gilt: u·e + v·m = 1.
Die Funktion d = invers_mod(e,m) kann man mit dem erweitereten euklidischen Algorithmus ermitteln (Programm: siehe unten).

Der erweiterte euklidische Algorithmus liefert uns den größten gemeinsamen Teiler t=ggT(a,b) zweier ganzer Zahlen a und b und passende ganze Zahlen u und v mit u·a + v·b = t.

Satz: Ist t = ggT(a,b), dann gibt es ganze Zahlen u und v mit:
u·a + v·b = t
Beispiel: a=18 und b=12
1·18 + (   -1)·12 = 6 oder
7·18 + (-10)·12 = 6      
Beweis mit vollständiger Induktion: siehe unten

Der euklidische Algorithmus fußt auf der Rekursionsformel ggT(a,0) = a und ggT(a,b) = ggT(b,a mod b) für b <>0
      z.B. ggT(100,35)=ggT(35,100 mod 35)= ggT(35,30)
           ggT(35,30) =ggT(30,35 mod 30) = ggT(30,5)
           ggT(30,5)  =ggT(5,30 mod 5)   = ggT(5,0) = 5
Ausführlicher in Lektion 9.

Diese Rekursion müssen wir jetzt nur ausführlicher betrachten:
Zur Erinnerung:    a   div  b = ganzzahliger Teil von a/b.
      Beispiel:    100 div 35 = 2, da 100/35 = 2 Rest 30
                   a   mod  b = ganzzahliger Rest bei a/b
      Beispiel     100 mod 35 = 30, da 100/35 = 2 Rest 30
      Stets gilt:  a   = (a div b)·b  + (a mod b)
      Beispiel:    100 =     2    ·35 +     30
Nun zum erweiterten euklidischen Algorithmus:
Da auch ggT(b, a mod b) = t ist, gibt es auch ganze Zahlen u0 und v0 mit:
        u0·b + v0·(a mod b) = t.
Mit a = (a div b)·b + (a mod b) folgt daraus:
—————————————————————————————————————————————
       a mod b = a - (a div b)·b
       u0·b + v0·(a - (a div b)·b = t
       v0·a + (u0 - v0·(a div b))·b = t
Somit ist u·a + v·b = d für u = v0 und v = u0 - v0 ·(a div b). Und damit haben wir eine Rekursionsformel für u und v, wobei für den Anfangswert a = ggT(a,0,u,v) gilt: u = 1 und v = 0, da 1·a + 0·0 = a.

Beispiel:
130 = 2*61 + 8   => 8 = 130 - 2*61
 61 = 7*8  + 5   => 5 = 61 - 7*8
                      = 61 - 7*(130-2*61)
                      = -7*130 + 15*61
  8 = 1*5 + 3    => 3 = 8 - 1*5
                      = 130 - 2*61 - (-7*130+15*61)
                      = 8*130 - 17*61
  5 = 1*3 + 2    => 2 = 5 - 1*3 = -7*130 + 15*61 - 1*(8*130-17*61)
                      = -15*130 + 32*61
  3 = 1*2 + 1    => 1 = 3 - 1*2 = 8*130 - 17*61 - 1*(-15*130 + 32*61)
                      = 23*130 - 49*61
Somit ist gezeigt: ggT(130,61) = 1 und es gibt ganze Zahlen u,v so, dass
    u*130 +  v*61  =1  nämlich
   23*130 - 49*61 = 1


Der Existenzbeweis für u und v liegt nun auf der Hand:
I Rekursionsanfang: für a = 0 und beliebiges b gibt es u,v so, dass u·a +v·b =b (u=0 v=1)
II Mit der Annahme "Für alle Zahlen x < a und für alle b gibt es passende u0 und v0 mit u0·x + v0·b = t" können wir mit Hilfe der Rekursionsformel (siehe oben) beweisen, dass es u und v gibt mit u·a + v·b = t.

Nebenbei bemerkt:
Wir haben die Existenz einer Lösung für
  u·a+v·b=t für t=ggT(a,b)
bewiesen.
Weitere Darstellungen dieser Form sind für qεZ
         b             a
  (u + q·-)·a + (v - q·-)·b = t
         t             t
Den Algorithmus übersetzten wir noch nach Delphi:

Function ggTerw(a,b: integer; var u,v: integer):integer;
  var u0, v0:integer;
begin
  if b = 0 then Begin
    result := a;
    u := 1;
    v := 0;
  End else Begin
    result := ggTerw(b, a mod b, u0, v0);//rekursiv
    u := v0;
    v := u0 - (a div b)*v0;
  End;
end;
Nun kommen wir zur Berechnung der Zahl d = invers_mod(e,m) mit e·d = 1 mod m.

Mit Hilfe des euklidischen Algorithmus ermitteln wir u und v mit u·e + v·m = ggT(e,m) = 1. Dann ist mit d = u die Beziehung d·e = 1 - v·m erfüllt, d.h. es gilt d·e = 1 mod m.
Beispiel: gesucht d so, dass d·13 = 1 mod 180.
Der erweiterte euklidische Algorithmus liefert
                       97·13 + (-7)·180 = 1
Somit: 97·13 = 1 mod 180
Nach Delphi übersetzt.

function invers_mod(e,m: integer): integer;
  var d,v: integer;
begin
  ggTerw(e,m,d,v); //der Funktionswert von ggT wird nicht benötigt
  if d < 0 then d := d + m;
  result := d;
end;
Die Funktion ohne externen Aufruf von ggTerw:
function invers_mod0(e,m: integer): integer;
      var v: integer;
   procedure ggTerw(a,b: integer; var u,v: integer);
     var u0, v0:integer;
  begin
    if b = 0 then Begin
      u := 1;
      v := 0;
    End else Begin
      ggTerw(b, a mod b, u0, v0);//rekursiv
      u := v0;
      v := u0 - (a div b)*v0;
    End;
  end;
begin
  ggTerw(e,m,result,v);
  if result < 0 then result := result + m;
end;
Hier noch die Funktion iterativ formuliert:

function invers_mod(e,m:integer):integer;
  var m0,x0,x1,y0,y1,xx,yy,q,r,sign:integer;
begin
  m0:=m; x0:=1; x1:=0; y0:=0; y1:=1; sign:=1;
  while e <> 0 do Begin
    q:=m div e;
    r:=m mod e;
    m:=e;
    e:=r;
    xx:=x1;
    yy:=y1;
    x1:=q*x1+x0;
    y1:=q*y1+y0;
    x0:=xx;
    y0:=yy;
    sign:=-sign;
  End;
  y0:=-sign*y0;
  if y0 < m then y0:=m0+y0;
  result:=y0;
end;
(Gibt es noch jemanden, der behauptet, iterativ sei einfacher als rekursiv?)

Anhang III größte bekannte Primzahl - Preisrätsel

Die größte bekannte Primzahl

                                                 11213
Stand 1969: Stempel der Universität Wisconsin: "2     - 1 is prime".
Unvorstellbar: Im Dezimalsystem hat diese Primzahl 3 376 Stellen.
  11213
2      -1 = 28113037916606000454781559178799143008468...2191
Der genaue Wert kann mit TTMathe (Menü "Rechenblatt|Extras|4000 Dezimalstellen") berechnet werden.
Stand Juli 2002: Der 20-jährigen  Mathematik-Enthusiast Michael Cameron aus Kanada
                   13 466 917
fand die Primzahl 2          - 1 mit Hilfe eines weltumspannenden Computernetzwerks.
(Siehe auch Aufgabe.)
Diese Primzahl hat im Dezimalsystem über 4 Millionen Stellen.
(Quelle: http://www.primzahlen.de)
Nachtrag Dezember 2004: Inzwischen wurde der Primzahlrekord wieder gebrochen:
Neuer Mersenne-PZ-Rekord: 2 20 996 011- 1 mit 6 320 430 Dezimalstellen.
Nachtrag Februar 2005: Neuer Mersenne-PZ-Rekord: 2 25 964 951- 1 mit 7 816 230 Dezimalstellen.
(Errechnet von April 1999 bis 18. Februar 2005 mit den 25 Computern des Augenzentrums vom Augenarzt Martin Novak aus Michelfeld bei Schwäbisch Hall, Baden-Württemberg).

Nachtrag September 2008: Die neuen Weltrekorde häufen sich. Laufend werden immer größere Primzahlen entdeckt.

Nachtrag: Januar 1918 Der Hobby-Mathematiker Jonathan Pace findet bislang größte Primzahl. 277232917-1 ist Primzahl. Diese Mersenne-Primzahl ist 23 249 425 Stellen lang. (Mersenne-Primzahlen sind nach dem französischen Priester Marin Mersenne benannt, der sie im Jahr 1644 beschrieb.)

Primzahltest

Eine große Primzahl zu finden, ist wesentlich leichter, als eine große Zahl daraufhin zu überprüfen, ob sie prim ist.

Wie lange braucht man wohl, um eine 100-stellige Zahl zu faktorisieren?
1977 geschätzt: 40 Billiarden Jahre.
1994 in 8 Monaten faktorisiert auf 1600 Internet-Rechnern.

Stand Februar 2002 (tecChannel.de): Den Mathematikern Prof. Dr. Jens Franke, Dr. Thorsten Kleinjung und Friedrich Bahr vom Institut für Mathematik an der Universität Bonn ist es nach eigenen Angaben gelungen, eine Zahl mit 158 Stellen (entspricht 524 Bits) in ihre Primfaktoren zu zerlegen. Das sei neuer Weltrekord.

Factoring Challenge der Firma RSA Security Inc (Stand 2001)

Die Firma RSA Security Inc bietet $ 20 000, wer folgende 643-Bit-Zahl, hier als Dezimalzahl mit 193 Stellen geschrieben, in ihre Primfaktoren zerlegt:
31074182404900437213507500358885679300373460
22842727545720161948823206440518081504556346
82967172328678243791627283803341547107310850
19195485290073377248227835257423864540146917
36602477652346609
Stand 5.12.2003: Das Bundesamt für Sicherheit in der Informationstechnik hat den RSA-576 (174 Stellen lange Zahl) faktorisiert.
1881 9881292060 7963838697 2394616504 3980716356 3379417382 7007633564
2298885971 5234665485 3190606065 0474304531 7388011303 3967161996 9232120573
4031879550 6569962213 0516875930 7650257059
=
3980750 8642406493 7397125500 5503864911 9906436234 2526708406 3851895759
4638895726 1768583317
*
4727721 4610743530 2536223071 9730482246 3291469530 2097116459 8521711305
2071125636 3590397527
Genauere Infos

Stand November 2005: Das Bundesamt für Sicherheit in der Informationstechnik hat die oben genannte RSA-Challenge (193-dezimalstellige) Zahl faktorisiert. Das Team benötigte laut c't 25/2005 S.64 fünf Monate Rechenzeit auf einem Opteron-Clustermit 80 2,2 GHz-Prozessoren.
Stand Mai 2007: Das RSA Factoring Challenge wurde im Mai 2007 als beendet erklärt. Siehe: Wikipedia-Artikel.

Stand Januar 2010 (cis/dpa)
Neuer Entschlüsselungsrekord: Einen sogenannten RSA-Schlüssel von 768 Bit Länge knackte ein Forscherteam mit Hilfe eines Rechnernetzwerks - und jahrelanger Arbeit. In zehn Jahren, fürchten die Wissenschaftler, könnte die nächste Hürde fallen - und die schützt auch Kreditkartendaten.

Bonn - Die heute gebräuchlichen Schlüssel zur Sicherung etwa von Kreditkartennummern im Internet könnten nach Erkenntnissen von Forschern schon in einigen Jahren unsicher werden. Ein internationales Team unter Bonner Beteiligung hat jetzt einen 768 Bit langen Schlüssel geknackt. Das sei eine Zahl mit 232 Stellen und damit Weltrekord, teilte die Universität Bonn am Freitag mit. Damit sind die Forscher dem aktuell gängigen Schlüssel von 1024 Bit schon ein Stück näher gekommen. Die Forscher nutzten ein Computernetzwerk. Auf einem herkömmlichen PC hätte das Knacken dieses Schlüssels ihren Angaben zufolge rund 2000 Jahre gedauert.

Mit dem ersten Rechenschritt zur Entschlüsselung waren 80 PC ein halbes Jahr lang beschäftigt. Der zweite und wesentlich aufwendigere Schritt dauerte etwa zwei Jahre - mehrere hundert Rechner waren daran beteiligt.

Viele Verfahren zur Verschlüsselung sensibler Daten beruhen darauf, dass es äußerst schwierig ist, große Zahlen in ihre sogenannten Primfaktoren zu zerlegen. Primfaktoren sind diejenigen Primzahlen, die, miteinander multipliziert, die gesuchte Zahl ergeben. So hat etwa die Zahl 21 die Primfaktoren 3 und 7 (3 mal 7 gleich 21). Die US-Forscher Ron Rivest, Adi Shamir, and Leonard Adleman entwickelten 1977 und 1978 ein Verfahren zur Datenverschlüsselung und nutzten es später auch kommerziell. Ihre nach ihren Initialen "RSA" genannte Technik steckt inzwischen in jedem Internetbrowser. Ein kleines Programm verschlüsselt dort etwa Kreditkartennummern so, dass böswillige Lauscher mit ihnen nichts anfangen können.

"Um drei Größenordnungen schwieriger als das jetzige Projekt"

Die jetzt geknackte Zahl trägt die nüchterne Bezeichnung RSA-768, das heißt, sie hat 768 Bit. In Dezimalschreibweise entspricht das 232 Stellen. Damit handelt es sich um das größte Zahlenungetüm von allgemeiner Form, das bislang in seine Primfaktoren zerlegt wurde. "Die Zerlegung eines 1024-Bit-Schlüssels wäre um drei Größenordnungen schwieriger als das jetzt abgeschlossene Projekt", sagte Prof. Jens Franke vom Institut für Mathematik der Universität Bonn. Dennoch werde der erste 1024-Bit-Schlüssel vermutlich noch vor Ende des Jahrzehnts geknackt.

Gestützt wird diese Einschätzung durch die bisherigen Rekorde: 1999 fiel RSA-512, sechs Jahre später RSA-663 und nun RSA-768. Um weiterhin eine verlässliche Sicherung zu gewährleisten, empfehlen Experten bereits, nach Ende dieses Jahres keine 1024-Bit-Schlüssel mehr zu verwenden, sondern zu 2048-Bit-Schlüsseln überzugehen.

An dem Weltrekord waren außer der Universität Bonn das Bundesamt für Sicherheit in der Informationstechnologie, das Centrum Wiskunde & Informatica in den Niederlanden, die schweizerische École polytechnique fédérale de Lausanne, das französische Institut national de recherche en informatique et en automatique sowie die japanische Nippon Telegraph and Telephone beteiligt.
Vorgerechnetes Beispiel

Lit.: Johannes Buchmann: Einführung in die Kryptologie. Springer-Lehrbuch 1999.

Dort wird die Public-Key Verschlüsselung folgendermaßen eingeführt:

Alice schickt einen verschlüsselten Text tan Bob. (Man muss damit rechnen, dass Unberechtigte den Text mitlesen.) Der Text tz.B. "BCA"entspricht der Zahl m=ord(B)+256*ord(C)+256^2*ord(A).

Nur Bob soll den Text wieder dechiffrieren können.

Dies kann er auf folgende Weise:

Bob teilt Alice seinen öffentlichen Schlüssel (e,n)(Zwei Zahlen) mit. Alice verschlüsselt den Text tbzw. die Zahl mzu c=m emod n und offenbart Bob c. Bob kann den verschlüsselte Text cmit seinem privaten Schlüssel dentschlüsseln ( Formel: m=c dmod n ). Unberechtigte können mit der Kenntnis von e, nund cden Wert dund damit den Text nicht ermitteln (siehe Theorie). Nur Bob kennt dund ist in der Lage, die Nachricht von Alice zu entschlüsseln.


Lösung zu c=2 13466917-1
a) c=10 xergibt x=13466917·lg2 = 4053945,966. Somit hat x=9.247·10 4053945offensichtlich 4 053 946 Stellen.
b) Die Anzahl der Multiplikationen für c ist von der Größenordnung lb(13466917) = 24.


Die genaue Anzahl ergibt sich aus der Dualdarstellung der Hochzahl: 13466917(10)=110011010111110100100101(2). Außer den 23 Multiplikationen für die Potenzen sind noch 14 Multiplikationen zusätzlich nötig.

Download im Verzeichnis Verschlüsselungen


Anhang IV Binärdateien in Text-Dateien umwandeln

Beim RSA-Algorithmus erhalte ich aus einer Textdatei eine Binärdatei. Diese kann ich zum Beispiel nur als Anhang mit einer e-mail verschicken. Wenn ich das nicht möchte, kann ich vor dem Verschicken die Binärdatein in eine Textdatei (d.h. eine Datei ohne Steuerzeichen dazwischen) verwandeln, diese Textdatei in das e-mail kopieren und dann versenden.

Dies gilt auch für EXE- und JPG-Dateien uns so weiter.

In der folgend unit umwandlungsprozeduren.pas wird dies erledigt.