Station - Sicherheit und die Berechnung des modularen Inversen

Sicherheit des Verfahrens mit modularer Multiplikation

Ist das Verfahren mit modularer Multiplikation sicher? Die Antwort auf diese Frage hängt davon ab, ob man aus dem öffentlichen Schüssel (e, n) direkt den privaten Schlüssel (d, n) berechnen kann. Das soll im Folgenden ausprobiert werden. Die erforderlichen Rechnungen können dabei mit geeigneten Python-Funktionen durchgeführt werden.

Aufgabe 1: Das modulare Inverse berechnen

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

>>> modInv(16, 33)
31

Aufgabe 2: Geheimcodes knacken

Aufgabe 3: Laufzeitverhalten der Funktion modInv

(a) Bestimme das modulare Inverse von a = 775517959261225265313877628572204089387832653836742449 bzgl. des Moduls n = 1000010000100001000010000100001000010000100001000010000 mit Hilfe der Funktion modInv. Zur Kontrolle: Es müsste b = 49 herauskommen.

(b) Bestimme mit dem Resultat aus (a) das modulare Inverse von b = 49 bzgl. des Moduls n = 1000010000100001000010000100001000010000100001000010000. Bestimme anschließend das gesuchte modulare Inverse mit der Funktion modInv. Welches Problem tritt hier auf? Hast du eine Vermutung, warum dieses Problem auftritt.

(c) Hier soll ebenfalls das modulare Inverse von b = 49 bzgl. des Moduls n = 1000010000100001000010000100001000010000100001000010000 bestimmt werden. Die oben vorgegebene Funktion ist hier um Ausgaben ergänzt worden. Nach jeweils 10 Millionen getesteten Zahlen wird eine Ausgabe auf dem Bildschirm erzeugt.

def modInvMitAusgaben(e, n):
    gefunden = False
    d = 1
    while d <= n and not gefunden:
        if d % 10000000 == 0:
            print("Anzahl der Versuche: ", d)
        if (e * d) % n == 1:
            gefunden = True
        else:
            d = d + 1
    if d > n:
        d = -1
    return d

Python-Protokoll:

>>> modInvMitAusgaben(49, 1000010000100001000010000100001000010000100001000010000)
Anzahl der Versuche:  10000000
Anzahl der Versuche:  20000000
Anzahl der Versuche:  30000000
...

Probiere das selbst einmal aus. Miss (ungefähr) die Zeit, die zwischen zwei Ausgaben verstreicht. Mit dieser Zeit kannst du jetzt eine Art Hochrechnung machen, wie lange man in etwa warten muss, bis das Ergebnis 775517959261225265313877628572204089387832653836742449 berechnet ist.

Beurteile mit den gewonnenen Erkenntnissen die Sicherheit des Verfahrens mit modularer Multiplikation.