Nun gut, hinter dem Begriff verbirgt sich nichts Aufregendes, ist im Grunde ganz simpel. Wenn Du in der Schule Schwerpunkt Mathe hast wirst Du das Rechnen in unendlichen Ringen oder Körpern schon gewohnt sein (N,Z,...). Neben diesen Systemen gibt es noch sog. "Restklassenringe" (geschrieben mit dem Formelsymbol des verwendeten Zahlensystems plus einem Wert im Index rechts unten). Diese Systeme unterscheiden sich von den normalen Rechensystemen insofern, als dass jede ausgeführte Operation modulo n reduziert wird (vergleichbar mit Überläufen von Variablen), wobei n den Modul des entsprechenden Restklassenringes darstellt. Rechnen wir beispielsweise in Z13, so liegen alle Ergebnisse unserer arithmetischen Operationen im Bereich von 0-12 (analog zur schriftlichen Division kann der Teilungsrest nie größer sein als der Divisor). In solchen Systemen ist es unter gewissen Voraussetzungen möglich mit den bereits vielfach genannten "multiplikativen Inversen" zu rechnen. Ein einfaches Beispiel: Rechnen wir in Z14 (n=14), nehmen ein a=3 und ein dazu inverses b=5, dann ergibt
4 * 3 mod 14 = 12
12 * 5 mod 14 = 4
3 * 5 mod 14 = 1
Wie man sieht ergibt die Rechnung mit einer Beispielzahl 4 die Zahl 12 (sozusagen die verschlüsselte 4), eine weitere Rechnung mit dem zu 3 inversen Multiplikativen 5 ergibt wieder 4. Eine Multiplikation von von a und b resultiert in der Zahl 1. Das ist eigentlich der ganze Zauber des RSA-Algorithmus (genauer gesagt verwendet der RSA-Algorithmus keine Multiplikationen sondern modulare Potenzierungen). Um solche inversen Multiplikativen zu erzeugen ist als wichtige Bedingung zunächst die Teilerfremdheit von a und n zu beachten (ggT(a,n)=1, hier wäre der Begriff "relativ prim" anzuwenden). Um zu einem gewählten a ein passendes b zu generieren gibt es nun verschiedene Möglichkeiten. Einmal kann man den Satz von Fermat in Verbindung mit der Eulerschen Phi-Funktion verwenden (Phi(n) bezeichnet sämtliche zu n teilerfremden Zahlen < n ). Da gilt a^Phi(n)=1 mod n (man sagt auch a^Phi(n) ist kongruent zu 1 modulo n) lässt sich über a^(Phi(n)-1) mod n ein entsprechendes Inverses zu a finden. Ein Beispiel:
a = 3 , n = 17
Phi(n)=16
a^15 mod 17 = 6
Test:
4 * 3 mod 17 = 12
12 * 6 mod 17 = 4
---
In der Praxis ist diese Methode allerdings unüblich, da sie eine modulare Potenzierung erfordert, was viel Rechenzeit kostet. Gebräuchlicher hingegen ist der sog. "erweiterte euklidische Algorithmus". Um ihn zu verstehen sollte man zunächst die normale Variante, also den "euklidischen Algorithmus" betrachten, der dazu dient den größten gemeinsamen Teiler zweier Zahlen zu finden. Dabei gilt folgende Vorgehensweise:
ggT(a1,a2)
a1 = a2*q1 + a3 0<=a3<a2
a2 = a3*q2 + a4 0<=a4<a3
a3 = a4*q3 + a5 0<=a5<a4
...
am-1 = am*qm-1 0<=am<am-1
ggT(a1,a2)=am
---
Was hier getan wird ist solange zu dividieren bis schliesslich kein Rest mehr auftaucht (was spätestens bei der Division durch 1 der Fall ist). Zunächst rechnet man also a1/a2 und erhält so q1, dann wird a1 mod a2 gerechnet und somit a3 festgestellt. Den Quotienten aus der ersten Division (bzw. den Dividenden, falls der größer als der Quotient sein sollte) verwendet man nun in der zweiten Rechnung und dividiert mit dem oben erhaltenen Rest. So wird fortgefahren bis kein Rest mehr zurückbleibt. Ein Beispiel:
ggT(23,47):
23 = 0 * 47 + 23
47 = 2 * 23 + 1
23 = 23* 1
Wie man sieht ist der ggT von 23 und 47 = 1. Stellt man die oben geschriebenen Gleichungen nun um, so dass aus
(1)am-2 = am-1*qm-2 + a m
(2)am = am-2 - am-1 * qm-2
wird, fährt so fort wobei man weiterhin
(3)am-1 = am-3 - am-2*qm-3
erhält, so kann man in Gleichung 2 den Wert am-1 durch die rechte Seite der Gleichung 3 ersetzen, wobei sich
(4)am= am-2 - qm-2 * (am-3 - am-2*qm-3)
ergibt. Wenn sich am = 1 ergibt benutzt man die vorher gewonnenen Faktoren, die eingesetzt werden und somit eine Gleichung der Form 1 = a*u + b*v ergeben. Aus diesen Faktoren lässt sich dann das multiplikative Inverse ausrechnen. Ein Beispiel für den RSA-Algorithmus:
p=11 q=7 n=77 Phi(n)=(p-1)(q-1) <=> 60
a=13 b=?
Beginnen wir jetzt mit dem euklidischen Algorithmus zur Berechnung des ggT(13,60):
13 = 0*60 + 13
60 = 4*13 + 8
13 = 1*8 + 5
8 = 1*5 + 3
5 = 1*3 + 2
3 = 2*1 + 1
2 = 2*1
Interessant ist für uns lediglich die vorletzte Gleichung. Jetzt formen wir der Reihe nach um, so dass der Divisionsrest jeweils links steht:
1:1 = 3 - 2 * 1
2:2 = 3 - 3 * 1
3:3 = 8 - 5 * 1
4:5 =13 - 1 * 8
5:8 =60 - 4 *13
Jetzt benutzen wir jeweils die nachfolgende Gleichung und setzen zunächst 2 in 1 ein, erhalten somit 1', setzen 3 in 1' ein und fahren so fort bis wir die beiden Orginalzahlen 13 und 60 mit 2 Linear-Faktoren erhalten:
1':1=3-5+3 <=> 1 = 2*3 -5
2':1=2*8-2*5-5 <=> 1 = 2*8 - 3*5
3':1=2*8-3*13+3*8 <=> 1 = 5*8-3*13
4':1=5*60-20*13-3*13 <=> 1 = 5*60 - 23*13
Unsere letzte Gleichung hat also die Form 1 =a*u + b*v, wobei u = 5 und v = -23.
Rechnen wir nun 23 * 13 mod 60 = 59 so stellt man fest, dass 23 nicht das inverse Multiplikative sein kann. Rechnen wir also (60+(-23)) * 13 mod 60 = 1 und haben damit b = 37. Analog könnten wir Fermats Satz benutzen und b durch a^(Phi(n)-1) mod n berechnen. Da Phi(60)=48 ergibt a^47 mod 60 =37.
Jetzt wo wir ein inverses Paar a=13<>b=37 haben können wir entweder mit p * a mod Phi(n) = c , c * b mod Phi(n) = p
oder mit p^a mod n = c, c^b mod n = p rechnen. Die zweite Variante ist beim RSA-Algorithmus natürlich die einzig sinnvolle, da unter Veröffentlichung von Phi(n) leicht inverse Paare von jedem berechnet werden könnten. Ich empfehle wie gesagt das Buch "Kryptographie in C und C++", da dort viele hier verwendeten Algorithmen erklärt und eine Reihe Verweise zu weiteren Materialien genannt werden.
Hier noch eine C-Funktion die den Zweck der Findung eines solchen Inversen erfüllen sollte:
----
int ggt_inv(int a, int n)
{
int residue=0;
int g=0;
int q=0;
int t3=0;
int t1=0;
int v1=0;
int v3=0;
int u=1;
g=a;
v3=n;
START:
q=g/v3;
t3=g%v3;
t1=u-q*v1%n;
u=v1;
g=v3;
v1=t1;
v3=t3;
if (v3>0)
{
goto START;
}
return u;
}
----
[Dieser Beitrag wurde von File Overkill am 01. Januar 2001 um 17:24 editiert.]