Station - Berechnung des modularen Inversen

Naiver Berechnung des modularen Inversen

Im letzen Abschnitt wurde der folgende Baustein zur Berechnung des modularen Inversen benutzt:

def modInv(e, n):
    gefunden = False
    d = 1
    while d <= n and not gefunden:
        if (e * d) % n == 1:
            gefunden = True
        else:
            d = d + 1
    if d > n:
        d = -1
    return d

Der Algorithmus, der diesem Baustein zu Grunde liegt, lässt sich informell so beschreiben: Prüfe der Reihe nach alle Zahlen, ob sie die geforderte Inversen-Eigenschaft haben. Beende diesen Prozess, wenn eine solche Zahl gefunden wurde, oder n erreicht ist.

Der Baustein ist nur für kleine n-Werte praktikabel. Bei größeren n-Werten kann es vorkommen, dass die Abarbeitung der Schleife so lange dauert, dass man in der zur Verfügung stehenden Zeit zu keinem Ergebnis kommt.

Wenn man beispielsweise das modulare Inverse von b = 49 bzgl. des Moduls n = 1000010000100001000010000100001000010000100001000010000 bestimmen möchte, so benötigt ein handelsüblicher Rechner für 10 Millionen Überprüfungen derzeit mehr als 1 Sekunde. Bis zum Ergebnis a = 775517959261225265313877628572204089387832653836742449 benötigt er dann in etwa t = 77551795926122526531387762857220408938783265383 Sekunden. Das sind mehr als 10³⁹ Jahre. Klar, dass man auf dieses Ergebnis nicht warten kann. Selbst wenn die Rechner um den Faktor 1000 schneller werden, so ist die Rechenzeit immer noch weit jenseits aller akzeptablen Grenzen.

Mit dem naiven Verfahren kann man also nicht garantieren, dass das modularen Inverse in vertretbarer Zeit berechnet werden kann.

Die Situation ändert sich nur, wenn ein besserer Algorithmus zur Berechnung des modularen Inversen gefunden wird.

Erweiterter euklidischer Algorithmus

Der euklidischer Algorithmus ist ein Standardalgorithmus zur Berechnung des größten gemeinsamen Teilers (kurz ggT) von zwei vorgegebenen natürlichen Zahlen. Dieser Algorithmus lässt sich so erweitern, dass hiermit auch modulare Inverse bestimmt werden können.

Wir betrachten zunächst ein Beispiel.

Gegeben sind die Zahlen a = 884 und b = 320.

Gesucht ist eine Darstellung der Gestalt ggT(a, b) = x*a + y*b mit zwei weiteren Zahlen x und y.

Die Berechnung erfolgt schrittweise:

(1) 884 = 2*320 + 244

    244 = 884 - 2*320 = (1*884 + 0*320) - 2*(0*884 + 1*320) = 1*884 - 2*320

(2) 320 = 1*244 + 76

     76 = 320 - 1*244 = (0*884 + 1*320) - 1*(1*884 - 2*320)) = (-1)*884 + 3*320  

(3) 244 = 3*76 + 16 

     16 = 244 - 3*76 = (1*884 - 2*320) - 3*((-1)*884 + 3*320) = 4*884 - 11*320

(4)  76 = 4*16 + 12

     12 = 76 - 4*16 = ((-1)*884 + 3*320) - 4*(4*884 - 11*320) = (-17)*884 + 47*320 

(5)  16 = 1*12 + 4

      4 = 16 - 1*12 = (4*884 - 11*320) - 1*((-17)*884 + 47*320) = 21*884 - 58*320 

(6)  12 = 3*4 + 0

      0 = 12 - 3*4 = (-17*884 + 47*320) - 3*(21*884 + -58*320) = -80*884 + 221*320

Die nummerierten Zeilen beschreiben die Berechnungsschritte des euklidischen Algorithmus.

Die darunter aufgeführten Zeilen beschreiben Umformungen, die zur Bestimmung von x und y benötigt werden.

Als Ergebnis der Berechnungen erhält man:

ggT(884, 320) = 4 = 21*884 + (- 58)*320 = x*884 + y*320

Also x = 21 und y = -58.

Implementierung des erweiterten euklidischen Algorithmus

Der folgende Python-Quelltext enthält eine Implementierung des erweiterten euklidischen Algorithmus. Zum Mitverfolgen ist eine print-Anweisung integriert. Wenn es nur auf eine schnelle Berechnung ankommt, sollte diese print-Anweisung entfernt (oder auskommentiert) werden.

def erweiterterEuklidischerAlgorithmus(a, b):
    aalt = a
    amitte = b
    xalt = 1
    xmitte = 0
    yalt = 0
    ymitte = 1
    while amitte != 0:
        q = aalt // amitte
        aneu = aalt - q * amitte
        xneu = xalt - xmitte * q
        yneu = yalt - ymitte * q
        xalt = xmitte
        xmitte = xneu
        yalt = ymitte
        ymitte = yneu
        aalt = amitte
        amitte = aneu
        print(amitte, ' = ', xmitte, ' * ', a, ' + ', ymitte, ' * ', b)
    return (aalt, xalt, yalt)

Das folgende Python-Protokoll zeigt, wie man den gezeigten Baustein nutzen kann:

>>> erweiterterEuklidischerAlgorithmus(884, 320)
244  =  1  *  884  +  -2  *  320
76  =  -1  *  884  +  3  *  320
16  =  4  *  884  +  -11  *  320
12  =  -17  *  884  +  47  *  320
4  =  21  *  884  +  -58  *  320
0  =  -80  *  884  +  221  *  320
(4, 21, -58)

Aufgabe 1

Bestimme mit Hilfe des erweiterten euklidischen Algorithmus den größten gemeinsamen Teiler von

• 45 und 39.
• 196 und 135.
• 301 und 139.

Überprüfe deine Ergebnisse mit Hilfe der Implementierung.

Schnelle Berechnung des modularen Inversen

Aus den Ergebnissen des erweiterten euklidischen Algorithmus lässt sich durch Umformung das modulare Inverse bestimmen.

Beispiel 1: Gesucht wird das modulare Inverse von a = 41 bzgl. m = 192.

>>> erweiterterEuklidischerAlgorithmus(41, 192)
(1, 89, -19)

Umformungen:

1 = 89*41 + (-19)*192

1 - (-19)*192 = 89*41

[1 - (-19)*192]% 192 = [89*41]%192

[1 + 19*192]% 192 = [89*41]%192

1 = [89*41]%192

Ergebnis: Das modulare Inverse ist b = 89.

Beispiel 2: Gesucht wird das modulare Inverse von a = 17 bzgl. m = 192.

>>> erweiterterEuklidischerAlgorithmus(17, 192)
(1, -79, 7)

Umformungen:

1 = (-79)*17 + 7*192

1 - 7*192 = (-79)*17

1 - 7*192 + 192*17 = (-79+192)*17

1 + 10*192 = 113*17

[1 + 10*192]%192 = [113*17]%192

1 = [113*17]%192

Ergebnis: Das modulare Inverse ist b = 113.

Die in den Beispielen gezeigten Umformungen lassen sich allgemein beschreiben und liefern - zusammen mit dem erweiterten euklidischen Algorithmus ein Verfahren zur Bestimmung des modularen Inversen.

def modInv(a, m):
    (ggt, x, y) = erweiterterEuklidischerAlgorithmus(a, m)
    if ggt > 1:
        return -1
    else:
        if x < 0:
            x = x + m
        return x

Aufgabe 2

Bestimme mit Hilfe analoger Umformungen das modulare Inverse von

• 139 bezüglich 301.
• 135 bezüglich 196.
• 39 bezüglich 45.

Überprüfe deine Ergebnisse mit Hilfe der Implementierung.

Aufgabe 3

Bestimme mit Hilfe der Implementierung das modulare Inverse von 49 bezüglich 1000010000100001000010000100001000010000100001000010000. Vergleiche mit dem naiven Ansatz.

Aufgabe 4

Beurteile abschließend die Sicherheit des Verfahrens mit modularer Multiplikation. Welche Rolle spielt hierbei der erweiterte euklidische Algorithmus?

Sicherheit des Verfahrens mit modularer Multiplikation

Aus den Ergebnissen und Überlegungen können wir jetzt die folgende Bewertung vornehmen: Das Verfahren mit modularer Multiplikation ist nicht sicher, da man den privaten Schlüssel schnell aus dem öffentlichen Schlüssel bestimmen kann.

Eine zentrale Rolle spielt hierbei der erweiterte euklidische Algorithmus. Dieser Algorithmus ermöglicht es, das modulare Inverse einer Zahl effizient zu berechnen.