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.

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

== 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 />
Den Schlüsselbuchstaben entspricht einer Zeichenkette mit der Länge 1. 
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="5bc3119bcc2b2">
(define schluesselbuchstabe "C")
</code>

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

Wir verschlüsseln nun 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="5bc3119bcc3bb">
(define maxzeichen
  (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>

<run id="5bc3119bcc43e">
(define max-key (maxzeichen geheimtext))
max-key
</run>

<run id="5bc3119bcc4a3">
(define new-key "r")
(knacken geheimtext max-key new-key)
</run>