Netzwerk-Know-how (tecCHANNEL COMPACT) Kapitel 12: RSA im Detail

Veröffentlicht: 13. Jul 2005

Von PROF. DR. STEPHAN EULER

RSA im Detail

Ausgangspunkt ist die Eulersche φ-Funktion (engl. totient function). Für eine natürliche Zahl n bezeichnet φ(n) die Anzahl von Zahlen kleiner n, die teilerfremd zu n sind. Teilerfremd bedeutet, dass zwei Zahlen keinen gemeinsamen ganzzahligen Faktor enthalten. Als Beispiel betrachten wir die Zahl 10 mit den beiden Faktoren 2 und 5. Dann ergibt φ(10)=4, da nur die Zahlen 1,3,7 und 9 teilerfremd zu 10 sind. Alle anderen Zahlen enthalten ebenfalls einen der beiden Teiler.

Für zwei natürliche Zahlen a und m, die ebenfalls teilerfremd sind, gilt der Satz von Euler (auch als Satz von Euler-Fermat bezeichnet)

wobei die Modulo-Funktion mod den Rest bei ganzzahliger Division angibt. Gleichung (14.1) besagt demnach, dass bei der Division

der Rest 1 übrig bleibt. Anders formuliert, es gibt eine natürliche Zahl L, die die Bedingung

erfüllt. Der Exponent kann mit einer weiteren natürlichen Zahl k in der Form

erweitert werden. Die Gleichheit lässt sich mit der Rechenregel

leicht zeigen. Ausführlich geschrieben erhält man

und nach 14.4

Nach dem Satz von Euler sind die Exponenten alle gleich 1, so dass sich in der Tat 14.3 auf a mod m reduziert.

Der Ausdruck k • φ(m) kann als 1 mod φ(m) gelesen werden. Bei der ganzzahligen Division durch φ(m) bleibt gerade der Rest 1 übrig. Im RSA-Algorithmus werden daher die Zahlen e und d genau so gewählt, dass sie die Bedingung e • d = 1 mod φ(m) erfüllen. Damit stellen sich zwei Probleme:

• Welchen Wert hat φ(m)?
• Wie kann bei gegebenen e der Wert von d berechnet werden?

Für beliebige Werte von n ist die Berechnung von φ(n) zeitaufwendig. Allerdings gibt es einige Sonderfalle. Insbesondere gilt für jede Primzahl p die Regel φ(p) = p -1, denn eine Primzahl enthält per Definition keine ganzzahligen Faktoren. Weiterhin lässt sich zeigen, dass für das Produkt zweier Primzahlen p und q die einfache Beziehung

gilt. Wenn man also m als Produkt zweier Primzahlen wählt, so reduziert sich die Berechnung von φ(m) auf die Multiplikation zweier Zahlen. Bleibt die Bestimmung von d. Es gilt

und damit

Es gilt dann, zwei ganze Zahlen d und k zu finden, die diese Beziehung erfüllen. Die Zahl k hat für RSA keine Bedeutung, aber d ist der gesuchte private Schlüssel. Die Lösung von (14.9) basiert auf dem Euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers (ggT) zweier Zahlen.

Berechnet wird die größte ganze Zahl, die beide Zahlen ohne Rest teilt. Das Verfahren beruht darauf, dass ein gemeinsamer Teiler d zweier Zahlen x und y auch deren Differenz teilt:

Da sowohl kx als auch ky ganze Zahlen sind, ist auch die Differenz wieder eine ganze Zahl. Um den ggT zu ermitteln, werden im Euklidischen Algorithmus iterativ Differenzen gebildet, wobei immer der kleinere Wert vom größeren abgezogen wird. Das neue Zahlenpaar x - y, y hat auf Grund von (14.10) wieder den gleichen ggT Irgendwann wird ein Wert 0 erreicht und der verbleibende Wert ist dann der ggt von x und y. Man kann das Verfahren beschleunigen, in dem man den kleineren Wert in einem Schritt so oft wie möglich abzieht und nur den verbleibenden Rest weiter verwendet. Dies entspricht wiederum einer Modulo-Operation. Eine beispielhafte Implementierung als Methode in Java hat folgende Form:

public static int ggt(int x, int y ) {
if( y > x ) return ggt( y, x); // x > y sichern while( y
> 0 ) {
System.out.printin( "x,y = " + x + " " + y);
int r = x % y;
x = y;
y = r;
}
return x;
} 
Mit den Werten 696 und 532 als Beispiel ergibt sich
x,y = 696#160; #160; 532
x,y = 532#160; #160; 164
x,y = 164#160; #160; 40
x,y = 40#160;4
ggT = 4

Die Methode berechnet in 5 Iterationen den ggT 4. In jedem Schritt wird der alte Wert von y nach x geschoben. Als neuer Wert für y wird der Rest der Division x/y eingesetzt. Dieser Rest kann damit in der Form x-k-y geschrieben werden, wobei k das Ergebnis der ganzzahligen Division von x durch y ist. Betrachten wir die Folge der entstehenden Restwerte. Der erste Wert ist

Dann berechnet sich der zweite Wert als

Der Wert y2 kann als eine Summe der Form a•x+b•y geschrieben werden. Die Koeffizienten a und b entstehen durch Addition und Multiplikation von ganzen Zahlen und sind damit selbst auch wiederum ganze Zahlen.

Diese Argumentation lässt sich auf die weiteren Restwerte verallgemeinern, so dass insbesondere auch für den letzten Restwert - den ggT - die Darstellung

resultiert. Damit haben wir den Ansatz zur Lösung der Beziehung (14.9). Wir haben e so gewählt, dass der ggT von e und φ(m) gerade den Wert 1 hat. Damit ist sicher gestellt, dass ganzzahlige Lösungen für d und k existieren. Die tatsächlichen Werte lassen sich mit einer Erweiterung des Euklidschen Algorithmus bestimmen. Im Prinzip wird dabei die oben skizzierte Berechnung der Koeffizienten aus den Vorgängerwerten vorgenommen.

Insgesamt ist damit ein einfacher Weg zur Berechnung des privaten Schlüssels eröffnet. Die Funktion φ(m) wird als einfaches Produkt zweier Zahlen berechnet und dann kann mit dem erweiterten Euklidschen Algorithmus aus φ(m) und dem öffentlichen Schlüssel e der private Schlüssel d berechnet werden.

Zum Seitenanfang

Implementierung

Nach der Darstellung der mathematischen Grundlagen sollen noch einige Aspekte der Implementierung betrachtet werden. Dazu dient die in Java realisierte Klasse RSADemo. Beim Aufruf kann man die Werte für p, q und e vorgeben. Das Programm berechnet dann das zugehörige d und bestimmt für alle Zeichen den verschlüsselten Wert. Die Implementierung des erweiterten Euklidschen Algorithmus verwendet eine rekursive Methode erweiterter Euklid. Diese Methode ruft sich immer wieder auf, bis der ggT erreicht ist. Dann werden davon ausgehend die Werte von u und v ermittelt.

Eine praktische Schwierigkeit besteht in der Berechnung der Potenzen. Zur Verschlüsselung muss die Potenz

berechnet werden. Die direkte Berechnung führt schnell zu einem Überlauf durch zu große Zahlen. Glücklicherweise gibt es eine einfache Methode, den Überlauf zu vermeiden. Betrachten wir dazu die Darstellung

bei der M in ein ganzzahliges Vielfaches von n und den Rest r aufgespalten wird. Dann gilt

Der erste Summand ist wiederum ein ganzzahliges Vielfaches von n und spielt damit bei der Modulo-Bildung keine Rolle. Nutzt man weiterhin die Beziehung r=M mod n, so kann man schreiben

Die Berechnung von Me lässt sich damit auf die Bestimmung von r = M mod n und Me-1 zurückführen. Die gleiche Argumentation kann auf die Auswertung von Me-1 angewandt werden. Insgesamt ergibt sich dann eine Folge von Multiplikationen und Restwertbildungen, bei denen die Zahlenwerte im darstellbaren Bereich bleiben. Die Methode aHochbModn stellt eine entsprechende Implementierung dar. Es sei angemerkt, dass die Berechnung wesentlich beschleunigt werden kann, wenn man anstelle der fortgesetzten Multiplikation mit Quadrieren arbeitet. Die Anzahl der benötigten Rechenoperationen wächst dann nur noch linear mit der Anzahl der Bits des Exponenten.

public class RSADemo
{
public static int u, v;

private static int erweiterterEuklid(int a, int b) {
int g ;
if (b==0) {
g=a;
u=1;
v=0;
} else {
g = erweiterterEuklid(b, a%b);
int t=u-a/b*v;
u=v;
v=t;
} return g;
}

public static int aHochbModn( int a, int b, int n ) {
int res = a % n;
for( int i=0; i < b-1; i++ ) {
res = (res * a) % n;
}
return res;
}

public static void main( String[] args) {
int p = 17;
int q = 11;
int e = 9;

for( int i=0; i < args.length; i++ ) {
if( args[i].equals("-p") ) {
p = Integer.parselnt( args[++i] );
} else if( args[i].equals("-q") ) {
q = Integer.parselnt( args[++i] );
} else if( args[i].equals("-e") ) {
e = Integer.parselnt( args[++i] );
} else {
System.out.println("unknown 
Argument: ?args[i]);
System.exit(1);
}
}
int n = p*q;
int ggt = erweiterterEuklid( (p-l)*(q-l), e);
System.out.println( "ggt = " + ggt);
if( ggt != 1 ) {
System.out.print( "e="+e+" und (p-1)*(q-1)="+ ?(p-1)*(q-1) );
System.out.printin( " sind nicht teilerfremd!"); 
System.exit(1);
}
System.out.println( "u,v: " + u + " " + v);
int d = v;
if( d < 0 ) d += (p-1)•(q-1); // negative Werte korrigieren
// Schleife über alle Zeichen
for( int m = 0; m < n; m++ ) {
System.out.print( "Zeichen = " + m);
int c = aHochbModn( m, e, n );
System.out.print( " G = " + c);
System.out.println( " D = " + aHochbModn(c,d,n) )
}
}
}

© www.tecCHANNEL.de

Zum Seitenanfang

| Home | Technische Artikel | Community