GNU Coreutils Codegolf

Neulich habe ich einige Perl-Einzeiler und ed/sed-Skripte gesehen, die mit minimalem Aufwand erstaunliche Ergebnisse liefern. Das hat mich inspiriert, einen Eigenen zu erstellen: Einen Einzeiler, der eine Substitutionschiffre entschlüsselt. Dabei spielt vorallem das Prinzip der UNIX-Pipe eine große Rolle.

Kurzum: Eine Substitutionschiffre ist eine der einfacheren (und auch unsichereren) Chiffren. Bei der Verschlüsselung wird ein Buchstabe des Klartextes durch einen des Schlüssels ersetzt. Obwohl die Chiffre praktisch nicht durch Brute-Force zu knacken ist (aufgrund des großen Schlüsselraums von $2^{88}$ ), ist sie anfällig für Kryptoanalyse¹. Über die Berechnung der Buchstabenfrequenz kann jeder Buchstabe mit der jeweiligen Frequenzposition der jeweiligen Sprache ausgetauscht werden. Um das alles in der Shell zu erreichen wird eine Pipeline kurz Pipe verwendet. In unixodien Betriebssystemen und deren Standard-Befehlszeilenprogramme (in Linux z.B. die GNU Coreutils) ist es möglich Standard-Datenströme miteinander zu verketten. Ein Programm empfängt dabei über die Standardeingabe (stdin) die Standardausgabe (stdout) des jeweils vorher aufgerufenen. Gegeben ist Substitutionschiffre 00_chiffrat2.txt:

Mit folgendem Einzeiler ist es möglich die gegebene Chiffre zu entschlüsseln:

tr $(sed 's/[.[:space:],:\-]//g' 00_chiffrat2.txt | fold -w1 | sort | uniq -c | sort -nr | awk '{ printf "%s", $2 }') 'etoainshrldwfcugympbvkzq' < 00_chiffrat2.txt

Okay, ehrlich gesagt handelt es sich hierbei um einen ziemlich langen Einzeiler der auch noch recht unübersichtlich ist. Dafür breche ich nun Schritt für Schritt herunter, was die einzelnen Befehle bewirken. Da eine Technik namens Befehlssubstitution (engl. command substitution) verwendet wurde, bietet es sich an, damit zu beginnen. Bei einer Befehlssubtitution wird der geschriebene Befehl (zwischen den Klammern nach dem $-Zeichen: $(<befehl>)) durch seine Ausgabe ersetzt. Bei der nachfolgenden Befehlssubstitution handelt es sich gleichzeitig auch um den komplexesten Vorgang des Einzeilers, nämlich die Frequenzanalyse der einzelnen Buchstaben des Textes:

sed 's/[.[:space:],:\-]//g' 00_chiffrat2.txt | fold -w 1 | sort | uniq -c | sort -nr | awk '{ printf "%s", $2 }'

Da die Substitution aber immer noch relativ sperrig ist, kann die Befehlskette noch weiter heruntergebrochen werden:

sed 's/[.[:space:],:\-]//g' 00_chiffrat2.txt

In diesem Schritt wird der Chiffrattext bereinigt. Hierfür wird der Stream-Editor sed mit dem Befehlt s verwendet. Dieser erlaubt es, einen regulären Ausdruck REGEX anzugeben, der mit einer ERSETZUNG und einem optionalen UMFANG (g für global) Zeichen im Text ersetzt (s/REGEX/ERSETZUNG/UMFANG). In diesem Fall sollen Punkte, Kommata, Bindestriche und Leerzeichen entfernt werden. Ziel ist es lediglich Buchstaben von a bis z zu erhalten, um deren Anzahl zu definieren:

actprphkamecqdnggpwafpxkanpfgceiqndqlrtikirckalafmceakciiftafrcdfroaceearqeaffvbbnigafcdearhkiprcafpfiuudkccdirqpxiceisanitafgrnaxxigjvaqlnwcekdvmeceimnprrgddkrdusaqcdkwopfradfrcedvmefdcjvaqlnwifdvmecdxkisifcprtakndumkaccwgvrcukdoifcikafmpndfmtaceeao

ceiepnntpwroincduhdanigqphhpmipfgdngkpmopcrpcdfiifgduacpqdndvkigxdrcikcddnpkmiudkafgddkgarxnpwepghiifcpqligcdceitpnnacgixaqcigraoxnwpfifdkodvrupqiodkicepfpoickitagiceiupqidupopfduphdvcudkcwuasitacepeipswhnpqlodvrcpqeipfgkvmmignwepfgrdoiuipcvkirtafrcdfopgiudkceircpakractprfdvrickwafmceinaucisifpcceihircducaoiractprringdotdklafmpfgpcxkirifcceiiniqckaqqvkkifctprqvcduugvkafmgpwnamecedvkractprxpkcduceiiqdfdowgkasiafxkixpkpcadfudkepcitiilceiunpctprrisifunamecrvxpfgtafrcdftedtprceakcwfafipfgepgpspkaqdrivnqikphdsiearkamecpflnitifcrndtnwkircafmrisikpncaoirdfceitpwdfipqenpfgafmdxxdraciceinaucrepucceixdrciktaceceiifdkodvrupqimpbigukdoceitpnnactprdfiducedrixaqcvkirteaqepkirdqdfckasigcepcceiiwirudnndtwdvphdvcteifwdvodsihamhkdceikartpcqeafmwdvceiqpxcadfhifipceackpf

Um die Anzahl jedes einzelnen Buchstaben zählen zu können, muss sich jeder Buchstabe in einer einzelnen Zeile befinden. Das wird durch Zuhilfenahme des Befehls fold erreicht bei dem das Argument -w die Anzahl der Spalten (hier 1) angibt:

sed 's/[.[:space:],:\-]//g' 00_chiffrat2.txt | fold -w 1

Daraus resultiert folgende Ausgabe (zur Übersichtlichkeit wurde die Mitte gekürzt):

a
c
t
p
r
…
a
c
k
p
f%

Im nächsten Schritt können alle Buchstaben Alphabetisch sortiert werden. Das ist notwendig, um im nächsten Schritt die Anzahl der Wiederholungen im Text zählen zu können. Das Programm sort sortiert die gelieferte Eingabe standardmäßig alphabetisch:

sed 's/[.[:space:],:\-]//g' 00_chiffrat2.txt | fold -w 1 | sort

Das Ergebnis (zur Übersichtlichkeit wurde die Mitte gekürzt):

a
a
a
a
…
x
x
x
x
x

Das Befehlszeilenprogramm uniq mit dem Argument -c zählt die wiederkehrende Anzahl eines Buchstaben:

sed 's/[.[:space:],:\-]//g' 00_chiffrat2.txt | fold -w 1 | sort | uniq -c

Nun steht links neben jedem Buchstaben seine Wiederkehrende Anzahl:

      1 
     73 a
      3 b
    103 c
     82 d
     59 e
     66 f
     35 g
     14 h
    110 i
      2 j
     57 k
      9 l
     25 m
     41 n
     21 o
     81 p
     30 q
     60 r
     13 s
     31 t
     30 u
     26 v
     21 w
     19 x

Listen von Buchstabenfrequenzen werden meist in Absteigender Ordnung gegeben. Wieder wird sort verwendet welches durch das Argument -nr die Buchstaben nach deren Vorkommen im Text sortiert:

sed 's/[.[:space:],:\-]//g' 00_chiffrat2.txt | fold -w 1 | sort | uniq -c | sort -nr

Der Buchstabe mit der höchsten Frequenz steht nun oben:

    110 i
    103 c
     82 d
     81 p
     73 a
     66 f
     60 r
     59 e
     57 k
     41 n
     35 g
     31 t
     30 u
     30 q
     26 v
     25 m
     21 w
     21 o
     19 x
     14 h
     13 s
      9 l
      3 b
      2 j
      1 

Im letzten Schritt der Frequenzanalyse wird eine Zeichenkette auf einer einzelnen Zeile gebildet. Hierfür verwende ich AWK. AWK an sich ist eine eigene Programmiersprache (was schon fast an schummeln grenzt – wird aber häufig im Linux/Unix Umfeld genutzt). Vielleicht ist das auch noch eleganter zu lösen, diese Lösung war aber auf die Schnelle war die Einzige die mir eingefallen ist:

sed 's/[.[:space:],:\-]//g' 00_chiffrat2.txt | fold -w 1 | sort | uniq -c | sort -nr | awk '{ printf "%s", $2 }'

Wir erhalten die Buchstabenfrequenz die unser Chiffrat repräsentiert:

icdpafrekngtuqvmwoxhslbj%

Bekannt ist, dass das vorliegende Chiffrat ein englischer Text ist. Es wird daher daher die Buchstabenfrequenz englischer Texte benötigt, welche gegeben ist. Nun wird mit tr die berechnete Buchstabenfrequenz mit der englischen übersetzt². Aus Gründen der Übersichtlichkeit wurde die lange Befehlssubstitution mit der berechneten Buchstabenfrequenz ersetzt:

tr 'icdpafrekngtuqvmwoxhslbj' 'etoainshrldwfcugympbvkzq' < 00_chiffrat2.txt

Entschlüsselt lautet der Text:

it was a bright cold day in april, and the clocks were striking thirteen. winston smith, his chin nuzzled into his breast in an effort to escape the vile wind, slipped quickly through the glass doors of victory mansions, though not quickly enough to prevent a swirl of gritty dust from entering along with him.

the hallway smelt of boiled cabbage and old rag mats. at one end of it a coloured poster, too large for indoor display, had been tacked to the wall. it depicted simply an enormous face, more than a metre wide: the face of a man of about forty-five, with a heavy black moustache and ruggedly handsome features. winston made for the stairs. it was no use trying the lift. even at the best of times it was seldom working, and at present the electric current was cut off during daylight hours. it was part of the economy drive in preparation for hate week. the flat was seven flights up, and winston, who was thirty-nine and had a varicose ulcer above his right ankle, went slowly, resting several times on the way. on each landing, opposite the lift-shaft, the poster with the enormous face gazed from the wall. it was one of those pictures which are so contrived that the eyes follow you about when you move. big brother is watching you, the caption beneath it ran. % 

Anmerkungen: Buchstabenketten die mit tr verwendet werden, müssen die gleiche Länge haben, sonst funktioniert die Übersetzung nicht. Es sei außerdem noch erwähnt, dass vereinzelt Buchstaben vertauscht wurden die mitunter eine ähnliche Frequenz im Englischen haben. Bei längeren Chiffraten tritt dieser Fehler aber nicht auf.