Caesar-Verschlüsselung

Aus ProgrammingWiki

(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))))

Monoalphabetische Verschlüsselung

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.
Der Schlüsselbuchstabe ist eine 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.

(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))))))

Wir legen einen gültigen Schlüsselbuchstaben fest:

(define schluesselbuchstabe "D")

Nun verschlüsseln wir einen einfachen Text:

(define klartext "Das ist ein relativ kurzer, aber brisanter Informatik-Text!") (define geheimtext (codieren klartext schluesselbuchstabe vor))

geheimtext

ausführen

(define neutext (codieren geheimtext schluesselbuchstabe rueck))

neutext

ausführen

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.
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.

(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))))))

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

(define max-key (maxbuchstabe geheimtext))

max-key

ausführen

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

(knacken geheimtext max-key "e")

ausführen

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

(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))))))

(mehrfachtest geheimtext max-key "ernstl")

ausführen