Bergervei/Caesar-Verschlüsselung

Wiki-Quelltext dieser Seite.

<language>SchemeJS</language>
<code id="5bc3035bb1d9a" hidden>
(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 korrekt?
  (lambda (str)
    (and (char-in-string? (string-car str) alphabet) (= (string-length str) 1))))
</code>

== Monoalphabetische Verschlüsselung ==

[[Bild:Caesar_Verschiebung.png|miniatur|hochkant=1.5|Schematische Darstellung einer Verschiebung um drei Buchstaben]]
[[Bild:Julius_Caesar.jpg|miniatur|links|Gaius Julius Caesar]]
Bei der monoalphabetischen Verschlüsselung wird jeder Buchstabe des Klartexts auf ein "Geheimalphabet" abgebildet. Dieses Geheimalphabet ergibt sich, indem man die Zeichen eines geordneten Alphabets um eine bestimmte Anzahl zyklisch nach rechts verschiebt (rotiert) und beim Verschieben über Z hinaus bei A beginnend weiterzählt. Die Verschiebungsweite bildet den Schlüssel, der für die gesamte Verschlüsselung unverändert bleibt. Als Schlüsselbuchstaben bezeichnet man den Anfangsbuchstaben des Geheimalphabets. Die Entschlüsselung erfolgt mit dem gleichen Schlüssel bzw. Schlüsselbuchstaben in umgekehrter Richtung.

Der Name der Caesar-Verschlüsselung geht auf den römischen Feldherrn '''Gaius Julius CAESAR''' (* 13. Juli 100 v. Chr.; † 15. März 44 v. Chr.) zurück, der diese Art der geheimen Kommunikation für seine militärische Korrespondenz verwendet haben soll. Dabei soll er eine Verschiebung des Alphabets um drei Buchstaben benutzt haben.

Verschlüsselungen, bei denen Texte mit dem gleichen Schlüssel sowohl ver- als auch entschlüsselt werden, heißen ''symmetrische Verschlüsselungsverfahren''.

== Implementation ==

Zunächst definieren wir das zulässige Alphabet, bestehend aus Groß- und Kleinbuchstaben sowie Ziffern. Um Textstrukturen zu erhalten, wollen wir die Sonderzeichen nicht in die Verschlüsselung einbeziehen.<br />
Der Schlüsselbuchstabe ist eine Zeichenkette mit der Länge 1.<br /> 
Das Ver- und Entschlüsseln soll mit den gleichen Prozeduren erfolgen. Lediglich "verschiedene Richtungen" müssen dabei berücksichtigt werden. 

<code id="5bc30a3c2133b">
(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 key richtung)
    (if (= (string-length str) 0) 
        ""
        (let ([step (- (char-pos (pos-char 1 key) alphabet) 1)])
         (char-cons (wandeln (string-car str) (richtung step)) 
                    (codieren (string-cdr str) key richtung))))))
</code>

Wir legen einen gültigen Schlüsselbuchstaben fest:

<code id="5bc35291c82f1">
(define schluesselbuchstabe "D")
</code>

<check>
(korrekt? schluesselbuchstabe) 
</check>

Nun verschlüsseln wir einen einfachen Text:

<code id="5bc3119bcc345">
(define klartext "Das ist ein relativ kurzer, aber brisanter Informatik-Text!")
(define geheimtext (codieren klartext schluesselbuchstabe vor))
</code>

<run id="5bc3035bb1f58">
geheimtext
</run>

<code id="5bc30a3c21455">
(define neutext (codieren geheimtext schluesselbuchstabe rueck))
</code>

<run id="5bc30a3c214eb">
neutext
</run>

== Häufigkeitsuntersuchungen ==

Eine monoalphabetische Verschlüsselung ist natürlich schnell zu "knacken". Im ungünstigsten Fall benötigen wir die Anzahl von Versuchen, die der Länge des verwendeten Alphabets entspricht.<br />
Im Allgemeinen geht es noch schneller, wenn wir den Schlüsselbuchstaben geschickt "erraten". Dazu ermitteln wir zunächst den häufigsten Buchstaben im Geheimtext. Zu ihm bestimmen wir die Verschiebungsweite, die sich zu einem häufig vermuteten Buchstaben im Klartext ergibt. Mit wenigen Versuchen lässt sich so der Klartext ermitteln.

<code id="5bc35291c837e">
(define maxbuchstabe
  (lambda (str)
    (letrec
        ([anzahl
          (lambda (el ls)
            (cond 
              [(null? ls) 0]
              [(eqv? el (car ls)) (+ 1 (anzahl el (cdr ls)))]
              [else
               (anzahl el (cdr ls))]))]
         [maxpaar
          (lambda (ls1 ls2)
            (if (null? ls1)
                (cons 0 #f)
                (let ([paar1 (cons (anzahl (car ls1) ls2) (car ls1))]
                      [paar2 (maxpaar (cdr ls1) ls2)])
                  (if (> (car paar1) (car paar2))
                      paar1
                      paar2))))])
      (string (cdr (maxpaar (string->list alphabet) (string->list str)))))))

(define knacken
  (lambda (str max-key new-key)
    (if (= (string-length str) 0) 
        ""
        (let ([step (- (char-pos (string-car new-key) alphabet) (char-pos (string-car max-key) alphabet))])
          (char-cons (wandeln (string-car str) step) 
                     (knacken (string-cdr str) max-key new-key))))))
</code>

Wir suchen den häufigsten Buchstaben im Geheimtext...

<code id="5bc354d71d9f0">
(define max-key (maxbuchstabe geheimtext))
</code>

<run id="5bc354d71da99">
max-key
</run>

... und führen ihn auf einen vermutlich häufigen Buchstaben des Klartextes zurück:

<run id="5bc35291c84e7">
(knacken geheimtext max-key "e")
</run>

Sollte der erste Versuch nicht zum Ziel führen, kann dieses Vorgehen natürlich auch "automatisiert" werden:

<code id="5bc35291c83f6">
(define mehrfachtest
  (lambda (str max-key new-str)
    (if (= (string-length new-str) 0)
        'ok
        (begin
          (display (knacken str max-key (string (string-car new-str))))
          (mehrfachtest str max-key (string-cdr new-str))))))
</code>

<run id="5bc35291c854a">
(mehrfachtest geheimtext max-key "ernstl")
</run>