Grundlagen der funktionsorientierten Programmierung mit SCHEME/Das Vigenère-Verfahren

Wiki-Quelltext dieser Seite.

<language>SchemeJS</language>
== Polyalphabetische Verschlüsselung ==

[[Datei:Blaise_Vigenere.jpg|miniatur|Blaise de Vigenère]]

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.<br />
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:

[[Datei:Vigenere1.jpg]]

Wir gehen also von der ''monoalphabetischen'' zur ''polyalphabetischen'' Verschlüsselung über.<br />
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 ==

<code id="5c5aa01e96c00" hidden>
(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))))
</code>

Wir übernehmen das zulässige Alphabet, bestehend aus Großbuchstaben, Kleinbuchstaben und Ziffern, aus dem [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Das Cäsar-Verfahren|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.

<code id="5c5aa01e96ca6">
(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)
    ...))
</code>

<check>
(let ([str "Verschlüsselungen in der Kryptologie"] [keyword "Geheimnis"])
  (and (equal? (codieren str keyword vor) (test str keyword vor))
       (equal? (codieren (codieren str keyword vor) keyword rueck)
               (test (test str keyword vor) keyword rueck))))
</check>

Wir legen ein gültiges Schlüsselwort fest:

<code id="4cb0c587632e7">
(define schluesselwort "Informatik")
</code>

<check>
(equal? schluesselwort (korrigieren schluesselwort)) 
</check>

Wir verschlüsseln nun einen einfachen Text:

<code id="4cb0c58763402">
(define klartext "Das ist ein brisanter Informatik-Text!")
(define geheimtext (codieren klartext schluesselwort vor))
</code>

<run id="4cb0c58763660">
geheimtext
</run>

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

<code id="4cb0c58763524">
(define neutext (codieren geheimtext schluesselwort rueck))
</code>

<run id="4cb0c58763780">
neutext
</run>

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

<run id="4cb0c5876389b">
(codieren geheimtext "Mathematik" rueck)
</run>

== Zusammmenfassung ==

<ul>
<li>
Das Vigenère-Verfahren ist ein ''symmetrisches polyalphabetisches'' Verschlüsselungsverfahren, d.h. ähnlich dem [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Das Cäsar-Verfahren|Cäsar-Verfahren]] wird nun ein Text mit dem gleichen Schlüsselwort entschlüsselt, mit dem er zuvor verschlüsselt wurde.<br />
Schlüsselwörter müssen auch in diesem Verfahren auf sehr sicheren Kanälen ausgetauscht werden.
</li>
<li>
Ähnliche Schlüsselwörter gleicher Länge führen auch zu ähnlichen Ergebnissen beim Ver- bzw. Entschlüsseln.
</li>
<li>
Die Sicherheit des Verfahrens ist um so größer, je länger das Schlüsselwort ist.
</li>
<li>
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.
</li>
</ul>

Zurück zu [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Ausgewählte Algorithmen der Kryptologie|ausgewählten Algorithmen der Kryptologie]].