Zahlentheoretische Algorithmen der Kryptografie

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.

Weiter mit: [Primzahltest] oder

Zahlentheoretische Algorithmen der Kryptografie

Modulare Exponentiation

Idee

Programm

Zusammenfassung