GNU Coreutils Codegolf

Neulich habe ich einige fancy 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 ist ein Substitutionschiffre 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: $2^{88}$ , ist sie allerdings 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 Standarteingabe (stdin) die Standartausgabe (stdout) des jeweils vorher aufgerufenen.

Gegeben ist folgende Substitutionschiffre aka. 00_chiffrat2.txt:

ac tpr p hkamec qdng gpw af pxkan, pfg cei qndqlr tiki 
rckalafm ceakciif. tafrcdf roace, ear qeaf fvbbnig afcd ear 
hkiprc af pf iuudkc cd irqpxi cei sani tafg, rnaxxig jvaqlnw 
cekdvme cei mnprr gddkr du saqcdkw opfradfr, cedvme fdc 
jvaqlnw ifdvme cd xkisifc p rtakn du mkaccw gvrc ukdo ifcikafm 
pndfm tace eao. 
 
cei epnntpw roinc du hdanig qphhpmi pfg dng kpm opcr. pc dfi 
ifg du ac p qdndvkig xdrcik, cdd npkmi udk afgddk garxnpw, epg 
hiif cpqlig cd cei tpnn. ac gixaqcig raoxnw pf ifdkodvr upqi, 
odki cepf p oicki tagi: cei upqi du p opf du phdvc udkcw-uasi, 
tace p eipsw hnpql odvrcpqei pfg kvmmignw epfgrdoi uipcvkir. 
tafrcdf opgi udk cei rcpakr. ac tpr fd vri ckwafm cei nauc. 
isif pc cei hirc du caoir ac tpr ringdo tdklafm, pfg pc 
xkirifc cei iniqckaq qvkkifc tpr qvc duu gvkafm gpwnamec 
edvkr. ac tpr xpkc du cei iqdfdow gkasi af xkixpkpcadf udk 
epci tiil. cei unpc tpr risif unamecr vx, pfg tafrcdf, ted tpr 
ceakcw-fafi pfg epg p spkaqdri vnqik phdsi ear kamec pflni, 
tifc rndtnw, kircafm risikpn caoir df cei tpw. df ipqe 
npfgafm, dxxdraci cei nauc-repuc, cei xdrcik tace cei ifdkodvr 
upqi mpbig ukdo cei tpnn. ac tpr dfi du cedri xaqcvkir teaqe 
pki rd qdfckasig cepc cei iwir udnndt wdv phdvc teif wdv odsi. 
ham hkdceik ar tpcqeafm wdv, cei qpxcadf hifipce ac kpf

Mit folgendem One-Liner 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 One-Liner 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. Denn 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, 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 für 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 auszutauschen in einem. Also 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 der jedes einzelnen Buchstaben zählen zu können, muss sich jeder Buchstabe in einer einzelnen Zeile befinden. Das wird mit durch Zuhilfenahme des Befehls fold erreicht bei dem das Argument -w die Anzahl der Spalten 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 standartmäß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

Buchstabe mit der höchsten Frequenz steht 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. Sie wird aber häufig im Linux/Unix Umfeld genutzt. Vielleicht geht es auch noch eleganter – auf die Schnelle war das aber die einzige Möglichkeit 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%

Wir wissen, dass das vorliegende Chiffrat ein englischer Text ist und benötigen Daher die Buchstabenfrequenz englische Texte. Nun wird mit tr die unsere berechnete Buchstabenfrequenz mit der englischen übersetzt². Zu 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.