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 1039 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*(1*320 + 0*884) = 1*884 - 2*320

(2) 320 = 1*244 + 76

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

(3) 244 = 3*76 + 16 

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

(4)  76 = 4*16 + 12

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

(5)  16 = 1*12 + 4

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

(6)  12 = 3*4 + 0

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 2

Teste den Baustein mit selbst gewählten Zahlen.

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 3

(a) Bestimme (durch eigene Umformungen / mit Hilfe des Bausteins) analog das modulare Inverse von a = 139 bzgl. des Moduls m = 301.

(b) Bestimme mit Hilfe des Bausteins das modulare Inverse von a = 49 bzgl. des Moduls m = 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.

X

Fehler melden

X

Suche