Modulare Addition & RSA-Verfahren

Implementierung Modulare Addition

Zu Beginn der Stunde hat Elias das fertige Programm vorgeführt. Die im letzten Protokoll beschriebenen Änderungen wurden implementiert und somit war es nun möglich „beliebige“ (die 256 ersten des Unicodes) Zeichenketten zu verschlüsseln.

Das fertige Programm sieht so aus:

def zerlegung(wort, blocklaenge):
    liste = []
    block = ''
    for c in wort:
        if len(block) == blocklaenge:
            liste = liste + [block]
            block = ''
        block = block + c
    if block != '':
        fehlend = blocklaenge - len(block)
        block = block + fehlend * ' '
        liste = liste + [block]
    return liste

def codierungBlock(wort):
    hilfszahl = 0
    for c in wort:
        hilfszahl = hilfszahl*256 + ord(c)
    return hilfszahl

def codierungBlockListe(blockListe):
    liste = []
    for block in blockListe:
        liste = liste + [codierungBlock(block)]
    return liste

def codierung(wort, blocklaenge):
    return codierungBlockListe(zerlegung(wort, blocklaenge))

def decodierungBlockcodierung(zahl, blocklaenge):
    wort = ''
    while blocklaenge > 0:
        rest = zahl % (256)
        wort = chr(rest) + wort
        zahl = zahl // (256)
        blocklaenge = blocklaenge - 1
    return wort
    
def decodierungListeBlockcodierung(zahlenListe, blocklaenge):
    liste = []
    for zahl in zahlenListe:
        liste = liste + [decodierungBlockcodierung(zahl, blocklaenge)]
    return liste

def zusammenfuegung(liste):
    ergebnis = ''
    listeOhneLetztesWort = liste[:len(liste)-1]
    letztesWort = liste[len(liste)-1]
    for wort in listeOhneLetztesWort:
        ergebnis = ergebnis + wort
    # Leerzeichen am Ende entfernen
    m = len(letztesWort)-1
    gefunden = False
    while m >= 0 and not gefunden:
        c = letztesWort[m]
        if c != ' ':
            gefunden = True
        else:
            m = m-1
    letztesWort = letztesWort[0:m+1]
    ergebnis = ergebnis + letztesWort
    return ergebnis

def decodierung(zahlenListe, blocklaenge):
    return zusammenfuegung(decodierungListeBlockcodierung(zahlenListe, blocklaenge))

def verschluesselteZahl(zahl, schluessel):
    return (zahl + schluessel[0]) % schluessel[1]

def verschluesselung(zahlenListe, schluessel):
    liste = []
    for zahl in zahlenListe:
        liste = liste + [verschluesselteZahl(zahl, schluessel)]
    return liste

Eine mögliche Ausführung würde so aussehen: (Der Schlüssel muss dabei größer als die maximal größte Zahl sein also bei einer Blocklänge von 3 min. 256**3 = 16777216.)

codierung("Hört alle das Nimmerland Album! <3",3)
[4781682, 7610465, 7105637, 2122849, 7544910, 6909293, 6648428, 6385252, 2113900, 6452589, 2170940, 3350560]
>>> verschluesselung([4781682, 7610465, 7105637, 2122849, 7544910, 6909293, 6648428, 6385252, 2113900, 6452589, 2170940, 3350560], (1000000001,2000000000))
[1004781683, 1007610466, 1007105638, 1002122850, 1007544911, 1006909294, 1006648429, 1006385253, 1002113901, 1006452590, 1002170941, 1003350561]
>>> verschluesselung([1004781683, 1007610466, 1007105638, 1002122850, 1007544911, 1006909294, 1006648429, 1006385253, 1002113901, 1006452590, 1002170941, 1003350561], (2000000000-1000000001,2000000000))
[4781682, 7610465, 7105637, 2122849, 7544910, 6909293, 6648428, 6385252, 2113900, 6452589, 2170940, 3350560]
>>> decodierung([4781682, 7610465, 7105637, 2122849, 7544910, 6909293, 6648428, 6385252, 2113900, 6452589, 2170940, 3350560], 3)
'Hört alle das Nimmerland Album! <3'

Qualität des Verfahrens

Sehr unsicher: Man kann mithilfe des öffentlichen Schlüssels sehr leicht den privaten Schlüssel herausfinden.
Man braucht ein Verfahren, bei dem es nicht so leicht ist, auf den privaten Schlüssel zu schließen, sich öffentlicher und privater Schlüssel aber trotzdem gegenseitig aufheben.
Lösung: Das RSA-Verfahren. Hauptänderung: Die Nachricht wird nicht mit dem Schlüssel addiert sonder potenziert. Der Rest des Codes bleibt gleich.

...
def verschluesselteZahl(zahl, schluessel):
    return (zahl ** schluessel[0]) % schluessel[1]
...

Die nötigen Schlüssel e, N -> Öffentlicher Schlüssel und d, N -> privater Schlüssel werden wie folgt berechnet:

Erzeugung des öffentlichen und privaten Schlüssels:

  1. Wähle zwei Primzahlen p und q wie z.B. 17 und 31
  2. Berechne das sogenannte RSA Modul N = p * q
  3. Berechne die Eulersche Funktion φ(N) = (p-1) * (q-1)
  4. Wähle eine zu φ(N) teilerfremde Zahl e mit 1 < e < φ(N)
  5. Ermittle eine Zahl d, für die gilt: Division von (e * d) durch φ(N) ergibt den Rest 1

Hausaufgabe

Führe das RSA-Verfahren durch, indem du dir zuerst zwei Schlüssel erstellst und dann erst einmal eine Zahl, danach auch einen Texts mit Hilfe des Programms von oben verschlüsselst. (Tipp: Zum Probieren, welche Zahl für d in Frage kommt, kannst du folgenden Code in Python benutzen:)

for d in range(2, phi-1):
    if((e*d)%phi == 1):
         print(d)
         break


Schreibe einen Kommentar