EINFÜHRUNG

Das Geheimhalteprinzip spielt in unserer modernen Welt eine immer wichtigere Rolle. Zum Schutz der Privatsphäre, aber auch zur Geheimhaltung wichtiger staatlicher, industrieller und militärischer Informationen ist es nötig, Daten derart zu verschlüsseln, dass die verschlüsselten Daten wohl in die Hände von Unbefugten fallen können, es aber ohne Bekanntgabe der Entschlüsselungsmethode unmöglich oder zumindest sehr schwierig ist, die Originalinformation herauszufinden.

Bei der Verschlüsselung (encoding) werden die  Originaldaten in verschlüsselte (chiffrierte) Daten umgewandelt. Bei der Entschlüsselung (decoding) werden die Originaldaten wieder hergestellt. Verwendet man für die Daten das Buchstabenalphabet, so spricht man auch von Klartext und Kryptotext.

Die Beschreibung des Verfahrens zum Entschlüsseln wird Schlüssel genannt. Es kann sich auch nur um eine einzige Zahl, eine Zahlen- oder eine Buchstabenfolge (ein Schlüsselwort) handeln. Wird beim Verschlüsseln und Entschlüsseln derselbe Schlüssel verwendet, so spricht man von einem symmetrischen Kryptoverfahren, andernfalls von einem asymmetrischen Kryptoverfahren.

CAESAR-VERSCHLÜSSELUNG

Nach der Überlieferung soll bereits Julius Cäsar (100 v.Chr. - 44 v.Chr.) folgendes Verfahren für seine militärische Korrespondenz angewendet haben: Jeder Buchstabe des Klartexts wird dabei alphabetisch um eine bestimmte feste Schlüsselzahl nach rechts verschoben, wobei man nach Z wieder bei A weiterfährt.

Das Alphabet wird bei dieser Methode also in einem Ringbuffer angelegt. Mit dem Schlüssel 3 werden die Buchstaben A in D, B in E, C in F, D in G, usw. verschlüsselt. In deinem Programm verwendest du Textdateien für die Daten, damit du sie leicht verändern und weitergeben kannst. Den Klartext schreibst du mit irgendeinem Texteditor in die Datei original.txt, die du im Verzeichnis, in dem sich dein Programm befindet, speichern musst. Verwende für den Text nur Grossbuchstaben und das Leerzeichen. Du kannst mehrere Zeilen schreiben, also beispielsweise

HEUTE TREFFEN WIR UNS UM ACHT
LIEBER GRUSS
TANIA

Der Encoder verschlüsselt den von der Datei eingelesene Textstring msg mit der Funktion encode(msg), wobei ausser für den Zeilenumbruch \n jedes Zeichen durch das entsprechende Kryptozeichen ersetzt wird.

import string
key = 4
alphabet = string.ascii_uppercase + " "

def encode(text):
    enc = ""
    for ch in text:
        if ch != "\n":
            i = alphabet.index(ch)               
            ch = alphabet[(i + key) % 27]
        enc += ch
    return enc
    
fInp = open("original.txt")
text = fInp.read()
fInp.close() 

print("Original:\n", text)
krypto = encode(text)
print("Krypto:\n", krypto)

fOut = open("secret.txt", "w")    
for ch in krypto:
    fOut.write(ch)
fOut.close()      

Dein verschlüsselter Text sieht wie folgt aus:

LIYXIDXVIJJIRD MVDYRWDYQDEGLX
PMIFIVDKVYWW
XERME

Der Decoder ist ganz analog aufgebaut, nur dass die Zeichen im Alphabet rückwärts verschoben werden.

import string
key = 4
alphabet = string.ascii_uppercase + " "

def decode(text):
    dec = ""
    for ch in text:
        if ch != "\n":
            i = alphabet.index(ch)          
            ch = alphabet[(i - key) % 27]
        dec += ch
    return dec

fInp = open("secret.txt")
krypto = fInp.read()
fInp.close() 

print("Krypto:\n", krypto)
msg = decode(krypto)
print("Message:\n", msg)

fOut = open("message.txt", "w")    
for ch in msg:
    fOut.write(ch)
fOut.close()      

MEMO

VERSCHLÜSSELUNG NACH DEM VIGENÈRE-VERFAHREN

import string
key = "ALICE"
alphabet = string.ascii_uppercase + " " 

def encode(text):
    keyList = []
    for ch in key:
        i = alphabet.index(ch)
        keyList.append(i)
    print("keyList:", keyList)
    enc = ""
    for n in range(len(text)):
        ch = text[n]
        if ch != "\n":
            i = alphabet.index(ch)  
            k = n % len(key)                
            ch = alphabet[(i + keyList[k]) % 27]      
        enc += ch
    return enc

fInp = open("original.txt")
text = fInp.read()
fInp.close() 

print("Original:\n", text)
krypto = encode(text)
print("Krypto:\n", krypto)
fOut = open("secret.txt", "w")    
for ch in krypto:
    fOut.write(ch)
fOut.close()     

Der Decoder ist wiederum praktisch identisch.

import string
key = "ALICE"
alphabet = string.ascii_uppercase + " " 

def decode(text):
    keyList = []
    for ch in key:
        i = alphabet.index(ch)
        keyList.append(i)
    print("keyList:", keyList)
    enc = ""
    for n in range(len(text)):
        ch = text[n]
        if ch != "\n":
            i = alphabet.index(ch)  
            k = n % len(key)                
            ch = alphabet[(i - keyList[k]) % 27]      
        enc += ch
    return enc

fInp = open("secret.txt")
krypto = fInp.read()
fInp.close() 

print("Krypto:\n", krypto)
msg = decode(krypto)
print("Message:\n", msg)
fOut = open("message.txt", "w")    
for ch in msg:
    fOut.write(ch)
fOut.close()      

MEMO

VERSCHLÜSSELUNG NACH DEM RSA-VERFAHREN

		Schritt 1: Der Empfänger erzeugt den private key und den public key und schickt den public key an den Sender.
		Schritt 2: Der Sender verschlüsselt seine Nachricht mit dem public key und schickt den verschlüsselten Text zurück.
		Schritt 3: Der Empfänger entschlüsselt den Text mit dem private key.

Die Schlüssel werden mit folgendem Algorithmus erzeugt, der auf der Zahlentheorie beruht [mehr... Einen elementaren Beweis findest du im Buch Barth, Algorithmik für Einsteiger, Springer-Verlag].

Zuerst werden zwei Primzahlen p und q gewählt, die für ein sicheres System mehrere hundert Stellen haben sollten. Man multipliziert diese und bildet m = p*q. Aus der Zahlentheorie weiss man, dass die Eulersche Funktion φ(m) = (p-1)*(q-1) die Zahl der teilerfremden Zahlen zu m ist (a, b sind teilerfremd, wenn der grösste gemeinsame Teiler ggT(a,b) = 1 ist).

Als nächstes wählt man eine Zahl e, die kleiner als φ und  teilerfremd zu φ ist. Damit ist der öffentliche Schlüssel bereits erstellt, er besteht aus dem Zahlenpaar:

Öffentlicher Schlüssel: [m, e]

Hier ein Beispiel mit den kleinen Primzahlen p = 73 und q = 151:

m = 73 * 151 = 11023,    φ = 72 * 150 = 10800,    e = 11 (gewählt teilerfremd zu φ)

Öffentlicher Schlüssel: [m, e] = [11023, 11]

Der private Schlüssel besteht dann aus dem Zahlenpaar:

Privater Schlüssel: [m, d]

wobei für die Zahl d muss gelten: (d * e) mod φ = 1

(da e und φ teilerfremd sind, sagt das Lemma von Bézout aus der Zahlentheorie, dass die Gleichung mindestens eine Lösung hat).

Du kannst mit deinen Werten für e und φ die Zahl d mit einem einfachen Programm bestimmen, indem du in einer for-Schleife 100 000 Werte für d ausprobierst.

e = 11
phi = 10800

for d in range(100000):
    if  (d * e) % phi == 1:
        print "d", d

Du erhältst mehrere Lösungen (5891, 16691, 27491, 49091, usw.). Im Prinzip brauchst du aber nur die erste, um den privaten Schlüssel festzulegen.

Privater Schlüssel: [m, d] = [11023, 5891]

Die Berechnung des privaten Schlüssels ist hier nur deswegen so einfach, da du die Zahlen p und q und damit auch die Zahl φ kennst. Ohne Kenntnis dieser Zahlen lässt sich der private Schlüssel nur mit einem grossen Aufwand berechnen

Mit dem RSA-Algorithmus werden Zahlen verschlüsselt. Um einen Text zu verschlüsseln, verwendest du den ASCII-Code jedes Zeichens und bildest mit dem öffentlichen Schlüssel [m, e] den Verschlüsselungswert s für den Geheimtext  gemäss der Formel

s = r^e (modulo m).

Diese Verschlüsselungszahlen schreibst du zeilenweise in die Datei secret.txt.

publicKey = [11023, 11]

def encode(text):
    m = publicKey[0]
    e = publicKey[1]
    enc = ""
    for ch in text:
        r = ord(ch)
        s = int(r**e % m)
        enc += str(s) + "\n"
    return enc

fInp = open("original.txt")
text = fInp.read()
fInp.close() 

print("Original:\n", text)
krypto = encode(text)
print("Krypto:\n", krypto)
fOut = open("secret.txt", "w")    
for ch in krypto:
    fOut.write(ch)
fOut.close()      

Im Decoder liest du die Zahlen von der Datei secret.txt zuerst in eine Liste. Zum Entschlüsseln berechnest du mit dem privaten Schlüssel aus der Verschlüsselungszahl s die ursprüngliche Zahl gemäss der Formel

r = s^d (modulo m).

Dies ist der ASCII-Code des ursprünglichen Zeichens.

privateKey = [11023, 5891]

def decode(li):
    m = privateKey[0]
    d = privateKey[1]
    enc = ""
    for c in li:
        s = int(c)
        r = s**d % m
        enc += chr(r)
    return enc

fInp = open("secret.txt")
krypto = []
while True:
   line = fInp.readline().rstrip("\n")
   if line == "":
       break
   krypto.append(line)
fInp.close() 

print("Krypto:\n", krypto)
msg = decode(krypto)
print("Message:\n", msg)
fOut = open("message.txt", "w")    
for ch in msg:
    fOut.write(ch)
fOut.close()    

MEMO

AUFGABEN