Man nimmt dazu die Binäre Exponentation, genauer gesagt die binäre Expansion des Exponenten zu Hilfe. Stelle dir den Exponenten als Binärzahl vor, zb. 11 = 01011b.
Dieses Binärzahl ist 4 bits groß wir benötigen also 3 mal modulare Quadrierung + 2 mal eine modulare Multiplikation.
Es gibt nun eine Binäre Exponentation die die Bits des Exponenten von Links nach Rechts abarbeitet, also die Linksorientiere Binäre Exponentation und eine die von Rechts nach Links vorgeht.
2^11 sähe also so aus:
Code:
Bit 3210
2 ^ 1011b
Base = B = 2
Exponent = 1011b
0.) T = B da Bit 3 = 1, ist immer 1
1.) T = T^2 -> 2^2 da Bit 2 = 0 nichts weiter
2.) T = T^2 -> (2^2)^2 da Bit 1 = 1 somit T := T * B -> (2^2)^2 * 2
3.) T = T^2 -> ((2^2)^2 * 2)^2 da Bit 0 = 1 somit T := T * B -> ((2^2)^2 * 2)^2 * 2
5.) T = ((B^2)^2 * B)^2 * B = 2^11 = 2048
Der Schritt 0. ist die Initialization, und Schritte 1-3 sind die Exponentations Schleife die das Höchste Bit des Exponenten nicht mehr berücksichtigt. Sie geht also vom 2. höchsten Bit des Exponenten runter bis auf Bit 0. In Schritt 5. enthält T das Resultat.
Dies wäre die binäre Exponentation, um sie modular zu machen muß nur jede Operation, sprich Quadrierung T := T^2 und T := T * B modular arbeiten also T := T^2 mod N und T := T * B mod N.
Es gibt nun verschiedene Ansätze wie man die Anzahl der Quadrierungen und Multiplikationen bei langen Exponenten verringern kann, d.h. diese Berechnung beschleunigt. Denn bei RSA arbeitet man ja mit Modulen die ca. 1024 Bit groß sind, d.h. Exponenten mit 1024 Bit. Man benötigt also im Durchschnitt 1024 mal modulare Quadierungen und ca. 512 mal modulare Multiplikationen pro Modulare Exponentation.
Die erste Optimierung ist der Montgomery Trick. Statt als die "mod" Operation als Divisionsalgorithmus zu coden, der langsam ist, wird in der Montgomery Domain diese durch Multiplikationen ersetzt.
Die zweite Optimierung ist es den Exponenten nicht Bit für Bit abzuarbeiten, sondern zB. 2 Bits des Expotenten mit einmal abzuarbeiten. Um dies zu können benötigt man eine Tabelle mit allen vorberechneten Exponenten für die Bits 00,01,10,11 also 4 vorberechnete Werte. Dies benötigt 3 Quadrierungen und 2 Multiplikationen. Die Exponentationsschleife arbeitet nun 2 Bits mit einmal ab. Statt 1024 Quadrierungen + 512 Multiplikationen, werden also nur noch 1027 Quadierungen und 258 Multiplikationen benötigt. Eine Quadrierung kann wenn sie clever programmiert wurde ca. 1.5 mal schneller sein als eine Multiplikation. Man könnte statt 2 Bits auch 4 Bits benutzen. Diese Technik nennt sich dann "x Bit Sliding Window" Technik. Es gibt noch viele andere Verfahren.
Eine weitere Optimierung bei RSA von Faktor 4 mal schneller gibt es bei der Entschlüsselung. Statt M := C^D mod N , also Orginalmessage := CipherMessage^DecryptionExponent mod Modulus zu rechnen wird das "Chinese Remainder Theorem" sprich der Chinesische Restesatz angewendet.
Dazu benötigt man aber bestimmte Vorberechnungen, eben die Primzahlen P,Q die N = P * Q bilden und noch einige andere Werte. Durch das CRT wird dann alles 4 mal beschleunigt.
Gruß Hagen