Cryptographie M1 Informatique 2017-2018

Cours 1

Introduction

Autrefois réservée aux communications militaires et diplomatiques, la cryptographie fait aujourd'hui partie du quotidien de tout informaticien, et en fait de tout utilisateur d'un site de commerce en ligne, d'une carte bancaire, d'un téléphone portable ou même d'une télécommande de porte de garage, même si ceux-ci n'en sont pas forcément conscients.

On peut distinguer quelques grandes périodes dans l'histoire de la cryptographie. De l'antiquité à la fin du moyen-âge, on utilisait essentiellement des systèmes de transposition simple, ou chiffres monoalphabétiques : chaque lettre est remplacée par une autre, toujours la même (une permutation de l'alphabet, donc). Les plus anciens de ces systèmes sont la scytale (mentionnée par Plutarque) et le chiffre de César (mentionné par Suétone dans la vie des douze Cesars).

La cryptanalyse de ces systèmes n'est pas difficile et relève plus de la rubrique « jeux » des magazines que de la cryptologie moderne. La résolution de certains cryptogrammes peut malgré tout demander une bonne dose de patience et d'ingéniosité, et reste une bonne source d'exercices de programmation.

À la renaissance, on voit apparaître de nouveaux systèmes beaucoup plus résistants, dont le plus célèbre est le chiffre de Vigenère. Considéré comme sûr pendant près de trois siècles, il a été craqué dans la seconde moitié du XIXème siècle.

Entre cette période et la seconde guerre mondiale, on voit apparaître de nombreux chiffres nouveaux, et parallèlement de nouvelles méthodes de cryptanalyse.

On peut considérer que la cryptographie « moderne » commence pendant la seconde guerre mondiale, avec la construction en Angleterre du premier ordinateur, destiné au décryptage des communications allemandes.

Dans les années 1970, le déploiement des réseaux informatiques oblige à repenser la cryptographie : si $N$ noeuds d'un réseau doivent pouvoir communiquer confidentiellement les uns avec les autres, il faut en principe $N(N-1)/2$ clefs (une pour chaque lien bidirectionnel), ou à la rigueur router les communications par un noeud central, mais comment assurer que les $N$ clefs puissent être distribuées sans qu'aucune ne soit interceptée ? La solution est fournie par la cryptographie à clef publique.

On trouvera ici les definitions des principaux termes utilisée en cryptographoe.

Niveau 0: le chiffre de César

Le principe est de décaler cycliquement la valeur de chaque lettre (de 3 dans l'exemple historique).

Le plus simple est de construire une table de traduction (module string).

In [1]:
# Chiffre de César

from string import ascii_uppercase as AA
from string import ascii_lowercase as aa
k = 3
BB = AA[k:]+AA[:k]
print AA
print BB
ABCDEFGHIJKLMNOPQRSTUVWXYZ
DEFGHIJKLMNOPQRSTUVWXYZABC

In [2]:
from string import maketrans
tt = maketrans(aa,BB)
text = 'le cheval de mon cousin ne mange du foin que le dimanche'
msg = text.translate(tt)
print msg
OH FKHYDO GH PRQ FRXVLQ QH PDQJH GX IRLQ TXH OH GLPDQFKH

Comme il n'y a que 25 clés possibles, il est évidemment possible de les essayer toutes. Toutefois, la méthode statistique nous sera utile dans des cas plus difficiles ...

In [3]:
# Cryptanalyse

stats = {c:msg.count(c) for c in set(msg)}
print stats
{' ': 11, 'D': 3, 'G': 3, 'F': 3, 'I': 1, 'H': 8, 'K': 2, 'J': 1, 'L': 3, 'O': 3, 'Q': 6, 'P': 3, 'R': 3, 'T': 1, 'V': 1, 'Y': 1, 'X': 3}

In [4]:
ll = stats.items()
ll.sort(lambda x,y:y[1]-x[1])
print ll
[(' ', 11), ('H', 8), ('Q', 6), ('D', 3), ('G', 3), ('F', 3), ('L', 3), ('O', 3), ('P', 3), ('R', 3), ('X', 3), ('K', 2), ('I', 1), ('J', 1), ('T', 1), ('V', 1), ('Y', 1)]

In [5]:
# La lettre la plus fréquente est 'H', qui encode donc probablement le 'E'
# Ca ne marche pas à tous les coups

perec = '''Anton Voyl n'arrivait pas à dormir. Il alluma. Son Jaz marquait minuit vingt. Il poussa un profond soupir, 
s'assit dans son lit, s'appuyant sur son polochon. Il prit un roman, il l'ouvrit, il lut; mais il n'y saisissait qu'un 
imbroglio confus, il butait à tout instant sur un mot dont il ignorait la signification.
Il abandonna son roman sur son lit. Il alla à son lavabo; il mouilla un gant qu'il passa sur son front, sur son cou.
Son pouls battait trop fort. Il avait chaud. Il ouvrit son vasistas, scruta la nuit. Il faisait doux. 
Un bruit indistinct montait du faubourg. Un carillon, plus lourd qu'un glas, plus sourd qu'un tocsin, 
plus profond qu'un bourdon, non loin, sonna trois coups. Du canal Saint-Martin, un clapotis plaintif signalait 
un chaland qui passait.
Sur l'abattant du vasistas, un animal au thorax indigo, à l'aiguillon safran, ni un cafard, ni un charançon, 
mais plutôt un artison, s'avançait, traînant un brin d'alfa. Il s'approcha, voulant l'aplatir d'un coup vif, mais 
l'animal prit son vol, disparaissant dans la nuit avant qu'il ait pu l'assaillir.'''


# Pour pouvoir traiter du texte "normal", c'est à dire en UTF-8 avec des lettres accentuées , le petit bricolage
# vu dans le cours de Python sera utile

xx = 'àâäéèêëïîôöùûüÿç'.decode('utf8').encode('latin1')
yy = 'aaaeeeeiioouuuyc'.decode('utf8').encode('latin1')
uu = maketrans(xx,yy)

text = perec.decode('utf8').encode('latin1').translate(uu).lower()
print text
anton voyl n'arrivait pas a dormir. il alluma. son jaz marquait minuit vingt. il poussa un profond soupir, 
s'assit dans son lit, s'appuyant sur son polochon. il prit un roman, il l'ouvrit, il lut; mais il n'y saisissait qu'un 
imbroglio confus, il butait a tout instant sur un mot dont il ignorait la signification.
il abandonna son roman sur son lit. il alla a son lavabo; il mouilla un gant qu'il passa sur son front, sur son cou.
son pouls battait trop fort. il avait chaud. il ouvrit son vasistas, scruta la nuit. il faisait doux. 
un bruit indistinct montait du faubourg. un carillon, plus lourd qu'un glas, plus sourd qu'un tocsin, 
plus profond qu'un bourdon, non loin, sonna trois coups. du canal saint-martin, un clapotis plaintif signalait 
un chaland qui passait.
sur l'abattant du vasistas, un animal au thorax indigo, a l'aiguillon safran, ni un cafard, ni un charancon, 
mais plutot un artison, s'avancait, trainant un brin d'alfa. il s'approcha, voulant l'aplatir d'un coup vif, mais 
l'animal prit son vol, disparaissant dans la nuit avant qu'il ait pu l'assaillir.

In [6]:
# Maintenant, chiffrons le :

msg = text.translate(tt)
print msg
DQWRQ YRBO Q'DUULYDLW SDV D GRUPLU. LO DOOXPD. VRQ MDC PDUTXDLW PLQXLW YLQJW. LO SRXVVD XQ SURIRQG VRXSLU, 
V'DVVLW GDQV VRQ OLW, V'DSSXBDQW VXU VRQ SRORFKRQ. LO SULW XQ URPDQ, LO O'RXYULW, LO OXW; PDLV LO Q'B VDLVLVVDLW TX'XQ 
LPEURJOLR FRQIXV, LO EXWDLW D WRXW LQVWDQW VXU XQ PRW GRQW LO LJQRUDLW OD VLJQLILFDWLRQ.
LO DEDQGRQQD VRQ URPDQ VXU VRQ OLW. LO DOOD D VRQ ODYDER; LO PRXLOOD XQ JDQW TX'LO SDVVD VXU VRQ IURQW, VXU VRQ FRX.
VRQ SRXOV EDWWDLW WURS IRUW. LO DYDLW FKDXG. LO RXYULW VRQ YDVLVWDV, VFUXWD OD QXLW. LO IDLVDLW GRXA. 
XQ EUXLW LQGLVWLQFW PRQWDLW GX IDXERXUJ. XQ FDULOORQ, SOXV ORXUG TX'XQ JODV, SOXV VRXUG TX'XQ WRFVLQ, 
SOXV SURIRQG TX'XQ ERXUGRQ, QRQ ORLQ, VRQQD WURLV FRXSV. GX FDQDO VDLQW-PDUWLQ, XQ FODSRWLV SODLQWLI VLJQDODLW 
XQ FKDODQG TXL SDVVDLW.
VXU O'DEDWWDQW GX YDVLVWDV, XQ DQLPDO DX WKRUDA LQGLJR, D O'DLJXLOORQ VDIUDQ, QL XQ FDIDUG, QL XQ FKDUDQFRQ, 
PDLV SOXWRW XQ DUWLVRQ, V'DYDQFDLW, WUDLQDQW XQ EULQ G'DOID. LO V'DSSURFKD, YRXODQW O'DSODWLU G'XQ FRXS YLI, PDLV 
O'DQLPDO SULW VRQ YRO, GLVSDUDLVVDQW GDQV OD QXLW DYDQW TX'LO DLW SX O'DVVDLOOLU.

In [7]:
stats = {c:msg.count(c) for c in set(msg)}
print stats
{'\n': 10, ' ': 176, "'": 20, '-': 1, ',': 23, '.': 16, ';': 2, 'A': 2, 'C': 1, 'B': 3, 'E': 10, 'D': 110, 'G': 22, 'F': 19, 'I': 13, 'K': 6, 'J': 10, 'M': 1, 'L': 94, 'O': 64, 'Q': 92, 'P': 16, 'S': 27, 'R': 68, 'U': 45, 'T': 8, 'W': 67, 'V': 72, 'Y': 14, 'X': 70}

In [8]:
ll = stats.items()
ll.sort(lambda x,y:y[1]-x[1])
print ll
[(' ', 176), ('D', 110), ('L', 94), ('Q', 92), ('V', 72), ('X', 70), ('R', 68), ('W', 67), ('O', 64), ('U', 45), ('S', 27), (',', 23), ('G', 22), ("'", 20), ('F', 19), ('.', 16), ('P', 16), ('Y', 14), ('I', 13), ('\n', 10), ('E', 10), ('J', 10), ('T', 8), ('K', 6), ('B', 3), (';', 2), ('A', 2), ('-', 1), ('C', 1), ('M', 1)]

In [9]:
# C'est le 'D' qui est le plus fréquent. Si on fait l'hypothèse qu'il code le 'E', on essaie
CC = AA[-1:]+AA[:-1]
print CC
ZABCDEFGHIJKLMNOPQRSTUVWXY

In [10]:
vv = maketrans(CC,aa)
msg.translate(vv)
Out[10]:
"erxsr zscp r'evvmzemx tew e hsvqmv. mp eppyqe. wsr ned qevuyemx qmrymx zmrkx. mp tsywwe yr tvsjsrh wsytmv, \nw'ewwmx herw wsr pmx, w'ettycerx wyv wsr tspsglsr. mp tvmx yr vsqer, mp p'syzvmx, mp pyx; qemw mp r'c wemwmwwemx uy'yr \nmqfvskpms gsrjyw, mp fyxemx e xsyx mrwxerx wyv yr qsx hsrx mp mkrsvemx pe wmkrmjmgexmsr.\nmp eferhsrre wsr vsqer wyv wsr pmx. mp eppe e wsr pezefs; mp qsymppe yr kerx uy'mp tewwe wyv wsr jvsrx, wyv wsr gsy.\nwsr tsypw fexxemx xvst jsvx. mp ezemx gleyh. mp syzvmx wsr zewmwxew, wgvyxe pe rymx. mp jemwemx hsyb. \nyr fvymx mrhmwxmrgx qsrxemx hy jeyfsyvk. yr gevmppsr, tpyw psyvh uy'yr kpew, tpyw wsyvh uy'yr xsgwmr, \ntpyw tvsjsrh uy'yr fsyvhsr, rsr psmr, wsrre xvsmw gsytw. hy gerep wemrx-qevxmr, yr gpetsxmw tpemrxmj wmkrepemx \nyr gleperh uym tewwemx.\nwyv p'efexxerx hy zewmwxew, yr ermqep ey xlsveb mrhmks, e p'emkymppsr wejver, rm yr gejevh, rm yr glevergsr, \nqemw tpyxsx yr evxmwsr, w'ezergemx, xvemrerx yr fvmr h'epje. mp w'ettvsgle, zsyperx p'etpexmv h'yr gsyt zmj, qemw \np'ermqep tvmx wsr zsp, hmwtevemwwerx herw pe rymx ezerx uy'mp emx ty p'ewwemppmv."
In [11]:
# Visiblement, c'est raté. Essayons avec la deuxième lettre la plus fréquente du français, qui est le 'S'
ord('D')-ord('S')
Out[11]:
-15
In [12]:
CC=AA[21:]+AA[:21]
vv = maketrans(CC,aa)
msg.translate(vv)
Out[12]:
"ivbwv dwgt v'izzqdiqb xia i lwzuqz. qt ittcui. awv rih uizyciqb uqvcqb dqvob. qt xwcaai cv xzwnwvl awcxqz, \na'iaaqb liva awv tqb, a'ixxcgivb acz awv xwtwkpwv. qt xzqb cv zwuiv, qt t'wcdzqb, qt tcb; uiqa qt v'g aiqaqaaiqb yc'cv \nqujzwotqw kwvnca, qt jcbiqb i bwcb qvabivb acz cv uwb lwvb qt qovwziqb ti aqovqnqkibqwv.\nqt ijivlwvvi awv zwuiv acz awv tqb. qt itti i awv tidijw; qt uwcqtti cv oivb yc'qt xiaai acz awv nzwvb, acz awv kwc.\nawv xwcta jibbiqb bzwx nwzb. qt idiqb kpicl. qt wcdzqb awv diaqabia, akzcbi ti vcqb. qt niqaiqb lwcf. \ncv jzcqb qvlqabqvkb uwvbiqb lc nicjwczo. cv kizqttwv, xtca twczl yc'cv otia, xtca awczl yc'cv bwkaqv, \nxtca xzwnwvl yc'cv jwczlwv, vwv twqv, awvvi bzwqa kwcxa. lc kivit aiqvb-uizbqv, cv ktixwbqa xtiqvbqn aqovitiqb \ncv kpitivl ycq xiaaiqb.\nacz t'ijibbivb lc diaqabia, cv ivquit ic bpwzif qvlqow, i t'iqocqttwv ainziv, vq cv kinizl, vq cv kpizivkwv, \nuiqa xtcbwb cv izbqawv, a'idivkiqb, bziqvivb cv jzqv l'itni. qt a'ixxzwkpi, dwctivb t'ixtibqz l'cv kwcx dqn, uiqa \nt'ivquit xzqb awv dwt, lqaxiziqaaivb liva ti vcqb idivb yc'qt iqb xc t'iaaiqttqz."
In [13]:
# Toujours pas ... Essayons la suivante, le 'A'
CC=AA[3:]+AA[:3]
vv = maketrans(CC,aa)
msg.translate(vv)
Out[13]:
"anton voyl n'arrivait pas a dormir. il alluma. son jaz marquait minuit vingt. il poussa un profond soupir, \ns'assit dans son lit, s'appuyant sur son polochon. il prit un roman, il l'ouvrit, il lut; mais il n'y saisissait qu'un \nimbroglio confus, il butait a tout instant sur un mot dont il ignorait la signification.\nil abandonna son roman sur son lit. il alla a son lavabo; il mouilla un gant qu'il passa sur son front, sur son cou.\nson pouls battait trop fort. il avait chaud. il ouvrit son vasistas, scruta la nuit. il faisait doux. \nun bruit indistinct montait du faubourg. un carillon, plus lourd qu'un glas, plus sourd qu'un tocsin, \nplus profond qu'un bourdon, non loin, sonna trois coups. du canal saint-martin, un clapotis plaintif signalait \nun chaland qui passait.\nsur l'abattant du vasistas, un animal au thorax indigo, a l'aiguillon safran, ni un cafard, ni un charancon, \nmais plutot un artison, s'avancait, trainant un brin d'alfa. il s'approcha, voulant l'aplatir d'un coup vif, mais \nl'animal prit son vol, disparaissant dans la nuit avant qu'il ait pu l'assaillir."

Niveau 0.5 : substitutions monoalphabétiques

La clef est une permutation de l'alphabet. Chaque lettre est donc toujours codée de la même manière. Un cryptogramme assez long aura donc la même distribution de fréquences qu'un texte en langue naturelle.

Pour la cryptanalyse, on démarre avec les fréquences et on essaie d'aligner une table de traduction. Si le texte est court, ce n'est pas forcément facile.

On peut trouver des fréquences de lettres ici.

Pour le français, les lettres classées par fréquences décroissantes sont

E A I S T N R U L O D M P C V Q G B F J H Z X Y K W

Chiffrement affine

Comme il est dfficile de retenir par coeur une permutation de l'alphabet, on a utilisé divers systèmes permettant d'en engendrer à partir d'une information plus simple.

Le chiffre de César revient à représenter les 26 lettres de l'alphabet par un entier modulo 26 :

$$A=0, B=1, C=2,\ldots, Y=24, Z=25\ \mod 26$$.

et à remplacer la lettre de code $x$ par celle de code $y=x+b$, où $b\in {\mathbb Z}/26{\mathbb Z}$ est la clef.

On peut compliquer un peu le système en la codant par $y=ax+b$, où $a\in ({\mathbb Z}/26{\mathbb Z})^*$ doit être inversible pour que le message soit déchiffrable.

Voici la table d'addition modulo 26 :

In [14]:
for x in range(26):
    for y in range(26): print "%2d "% ((x+y) % 26),
    print
 0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25 
 1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25   0 
 2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25   0   1 
 3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25   0   1   2 
 4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25   0   1   2   3 
 5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25   0   1   2   3   4 
 6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25   0   1   2   3   4   5 
 7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25   0   1   2   3   4   5   6 
 8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25   0   1   2   3   4   5   6   7 
 9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25   0   1   2   3   4   5   6   7   8 
10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25   0   1   2   3   4   5   6   7   8   9 
11  12  13  14  15  16  17  18  19  20  21  22  23  24  25   0   1   2   3   4   5   6   7   8   9  10 
12  13  14  15  16  17  18  19  20  21  22  23  24  25   0   1   2   3   4   5   6   7   8   9  10  11 
13  14  15  16  17  18  19  20  21  22  23  24  25   0   1   2   3   4   5   6   7   8   9  10  11  12 
14  15  16  17  18  19  20  21  22  23  24  25   0   1   2   3   4   5   6   7   8   9  10  11  12  13 
15  16  17  18  19  20  21  22  23  24  25   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14 
16  17  18  19  20  21  22  23  24  25   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15 
17  18  19  20  21  22  23  24  25   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16 
18  19  20  21  22  23  24  25   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17 
19  20  21  22  23  24  25   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18 
20  21  22  23  24  25   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19 
21  22  23  24  25   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20 
22  23  24  25   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21 
23  24  25   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22 
24  25   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23 
25   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24 

Et la table de multiplication :

In [18]:
for x in range(1,26):
    for y in range(1,26): print "%2d "% ((x*y) % 26),
    print
 1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25 
 2   4   6   8  10  12  14  16  18  20  22  24   0   2   4   6   8  10  12  14  16  18  20  22  24 
 3   6   9  12  15  18  21  24   1   4   7  10  13  16  19  22  25   2   5   8  11  14  17  20  23 
 4   8  12  16  20  24   2   6  10  14  18  22   0   4   8  12  16  20  24   2   6  10  14  18  22 
 5  10  15  20  25   4   9  14  19  24   3   8  13  18  23   2   7  12  17  22   1   6  11  16  21 
 6  12  18  24   4  10  16  22   2   8  14  20   0   6  12  18  24   4  10  16  22   2   8  14  20 
 7  14  21   2   9  16  23   4  11  18  25   6  13  20   1   8  15  22   3  10  17  24   5  12  19 
 8  16  24   6  14  22   4  12  20   2  10  18   0   8  16  24   6  14  22   4  12  20   2  10  18 
 9  18   1  10  19   2  11  20   3  12  21   4  13  22   5  14  23   6  15  24   7  16  25   8  17 
10  20   4  14  24   8  18   2  12  22   6  16   0  10  20   4  14  24   8  18   2  12  22   6  16 
11  22   7  18   3  14  25  10  21   6  17   2  13  24   9  20   5  16   1  12  23   8  19   4  15 
12  24  10  22   8  20   6  18   4  16   2  14   0  12  24  10  22   8  20   6  18   4  16   2  14 
13   0  13   0  13   0  13   0  13   0  13   0  13   0  13   0  13   0  13   0  13   0  13   0  13 
14   2  16   4  18   6  20   8  22  10  24  12   0  14   2  16   4  18   6  20   8  22  10  24  12 
15   4  19   8  23  12   1  16   5  20   9  24  13   2  17   6  21  10  25  14   3  18   7  22  11 
16   6  22  12   2  18   8  24  14   4  20  10   0  16   6  22  12   2  18   8  24  14   4  20  10 
17   8  25  16   7  24  15   6  23  14   5  22  13   4  21  12   3  20  11   2  19  10   1  18   9 
18  10   2  20  12   4  22  14   6  24  16   8   0  18  10   2  20  12   4  22  14   6  24  16   8 
19  12   5  24  17  10   3  22  15   8   1  20  13   6  25  18  11   4  23  16   9   2  21  14   7 
20  14   8   2  22  16  10   4  24  18  12   6   0  20  14   8   2  22  16  10   4  24  18  12   6 
21  16  11   6   1  22  17  12   7   2  23  18  13   8   3  24  19  14   9   4  25  20  15  10   5 
22  18  14  10   6   2  24  20  16  12   8   4   0  22  18  14  10   6   2  24  20  16  12   8   4 
23  20  17  14  11   8   5   2  25  22  19  16  13  10   7   4   1  24  21  18  15  12   9   6   3 
24  22  20  18  16  14  12  10   8   6   4   2   0  24  22  20  18  16  14  12  10   8   6   4   2 
25  24  23  22  21  20  19  18  17  16  15  14  13  12  11  10   9   8   7   6   5   4   3   2   1 

Les lignes (ou colonnes) paires et celle de 13 ne contiennent pas 1 (et contiennent 0). Il faut donc que $$a\in\{1,3,5,7,8,11,15,17,19,21,23,25\}.$$

Par exemple, l'inverse de 7 est 15 car $7\times 15 = 105 = 8\times 13+1\equiv 1\ \mod 26$.

Donc, $(a,b)=(7,12)$ serait une clef valable, et la formule de déchiffrment serait

$$ x = a^{-1}(y-b) = 15\times (y+24) \mod 26.$$

In [19]:
d = {x:aa.index(x) for x in aa}
print d
{'a': 0, 'c': 2, 'b': 1, 'e': 4, 'd': 3, 'g': 6, 'f': 5, 'i': 8, 'h': 7, 'k': 10, 'j': 9, 'm': 12, 'l': 11, 'o': 14, 'n': 13, 'q': 16, 'p': 15, 's': 18, 'r': 17, 'u': 20, 't': 19, 'w': 22, 'v': 21, 'y': 24, 'x': 23, 'z': 25}

In [20]:
def i26(x):
    if x%2 and x%13: return [y for y in range(1,26) if (x*y)%26==1][0]
    else: return None
In [21]:
i26(7)
Out[21]:
15
In [22]:
print i26(4)
None

On implantera les systèmes cryptographiques comme des classes possédant des méthodes crypt et uncrypt :

In [23]:
class Affine(object):
    def __init__(self,a,b):
        assert x%2 and x%13
        self.a = a; self.b = b
        self.d = i26(a)
        
        
    def crypt(self,msg):
        return ''.join([aa[(self.a*aa.index(c)+self.b)%26] for c in msg if c in aa]).upper()
    
    def uncrypt(self,crpt):
        return ''.join([aa[(self.d*(AA.index(c)-self.b))%26] for c in crpt if c in AA])
In [24]:
A = Affine(7,12)
A.crypt('le cheval de mon cousin ne mange du foin que le dimanche')
Out[24]:
'LOAJODMLHOSGZAGWIQZZOSMZCOHWVGQZUWOLOHQSMZAJO'
In [25]:
A.uncrypt(_)
Out[25]:
'lechevaldemoncousinnemangedufoinqueledimanche'
In [26]:
y = 'LOAJODMLHOSGZAGWIQZZOSMZCOHWVGQZUWOLOHQSMZAJO'
In [27]:
stats = {c:y.count(c) for c in set(y)}
ll = stats.items()
ll.sort(lambda x,y:y[1]-x[1])
print ll
[('O', 8), ('Z', 6), ('A', 3), ('G', 3), ('H', 3), ('M', 3), ('L', 3), ('Q', 3), ('S', 3), ('W', 3), ('J', 2), ('C', 1), ('D', 1), ('I', 1), ('U', 1), ('V', 1)]

Les deux lettres les plus fréquentes sont O et Z, qu'on peut essayer d'identifier à E et A:

In [28]:
print AA.index('O'), AA.index('Z'), AA.index('E'), AA.index('I')
14 25 4 8

Ça donne le système $4a+b=14$, $0a+b=25$ qui n'a pas de solutions.

In [29]:
x='lechevaldemoncousinnemangedufoinqueledimanche'
print {c:x.count(c) for c in set(x)}
{'a': 3, 'c': 3, 'e': 8, 'd': 3, 'g': 1, 'f': 1, 'i': 3, 'h': 2, 'm': 3, 'l': 3, 'o': 3, 'n': 6, 'q': 1, 's': 1, 'u': 3, 'v': 1}

L'hypothèse E=O est correcte mais Z chiffre le N. Il faut donc tâtonner un peu.

Les Cryptochallenges de la NSA

Pour s'essayer aux chiffres monoalphabétiques arbitraires, on peut jouer au NSA Cryptochallenge (apple ou android).

On fait évoluer une table de traduction en s'aidant du dictionnaire anglais et d'expressions régulières.

In [30]:
### Un exemple 

nsa = 'X 1998 KDUQHSH GNDQP QDMEYJ INDYV PFXP PFH SXZNQEPW NI HMMEK EKMXYV, X JXPHLXW INQ SEMMENYK NI ESSEJQXYPK, EK EY YHL ZHQKHW.'
In [31]:
stats = {c:nsa.count(c) for c in set(nsa)}
print stats
{' ': 21, ',': 2, '.': 1, '1': 1, '9': 2, '8': 1, 'E': 10, 'D': 4, 'G': 1, 'F': 2, 'I': 4, 'H': 8, 'K': 7, 'J': 3, 'M': 6, 'L': 2, 'N': 7, 'Q': 7, 'P': 7, 'S': 5, 'U': 1, 'W': 3, 'V': 2, 'Y': 7, 'X': 8, 'Z': 2}

In [32]:
ll = stats.items()
ll.sort(lambda x,y:y[1]-x[1])
print ll
[(' ', 21), ('E', 10), ('H', 8), ('X', 8), ('K', 7), ('N', 7), ('Q', 7), ('P', 7), ('Y', 7), ('M', 6), ('S', 5), ('D', 4), ('I', 4), ('J', 3), ('W', 3), (',', 2), ('9', 2), ('F', 2), ('L', 2), ('V', 2), ('Z', 2), ('.', 1), ('1', 1), ('8', 1), ('G', 1), ('U', 1)]

In [33]:
# On essaie d'aligner avec les fréquences en anglais

xx='ETAOINSRHDLUCMFYWGPB'
yy='EHXKNQPYMSDIJWFLVZGU'
ww=maketrans(yy,xx)
print nsa
print nsa.translate(ww)
X 1998 KDUQHSH GNDQP QDMEYJ INDYV PFXP PFH SXZNQEPW NI HMMEK EKMXYV, X JXPHLXW INQ SEMMENYK NI ESSEJQXYPK, EK EY YHL ZHQKHW.
A 1998 OLBNTDT PILNS NLHERC UILRW SFAS SFT DAGINESM IU THHEO EOHARW, A CASTYAM UIN DEHHEIRO IU EDDECNARSO, EO ER RTY GTNOTM.

In [34]:
# IU -> IS ? N->I, I->S
xx='ETAOINURHDLSCMFYWGPB'
yy='EHXKNQPYMSDIJWFLVZGU'
ww=maketrans(yy,xx)
print nsa
print nsa.translate(ww)
X 1998 KDUQHSH GNDQP QDMEYJ INDYV PFXP PFH SXZNQEPW NI HMMEK EKMXYV, X JXPHLXW INQ SEMMENYK NI ESSEJQXYPK, EK EY YHL ZHQKHW.
A 1998 OLBNTDT PILNU NLHERC SILRW UFAU UFT DAGINEUM IS THHEO EOHARW, A CAUTYAM SIN DEHHEIRO IS EDDECNARUO, EO ER RTY GTNOTM.

In [35]:
# NI ->IS, PFH -> THE ?

xx = 'AISTHE' 
yy = 'XNIPFH'
ww=maketrans(yy,xx)
print nsa
print nsa.translate(ww)
X 1998 KDUQHSH GNDQP QDMEYJ INDYV PFXP PFH SXZNQEPW NI HMMEK EKMXYV, X JXPHLXW INQ SEMMENYK NI ESSEJQXYPK, EK EY YHL ZHQKHW.
A 1998 KDUQESE GIDQT QDMEYJ SIDYV THAT THE SAZIQETW IS EMMEK EKMAYV, A JATELAW SIQ SEMMEIYK IS ESSEJQAYTK, EK EY YEL ZEQKEW.

In [36]:
# C'est sur la bonne voie
# JATELAW : ^.ATE.A.$ dans le dictionnaire donne GATEWAY 
# etc ... 

xx = 'ASUPREMISNTHCOJFLGWYD'
yy = 'XKDUQHSEKYPFGNZIMJLWV'
ww=maketrans(yy,xx)
print nsa
print nsa.translate(ww)
X 1998 KDUQHSH GNDQP QDMEYJ INDYV PFXP PFH SXZNQEPW NI HMMEK EKMXYV, X JXPHLXW INQ SEMMENYK NI ESSEJQXYPK, EK EY YHL ZHQKHW.
A 1998 SUPREME COURT RULING FOUND THAT THE MAJORITY OF ELLIS ISLAND, A GATEWAY FOR MILLIONS OF IMMIGRANTS, IS IN NEW JERSEY.

In [37]:
# Autre exemple, semaine du 2/11/2015

nsa = 'C VTZCA VLT NKXGGQR STIIQQ TA LQH GCK CAR NBIIQHQR PLXHR-RQEHQQ FBHAN VTA AQCHGO $3 ZXGGXTA XA RCZCEQN IHTZ ZSRTACGR\'N XA 1992.'
stats = {c:nsa.count(c) for c in set(nsa)}
print stats
{' ': 21, '$': 1, "'": 1, '-': 1, '.': 1, '1': 1, '3': 1, '2': 1, '9': 2, 'A': 10, 'C': 8, 'B': 2, 'E': 2, 'G': 7, 'F': 1, 'I': 5, 'H': 7, 'K': 2, 'L': 3, 'O': 1, 'N': 5, 'Q': 11, 'P': 1, 'S': 2, 'R': 8, 'T': 8, 'V': 3, 'X': 6, 'Z': 5}

In [38]:
ll = stats.items()
ll.sort(lambda x,y:y[1]-x[1])
print ll
[(' ', 21), ('Q', 11), ('A', 10), ('C', 8), ('R', 8), ('T', 8), ('G', 7), ('H', 7), ('X', 6), ('I', 5), ('N', 5), ('Z', 5), ('L', 3), ('V', 3), ('9', 2), ('B', 2), ('E', 2), ('K', 2), ('S', 2), ('$', 1), ("'", 1), ('-', 1), ('.', 1), ('1', 1), ('3', 1), ('2', 1), ('F', 1), ('O', 1), ('P', 1)]

In [39]:
xx='ETAOINSRHDLUCMFYWGPB'
yy='QACRTGHXINZLVBEKSFOP'
ww=maketrans(yy,xx)
print nsa
print nsa.translate(ww)
C VTZCA VLT NKXGGQR STIIQQ TA LQH GCK CAR NBIIQHQR PLXHR-RQEHQQ FBHAN VTA AQCHGO $3 ZXGGXTA XA RCZCEQN IHTZ ZSRTACGR'N XA 1992.
A CILAT CUI DYRNNEO WIHHEE IT UES NAY ATO DMHHESEO BURSO-OEFSEE GMSTD CIT TEASNP $3 LRNNRIT RT OALAFED HSIL LWOITANO'D RT 1992.

In [40]:
xx='ENADOLFISMWRHCUGPCBYT'
yy='QACRTGIXNZVHLWBEKSFOP'
ww=maketrans(yy,xx)
print nsa
print nsa.translate(ww)
C VTZCA VLT NKXGGQR STIIQQ TA LQH GCK CAR NBIIQHQR PLXHR-RQEHQQ FBHAN VTA AQCHGO $3 ZXGGXTA XA RCZCEQN IHTZ ZSRTACGR'N XA 1992.
A WOMAN WHO SPILLED COFFEE ON HER LAP AND SUFFERED THIRD-DEGREE BURNS WON NEARLY $3 MILLION IN DAMAGES FROM MCDONALD'S IN 1992.

Dans les communications militaires, on supprimait espaces et ponctuation, et les chiffres étaient écrit en toutes lettres. Pour la lisibilté, on présentait en général le cryptogramme par blocs de cinq lettres :

Niveau 1 : chiffres polyalphabétiques : Vigenère

La clef est un mot que l'on répète indéfiniment et que l'on ajoute au texte modulo le cadinal de l'alphabet (26 pour nous) :

clef = SECRET

texte :         LE CHEVAL DE MON COUSIN NE MANGE DU FOIN QUE LE DIMANCHE
clef  :         SE CRETSE CR ETS ECRETS EC RETSE CR ETSE CRE TS ECRETSEC
cryptogramme :  DI EYIOSP FV QHF GQLWBF RG DEGYI FL JHAR SLI EW HKDEGULG
In [41]:
print map(ord,'SECRET')
print map(ord, AA)
[83, 69, 67, 82, 69, 84]
[65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90]

In [42]:
s = 'LECHEVALDEMONCOUSINNEMANGEDUFOINQUELEDIMANCHE'
k = 'SECRET'
print ''.join([chr((ord(s[i])-65+ord(k[i%6])-65)%26 + 65)  for i in range(len(s))])
DIEYIOSPFVQHFGQLWBFRGDEGYIFLJHARSLIEWHKDEGULG

Le système revient donc à utiliser $m$ alphabets de César différents, où $m$ est la longueur de la clef.

Si on parvient à déterminer la longueur de la clef, l'analyse des fréquences permettra de la retouver à partir d'un texte assez long.

Il existe pour cela deux méthodes : l'analyse des trigrammes (Babbage/Kasiski) et l'indice de coïncidence (Friedman).

Méthode des trigrammes (Babbage, Kasiski)

On construit un dictionnaire dont les clefs sont les facteurs de longueur 3 du cryptogramme :

dic['xyz']=[12,56,123] 
si 'xyz' apparaît aux positions 12, 56, 123. Pour les trigrammes qui apparaissent plus d'une fois, on calcule les distances entre leurs occurences successives. La longueur de la clef divise la majorité de ces distances. Ce sera leur pgcd après élimination des faux positifs. Par exemple, pour le cryptogramme
XAUNM EESYI EDTLL FGSNB WQUFX PQTYO RUTYI INUMQ IEULS 
MFAFX GUTYB XXAGB HMIFI IMUMQ IDEKR IFRIR ZQUHI ENOOO 
IGRML YETYO VQRYS IXEOK IYPYO IGRFB WPIYR BQURJ IYEMJ 
IGRYK XYACP PQSPB VESIR ZQRUF REDYJ IGRYK XBLOP JARNP 
UGEFB WMILX MZSMZ YXPNB PUMYZ MEEFB UGENL RDEPB JXONQ 
EZTMB WOEFI IPAHP PQBFL GDEMF WFAHQ

la liste (triée) des distances entre occurences d'un même trigramme est

[20, 20, 25, 25, 25, 30, 30, 30, 30, 30, 30, 30, 30, 65, 70, 75, 75, 95, 170, 201]
et on en conclut facilement que la longueur de la clef doit être 5 (mais ce n'est pas toujours aussi évident).

Pour trouver la clef, on peut ensuite procéder à l'analyse des fréquences sur les 5 sous chaines

s[i::5]
.

Mais ce n'est pas le plus efficace. Il vaut mieux recourir à la méthode statistique.

Méthode de Friedman (indice de coïncidence)

L'indice de coïncidence $I_c(w)$ d'une chaîne de caractères $w$ est la probabilité pour que deux caractères pris au hasard (à des positions différentes, évidemment) soient identiques.

Si $n$ est le nombre total de lettres de $w$ et $n_x$ le nombre de lettres $x$ dans $w$, le nombre total de couples de lettres $(w_i,w_j)$ ($i\not=j)$ vaut $n(n-1)$, et le nombre de couples pour lesquels $w_i=w_j=x$ vaut $n_x(n_x-1)$.

Donc, si $X$ est l'alphabet de $w$, $$I_c(w) =\sum_{x\in X}\frac{n_x(n_x-1)}{n(n-1)}.$$

Dans une langue naturelle, les lettres n'apparaissent pas toutes avec la même fréquence, et l'indice de coincidence d'un texte sera très différent de celui d'une chaîne aléatoire, lequel vaudrait environ $1/26$ (pourquoi ?). Pour le français, la valeur moyenne est $0.0746$.

Dans un texte chiffré avec un clef de longueur $k$, deux lettres sont

  • ou bien chiffrées avec la même lettre de la clé. Il y a $n(n/k-1)/2$ telles paires,
  • ou bien avec une lettre différente. Il y a $n(n-n/k)/2$ telles paires.

Comme il y a $n(n-1)/2$ paires de lettres dans le texte, l'indice de coïncidence probable du texte $w$ sera $$ I_c(w)\simeq\frac{n(i_L-i_A)+k(ni_A-i_L)}{k(n-1)} $$ où $i_A=1/N$ où $N$ est le nombre de lettres de l'alphabet, et $i_L$ est l'indice de coïncidence de la langue considérée.

En inversant cette formule, on en déduit une estimation de la longueur $k$ $$ k=\frac{n(i_L-i_A)}{(n-1)I_c(w)-ni_A+i_L}. $$

Cette formule ne donne pas toujours de très bons résultats. On peut aussi simplement calculer l'indice de coïncidence des sous-chaînes w[::m], la longueur de la clef sera en général le $m$ qui donne la valeur maximale.

Equivalents modernes de César et Vigenère

On ne travaille plus avec un alphabet de 26 lettres, mais avec des octets. On a donc maintenant 256 "caractères".

On remplace le décalage par le OU exclusif (XOR), qui a l'avantage d'être involutif.

In [43]:
class CyberCesar(object):
    def __init__(self,k):
        self.k = k
        
    def crypt(self,buf):
        return [b^self.k for b in buf]
    
    def uncrypt(self,buf): 
        return self.crypt(buf)
In [44]:
C = CyberCesar(0xe2)
In [45]:
y = C.crypt(map(ord,'À bon chat bon rat !'))
print(y)
[33, 98, 194, 128, 141, 140, 194, 129, 138, 131, 150, 194, 128, 141, 140, 194, 144, 131, 150, 194, 195]

Pour les calculs, on travaille avec des entiers, il faut donc des fonctions de conversion.

In [46]:
print map(chr,y)
['!', 'b', '\xc2', '\x80', '\x8d', '\x8c', '\xc2', '\x81', '\x8a', '\x83', '\x96', '\xc2', '\x80', '\x8d', '\x8c', '\xc2', '\x90', '\x83', '\x96', '\xc2', '\xc3']

Il n'y a aucun caractère imprimable dans le résultat. On utilise principalement deux encodages pour les données binaires : hex et base64.

In [47]:
def hex2buf(hh):
    return map(ord,hh.decode('hex'))

def buf2hex(bb):
    return ''.join(['%2x'%b for b in bb])

def str2buf(s):
    return map(ord,s)

def buf2str(bb):
    return ''.join([chr(b) for b in bb])
In [48]:
x = 'À bon chat bon rat !'
In [49]:
C = CyberCesar(0xe2)
In [50]:
y = C.crypt(str2buf(x))
print y
[33, 98, 194, 128, 141, 140, 194, 129, 138, 131, 150, 194, 128, 141, 140, 194, 144, 131, 150, 194, 195]

In [51]:
z = buf2hex(y)
print z
2162c2808d8cc2818a8396c2808d8cc2908396c2c3

In [52]:
u = C.uncrypt(y)
print u
[195, 128, 32, 98, 111, 110, 32, 99, 104, 97, 116, 32, 98, 111, 110, 32, 114, 97, 116, 32, 33]

In [53]:
print buf2str(u)
À bon chat bon rat !

In [54]:
def b642buf(cc):
    return map(ord,cc.decode('base64'))

def buf2b64(bb):
    return ''.join([chr(b) for b in bb]).encode('base64')
    
In [55]:
z = buf2b64(y)
print z
IWLCgI2MwoGKg5bCgI2MwpCDlsLD


In [56]:
print b642buf(z)
[33, 98, 194, 128, 141, 140, 194, 129, 138, 131, 150, 194, 128, 141, 140, 194, 144, 131, 150, 194, 195]

In [57]:
### Vigenère

class CyberVigenere(object):
    def __init__(self,k):
        self.k = k
        self.m = len(k)
        
            
    def crypt(self,buf):
        return [buf[i]^self.k[i%self.m] for i in range(len(buf))]
    
    def uncrypt(self,buf): 
        return self.crypt(buf)
    
In [58]:
key = str2buf('Vigenère')
key
Out[58]:
[86, 105, 103, 101, 110, 195, 168, 114, 101]
In [59]:
V = CyberVigenere(key)
In [60]:
x = 'Il est plus facile de se laver les dents dans un verre à pied que de se laver les pieds dans un verre à dents.'
xx = str2buf(x)
yy = V.crypt(xx)
In [61]:
print buf2b64(yy)
print buf2hex(yy)
HwVHAB23iAIJIxpHAw+gwR4Adg0CRR2miB4EIAwVRQKm21IBMwcTFk6nyRwWdhwJRRim2gAAdqrH
RR6qzRZFJxwCRQqmiAEAdgUGEwuxiB4AJUkXDAun21IBNwcURRutiAQAJBsCRa1jiBYAOB0USw==

1f 547 01db788 2 9231a47 3 fa0c11e 076 d 2451da6881e 420 c1545 2a6db52 133 713164ea7c91c16761c 94518a6da 0 076aac7451eaacd1645271c 245 aa688 1 076 5 613 bb1881e 0254917 c ba7db52 137 714451bad88 4 0241b 245ad638816 0381d144b

In [62]:
buf2str(yy)
Out[62]:
"\x1f\x05G\x00\x1d\xb7\x88\x02\t#\x1aG\x03\x0f\xa0\xc1\x1e\x00v\r\x02E\x1d\xa6\x88\x1e\x04 \x0c\x15E\x02\xa6\xdbR\x013\x07\x13\x16N\xa7\xc9\x1c\x16v\x1c\tE\x18\xa6\xda\x00\x00v\xaa\xc7E\x1e\xaa\xcd\x16E'\x1c\x02E\n\xa6\x88\x01\x00v\x05\x06\x13\x0b\xb1\x88\x1e\x00%I\x17\x0c\x0b\xa7\xdbR\x017\x07\x14E\x1b\xad\x88\x04\x00$\x1b\x02E\xadc\x88\x16\x008\x1d\x14K"
In [63]:
print buf2str(V.uncrypt(yy))
Il est plus facile de se laver les dents dans un verre à pied que de se laver les pieds dans un verre à dents.

Cette version modernisée de Vigenère est tout aussi vulnérable aux attaques décrites précédemment, sauf dans le cas où la longueur de la clé est égale à la longueur du message, et à condition que la clé ne soit utilisée qu'une seule fois. C'est le one-time pad, ou chiffre de vernam.

Le one-time pad

In [64]:
K = open('/dev/urandom').read(256)
In [65]:
print K.encode('hex')
e6b81ccc1c7d911ceff870559c29ba15190ae16751fe4465b9577ae79a5c5d2f0579ae1e6283dddc9c161b23d285732ef6c67807daa2ad75f48f46c77052257fbc822894f299ee3290f4eb9d164e981e5ee5ed4083f6dbfba5d23e150cf06012116dc9ddbfa6f6c3a5237a615051d446cc40ca0efddee23e7ee2126aade2682adcb6a8ecb198e8649a9794d66c19547f199982519518dfefa55d62796048d31d0494822b0f969c6bc191fcbcb700c0159c43b2db776dbef36b931c546a3a60ab96402373d3b674e5afad7874e986ebcd525f6c8e96cfefa3463f2169a3c2b8cb112c5aac64e43c0fe3fb8de9b91bcd4bba4079f69d68552a7f951133d3d168e1

In [66]:
def crypt(msg,key,offset):
    return ''.join([chr(ord(c)^ord(k)) for c,k in zip(msg,key[offset::])])
In [67]:
msg = 'abracadacra'
In [68]:
crypt(msg,K,0).encode('hex')
Out[68]:
'87da6ead7f1cf57d8c8a11'
In [69]:
crypt(_.decode('hex'),K, 0)
Out[69]:
'abracadacra'
In [70]:
class OneTimePad(object):
    def __init__(self,key):
        self.key=key
    
    def crypt(self,msg,offset):
        return ''.join([chr(ord(c)^ord(k)) for c,k in zip(msg,self.key[offset::])])
    
    def uncrypt(self,msg,offset):
        return crypt(self,msg,offset)
    
        
        
In [71]:
OTP=OneTimePad(K)
In [72]:
OTP.crypt('abraadabra',0)
Out[72]:
'\x87\xdan\xad}\x19\xf0~\x9d\x99'
In [72]:
 
In []: