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.
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
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)}
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
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.