RSA Verfahren

Einführung

RSA (benannte nach Rivest, Shamir und Adleman) ist ein asymmetrisches kryptographisches Verfahren, das sowohl zum Verschlüsseln als auch zum digitalen Signieren verwendet werden kann (Quelle: http://people.csail.mit.edu/rivest/Rsapaper.pdf). Es verwendet ein Schlüsselpaar, bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder Signieren von Daten verwendet wird, und einem öffentlichen Schlüssel, mit dem man verschlüsselt oder Signaturen prüft. Der private Schlüssel wird geheim gehalten und kann nur mit extrem hohem Aufwand aus dem öffentlichen Schlüssel berechnet werden.

Verfahren

Im folgenden wird das Verfahren anhand eines einfachen Beispiels erklärt:

Bob wählt zwei Primzahlen p = 47 und q = 59 und bestimmt deren Produkt N = 2773. Aus diesen Zahlen werden zwei Schlüssel e = 17 (encryption key) und d = 157 (decrytion key) bestimmt. Die Erzeugung dieser Schlüssel wird im folgenden Kapitel erläutert. Die beiden Zahlen N und e gibt Bob allen, die ihm geheime Botschaften verschicken wollen, bekannt. N und e sind der sog. public key. Die Zahl d , die Bob nicht bekannt gibt ist dann der sog. privat key.

folgendefolgendeQuellfolgendefolgendeQuellQuellQuelle(http://www.inf-schule.de)

Um einen Text, bestehend aus Wörtern zu verschlüsseln, muss man zuerst diese Wörter in eine Folge von Zahlen (z.B. entsprechend seinem ASCII-Code) übersetzen und fassen den gesamten Text zu 4er-Blöcken zusammen. So ergibt sich z.B. für den Klartext K: 0920 1900 0112 1200 ... Nun chiffriert man den ersten 4er Block, nämlich m = 0920, und benutz dabei : c= m^e mod N. Im konkreten Fall ergibt sich somit der Chiffre: 0920¹⁷ mod 2773 = 92017 mod 2773 = 948.Bob erhält diese Nachricht und entschlüsselt sie mit: m = c^d mod N. Er bekommt damit wieder konkret 948157 mod 2773 = 920 (oder als 4er Block 0920).

Der öffentliche Schlüssel (public key) ist also ein Zahlenpaar ( e , N ) und der private Schlüssel (private key) wie beschrieben ebenfalls ein Zahlenpaar ( d , N ) wobei N bei beiden Schlüsseln gleich ist. Man nennt N RSA-Modul, e auch den Verschlüsselungsexponenten und d den Entschlüsselungsexponenten. Diese Zahlen werden durch das folgende Verfahren erzeugt:

Schlüsselerzeugung

1. Wähle zufällig und stochastisch unabhängig zwei Primzahlen p ≠ q . Diese sollen die gleiche Größenordnung haben, aber nicht zu dicht beieinander liegen, so dass der folgende Rahmen ungefähr eingehalten wird: 0,1 < | log 2 ⁡ p − log 2 ⁡ q | < 30.

2. Berechne RSA-Modul: N = p ⋅ q

3. Berechne die Eulersche φ-Funktion von N: φ ( N ) = ( p − 1 ) ⋅ ( q − 1 ).

4. Wähle eine zu φ ( N ) teilerfremde Zahl e , für die gilt 1 < e < φ ( N .

5. Berechne den Entschlüsselungsexponenten d als Multiplikatives Inverses von e bezüglich des Moduls φ ( N ). Es soll also difolgendedifolgendeedifolgendedifolgendeeee folgendes gelten: e ⋅ d ≡ 1 ( mod φ ( N ) )

Die Zahlen p , q und φ ( N ) werden nicht mehr benötigt und können nach der Schlüsselerstellung gelöscht werden. Es ist jedoch relativ einfach, diese Werte aus e, d und N zu rekonstruieren. Aus Effizienzgründen wird e klein gewählt.

Falltürfunktion

Funktionen, bei denen eine Richtung leicht, die andere (Umkehrfunktion) schwierig zu berechnen ist, bezeichnet man als Einwegfunktionen (engl. one-way function). Beispielsweise ist nach aktuellem Wissensstand die Faktorisierung einer großen Zahl, also ihre Zerlegung in ihre Primfaktoren, sehr aufwändig, während das Erzeugen einer Zahl durch Multiplikation von Primzahlen recht einfach und schnell möglich ist.

Konkret basiert diese Falltürfunktion auf der Primfaktorzerlegung. c^d mod N ist leicht zu berechnen: 920¹⁷ mod 2773 = 92017 mod 2773 = 948. Wie wäre es jedoch anders herum? Für welches d gilt 920^d mod 2773 = 948 ?

Ähnlich verhält es sich für die Berechnung von d=(k*phiN(n)+1)/e

Der private Schlüssel d ist leicht zu bestimmen, wenn man die Primfaktoren von φ ( N ) kennt. Ohne die Kenntnis der Primfaktoren von φ ( N ) benötigt es sehr viel Rechenaufwand diese zu bestimmen. Vorsegesetzt die Primfaktoren haben eine gewisse Größe.

square-and-multiply-Verfahren

Um eine Nachricht zu ver- bzw. entschlüsseln rechnet man c= m^e mod N bzw. m = c^d mod N. Für positive ganze Zahlen scheitert die Java-Anweisung int y = Math.pow(g, x) % p; schnell an den großen Potenzen. Schon die Berechnung von 7²³ % 13 erfolgt wegen der 18-stelligen Zwischenergebnisse nicht korrekt. Deshalb muss ein schnelles und besseres Verfahren zur Berechnung von c bzw. m gewählt werden, welches zu große Zwischenergebnisse verhindert (Quelle: Moderne Verfahren der Kryptographie: Von RSA zu Zero-Knowledge Albrecht Beutelspacher, Jörg Schwenk, Klaus-Dieter Wolfenstetter Springer-Verlag, 27.05.2010 S125 ff).

Die binäre Exponentiation (auch Square-and-Multiply genannt) ist eine effiziente Methode zur Berechnung von natürlichen Potenzen. Dieser Algorithmus wurde bereits um ca. 200 v. Chr. in Indien entdeckt und ist in einem Werk namens Chandah-sûtra niedergeschrieben.

Um zunächst m¹³ zu berechnen, kann man sich die Binärdarstellung des Exponenten zunutze machen: 13 = 8 + 4 + 0 + 1 = (1101)₂. Damit lässt sich m¹³ = m^8+4+0+1 = m⁸ * m⁴ * 1 * m¹ = m⁸ * m⁴ * m¹ schreiben, wobei zu beachten ist, dass m² = (m¹)², m⁴ = (m²)² und g⁸ = (g⁴)² ist. Die Binärdarstellung von 13 ist durch die von hinten nach vorne gelesenen Reste in der Kette 13 : 2 = 6 Rest 1, 6 : 2 = 3 Rest 0, 3 : 2 = 1 Rest 1 und 1 : 2 = 0 Rest 1 gefunden. Der normale square-&-multiply-Algorithmus ergibt sich wie folgt: Weil beim Divisionsrest-Verfahren zur Bestimmung der Dualdarstellung des Exponenten x zuerst das niederwertigste Bit gefunden wird, wird beim Multiplizieren mit der kleinsten Potenz m¹ begonnen. Hat die Dualdarstellung eine 0 (keine 1), wird die entsprechende Potenz von m nicht mit in die Multiplikation aufgenommen. Und der ganzzahlige Anteil der Division x: 2 (x ist der Exponent also e bzw. d) wird wieder in der Variablen x gespeichert, sodass im Programm die Variable x immer kleiner wird und das Verfahren bei x=0 endet.

Dieses Verfahren ist schnell (der Aufwand, d.h. die Zahl der Schleifendurchläufe, hängt nur von der Länge der Dualdarstellung des Exponenten ab, also nur von log2(x)). Selbst Exponenten x mit 100 Dezimalstellen würden nur zu leicht machbaren 330 Schleifendurchläufen führen.

Da man bei c= m^e mod N bzw. m = c^d mod N aber nur den Rest der Potenz bezüglich der Division durch N sucht, kann man wegen (a*b)%N = (a%N)*(b%N) % N schon alle Faktoren modulo N nehmen und damit schon alle Zwischenergebnisse angenehm klein halten. Ein N über 100 Dezimalstellen wird der Ganzzahlbereich gesprengt. Im Fall von N bis etwa 46340 reicht die übliche Ganzzahlarithmetik. Für einen Modulus über 46340 enthält die Java Klasse BigInteger eine Implementation des square-&-multiply-Verfahrens mit Modulus in der Methode modPow, die mit BigInteger y = g.modPow(x,p); aufgerufen werden kann.

public static int doSquareMultiply (int basis, int exponent, int modulus)

// basierend auf square-&-multiply-Verfahren, wenn nur Divisions-Rest der Potenz gebraucht wird

{

int ergebnis = 1;

int potenz = basis;

while (exponent > 0)

{

if (exponent % 2 == 1)

{

ergebnis = (ergebnis * potenz) % modulus; // multipliziere, dann davon der Rest

}

potenz = (potenz * potenz) % modulus; // quadriere, dann davon der Rest

exponent = exponent / 2;

}

return (ergebnis); // ergebnis liefert (basis hoch exponent) mod modulus

}