Modulare Exponentiation

Die modulare Exponentiation spielt allgemein in der Kryptografie eine große Rolle. Im RSA-Verfahren beispielsweise besteht die Chiffrierung in der Berechnung von m^e mod n. Hierbei sind m, e und n sehr große Zahlen (typischerweise 512 oder 1024 Bit lang).

Um m^e mod n zu berechnen, sind zum Glück nicht e Multiplikationen von m mit sich selbst erforderlich. Schon bei einer Länge von e von nur 50 Bit wären dies eine Billiarde Multiplikationen.

Tatsächlich genügen weniger als 2 log(e) Multiplikationen, also weniger als 100 bei einem 50-Bit-Exponenten.

Ausgangspunkt ist die Auswertung der Binärdarstellung des Exponenten nach dem Horner-Schema.

So wird beispielsweise die Binärdarstellung 1101 nach dem Horner-Schema wie folgt ausgewertet:

((((0) · 2 + 1) · 2 + 1) · 2 + 0) · 2 + 1 = 13

Daraus ergibt sich unmittelbar das Verfahren zur Exponentiation, hier also zur Berechnung von m¹³:

m^{((((0) · 2 + 1) · 2 + 1) · 2 + 0) · 2 + 1} = m¹³

Unter Anwendung der Regeln für die Potenzrechnung ergibt sich somit

((((m⁰)² · m¹)² · m¹)² · m⁰)² · m¹ = m¹³

Zur Auswertung einer k-Bit-Binärzahl sind k Multiplikationen mit 2 und k Additionen erforderlich (bzw. sogar weniger Additionen, wenn die Addition von 0 weggelassen wird). Entsprechend sind für die Exponentiation nach diesem Verfahren bei einem k-Bit-Exponenten k Quadrate und k Multiplikationen erforderlich (bzw. sogar weniger Multiplikationen, wenn die Multiplikation mit m⁰ = 1 weggelassen wird).

Die folgende Gegenüberstellung zeigt das Programm zur Auswertung einer binär dargestellten Zahl e der Länge k nach dem Horner-Schema sowie das entsprechende Programm zur Exponentiation einer Zahl m mit dem Exponenten e.

int s=0;
for (int i=k-1; i>=0; i--)
{
    s=s*2;
    if (e[i]==1)
        s=s+1;
}

int s=1;
for (int i=k-1; i>=0; i--)
{
    s=s*s;
    if (e[i]==1)
        s=s*m;
}

Aus dem zweiten dieser Programme ist das folgende Programm zur modularen Multiplikation beliebig großer Zahlen (Java-Typ java.math.BigInteger) abgeleitet. Nach jeder Multiplikation wird das Zwischenergebnis modulo n reduziert.

Funktion modexp

Eingabe:

Zahl m, Exponent e, Modul n

Ausgabe:

m^e mod n

Methode:

BigInteger modexp(BigInteger m, BigInteger e, BigInteger n)
{
    int k=e.bitLength();
    BigInteger s=BigInteger.ONE;
    for (int i=k-1; i>=0; i--)
    {
        s=s.multiply(s).mod(n);
        if (e.testBit(i))
            s=s.multiply(m).mod(n);
    }
    return s;
}

Die schnelle modulare Multiplikation ist von fundamentaler Bedeutung in der Kryptografie, so etwa für RSA-Verschlüsselung und -Signatur, Diffie-Hellman-Schlüsselvereinbarung, aber auch für den Miller-Rabin-Primzahltest.

Das hier dargestellte Verfahren zur schnellen modularen Exponentiation m^e mod n erfordert O(log e) Multiplikationen und Reduktionen modulo n, d.h. die Zeitkomplexität verhält sich höchstens linear zur Länge des Exponenten in Bit.

Eine Variante des Verfahrens zur schnellen modularen Exponentiation arbeitet die Binärdarstellung beginnend beim letzten Bit ab.

Für den Miller-Rabin-Primzahltest wird das hier angegebene Verfahren benutzt, da es in der Variablen s die dort benötigte Folge von Quadratzahlen modulo n (sogenannte quadratische Reste) erzeugt.

Weiter mit: [Primzahltest] oder

Modulare Exponentiation

Idee

Programm

Zusammenfassung