Das Vigenère-Verfahren

Aus ProgrammingWiki

Polyalphabetische Verschlüsselung

Um Häufigkeitsanalysen eines verschlüsselten Textes unbrauchbar zu machen, greifen wir eine einfache und zugleich geniale Idee des französischen Diplomaten und Kryptographen Blaise de Vigenère (* 15. April 1523; † 1596) auf.
Statt eines einzelnen "Geheimalphabets" benutzen wir mehrere, die durch ein Schlüsselwort repräsentiert werden. Jedes Zeichen des Klartextes wird nun mit einem Alphabet verschlüsselt, das jeweils einem Buchstaben des Schlüsselwortes entspricht. Das Schlüsselwort verwenden wir dabei zyklisch bis zum Ende des zu übertragenden Textes:

Wir gehen also von der monoalphabetischen zur polyalphabetischen Verschlüsselung über.
Die Vigenère-Verschlüsselung hielt man lange Zeit für absolut sicher. Erst um 1850, fast 300 Jahre nach Vigenère, konnte der englische Mathematiker Charles Babbage (* 26. Dezember 1791; † 18. Oktober 1871) die Vigenère-Chiffrierungen systematisch entziffern.

Implementation

(define sqr (lambda (x) (* x x))) (define mod (lambda (n m) (if (< n 0) (- m (modulo (abs n) m)) (modulo n m)))) (define string-car (lambda (str) (string-ref str 0))) (define string-cdr (lambda (str) (substring str 1 (string-length str)))) (define char-pos (lambda (z str) (letrec ([pos (lambda (n str) (cond [(= (string-length str) 0) 0] [(equal? z (string-car str)) n] [else (pos (+ n 1) (string-cdr str))]))]) (pos 1 str)))) (define pos-char (lambda (n str) (string-ref str (mod (- n 1) (string-length str))))) (define char-cons (lambda (z str) (string-append (string z) str))) (define char-in-string? (lambda (z str) (cond [(= (string-length str) 0) #f] [(equal? z (string-car str)) #t] [else (char-in-string? z (string-cdr str))]))) (define korrigieren (lambda (str) (cond [(= (string-length str) 0) ""] [(char-in-string? (string-car str) alphabet) (char-cons (string-car str) (korrigieren (string-cdr str)))] [else (korrigieren (string-cdr str))]))) (define test (lambda (str keyword richtung) (letrec ([keypos (lambda (str n) (if (= (string-length str) 0) "" (let ([step (- (char-pos (pos-char n keyword) alphabet) 1)]) (char-cons (wandeln (string-car str) (richtung step)) (keypos (string-cdr str) (+ n 1))))))]) (keypos str 1))))

Wir übernehmen das zulässige Alphabet, bestehend aus Großbuchstaben, Kleinbuchstaben und Ziffern, aus dem Cäsar-Verfahren. Auch die Vereinbarung, Sonderzeichen unberücksichtigt zu lassen, wollen wir beibehalten. Beim Codieren müssen wir nun dafür sorgen, dass das Schlüsselwort zyklisch "abgearbeitet" wird.

(define gross "ABCDEFGHIJKLMNOPQRSTUVWXYZ") (define klein "abcdefghijklmnopqrstuvwxyz") (define number "1234567890") (define sonder "+-/.,;:!? ") (define platzhalter #\*) (define alphabet (string-append gross klein number)) (define vor +) (define rueck -) (define wandeln (lambda (z step) (cond [(char-in-string? z sonder) z] [(char-in-string? z alphabet) (pos-char (+ (char-pos z alphabet) step) alphabet)] [else platzhalter]))) (define codieren (lambda (str keyword richtung) ...))

Wir legen ein gültiges Schlüsselwort fest:

(define schluesselwort "Informatik")

Wir verschlüsseln nun einen einfachen Text:

(define klartext "Das ist ein brisanter Informatik-Text!") (define geheimtext (codieren klartext schluesselwort vor))

geheimtext

ausführen

Nun muss dieser Text mit dem gleichen Schlüsselwort entschlüsselt werden können:

(define neutext (codieren geheimtext schluesselwort rueck))

neutext

ausführen

Abschließend experimentieren wir mit einem modifizierten Schlüsselwort:

(codieren geheimtext "Mathematik" rueck)

ausführen

Zusammmenfassung

• Das Vigenère-Verfahren ist ein symmetrisches polyalphabetisches Verschlüsselungsverfahren, d.h. ähnlich dem Cäsar-Verfahren wird nun ein Text mit dem gleichen Schlüsselwort entschlüsselt, mit dem er zuvor verschlüsselt wurde.
  Schlüsselwörter müssen auch in diesem Verfahren auf sehr sicheren Kanälen ausgetauscht werden.
• Ähnliche Schlüsselwörter gleicher Länge führen auch zu ähnlichen Ergebnissen beim Ver- bzw. Entschlüsseln.
• Die Sicherheit des Verfahrens ist um so größer, je länger das Schlüsselwort ist.
• Wenn die Länge des Schlüsselwortes bekannt ist, kann der Text mit Häufigkeitsanalysen aller Zeichen entschlüsselt werden, die untereinander den Abstand dieser Länge haben. Mit geschickten "Periodizitätsuntersuchungen" können also Vigenère-verschlüsselte Texte "geknackt" werden.

Zurück zu ausgewählten Algorithmen der Kryptologie.