Hexen1x1
Kap.3)   DARSTELLUNG MODULARER ALGORITHMEN
               in Java

Index

     3.1   Modulare Arithmetik, kurze Übersicht
     3.2   Eulers Generalisierung, Anwendung auf das RSA-Verfahren
     3.3   Modulare Algorithmen in Java

  Dieses letzte Kapitel ist als Anhang gedacht für Leser, die mit modularer Arithmetik und modularen Algorithmen noch nicht hinreichend vertraut sind.


     3.1   Modulare Arithmetik, kurze Übersicht

Index

   3.1.1   Begriffe der modularen Arithmetik
   3.1.2   Galois-Feld (endlicher Körper), Axiome modularer Arithmetik
   3.1.3   Äquivalenzen 
   3.1.4   Reduktionen
   3.1.5   Sätze
   3.1.6   Tests

  Wir geben eine kurze Übersicht über die von Fermat (17. Jh.), Euler (18. Jh.) und Galois (19. Jh.) begründete modulare Arithmetik. Dieses Gebiet der Zahlentheorie hat durch das kryptographische Verfahren von Rivest, Shamir, Adleman (1977) große aktuelle Bedeutung erlangt.


   3.1.1   Begriffe der modularen Arithmetik
   a / b        ganzzahl. Division, z.B. 9/5        =1   ,a>=0,b>0
   a mod b      ganzzahl. Div-Rest, z.B. 9 mod 5    =4   ,a>=0,b>0
   Inverse(a)   modulo n          , z.B. Inverse(2) modulo 5=3,a>0
   gcd(a.b)     groesst.gem.Teiler, z.B. gcd(6,10)  =2      
   p prim       Primzahl          , z.B. 7 ist prim           
   a relprim b  teilerfremd       , z.B. 8 ist relprim 9  
   phi(n)       Anzahl m relprim n, z.B. phi(4)     =2      ,0<m<n
   phi(p)      = p-1              , z.B. phi(5)     =4     ,p prim
   phi(p*q)    =(p-1)(q-1)        , z.B. phi(3*5)   =8  ,p!=q prim
   3.1.2   Galois-Feld (endlicher Körper), Axiome modularer Arithmetik
   n>1                 °  entsprechendes gilt auch fuer +    
   Assoziativ -Gesetz  °: a*(b*c)      mod n = (a*b)*c mod n 
   Kommutativ -Gesetz  °: a* b         mod n =  b*a    mod n
   Einheit 1   Existenz°: a* 1         mod n =  a  ,impliziert a<n
   Inverse(a)  Existenz°: a*Inverse(a) mod n =  1      ,falls a!=0
   Reduktions -Gesetz  °: a* b         mod n =(a mod n)*b mod n
   Distributiv-Gesetz   : a*(b+c)      mod n =(a*b)+(a*c) mod n

      z.B. {0,1,2}      : n=3, Inverse(1)=1,Inverse(2)=2, ein G.F. 
           {0,1,2,3}    : n=4, Inverse(2) exist. nicht,  kein G.F.
   3.1.3   Äquivalenzen 
   1) a,b invers mod n      <=> t exist.mit a*b=n*t+1       ,a,b>0
   2) a relprim n           <=> b exist.mit a,b invers mod n,a,b>0
   3) a relprim n           <=> a mod n relprim n             ,a>0
   4) a relprim b           <=> gcd(a,b)=1                  ,a,b>0
   5) a relprim b,c         <=> a relprim b*c             ,a,b,c>0
   6) a mod p = b mod p,                                    ,a,b>0
      a mod q = b mod q     <=> a mod p*q = b mod p*q   ,p!=q prim
   7) a*x mod n=a*y mod n   <=> x mod n   = y mod n   ,a relprim n
   8) x^2 mod p=1           <=> x mod p=1 oder x mod p=p-1 ,p prim
   3.1.4   Reduktionen
   a^(s*t) mod n             = (a^s mod n)^t mod n         
     Potenz-Reduktion            aus Reduktions-Gesetz
   gcd(a,b)                  =  gcd(b mod a,a)             ,0<a<=b
     Euklids Reduktion           {Teiler(a,b)}={Teiler(b-a,a)}
   3.1.5   Sätze
   gcd(a,b)=c                => s,t exist.mit c=s*a+t*b     ,a,b>0
     Euklids Satz                vgl. Eukl.erw.Red.Algorith. s.u.
      z.B. gcd(6,10)=2       => x=2,y=-1 exist.mit 2*6-1*10=2
   a relprim p prim          => a^(p-1) mod p = 1         
     Fermats Satz                aus Eulers Generalisierung s.u. 
      z.B. 2 relprim 3 prim  => 2^ 2    mod 3 = 1
   a relprim p!=q prim       => a^((p-1)*(q-1))mod(p*q)=1 
     Eulers  Satz                aus Eulers Generalisierung s.u.
      z.B.2 relprim 3,5 prim => 2^( 2   * 4   )mod(3*5)=1
   3.1.6   Tests
   x^(p-1) mod p !=1, 0<x<p  => p nonprim
     Fermats Test                aus Fermats Satz
   x^2 mod p=1,1<x mod p<p-1 => p nonprim
     Rabin-Millers Test s.u.     aus Aequivalenz 8)
     3.2   Eulers Generalisierung, Anwendung auf das RSA-Verfahren

Index

   3.2.1   Eulers Generalisierung von Fermats Satz 
   3.2.2   RSA-Verschlüsselung/Entschlüsselung

  Das RSA-Verfahren mit seinen modularen Potenzierungs-Algorithmen zur Verschlüsselung und Entschlüsselung beruht auf dem Satz von Fermat (französischer Mathematiker, 18. Jh.) und der Generalisierung dieses Satzes durch Euler (schweizer Mathematiker, 19. Jh. ). Der nachfolgend skizzierte Euler'sche Beweis ist ein mathematischer Leckerbissen.


   3.2.1   Eulers Generalisierung von Fermats Satz

   Satz:  Aus  a relativ prim n  folgt  a^phi(n) mod n = 1 
   Beweis:

  {r[1]         ,..., r[phi(n)]} Menge der 1<=r[i]<n relprim n

  {r[1]*a mod n ,..., r[phi(n)]*a mod n} ist Permutation davon,
   da alle Elemente <n (modulo n), relprim n (Aequivalenz 5)
   und verschieden (weil r[i] verschieden, Aequivalenz 7), d.h.
  (r[1]*a mod n)*...*(r[phi(n)]*a mod n) = r[1]*..*r[phi(n)]

   Auf beiden Seiten mod n ergibt nach Reduktions-Gesetz
   r[1]*a* ...*r[phi(n)]*a        mod n  = r[1]*..*r[phi(n)] mod n
   r[1]*   ...*r[phi(n)]*a^phi(n) mod n  = r[1]*..*r[phi(n)] mod n

   Daraus folgt          a^phi(n) mod n  = 1       (Aequivalenz 7)
   3.2.2   RSA-Verschlüsselung/Entschlüsselung
   Voraussetzung:
       2<p,q verschiedene Primzahlen 
       n modul = pq
       n>M Message
       1<e encryption key   relprim (p-1)(q-1)
       d decryption   key = Inverse(e) modulo (p-1)(q-1)
   Satz: "Entschlüsselung(Verschlüsselung(Message M))=Message M"
       (M^e mod n)^d mod n = M               Satz, d.h.
        M^(ed) mod n = M                     Potenz-Reduktion
   Beweis:

   falls M=0:                                trivial
        M^(ed) mod n =          M mod n       =0, da M=0
   falls 0<M relprim p,q:
        M^(ed)                    mod n   
    =   M^((p-1)(q-1)t+1)         mod n      Aequivalenz 1)
    = M(M^ (p-1)(q-1))^t          mod n   
    = M(M^ (p-1)(q-1) mod n)^t    mod n      Potenz-Reduktion
       '---------,---------'            
    =   M        1          ^t    mod n      Eulers Satz
    =   M                         mod n
   falls 0<M relprim p und q teilt M (oder umgekehrt):
    modulo p gilt:                       
        M^(ed)                    mod p   
    =   M^((p-1)(q-1)t+1)         mod p      Aequivalenz 1)
    = M(M^ (p-1))      ^((q-1)t)  mod p
    = M(M^ (p-1) mod p)^((q-1)t)  mod p      Potenz-Reduktion
       '-------,------'
    =   M      1       ^((q-1)t)  mod p      Fermats Satz
    =   M                         mod p
    modulo q gilt:                           trivial 
        M^(ed) mod q =          M mod q       =0, q teilt M
    modulo n=pq gilt:                        aus modulo p,q nach
        M^(ed) mod pq=          M mod pq      Aequivalenz 6) 
     3.3   Modulare Algorithmen in Java

Java-Programm-Index

   3.3.1  Euklids Reduktions-Algorithmus (größter gemeinsamer Teiler)
   3.3.2  Euklids erweiterter Reduktions-Algorithmus (modulare Inverse)
   3.3.3  Reduktions-Algorithmus zur Berechnung modularer Potenzen 
   3.3.4  Rabin-Millers probabilistischer Primzahltest

  "Programmieren heißt Verstehen" sagt Nygaard, einer der Autoren der Programmiersprache SIMULA (1965). Auch Java (1996) zählt zur SIMULA-Familie der objektorienterten Programmiersprachen. Java, die für Applet-Programmierung heute am meisten verwendete Programmiersprache, bietet wie andere Programmiersprachen standardmäßig modulare Operatoren / für ganzzahlige Division und % für ganzzahligen Divisionsrest (entspricht mod in der Mathematik) und enthält darüber hinaus auch die "RSA-maßgeschneiderte" Klasse BigInteger für das Rechnen mit beliebig großen Zahlen und mit modularen Methoden: modPow() für schnelle Potenzierung, gcd() für die Bestimmung des größten gemeinsamen Teiler (greatest common divisor) nach Euklids Reduktions-Algorithmus, isProbablePrime() für schnellen probabilistischen Test auf Primzahleigenschaft u. a. m.

  Wer in Java zu programmieren versteht, dem eröffnen die nachfolgenden kurzen instruktiven Java-Programme einen leichten Zugang zu modularen Algorithmen "und wer's nie gekonnt, der stehle weinend sich aus diesem Bund" (Schiller: "An die Freude") oder begnüge sich mit den kurzen Hinweisen auf die Prinzipien der Algorithmen.


   3.3.1  Euklids Reduktions-Algorithmus (größter gemeinsamer Teiler)

  Zur einfachen Darstellung des Algorithmus beschränken wir uns auf die Zahldarstellung int. Die Klasse BigInteger enthält bereits die Methode a.gcd(b).
  int gcd(int a,int b)                   // 0<a<b
   {int[]        A={a},
                 B={b};
    for(;;) {if (A[0]==0) {return B[0];}
                 B[0]%=A[0];             // Euklids Reduktion                          
                 change(A,B);            // Tausch von A und B
            }
   }
Beispiel: gcd(66,385)=11
      a=A[0]   b=B[0]
        ----     ----
          66      385
          55       66
          11       55
           0       11
                 ----
               gcd(a,b)
Prinzip: Die Menge der Teiler(a,b) ist gleich der Menge der Teiler(b-a,a) und - da Modulbildung gedeutet werden kann als mehrfache Subtraktion - gleich der Menge der Teiler (b mod a,a). Im obigen Java-Programm wird b=b mod a berechnet durch B[0]%=A[0].


   3.3.2  Euklids erweiterter Reduktions-Algorithmus (modulare Inverse)

  Zur einfachen Darstellung des Algorithmus beschränken wir uns auf die Zahldarstellung int. Die Klasse BigInteger enthält bereits die Methode a.modInverse(n). .
  int modInverse(int a,int n)            // 0<a<n, gcd(a,n)=1 
   {int[]        A= {  a,  1,  0},       // A[0]=A[1]*a+A[2]*n
                 // {gcd,inv,fac},          gcd =inv *a+fac *n
                 //  gcd                    wird 1
                 //      inv                wird die Inverse
                 //          fac            wird nichtpos. Faktor   
                 N= {  n,  0,  1};       // N[0]=N[1]*a+N[2]*n
    for(;;) {if (A[0]==1) {return A[1];}
             final
             int QUOT =N[0]/A[0];
                 N[0]-=QUOT*A[0];        // EuklRedukt: N[0]%=A[0]
                 N[1]-=QUOT*A[1];     
                 N[2]-=QUOT*A[2];        // N[0]=N[1]*a+N[2]*n   
                 change(A,N);            // Tausch von A und N
            }                               
   } // A[2], N[2] sind redundant und dienen nur zur Erlaeuterung 
Beispiel: inv(67,385)=23
      a=A[0]     n=N[0]       A[1]       N[1]       A[2]      N[2]
        ----       ----       ----       ----       ----      ----
          67        385          1          0          0         1
          50         67         -5          1          1         0
          17         50          6         -5         -1         1
          16         17        -17          6          3        -1
           1         16         23        -17         -4         3
        ----                  ----                  ----         
      gcd(a,n)            = inv(a,n) * a       +     fac * n
Prinzip: Wie im vorhergehenden Reduktions-Algorithmus wird der größte gemeinsame Teiler von A[0] und N[0] berechnet, der voraussetzungsgemäß zu 1 wird. Als "Nebeneffekt" wird die mitgeführte zweite Komponente A[1] zur modularen Inversen von a.


   3.3.3  Reduktions-Algorithmus zur Berechnung modularer Potenzen 

  Zur einfachen Darstellung des Algorithmus beschränken wir uns auf die Zahldarstellung int. Die Klasse BigInteger enthält bereits die Methode a.modPow(pow,n).
  int modPow(int a,int pow,int n)                // fuer a,pow >=0
   {final String POW=Integer.toBinaryString(pow);// bin. Zaehlung,
    int          y=1    , power=0;               // dez. Rechnung
    for(int      i=0;i<POW.length();i++)         
     {           y=y*y%n; power*=2;              // Potenz-Redukt.
      if        (POW.charAt(i)=='1')
                {y=y*a%n; power+=1;}             // Potenz-Redukt.
     }                                  return y;
   } // power ist redundant und dient nur zur Erlaeuterung 
Beispiel: modPow(5,6,7)=1, POW=110 Binaer-Darstellung von pow=6
      i  POW(i)     y =   a ^ power %   n
   ----  ------  ------------------------
      0       1     1 =   5 ^   0   %   7 
                    5 =   5 ^   1   %   7 
      1       1     4 =   5 ^   2   %   7 
                    6 =   5 ^   3   %   7 
      2       0     1 =   5 ^   6   %   7 
   ----  ------  ------------------------
                    1 =   a ^ pow   %   n
Prinzip: Die binäre Darstellung der Potenz dient nur zur Ablesung der nächsten Multiplikation von 2 auf die Potenz (entspricht Quadrierung des Resultats y=a*..*a) und der nächsten Addition von 1 auf die Potenz (entspricht Multiplikation des Resultats y=a*..*a mit a). Die Multiplikationen und Additionen selbst werden dezimal ausgeführt und jeweils modular reduziert.


   3.3.4  Rabin-Millers probabilistischer Primzahltest

  Zur einfachen Darstellung des Algorithmus beschränken wir uns auf die Zahldarstellung int. Die Klasse BigInteger enthält bereits die Methode p.isProbablePrime(certainty).
  boolean isProbablePrime(int p,int certainty) // p>1, certainty>0
   {final String POW=Integer.toBinaryString(p-1);// bin. Zaehlung,
    for(int      c=1;c<=certainty;c++)           // dez. Rechnung
     {final int  RAND=(int)((p-1)*Math.random()+1);
      int        y=1,        power=0;            // y=modPow 
      for(int    i=0;i<POW.length();i++)         //   (RAND,p-1,n)
       {final                                    
        boolean  TEST= 1<y && y<p-1 ;
                 y=y*y%p;    power*=2;           // Potenz-Redukt.
        if      (TEST && y==1)   {return false;} // Rab.-Mil. Test
        if      (POW.charAt(i)=='1')
                {y=y*RAND%p; power+=1;}          // Potenz-Redukt.
       }
      if        (y!=1)           {return false;} // Fermat's  Test
     }                            return true;   
   } // power ist redundant und dient nur zur Erlaeuterung
Beispiel: isProbablePrime(7,2)=true, POW=110 BinDarst.von p-1=6
      i  POW(i)     y =RAND ^power %   n  
   ----  ------  -----------------------
      0       1     1 =   5 ^    0 %   7
                    5 =   5 ^    1 %   7
      1       1     4 =   5 ^    2 %   7
                    6 =   5 ^    3 %   7
      2       0     1 =   5 ^    6 %   7
   ----  ------  -----------------------
                    1 =RAND ^(p-1) %   p  certainty=1 prob=0.5

      i  POW(i)     y =RAND ^power %   n  
   ----  ------  -----------------------
      0       1     1 =   4 ^    0 %   7
                    4 =   4 ^    1 %   7
      1       1     2 =   4 ^    2 %   7
                    1 =   4 ^    3 %   7
      2       0     1 =   4 ^    6 %   7
   ----  ------  -----------------------
                    1 =RAND ^(p-1) %   p  certainty=2 prob=0.75
Prinzip: Fermats Test auf Primzahleigenschaft (3.1.6) wird durch Potenzierung mit binärer Zählung (3.3.3) ausgeführt und bei jeder modularen Quadrierung außerdem Rabin-Millers Test (3.1.6) durchgeführt. Fällt der Test negativ aus (return false), so ist die Zahl sicher nicht prim! Fällt der Test positiv aus (return true), so ist die Zahl mindestens mit der Wahrscheinlichkeit prob = 1-2^( -certainty) prim. Dieser probabilistische Test ist für große Zahlen die einzige Möglichkeit, auf Primzahleigenschaft zu prüfen, und bietet für große Werte von certainty, z.B. 100, in der Kryptographie praktisch ausreichende Testsicherheit.
Hexen1x1