Arithmetik

Montgomery-Multiplikation

In der Kryptografie ist die modulare Exponentiation ai mod n eine häufige Rechen­operation. Realisiert wird die modulare Exponentiation durch das schnelle Square-and-Multiply-Verfahren, bei dem aber dennoch viele modulare Multi­plikationen der Form a·b mod n erforderlich sind. Dabei sind die beteiligten Zahlen sehr groß, z.B. 1024 Bit lang. Die Reduktion modulo n verlangt normalerweise eine Division; diese ist bei großen Zahlen sehr aufwendig.

Die Montgomery-Multi­plikation [Mont 85] ist ein Verfahren zur modularen Multi­plikation, bei dem nur in einer Vorbereitungs­phase eine Reduktion modulo n erforderlich ist. Anschließend sind nur Multi­plikationen und Additionen erforderlich sowie außerdem div- und mod-Operationen mit einer Zweierpotenz m. Bei binärer Zahlen­darstellung sind aber diese beiden letzteren Operationen sehr einfach zu realisieren.

Bei der Montgomery-Multi­plikation wird nicht im Ring ℤn gerechnet, sondern in einem isomorphen Ring. Hierdurch ist es möglich, die Reduktion modulo n durch die erwähnten leichteren Operationen mit der Zweierpotenz m zu ersetzen.

Grundlagen

Die Menge ℤn = {0, ..., n-1} bildet mit den Ver­knüpfungen Addition modulo n und Multi­plikation modulo n sowie den neutralen Elementen 0 bzw. 1 einen Ring mit Eins:

R  =  (ℤn, +n, ·n, 0, 1)

Die Ver­knüpfungen +n und ·n bedeuten Addition modulo n und Multi­plikation modulo n.

Bei der Montgomery-Multi­plikation wird ein zu R isomorpher Ring S verwendet. Die Abbildung h von R nach S ist wie folgt definiert:

h(a)  =  a·m mod n

für alle a ∈ R. Hierbei ist m eine Zweierpotenz größer als n.

Damit ergibt sich der Ring S als

S  =  (ℤn, +n, ⊙, 0, e)

Die Ver­knüpfungen in S sind Addition modulo n sowie folgende speziell definierte Multi­plikation ⊙. Für alle Elemente x, y ∈ S ist

x ⊙ y  =  x · y · m-1 mod n

Offenbar ist diese Multi­plikation assoziativ und kommutativ. Das bezüglich dieser Multi­plikation neutrale Element e ist m mod n.

Damit die Abbildung h bijektiv ist, muss die Zahl m teilerfremd zu n sein – da aber in der Praxis n stets ungerade ist, ist dies bei einer Zweierpotenz m gegeben. Die Abbildung ist außerdem verknüpfungs­treu, denn es gilt für die Addition

h(a + b)Definition von h ≡ (a + b) · mAusmultiplizieren ≡ a·m + b·mDefinition von h ≡ h(a) + h(b)     (mod n)

 

sowie für die Multi­plikation

h(a · b)Definition von h ≡ (a · b) · mMultiplikation mit 1 ≡ a · b · m · m · m-1Kommutativität der Multiplikation ≡ a · m · b · m · m-1

 

Definition von h ≡ h(a) · h(b) · m-1Definition von ⊙ ≡ h(a) ⊙ h(b)     (mod n)

 

Damit ist die Abbildung h ein Iso­morphismus von R nach S. Für die Berechnung der Abbildung h und der inversen Abbildung h-1 sowie der Montgomery-Multi­plikation ⊙ spielt die im Folgenden definierte Montgomery-Reduktion eine ent­scheidende Rolle.

Montgomery-Reduktion

Die Montgomery-Reduktion ist definiert als die Funktion

mred(x)  =  x·m-1 mod n

für alle x ∈ {0, ..., n-1}.

Die Funktion mred ist identisch mit der inversen Abbildung h-1.

Die Montgomery-Reduktion ist auch Teil der Montgomery-Multi­plikation im Ring S:

x ⊙ y  =  x · y · m-1 mod n  =  mred(x·y)

und sie lässt sich verwenden, um die Abbildung h zu berechnen. Die Berechnung von h(a) wird in folgender Weise durchgeführt:

h(a)  =  a·m mod n  =  a·m·m·m-1 mod n  =  a ⊙ (m2 mod n)

Die Modulo-n-Reduktion von m2 ist erforderlich, weil die Verknüpfung ⊙ nur für Werte aus ℤn definiert ist.

 

Ziel ist es, die Montgomery-Reduktion ohne die aufwendige mod-n-Operation zu bewerk­stelligen und stattdessen nur div- und mod-Operationen mit der Zweierpotenz m durch­zuführen. Die Grundlage hierfür liefert der folgende Satz.

Satz:  (Montgomery, 1985)

Sei m > n und m teilerfremd zu n, sei ferner 0 ≤ x < n·m, und sei schließlich n' = - n-1 mod m und t = x·n' mod m. Dann gilt

x + t·n  ≡  0   (mod m),

d.h. x + t·n lässt sich ganzzahlig durch m dividieren. Ferner gilt

(x + t·n) div m  ≡  x·m-1   (mod n),

d.h. der Quotient q = (x + t·n) div m ist bereits fast der gesuchte Wert mred(x) = x·m-1 mod n. Allerdings gilt nicht die Gleichheit, sondern nur die Kongruenz modulo n. Mit folgender dritten Aussage aber lässt sich folgern, dass entweder q oder q – n der gesuchte Wert ist:

0  ≤  (x + t·n) div m  <  2n.

Beweis:  

Die erste Aussage des Satzes ergibt sich wie folgt:

x + t·nDefinition von t ≡ x + x·n'·nDefinition von n' ≡ x + x·(- n-1)·ninverse Elemente ergeben 1 ≡ x + x·(-1) ≡ x – x ≡ 0     (mod m)

 

Als nächstes zeigen wir die zweite Aussage:

(x + t·n) div mDefinition von div ≡ (x + t·n) · m-1Ausmultiplizieren ≡ x·m-1 + t·n·m-1Vielfaches von n ist kongruent 0 mod n ≡ x·m-1     (mod n)

 

Nach Voraus­setzung des Satzes gilt 0 ≤ x < n·m, ferner 0 ≤ t < m und damit

0   ≤   x + t·n   <   n·m + n·m  =  2·n·m

Nach Division durch m ergibt sich hieraus die dritte Aussage.

 

Unter Benutzung des Satzes von Montgomery ist es also möglich, die in der Funktion mred enthaltene mod-n-Berechnung zu vermeiden. Stattdessen ist lediglich eine Operation modulo m und eine Division durch m erforderlich. Da m eine Zweierpotenz ist, lassen sich diese Berechnungen bei binärer Zahlen­darstellung sehr einfach realisieren.

Algorithmus

Für die Realisierung der Montgomery-Reduktion, nämlich der Multi­plikation modulo n mit m-1, wird folgende Berechnung durchgeführt. Der Modul n mit n ungerade und die Zweierpotenz m > n sind vorgegeben.

 

Algorithmus Montgomery-Reduktion mred(x)

Eingabe:

Zahl x mit  0 ≤ x < n·m, vorausberechnete Zahl  n' = - n-1 mod m

Ausgabe:

mred(x)  =  x·m-1 mod n

Methode:

  1. setze  t = x·n' mod m
  2. setze  q = (x + t·n) div m
  3. wenn q ≥ n dann setze  q = q – n
  4. gib q zurück

 

Bei dieser Berechnung werden nur Addition und Multi­plikation sowie die div- und mod-Operation mit der Zweierpotenz m verwendet.

Anwendung

Anstelle der Berechnung c = a · b mod n wird h(c) = h(a) ⊙ h(b) berechnet. Hierzu müssen a und b in h(a) und h(b) trans­formiert werden, dann mit der Montgomery-Multi­plikation ⊙ multi­pliziert werden, und schließlich muss das Ergebnis h(c) mit der inversen Abbildung h-1 zurück­trans­formiert werden, um c zu erhalten. Wir hatten gesehen, dass sich alle diese Berechnungen mithilfe der Montgomery-Reduktion mred durchführen lassen.

Zwar lohnt sich dieser Aufwand für eine einzelne modulare Multi­plikation kaum, wohl aber für fortgesetzte modulare Multi­plikationen wie etwa bei der modularen Exponentiation. Bild 1 zeigt das Schema der Berechnungen; dieses Schema ist typisch für die Anwendung einer Trans­formation.

 

 

Bild 1: Berechnungsschema der modularen Exponentiation mithilfe von Montgomery-Multiplikationen 

Bild 1: Berechnungsschema der modularen Exponentiation mithilfe von Montgomery-Multiplikationen

 

Statt ai mod n direkt zu berechnen (oberer Pfeil), wird a zunächst in h(a) trans­formiert, dann wird mithilfe von Montgomery-Multi­plikationen h(a)i berechnet, also h(a) ⊙ ... ⊙ h(a) (i-mal). Weil die Abbildung h verknüpfungs­treu ist, ist dies dasselbe wie h(ai mod n). Mit der inversen Trans­formation h-1 ergibt sich schließlich ai mod n.

Implementierung

Es folgt die Implementierung in der Programmier­sprache Python; eine entsprechende Implementierung in Java ist ebenfalls vorhanden.

Gegeben ist der Modul n mit n ungerade. In der Funktion preprocess werden k und m = 2k ermittelt; ferner werden die Werte np = n' = -n-1 mod m und mm = m2 mod n voraus­berechnet. Die Hilfs­funktion inv2(n, k) zur Berechnung des multi­plikativ inversen Elements von n modulo 2k ist weiter unten angegeben.

In der Funktion mred wird die Operation mod m durch bitweises Und mit den k Einsen von m-1 realisiert, die Operation div m durch Rechts­schieben um k Stellen.

Die Berechnung von 2k wird durch Links­schieben von 1 um k Stellen realisiert, also durch Anhängen von k Nullen.

Auch gelegentlich vorkommende Berechnungen wie i%2 oder i//2 lassen sich durch Bit-Operationen realisieren (hier nicht durchgeführt).

 

# uebernimmt den Modul n und setzt k und m;
# berechnet np = - n hoch -1 mod m sowie mm = m*m mod n;
# setzt die Montgomery-Eins m1 = m mod n
def preprocess(n_):
    global n, k, m, np, mm, m1
    n=n_
    assert n%2==1, "n muss ungerade sein"
    k=int(log(n, 2))+1
    m=1<<k    # 2**k
    np=m-inv2(n, k)   # inverses Element von n modulo 2^k 
    mm=m*m % n
    m1=m % n

# Montgomery-Reduktion
def mred(x):
    global n, k, m, np
    t = (x * np) & (m-1)  # mod m
    q = (x + t*n) >> k    # div m
    if q>=n:
        q=q-n
    return q

# Montgomery-Multiplikation
def mmul(a, b):
    return mred(a*b)

# Transformation x -> h(x)
def mtra(x):
    global mm
    return mmul(x, mm)

 

Mithilfe dieser Funktionen lässt sich die schnelle modulare Exponentiation ai mod n wie folgt realisieren:

 

# modulare Exponentation a^i mod n 
def mexp(a, i):
    ha=mtra(a)
    hc=mmodexp(ha, i)
    c=mred(hc)
    return c

# schnelle modulare Montgomery-Exponentiation
def mmodexp(x, i):
    global m1
    if i==0:
        return m1
    if i%2==1:           # i ungerade
        return mmul(x, mmodexp(x, i-1))
    z=mmodexp(x, i//2)
    return mmul(z, z)

 

Multiplikativ inverses Element berechnen

In der Funktion preprocess wird das multi­plikativ inverse Element von n modulo m benötigt. Standardmäßig wird das multi­plikativ inverse Element mithilfe des erweiterten euklidischen Algorithmus berechnet. Im vorliegenden speziellen Fall ist allerdings der Modul m eine Zweierpotenz.

Eine brutal schnelle Alternative für die Berechnung des multi­plikativ inversen Elements von a modulo einer Zweierpotenz m = 2k ist folgende Funktion inv2. Die Berechnung beruht darauf, dass jeweils das inverse Element von a modulo einer Zweierpotenz 2i zu dem inversen Element von a modulo der Zweierpotenz 22i geliftet wird (sogenannte Hensel-Liftung). Ausgegangen wird vom inversen Element von a (a ungerade) modulo 2; dies ist stets 1. Das Verfahren ähnelt dem Newton-Verfahren zur Berechnung des Kehrwerts.

# schnelle Berechnung des multiplikativ inversen Elements
# von a mit a ungerade modulo einer Zweierpotenz m = 2^k
def inv2(a, k):
    if k==1:
        return 1
    m=2**k
    a=a % m
    r=inv2(a, (k+1)//2)
    return (2-a*r) * r % m

 

Auch hier lassen sich die Berechnung von m = 2k und die Reduktionen modulo m durch Bit-Operationen implementieren (siehe Funktion inv2s.

Die Funktion inv2 hat eine Zeit­komplexität von O(log(k)) = O(log(log(m))), im Vergleich zur Zeit­komplexität von O(log(m)) des erweiterten euklidischen Algorithmus.

 

Zusammenfassung

In der Kryptografie kommt die modulare Exponentiation als häufige Rechen­operation vor. Die beteiligten Zahlen sind sehr groß, und entsprechend aufwendig ist die modulo-Operation, für die normalerweise eine Division erforderlich ist.

Bei der Methode von Montgomery wird statt im Ring ℤn in einem isomorphen Ring gerechnet, dabei tritt an die Stelle der normalen modularen Multi­plikation die Montgomery-Multi­plikation. Diese lässt sich ohne die bei der normalen modularen Multi­plikation erforder­liche Division durchführen. Benutzt werden lediglich Addition, Multi­plikation und mod- und div-Operationen modulo einer Zweierpotenz. Bei binärer Zahlen­darstellung sind diese letzteren Operationen sehr einfach zu realisieren.

Besonders interessant ist die Montgomery-Multi­plikation bei Arithmetik mit Langzahlen, die als Arrays von 32-Bit-Wörtern dargestellt sind.

 

Literatur

[Mont 85]   P. Montgomery: Modular Multiplication Without Trial Division. Mathematics of Computation, Vol. 44, 170, 519-521 (1985)

 

Weiter mit:   [Montgomery-Multiplikation in Java]   oder   [up]

 

H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Created: 29.08.2014   Updated: 08.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden