Zum Inhalt springen

Square-and-Multiply

Aus FLBK-Wiki

Beim RSA-Verfahren werden Zahlen mit riesigen Exponenten potenziert. Schritt für Schritt zu multiplizieren würde viel zu lange dauern. Das wiederholte Quadrieren und Multiplizieren kommt mit wenigen Rechenschritten aus.

Definition

Square-and-Multiply (deutsch: wiederholtes Quadrieren und Multiplizieren) ist ein Verfahren, das eine Potenz [math]\displaystyle{ a^x \bmod n }[/math] mit wenigen Multiplikationen berechnet. Es nutzt die Darstellung des Exponenten [math]\displaystyle{ x }[/math] im Dualsystem:

  • Jede 1 in der Dualdarstellung steht für eine Zweierpotenz. Der Exponent ist die Summe dieser Zweierpotenzen.
  • Nach den Potenzgesetzen ist [math]\displaystyle{ a^x }[/math] deshalb das Produkt der Potenzen [math]\displaystyle{ a^1; a^2; a^4; a^8; \dots }[/math], die zu den Einsen gehören.
  • Diese Potenzen entstehen durch fortgesetztes Quadrieren, denn [math]\displaystyle{ \left(a^u\right)^2 = a^{2u} }[/math].

Nach jeder Rechnung wird der Rest modulo [math]\displaystyle{ n }[/math] gebildet, damit die Zahlen klein bleiben (siehe Rechenregeln).

Die Rechnung wird in einer Tabelle geführt, der Belegungstabelle. Sie hat für jedes Bit des Exponenten eine Zeile, beginnend mit dem Bit ganz rechts.

  1. Den Exponenten ins Dualsystem umrechnen und die Bits von rechts nach links untereinander schreiben.
  2. Spalte Quadrat: In der ersten Zeile steht [math]\displaystyle{ a \bmod n }[/math]. In jeder weiteren Zeile steht das Quadrat des Wertes darüber, modulo [math]\displaystyle{ n }[/math]. So entstehen der Reihe nach [math]\displaystyle{ a^1; a^2; a^4; a^8; \dots }[/math]
  3. Spalte Zwischenergebnis: Steht in der Zeile das Bit 1, wird das bisherige Zwischenergebnis mit dem Quadrat dieser Zeile multipliziert, modulo [math]\displaystyle{ n }[/math]. Beim ersten Bit 1 ist das Zwischenergebnis das Quadrat selbst. Steht in der Zeile das Bit 0, bleibt das Zwischenergebnis unverändert.
  4. Das letzte Zwischenergebnis ist [math]\displaystyle{ a^x \bmod n }[/math].

Die zweite Form arbeitet die Bits von links nach rechts ab und braucht nur ein Zwischenergebnis:

  1. Mit dem Zwischenergebnis 1 beginnen.
  2. Für jedes Bit, beginnend ganz links: das Zwischenergebnis quadrieren.
  3. Ist das Bit 1, zusätzlich mit [math]\displaystyle{ a }[/math] multiplizieren.
  4. Nach jedem Schritt den Rest modulo [math]\displaystyle{ n }[/math] bilden.

Beide Formen liefern dasselbe Ergebnis.

Aufwand

Hat der Exponent in der Dualdarstellung [math]\displaystyle{ t }[/math] Bit, braucht das Verfahren [math]\displaystyle{ t - 1 }[/math] Quadrierungen und für jede weitere 1 nach der ersten eine Multiplikation. Das sind zusammen höchstens [math]\displaystyle{ 2 \cdot (t - 1) }[/math] Rechenschritte, denn auch jede Quadrierung ist eine Multiplikation. Wer dagegen [math]\displaystyle{ a }[/math] immer wieder mit sich selbst multipliziert, braucht [math]\displaystyle{ x - 1 }[/math] Multiplikationen.

Der Aufwand wächst also nur mit der Länge des Exponenten in Bit und nicht mit seinem Wert. Erst dadurch lassen sich Potenzen mit den riesigen Exponenten des RSA-Verfahrens überhaupt berechnen.

Umsetzung in Java

Die Methode arbeitet von rechts nach links. Das letzte Bit des Exponenten liefert exponent % 2, die Division durch 2 entfernt es.

public static long potenzMod(long basis, long exponent, long modul) {
    long ergebnis = 1;
    long quadrat = basis % modul;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            ergebnis = ergebnis * quadrat % modul;
        }
        quadrat = quadrat * quadrat % modul;
        exponent = exponent / 2;
    }
    return ergebnis;
}

Der Datentyp long ist nötig, weil das Produkt zweier Zahlen kleiner als der Modul nicht mehr in ein int passen muss. Für Moduln in der Größe echter Schlüssel reicht auch long nicht. Dafür gibt es in Java die Klasse BigInteger.

Beispiele

Potenz mit der Belegungstabelle berechnen

Gesucht ist [math]\displaystyle{ 5^{23} \bmod 133 }[/math]. Der Exponent im Dualsystem: [math]\displaystyle{ 23 = 16 + 4 + 2 + 1 = 10111_2 }[/math]. Damit gilt [math]\displaystyle{ 5^{23} = 5^{16} \cdot 5^{4} \cdot 5^{2} \cdot 5^{1} }[/math].

Bit Potenz Quadrat mod 133 Zwischenergebnis mod 133
1 [math]\displaystyle{ 5^{1} }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ 5 }[/math]
1 [math]\displaystyle{ 5^{2} }[/math] [math]\displaystyle{ 5^{2} = 25 }[/math] [math]\displaystyle{ 5 \cdot 25 = 125 }[/math]
1 [math]\displaystyle{ 5^{4} }[/math] [math]\displaystyle{ 25^{2} = 625 \equiv 93 }[/math] [math]\displaystyle{ 125 \cdot 93 = 11625 \equiv 54 }[/math]
0 [math]\displaystyle{ 5^{8} }[/math] [math]\displaystyle{ 93^{2} = 8649 \equiv 4 }[/math] –
1 [math]\displaystyle{ 5^{16} }[/math] [math]\displaystyle{ 4^{2} = 16 }[/math] [math]\displaystyle{ 54 \cdot 16 = 864 \equiv 66 }[/math]

Das letzte Zwischenergebnis ist das Ergebnis: [math]\displaystyle{ 5^{23} \bmod 133 = 66 }[/math].

Die Bits des Exponenten werden jetzt von links nach rechts abgearbeitet, das Zwischenergebnis beginnt mit 1:

Bit quadrieren mod 133 bei Bit 1 mit 5 multiplizieren mod 133
1 [math]\displaystyle{ 1^{2} = 1 }[/math] [math]\displaystyle{ 1 \cdot 5 = 5 }[/math]
0 [math]\displaystyle{ 5^{2} = 25 }[/math] –
1 [math]\displaystyle{ 25^{2} = 625 \equiv 93 }[/math] [math]\displaystyle{ 93 \cdot 5 = 465 \equiv 66 }[/math]
1 [math]\displaystyle{ 66^{2} = 4356 \equiv 100 }[/math] [math]\displaystyle{ 100 \cdot 5 = 500 \equiv 101 }[/math]
1 [math]\displaystyle{ 101^{2} = 10201 \equiv 93 }[/math] [math]\displaystyle{ 93 \cdot 5 = 465 \equiv 66 }[/math]

Auch hier ist [math]\displaystyle{ 5^{23} \bmod 133 = 66 }[/math].

Aufwand vergleichen

Für [math]\displaystyle{ 5^{23} \bmod 133 }[/math] genügen 4 Quadrierungen und 3 Multiplikationen. Wer 5 Schritt für Schritt mit sich selbst multipliziert, braucht 22 Multiplikationen.