Trencant un xifratge de substitució

Aquest estiu, la segona sessió de les vermutacions va ser sobre criptografia, i en Ramon ens va posar com a exercici desencriptar un text encriptat mitjançant un xifratge de substitució. Aquest xifrat es pot trencar amb un full i un llapis, i una mica de paciència. Per anar una mica més ràpid, jo vaig utilitzar un petit script en perl que havia fet fa un temps i que està només acabat a mitges, però és més o menys operatiu (però per exemple només agafa textos amb A-Z, sense Ç o lletres per l’estil). Al resoldre’l, em van demanar que pengés l’arxiu, i així ho he fet aquí (és el subsolve).

Subsolve llegeix un text encriptat de stdin o d’un arxiu de text, i llavors permet anar trencant interactivament el text (i la clau). Evidentment, va bé saber (o tenir-ne una suposició raonable) la llengua en què està escrit el text. En aquest cas, subsolve permet comparar les freqüències del text amb una taula de freqüències de l’idioma, si es té aquesta taula. Les taules han d’estar guardades en arxius amb el nom llengua.ngr, on llengua és el codi de la llengua (per exemple, jo utilitzo en per anglès, ca per català, etc.) i n és la longitud de la cadena de la que es recompta la freqüencia (1 per lletres, 2 per dígrams, etc.). L’arxiu ha de contenir a cada línia una lletra, un o més espais i un número (la seva freqüència). Per exemple, l’arxiu amb la llista de freqüències de lletres en català (ca.1gr) seria:

a 12.55
b 1.32
c 3.60
ç 1.06
d 3.94
e 13.89
f 1.00
g 1.28
h 0.72
i 6.99
j 0.30
k 0.00
l 7.74
m 3.16
n 6.40
o 5.71
p 2.72
q 1.35
r 6.76
s 8.43
t 6.11
u 4.18
v 1.40
w 0.00
x 0.52
y 0.00
z 0.01

Per analitzar un text català encriptat, guardat a l’arxiu exemple.txt, es crida l’script amb

./subsolve.pl -f exemple.txt --lang ca --spaces

L’opció --spaces separa les lletres en grups de cinc. Es poden posar menys caràcters per línia amb l’opció -w o --width (per exemple, -w 30).

Una vegada dins, l’opció help o ? ens llista les accions possibles, i help <acció> mostra ajuda específica per una acció (per exemple, help count). count n (o simplement n) compta les freqüències de grups de n lletres. add Ab afegeix la correspondència A->b, on A és una lletra del text encriptat i b la corresponent en el text original. remove Ab ho elimina. show text mostra el text (majúscules la part encriptada, minúscules la part ja resolta). show key mostra la clau. search <cadena> n busca cadena al text, i mostra els resultats envoltats de text a dreta i esquerra de llargada n. La cadena pot contenir majúscules i minúscules (i el programa entén què signifiquen), i també expressions regulars senzilles. Per exemple search A.d 2 busca cadenes que continguin la lletra encriptada A, seguida de qualsevol lletra, seguida de la lletra del text original d, i retorna els resultats amb dues lletres a l’esquerra i a la dreta; o search [AB]C busca la cadena AC o BC; o search [AB]{2} busca les cadenes AA, AB, BA o BB. Per a més informació, feu servir help, llegiu-vos el codi o pregunteu-ho aquí! Comentaris o extensions a l’script són més que benvinguts.

En Ramon també ens va posar un altre exercici: trencar el xifrat Vigenère. Però això ja és una mica més difícil…

otlcat: concatenate and print outline files

Aquest cap de setmana passat vaig escriure un petit script en perl que funciona de manera semblant al famós cat, però que està especialment orientat a outlines. Ho he fet més que res perquè últimament estic trastejant una mica amb The Vim Outliner, com ja vaig comentar fa alguna setmana. Entre altres coses he organitzat una mica alguns How To que tenia repartits entre l’ordinador, aquest blog i internet, i que intentaré penjar quan estiguin una mica més estructurats, i algunes receptes senzilles de cuina, entre les que destaca la paella de carn (dissabte passat va ser un èxit!), que potser també penjaré. Ja veurem.

L’script en qüestió, otlcat, serveix per a imprimir els continguts d’un arxiu a la sortida estàndard (stdout). Si es criden diversos arxius, el seu contingut es concatena. Fins aquí res diferent del cat. La gràcia és que si l’arxiu de text en qüestió és un outline amb el format que utilitza The Vim Outliner (tabuladors per a especificar les jerarquies, els títols comencen directament després dels tabuladors i el text està delimitat pel caràcter ‘|‘), otlcat té un cert control sobre l’output i pot imprimir només fins a una certa profunditat, només text o títols, o títols i text amb profunditats diferents. Per exemple,

$ otlcat -Th2 exemple.otl

imprimiria tots els títol de jerarquia 1 i 2, però cap bloc de text, de l’arxiu exemple.otl.

Com sempre, el codi es troba aquí. Si us mireu una mica el codi, podeu canviar fàcilment el delimitador de text ‘|‘ per algun altre caràcter. Crec, per exemple, que hi ha outliners que utilitzen la coma, o el punt i coma. Per a veure com utilitzar exactament el programa n’he escrit una documentació. N’hi ha prou amb escriure

$ otlcat --man

per obrir una pàgina a l’estil de les man. Instal·lar-la i poder-la consultar com qualsevol altre man és ben fàcil. Per exemple, per posar la pàgina man al vostre directori local:

$ pod2man path/to/otlcat > ~/share/man/man1/otlcat.1

Més endavant potser escriuré altres scripts (per exemple, per just el contrari, un otlsplit no estaria malament). Si teniu alguna suggerència serà benvinguda!

Com a exemple d’aplicació, otlcat es pot utilitzar directament des del vim. Per exemple, si ens volem carregar tot el text (però no els títols) d’un conjunt de línies, les podem seleccionar des del mode visual (s’hi entra amb v) i seguidament escriure

:!otlcat -T

(que en realitat quedaria com :'<'>!otlcat -T). Fàcil!

Simulador d’una màquina enigma amb perl (III): Simulador bàsic

Ve de “Simulador d’una màquina enigma amb perl (II): Components bàsics“.

En el post anterior he explicat els components bàsics de la màquina Enigma, amb petit exemple. Veiem-ne ara una senzilla implementació amb perl, que encripta totes les lletres utilitzant el mateix alfabet, sense fer girar els rotors.

Utilitzant el mateix exemple anterior, hem de configurar la nostra màquina Enigma de manera que els rotors esquerre ($L), central ($M)  i dret ($R) siguin, corresponentment, el 3, el 2 i l’1. A més, seleccionem el reflector ($U) B i de panell de connexions ($P) les parelles AQ i FS. Així tenim les primeres línies del programa:

#! /usr/bin/perl

use strict;

#        ABCDEFGHIJKLMNOPQRSTUVWXYZ
my $P = 'QBCDESGHIJKLMNOPARFTUVWXYZ';
my $R = 'EKMFLGDQVZNTOWYHXUSPAIBRCJ';
my $M = 'AJDKSIRUXBLHWTMCQGZNPYFVOE';
my $L = 'BDFHJLCPRTXVZNYEIWGAKMUSQO';
my $U = 'YRUHQSLDPXNGOKMIEBFZCWVJAT';

Ara ens cal llegir el missatge. Ja que hi som, el passem també a majúscules i n’eliminem tots els caràcters que no siguin les 26 lletres de l’alfabet bàsci llatí:

my $o;

while () {
    y/a-z/A-Z/;
    y/A-Z//dc;
    $o .= $_;
}

Ja tenim el text pla a la variable $o. La podem recórrer caràcter per caràcter i anar-hi aplicant la transformació (&e) que vulguem:

$o =~ s/(.)/&e/eg;

Una vegada aplicada la transformació, ja només ens cal imprimir el text xifrat resultant, que podem separar convenientment en grups de cinc:

$o =~ s/(.{5})/$1 /g;
print "$o\n";

exit 0;

Recordem finalment què cal fer per encriptar. Si és la transformació del panell de connexions, les transformacions dels rotors dret, central i esquerre, respectivament, i la del reflector, llavors la transformació d’encriptar (&e en el codi) és el producte de permutacions . Així, la subrutina &e es pot escriure com:

sub e {
    $_ = $&;
    eval "y/A-Z/$P/";
    eval "y/A-Z/$R/";
    eval "y/A-Z/$M/";
    eval "y/A-Z/$L/";
    eval "y/A-Z/$U/";
    eval "y/$L/A-Z/";
    eval "y/$M/A-Z/";
    eval "y/$R/A-Z/";
    eval "y/$P/A-Z/";
    return $_;
}

Però atenció! Fins ara estem encriptant sempre amb el mateix alfabet, i això ofereix exactament la mateixa seguretat que un simple xifrat de substitució. Per canviar d’alfabet a cada lletra, la màquina enigma girava un o més rotors abans d’introduir cada lletra. Això ho veurem al proper post d’aquesta sèrie.

Segueix a “Simulador d’una màquina enigma amb perl (IV): El moviment dels rotors“.

Xifratge de transposició de columnes

Seguint amb la sèries de posts sobre sistemes criptogràfics simples, avui toca el xifratge de transposició de columnes. Els xifratges de transposició es basen en un simple reordenament de les lletres (o grups de lletres) d’un missatge. És a dir, el text xifrat és una simple permutació del missatge original.

En el cas de la transposició de columnes, el missatge original s’encripta escrivint el text en files d’una amplada determinada i llegint-lo per columnes. Aquestes columnes, abans de llegir-les, es poden reordenar seguint algun patró concret. Tant l’amplada de les columnes com l’ordre en què es llegeixen poden quedar fixats per la clau, que pot ser una paraula. Per exemple, la paraula “pebrot” té sis caràcters, i aquesta és doncs l’amplada de les files. La permutació de columnes queda determinada per l’ordre alfabètic dels caràcters de la clau, en aquest cas “16 5 2 18 15 20″. Utilitzant aquesta clau per encriptar el missatge “En Joan petit quan balla ara balla amb el dit” escriuríem:

P E B R O T
E N J O A N
P E T I T Q
U A N B A L
L A A R A B
A L L A A M
B E L D I T

El resultat encriptat queda, doncs,

JTNAL LNEAA LEATA AAIEP ULABO IBRAD NQLBM T

En aquest cas també he escrit un petit script en Perl, però no el copio directament aquí. Us el podeu copiar de la meva pàgina personal.

També he estat escrivint un simulador de l’Enigma, la màquina alemanya utilitzada durant la Segona Guerra Mundial. Properament, explicat en detall a Q. Manteniu-vos atents!

Quadern d’un sol ús

El quadern d’un sol és (one-time pad, OTP, en anglès) és un sistema de criptografia impossible de trencar si s’utilitza correctament. Es tracta d’un sistema de xifratge per substitució, on per encriptar se suma una clau secreta completament aleatòria al text pla. Per desencriptar, s’ha de restar la clau. En el cas de suma i restar lletres, per exemple, s’assigna un valor a cada lletra () i se suma un a un cada número del text pla amb el de la clau, mòdul 26. Per desencriptar, es fa el mateix però restant.

Aquí teniu altra vegada un script amb perl.

#! /usr/bin/perl -s

if ($h) {
   print<<"INFO";
$0 - One-time pad

Usage: $0 file

Read from stdin, output to stdout. Use file as the one-time pad. Use -d for
decipher.
INFO
    exit 0;
}

$f = $d ? -1 : 1;

$if = shift;
open IF, "$if" or die "Can't open file '$if'.\n";
while () {
    y/a-z/A-Z/;
    y/A-Z//dc;
    $p .= $_;
}
close P;

while (<>) {
    y/a-z/A-Z/;
    y/A-Z//dc;
    $o .= $_;
}
$o .= 'X' while length ($o)%5;
die "One-time pad '$if' is too short.\n" if (length ($o) > length ($p));
$o =~ s/./chr((ord($&)-ord('A')+$f*&e)%26+ord('A'))/eg;
$o =~ s/(.{5})/$1 /g;

print "$o\n";

sub e {
    $p =~ s/^(.)//;
    return ord($1) - ord('A') + 1;
}