Public-Key ... schnelle Exponention

[Meisterschmied]

Abend Allerseits,

kann mir jemand, der schon mal die sog. "schnelle Exponention" programmiert hat, wie man sie z. B. für Cryptprogramme braucht (also Public-Key-Verfahren (RSA)), verraten, wie er das getan hat. Ist auch bekannt unter fortlaufende Exponention, um zum Beispiel folgende Rechnung

a^123.390.234 mod n = x

zu lösen.

Als Delphi-Code sähe das so aus, nur mag er das nicht:

 x := IntPower(a,123.390.234) mod n; Danke!

MfG

Meisterschmied

[Chewie]

Lass mal die 3er-Trennzeichen (Punkte) weg

[Meisterschmied]

Danke, isses aber gar nicht. Hast zwar recht, aber der Code war jetzt gerad nur hingeschludert War ja nur ein Beispiel, für das was ich meine. Trotzdem die Änderung:

 x := IntPower(5,129384921) mod n;

[negaH]

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

[Meisterschmied]

Danke, das war ja schon recht eindeutig. Aber wie zählst du die Bits in deinem Code (3. Bit = 1?) und warum ist der Exponent 1011b? Und noch mal kurz zum Verständnis: Egal ob das Bit 0 oder 1 ist, T wird bei jedem Schritt quadriert, dagegen wird T auch noch verdoppelt, wenn das Bit 1 ist, bzw. es bleibt so wie es ist, wenn das Bit 0 ist. Richtig?

Vielen Dank übrigens für die ausführliche Antwort . Is hier echt das beste Forum, was ich kenne

Thanks,
Meisterschmied

[negaH]

Zitat:

Danke, das war ja schon recht eindeutig. Aber wie zählst du die Bits in deinem Code (3. Bit = 1?)

Dies hängt von der Darstellung der großen Integer in deinem Code ab. In meinem Code sind die Zahlen linear im Speicher gespeichert. D.h. $123456789ABCDEF0123456789ABCDEF steht im Speicher EF CD AB 89 67 45 23 01 EF CD AB 89 67 45 23 01 also in Little Endian. Somit ist es nun einfach die gesetzten Bits zu ermitteln, zB. mit der Assembleranweisung BT = BitTest.

Zitat:

und warum ist der Exponent 1011b?

1011 ist binär die dezimale Zahl 11. Das abschließende "b" zeigt an das die Zahl binär dargestellt wurde und nicht "h" hexadezimal oder "d" dezimal oder "o" oktal.

Zitat:

Und noch mal kurz zum Verständnis: Egal ob das Bit 0 oder 1 ist, T wird bei jedem Schritt quadriert, dagegen wird T auch noch verdoppelt, wenn das Bit 1 ist, bzw. es bleibt so wie es ist, wenn das Bit 0 ist. Richtig?

Hm, weiß ich doch nicht ?!? Spaß beiseite, du solltest dich jetzt in die Mathematik und Computeralgebra einarbeiten. D.h. du musst verstehen was Zahlensysteme wie Hexadeziaml und Binär bedeuten, wie Computer Zahlen verarbeiten und speichern, und eben einfach mal die Formel ((B^2)^2 * B)^2 * B mathematisch/algorithmisch analysieren. Dann wirst du sehen das bei einer Rechts nach Links, bzw. Oben nach Unten Bitauswertung des Exponentens das oberste gesetze Bit ignoriert wird und anschließend exakt Ln2(Exponent) -1 mal eine Quadierung und Hammingweight(Exponent) -1 mal eine Multiplikation fällig wird. Hammingweight() ist die Anzahl der auf 1 gesetzten Bits einer Zahl.

Zitat:

dagegen wird T auch noch verdoppelt, wenn das Bit 1 ist

Falsch, T wird mit der Basis multipliziert. Will man 2^y mod z ausrechnen, dann und nur dann wird T verdoppelt. Wird aber x^y mod z dann wird T ver'x'facht.


Ganz wichtig ist es, und das meine ich nicht abwertend oder überheblich, für solche Programmierungen zu wissen was der Computer und der Algorithmus macht. Du musst dir also unbedingt bestimmtes Grundlagenwissen aneigenen.

Dazu empfehle ich dir das Buch "Handbook of Applied Cryptography" von Menezes, van Oorschot, Vanstone ISBN 0-8493-8523-7.

Man könnte auch auf Donald Knuths Standardwerk "The Art of Computer Programming" Kapitel 4 "Arithmetic" hinweisen, ich persönlich finde es aber nicht ausreichend und veraltet. Trotzdem will ich's hier nicht verschweigen, da öfters an anderen Stellen darauf hingewiesen wird.

Gruß Hagen

[Meisterschmied]

Danke! Ich sehe, es gibt noch viel zu tun Ist doch zumindest schon mal ein Ansatzpunkt. Auf jeden Fall besten Dank, werd mich mal weiter umgucken. Hört sich recht vielversprechend an

Danke, das du dir die Zeit genommen hast .

Beste Grüße,
Meisterschmied

[negaH]

Eines noch, entscheidend ist es das bei der Modularen Exponentation bei jedem Zwischenschritt sofort modular reduziert wird. Einfach IntPower(2, $1234567890ABCDEF) mod N kann nicht funktionieren da
1.) 2^$1234567890ABCDEF gerechnet wird und
2.) erst dann mod N reduziert wird.

Der 1. Schritt würde eine so große Zahl erzeugen das sie nicht mehr exakt in einer Fließkommazahl darstellbar ist.

Bei der Implementation von RSA wird aber eine auf's Bit genaue Berechnung benötigt. Fließkommazahlen sind als schwachsinnig für eine RSA Berechnung.
Desweiteren sollte der Modulus N ca. 1024 Bits haben, sprich ca. 2^1024 groß sein, nur dann kann man RSA als technisch sicher bezeichnen. Da der Exponent bestenfalls zufälig gewählt wurde hiese dies das selbst dieser ca. 1024 Bit groß ist.

Mit IntPower() oder den Delphi Bordmitteln kann man also kein RSA umsetzen.

Gruß hagen