M1 Cryptographie 2017-2018

Exemples en Python 3

0. César

In [1]:
from string import ascii_uppercase as AA
from string import ascii_lowercase as aa
In [2]:
k = 3
BB = AA[k:]+AA[:k]
tt = str.maketrans(aa,BB) ###
In [3]:
print(tt) ###
{97: 68, 98: 69, 99: 70, 100: 71, 101: 72, 102: 73, 103: 74, 104: 75, 105: 76, 106: 77, 107: 78, 108: 79, 109: 80, 110: 81, 111: 82, 112: 83, 113: 84, 114: 85, 115: 86, 116: 87, 117: 88, 118: 89, 119: 90, 120: 65, 121: 66, 122: 67}
In [4]:
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
In [5]:
# Cryptanalyse

stats = {c:msg.count(c) for c in set(msg)}
print (stats)
{'R': 3, 'Q': 6, 'F': 3, 'J': 1, 'K': 2, ' ': 11, 'G': 3, 'X': 3, 'H': 8, 'V': 1, 'T': 1, 'L': 3, 'P': 3, 'I': 1, 'Y': 1, 'D': 3, 'O': 3}
In [6]:
ll = list(stats.items()) ###
ll.sort(key=lambda x:x[1],reverse=True) ###
print (ll)
[(' ', 11), ('H', 8), ('Q', 6), ('R', 3), ('F', 3), ('G', 3), ('X', 3), ('L', 3), ('P', 3), ('D', 3), ('O', 3), ('K', 2), ('J', 1), ('V', 1), ('T', 1), ('I', 1), ('Y', 1)]
In [7]:
# COntre-exemple tiré de "La disparition" de Geoge Perec

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


# En Python 3, les chaînes sont en unicode, 
# on peut donc se débarasser des lettres accentuées sans avoir à bricoler les encodages

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

text = perec.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 [8]:
# 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 [9]:
stats = {c:msg.count(c) for c in set(msg)}
ll = list(stats.items()) ###
ll.sort(key=lambda x:x[1], reverse=True)
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), ('P', 16), ('.', 16), ('Y', 14), ('I', 13), ('J', 10), ('E', 10), ('\n', 10), ('T', 8), ('K', 6), ('B', 3), (';', 2), ('A', 2), ('C', 1), ('M', 1), ('-', 1)]
In [10]:
# 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 [11]:
vv = str.maketrans(CC,aa) ###
msg.translate(vv)
Out[11]:
"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 [12]:
# 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[12]:
-15
In [13]:
CC=AA[21:]+AA[:21]
vv = str.maketrans(CC,aa)
msg.translate(vv)
Out[13]:
"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 [14]:
# Toujours pas ... Essayons la suivante, le 'A'
CC=AA[3:]+AA[:3]
vv = str.maketrans(CC,aa)
msg.translate(vv)
Out[14]:
"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."

0.5 Substitutions monoalphabétiques

Chiffrement affine

Table d'addition modulo 26

In [15]:
for x in range(26):
    for y in range(26): print ("%2d "% ((x+y) % 26),end=' ') ###
    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  

Table de multiplication

In [16]:
for x in range(1,26):
    for y in range(26): print ("%2d "% ((x*y) % 26),end=' ') ###
    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  
 0   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  
 0   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  
 0   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  
 0   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  
 0   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  
 0   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  
 0   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  
 0   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  
 0  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  
 0  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  
 0  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  
 0  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  
 0  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  
 0  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  
 0  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  
 0  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  
 0  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  
 0  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  
 0  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  
 0  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  
 0  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  
 0  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  
 0  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  
 0  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  
In [17]:
# Inverses par force brute
d = {x:aa.index(x) for x in aa}
print (d)
{'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
In [18]:
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 [19]:
i26(7)
Out[19]:
15
In [20]:
print (i26(4))
None
In [21]:
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 [22]:
A = Affine(7,12)
y=A.crypt('le cheval de mon cousin ne mange du foin que le dimanche')
y
Out[22]:
'LOAJODMLHOSGZAGWIQZZOSMZCOHWVGQZUWOLOHQSMZAJO'
In [23]:
A.uncrypt(_)
Out[23]:
'lechevaldemoncousinnemangedufoinqueledimanche'
In [24]:
stats = {c:y.count(c) for c in set(y)}
ll = list(stats.items())
ll.sort(key=lambda x:x[1],reverse=True)
print (ll)
[('O', 8), ('Z', 6), ('M', 3), ('Q', 3), ('S', 3), ('G', 3), ('A', 3), ('H', 3), ('L', 3), ('W', 3), ('J', 2), ('C', 1), ('V', 1), ('U', 1), ('I', 1), ('D', 1)]
In [25]:
print (AA.index('O'), AA.index('Z'), AA.index('E'), AA.index('I'))
14 25 4 8

Les cryptochallenges de la NSA

In [26]:
def freqs(y):
    stats = {c:y.count(c) for c in set(y)}
    ll = list(stats.items())
    ll.sort(key=lambda x:x[1],reverse=True)
    return ll
In [27]:
### 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 [28]:
print(freqs(nsa))
[(' ', 21), ('E', 10), ('X', 8), ('H', 8), ('K', 7), ('N', 7), ('P', 7), ('Q', 7), ('Y', 7), ('M', 6), ('S', 5), ('D', 4), ('I', 4), ('J', 3), ('W', 3), (',', 2), ('L', 2), ('F', 2), ('Z', 2), ('9', 2), ('V', 2), ('G', 1), ('1', 1), ('U', 1), ('8', 1), ('.', 1)]
In [29]:
yy = ''.join([x[0] for x in freqs(nsa) if x[0] in AA])
In [30]:
yy
Out[30]:
'EXHKNPQYMSDIJWLFZVGU'
In [31]:
len(yy)
Out[31]:
20
In [32]:
# On essaie d'aligner avec les fréquences en anglais

xx='ETAOINSRHDLUCMFYWGPB'
yy='EHXKNQPYMSDIJWFLVZGU'
ww=str.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 [33]:
# Le X->A et N->I sont probablkement corrects. I->S ?
# IU -> IS ? N->I, I->S
xx='ETAOINURHDLSCMFYWGPB'
yy='EHXKNQPYMSDIJWFLVZGU'
ww=str.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 [34]:
# NI ->IS, PFH -> THE ?

xx = 'AISTHE' 
yy = 'XNIPFH'
ww=str.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 [35]:
# C'est sur la bonne voie
# JATELAW : ^.ATE.A.$ dans le dictionnaire donne GATEWAY 
# etc ... 

xx = 'ASUPREMISNTHCOJFLGWYD'
yy = 'XKDUQHSEKYPFGNZIMJLWV'
ww=str.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 [36]:
# Autre exemple, semaine du 2/11/2015
# Faites le vous-mêmes ...

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 [37]:
print (list(map(ord,'SECRET'))) ###
print (list(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 [38]:
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 [39]:
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 [40]:
C = CyberCesar(0xe2)
y = C.crypt(map(ord,'À bon chat bon rat !'))
print(y) ### Résultat différent ! x est une chaîne unicode ici
[34, 194, 128, 141, 140, 194, 129, 138, 131, 150, 194, 128, 141, 140, 194, 144, 131, 150, 194, 195]
In [41]:
''.join(list(map(chr,y))) ###
Out[41]:
'"Â\x80\x8d\x8cÂ\x81\x8a\x83\x96Â\x80\x8d\x8cÂ\x90\x83\x96ÂÃ'
In [42]:
from codecs import encode, decode ### Très différent ici

def hex2buf(hh):
    return bytes(decode(hh,'hex')) 

def buf2hex(bb):
    return encode(bytes(bb),'hex')
#    return ''.join(['%2x'%b for b in bb])

def str2buf(s):
    return [ord(c) for c in s]

def buf2str(bb):
    return ''.join([chr(b) for b in bb])
In [43]:
x = 'À bon chat bon rat !'
In [44]:
y = C.crypt(str2buf(x))
print (y)
[34, 194, 128, 141, 140, 194, 129, 138, 131, 150, 194, 128, 141, 140, 194, 144, 131, 150, 194, 195]
In [45]:
z = buf2hex(y)
print (z)
b'22c2808d8cc2818a8396c2808d8cc2908396c2c3'
In [46]:
u = C.uncrypt(y)
print (u)
[192, 32, 98, 111, 110, 32, 99, 104, 97, 116, 32, 98, 111, 110, 32, 114, 97, 116, 32, 33]
In [47]:
print (buf2str(u))
À bon chat bon rat !
In [48]:
def b642buf(cc):
    return decode(cc,'base64')

def buf2b64(bb):
    return encode(bytes(bb),'base64')
In [49]:
z = buf2b64(y)
print (z)
b'IsKAjYzCgYqDlsKAjYzCkIOWwsM=\n'
In [50]:
bb = b642buf(z)
print (bb)
b'"\xc2\x80\x8d\x8c\xc2\x81\x8a\x83\x96\xc2\x80\x8d\x8c\xc2\x90\x83\x96\xc2\xc3'
In [51]:
print (C.uncrypt(bb)) ### buffer vu comme liste d'entiers
[192, 32, 98, 111, 110, 32, 99, 104, 97, 116, 32, 98, 111, 110, 32, 114, 97, 116, 32, 33]
In [52]:
### 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 [53]:
key = str2buf('Vigenère')
key
Out[53]:
[86, 105, 103, 101, 110, 232, 114, 101]
In [54]:
V = CyberVigenere(key)
In [55]:
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 [56]:
print (buf2b64(yy))
print (buf2hex(yy))
b'HwVHAB2cUhU6HBRFCIkRDDoMRwELyAEAdgUGEwuaUgkzGkcBC4YGFnYNBgsdyAcLdh8CFxyNUoV2\nGQ4ACsgDEDNJAwBOmxdFOggRABzIHgAlSRcMC4wBRTIICRZOnRxFIAwVFwvIkkUyDAkRHcY=\n'
b'1f0547001d9c52153a1c14450889110c3a0c47010bc80100760506130b9a5209331a47010b860616760d060b1dc8070b761f02171c8d528576190e000ac80310334903004e9b17453a0811001cc81e002549170c0b8c0145320809164e9d1c45200c15170bc89245320c09111dc6'
In [57]:
buf2str(yy)
Out[57]:
'\x1f\x05G\x00\x1d\x9cR\x15:\x1c\x14E\x08\x89\x11\x0c:\x0cG\x01\x0bÈ\x01\x00v\x05\x06\x13\x0b\x9aR\t3\x1aG\x01\x0b\x86\x06\x16v\r\x06\x0b\x1dÈ\x07\x0bv\x1f\x02\x17\x1c\x8dR\x85v\x19\x0e\x00\nÈ\x03\x103I\x03\x00N\x9b\x17E:\x08\x11\x00\x1cÈ\x1e\x00%I\x17\x0c\x0b\x8c\x01E2\x08\t\x16N\x9d\x1cE \x0c\x15\x17\x0bÈ\x92E2\x0c\t\x11\x1dÆ'
In [58]:
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.

Le one-time pad

In [59]:
K = open('/dev/urandom','rb').read(256)
In [60]:
print (encode(K,'hex'))
b'0445f14981220b11bb67200872498fa0a50797533b541cafc24ee89f5572940733eb9a71ae01dc1be53c18dbd101ef5c551124fef95156fc1932add159cf15ce09be912b3b912e411fdecc0b25c8bf5a66a48983009375d3a3f646da960464f4249af71573db0c05264530ce9bd7dc903db37ad7f4930076f64e0dbd8c06227313f352927212fe24ff115258d11e569e60b15d9728a57b0b1f8feb5365a6524393e251356c9913ff45ede7699e153005046696ac9e570f11839e829ce0e3d884b67fb3eeb674399eb5f178ef8a3c3628926f0ab2169819e4da73c8bac11cb090a37a65f7383f45bb230cdb9c6db64a1c8c543b840aa20e263de40d228fae8b23'
In [61]:
def otp(msg,key,offset):
    return bytes([ord(c)^k for c,k in zip(msg,key[offset::])]) ###
In [62]:
msg = 'abracadacra'
In [63]:
otp(msg,K,0)
Out[63]:
b"e'\x83(\xe2Cop\xd8\x15A"
In [64]:
class OneTimePad(object):
    def __init__(self,key):
        self.key=key
    
    def crypt(self,buf,offset):
        return bytes([c^k for c,k in zip(buf,self.key[offset::])])
    
    def uncrypt(self,buf,offset):
        return self.crypt(buf,offset)
    
        
In [65]:
OTP=OneTimePad(K)
In [66]:
msg = 'Il est plus facile de se laver les dents dans un verre à pied que de se laver les pieds dans un verre à dents.'
In [67]:
buf = str2buf(msg)
print (K)
b'\x04E\xf1I\x81"\x0b\x11\xbbg \x08rI\x8f\xa0\xa5\x07\x97S;T\x1c\xaf\xc2N\xe8\x9fUr\x94\x073\xeb\x9aq\xae\x01\xdc\x1b\xe5<\x18\xdb\xd1\x01\xef\\U\x11$\xfe\xf9QV\xfc\x192\xad\xd1Y\xcf\x15\xce\t\xbe\x91+;\x91.A\x1f\xde\xcc\x0b%\xc8\xbfZf\xa4\x89\x83\x00\x93u\xd3\xa3\xf6F\xda\x96\x04d\xf4$\x9a\xf7\x15s\xdb\x0c\x05&E0\xce\x9b\xd7\xdc\x90=\xb3z\xd7\xf4\x93\x00v\xf6N\r\xbd\x8c\x06"s\x13\xf3R\x92r\x12\xfe$\xff\x11RX\xd1\x1eV\x9e`\xb1]\x97(\xa5{\x0b\x1f\x8f\xebSe\xa6RC\x93\xe2Q5l\x99\x13\xffE\xed\xe7i\x9e\x150\x05\x04f\x96\xac\x9eW\x0f\x11\x83\x9e\x82\x9c\xe0\xe3\xd8\x84\xb6\x7f\xb3\xee\xb6t9\x9e\xb5\xf1x\xef\x8a<6(\x92o\n\xb2\x16\x98\x19\xe4\xdas\xc8\xba\xc1\x1c\xb0\x90\xa3ze\xf78?E\xbb#\x0c\xdb\x9cm\xb6J\x1c\x8cT;\x84\n\xa2\x0e&=\xe4\r"\x8f\xae\x8b#'
In [68]:
y = OTP.crypt(buf,0)
In [69]:
print (y)
b'M)\xd1,\xf2V+a\xd7\x12S(\x14(\xec\xc9\xc9b\xb77^to\xca\xe2"\x89\xe90\x00\xb4kV\x98\xba\x15\xcbo\xa8h\xc5Xy\xb5\xa2!\x9a2ugA\x8c\x8b4v\x1c9B\xc4\xb4=\xefd\xbbl\x9e\xf5N\x1b\xe2Kas\xbf\xbanW\xe8\xd3?\x15\x84\xf9\xeae\xf7\x06\xf3\xc7\x97(\xa9\xb6q\n\xd4R\xff\x85g\x16\xfb\xec%B ^\xba\xe8\xf9'
In [70]:
z = OTP.uncrypt(y,0)
z
Out[70]:
b'Il est plus facile de se laver les dents dans un verre \xe0 pied que de se laver les pieds dans un verre \xe0 dents.'
In [71]:
print(buf2str(z))
Il est plus facile de se laver les dents dans un verre à pied que de se laver les pieds dans un verre à dents.
In [ ]:
 
In [ ]: