GPU-Computing

Montgomery-Multiplikation

 aufwärts

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 ganze Zahlenn 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 ganze Zahlenn = {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  =  (ganze Zahlenn, +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 Element R. Hierbei ist m eine Zweierpotenz größer als n.

Damit ergibt sich der Ring S als

S  =  (ganze Zahlenn, +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 Element S ist

xy  =  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)   ≡   (a + b) · m   ≡   a·m + b·m   ≡   h(a) + h(b)     (mod n)

 

sowie für die Multi­plikation

h(a · b)   ≡   (a · b) · m   ≡   a · b · m · m · m-1   ≡   a · m · b · m · m-1

 

   ≡   h(a) · h(b) · m-1   ≡   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 Element {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:

xy  =  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 ganze Zahlenn 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 0kleiner gleichx < n·m, und sei schließlich n' = - n-1 mod m und t = x·n' mod m. Dann gilt

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

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

(x + t·n) div m  kongruent  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 kleiner gleich (x + t·n) div m  <  2n.

Beweis:  

Die erste Aussage des Satzes ergibt sich wie folgt:

x + t·n   ≡   x + x·n'·n   ≡   x + x·(- n-1n   ≡   x + x·(-1)   ≡   x – x   ≡   0     (mod m)

 

Als nächstes zeigen wir die zweite Aussage:

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

 

Nach Voraus­setzung des Satzes gilt 0kleiner gleichx < n·m, ferner 0kleiner gleicht < m und damit

kleiner gleich  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  0kleiner gleichx < 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 qgrößer gleichn 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 ent­sprechende 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 inverse zur Berechnung des multi­plikativ inversen Elementes 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.

 

# uebernimmt den Modul n und setzt k und m;
# berechnet - n hoch -1 mod m sowie m*m mod n;
# setzt die Montgomery-Eins
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=2**k
    np=m-inverse(n, m)
    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&1==1:           # i ungerade
        return mmul(x, mmodexp(x, i-1))
    z=mmodexp(x, i>>1)   # i div 2
    return mmul(z, z)

 

Als Hilfs­funktionen werden die Funktionen inverse und extendedGcd benötigt. Die Funktion inverse(a, n) berechnet das multi­plikativ inverse Element von a modulo n mithilfe des erweiterten euklidischen Algorithmus; dieser ist in der Funktion extendedGcd implementiert.

# ---------- Hilfsfunktionen
# berechnet das multiplikativ inverse Element von a in Zn*
def inverse(a, n):
    g, u, v=extendedGcd(a, n)
    if g!=1:
        return 0
    return u%n

# erweiterter euklidischer Algorithmus, rekursive Version
def extendedGcd(a, b):
    if b==0:
        return a, 1, 0
    else:
        g, u, v = extendedGcd(b, a%b)
        q=a//b
        return g, v, u-q*v

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 ganze Zahlenn 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 mit Langzahlen]   [Montgomery-Multiplikation in Java]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 29.08.2014   Updated: 07.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik