Le système de chiffrement décrit par l'auteur n'est pas une variante du chiffre Playfair : il ne chiffre pas les digrammes du clair.
Il s'agit en fait d'une substitution homophonique (ou chiffre homophone). Le carré de Playfair ne sert qu'à donner les 24 homophones de chaque lettre.
Malgré le nombre important d'homophones, on peut casser ce chiffre par une méthode Hill-Climbing quand on a un cryptogramme assez long.
import time
import random
import itertools
from math import log10
La fonction suivante chiffre la chaine clair avec l'alphabet alpha (alphabet de 25 lettres sans J).
Pour chaque lettre c de clair, on tire au hasard une lettre d dans alpha qui soit différente de c.
On chiffre le digramme cd en utilisant le carré Playfair d'alphabet alpha et on concatène le résultat à la chaine crypto.
Si on applique la fonction plusieurs fois avec les mêmes paramètres, on obtient des cryptos différents (principe du chiffrement homophone).
def C_pseudo_Playfair(clair, alpha):
clair = clair.replace('J', 'I')
crypto = ''
for c in clair:
d = random.choice([x for x in alpha if x != c])
idx = alpha.index(c)
i0, j0 = idx//5, idx%5 # coordonnées de c
idx = alpha.index(d)
i1, j1 = idx//5, idx%5 # coordonnées de d
if i0 == i1: # c et d sur même ligne
crypto += alpha[i0*5+(j0+1)%5] + alpha[i1*5+(j1+1)%5]
elif j0 == j1: # c et d sur même colonne
crypto += alpha[((i0+1)%5)*5+j0] + alpha[((i1+1)%5)*5+j1]
else:
crypto += alpha[i0*5+j1] + alpha[i1*5+j0]
return crypto
crypto = C_pseudo_Playfair('LABELLECHASSERESSENAIMEPASBEAUCOUPLESPASSANTSQUICHASSENT', 'ARTEMISBCDFGHKLNOPQUVWXYZ')
crypto
La fonction de déchiffrement suivante effectue l'opération inverse : pour chaque digramme du crypto, on détermine le digramme inverse en utilisant le carré de Playfair et on ajoute la première lettre de ce digramme au texte clair.
def D_pseudo_Playfair(crypto, alpha):
clair = ''
big = [crypto[i:i+2] for i in range(0, len(crypto), 2)]
for b in big:
idx = alpha.index(b[0])
i0, j0 = idx//5, idx%5 # coordonnées de b[0]
idx = alpha.index(b[1])
i1, j1 = idx//5, idx%5 # coordonnées de b[1]
if i0 == i1: # c de d sur même ligne
clair += alpha[i0*5+(j0-1)%5]
elif j0 == j1: # c de d sur même colonne
clair += alpha[((i0-1)%5)*5+j0]
else:
clair += alpha[i0*5+j1]
return clair
D_pseudo_Playfair(crypto, 'ARTEMISBCDFGHKLNOPQUVWXYZ')
Le cryptogramme donné en exemple par l'auteur :
k = 'GM IA CX MR HU FH CK DQ GP IA BC DR ME SO TY CG BC RQ OA MF CV AU MK UX RV IO DP MT EN ND DK WS PD \
NX UL MR IO QN RV BD BR IF OP BP IG UE OL SD SK LX TN DO BI AY VF RH'.replace(' ', '')
k
D_pseudo_Playfair(k, 'ARTEMISBCDFGHKLNOPQUVWXYZ')
Une fonction de score permet au programme de savoir si une chaine de caractères a une bonne chance d'être en "bon français".
Pour les détails, voir le début de substitution_mono.
Le fichier brut4g_fr.txt contient les effectifs des quadrigrammes obtenus à partir d'un corpus de textes français.
f = open('brut4g_fr.txt', 'r')
f4g = {}
total = 0
for line in f:
(w, c) = line.split(sep= ' ')
if len(w) == 4:
if w in f4g:
f4g[w] += int(c)
else:
f4g[w] = int(c)
total += int(c)
else:
print(w) # erreur
for w in f4g:
f4g[w] = -log10(f4g[w]/total)
f.close()
nonexist = -log10(0.5/total)
def logscore(s):
score = 0
for i in range(len(s)-3):
score += f4g.get(s[i:i+4], nonexist)
return score
def str_shuffle(s):
"""Retourne une chaîne obtenue en mélangeant les lettres de s.
"""
ls = list(s)
random.shuffle(ls)
return ''.join(ls)
La fonction suivante applique les symétries du carré sur le carré Playfair d'alphabet alpha.
sym = [
[4, 9, 14, 19, 24, 3, 8, 13, 18, 23, 2, 7, 12, 17, 22, 1, 6, 11, 16, 21, 0, 5, 10, 15, 20], # 0 :quart de tour direct
[20, 15, 10, 5, 0, 21, 16, 11, 6, 1, 22, 17, 12, 7, 2, 23, 18, 13, 8, 3, 24, 19, 14, 9, 4], # 1: quart de tour indirect
[24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0], # 2: demi-tour
[20, 21, 22, 23, 24, 15, 16, 17, 18, 19, 10, 11, 12, 13, 14, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4], # 3: symétrie axe horizontal
[4, 3, 2, 1, 0, 9, 8, 7, 6, 5, 14, 13, 12, 11, 10, 19, 18, 17, 16, 15, 24, 23, 22, 21, 20], # 4: symétrie axe vertical
[24, 19, 14, 9, 4, 23, 18, 13, 8, 3, 22, 17, 12, 7, 2, 21, 16, 11, 6, 1, 20, 15, 10, 5, 0], # 5: sym diag principale
[0, 5, 10, 15, 20, 1, 6, 11, 16, 21, 2, 7, 12, 17, 22, 3, 8, 13, 18, 23, 4, 9, 14, 19, 24] # 6: sym diag secondaire
]
def permut(alpha, n):
# assert(len(alpha) == 25)
return ''.join([alpha[i] for i in sym[n]])
La fonction suivante essaye d'affiner un alphabet alpha pour le crypto kk.
Pour cela, on applique à alpha toute une batterie de transformations : sitôt qu'on obtient un meilleur score, on retourne le score et le nouvel alphabet sans aller plus loin.
On peut utiliser d'autres transformations. J'ai essayé, par exemple, les permutations de 4 éléments de alpha, mais le temps d'exécution devient prohibitif. Plus on "ratisse large", plus on a de chance de tomber sur le bon alphabet, mais le programme est trop ralenti. Il faut trouver le bon compromis.
def affine(kk, alpha):
"""Cherche un alphabet ayant un meilleur score que alpha.
Retourne le score et le nouvel alphabet s'il existe.
Sinon retourne un score infini et une chaîne vide.
"""
best_score = logscore(D_pseudo_Playfair(kk, alpha))
for p in itertools.combinations(range(25), 2): # test permutation de deux éléments
nalpha = list(alpha)
nalpha[p[0]], nalpha[p[1]] = nalpha[p[1]], nalpha[p[0]]
nalpha = ''.join(nalpha)
score = logscore(D_pseudo_Playfair(kk, nalpha))
if score < best_score:
return score, nalpha
for i in range(7): # test des 7 symétries
nalpha = permut(alpha, i)
score = logscore(D_pseudo_Playfair(kk, nalpha))
if score < best_score:
return score, nalpha
m0 = [list(alpha[i*5:i*5+5]) for i in range(5)]
for p in itertools.permutations(range(4), 4): # test permutations lignes
m = [m0[p[0]], m0[p[1]], m0[p[2]], m0[p[3]], m0[4]]
nalpha = ''.join([''.join(m[i]) for i in range(5)])
score = logscore(D_pseudo_Playfair(kk, nalpha))
if score < best_score:
return score, nalpha
for p in itertools.permutations(range(4), 4):
m = list(m0)
for k in range(5): # permutation colonnes
m[k][0], m[k][1], m[k][2], m[k][3] = m[k][p[0]], m[k][p[1]], m[k][p[2]], m[k][p[3]]
nalpha = ''.join([''.join(m[i]) for i in range(5)])
score = logscore(D_pseudo_Playfair(kk, nalpha))
if score < best_score:
return score, nalpha
for p in itertools.permutations(range(25), 3): # test permutation de trois éléments
nalpha = list(alpha)
nalpha[p[0]], nalpha[p[1]], nalpha[p[2]] = nalpha[p[1]], nalpha[p[2]], nalpha[p[0]]
nalpha = ''.join(nalpha)
score = logscore(D_pseudo_Playfair(kk, nalpha))
if score < best_score:
return score, nalpha
return float('inf'), '' # pas trouvé
La fonction suivante utilise le Hill-Climbing pour trouver le meilleur alphabet correspondant à un alphabet tiré au hasard.
def _HC_pseudo_Playfair(crypto):
"""Par défaut alpha est sans J (anglais)
"""
best_alpha = str_shuffle('ABCDEFGHIKLMNOPQRSTUVWXYZ')
best_score = float('inf')
while True:
score, nalpha = affine(crypto, best_alpha)
if score < best_score:
best_score = score
best_alpha = nalpha
else:
return best_score, best_alpha
Même si le hasard fait bien les choses, il y a peu de chance de trouver le bon alphabet en appliquant une seule fois la fonction précédente. La fonction suivante applique plusieurs fois notre fonction de Hill-Climbing. Le nombre d'itérations est fixé à 100 par défaut : c'est un peu grand pour un crypto long, mais un peu faible pour un crypto court.
def HC_pseudo_Playfair(crypto, nb_iter = 100):
start = time.time()
best_score = float('inf')
best_alpha = ''
for _ in range(nb_iter):
score, alpha = _HC_pseudo_Playfair(crypto)
if score < best_score:
best_score = score
best_alpha = alpha
print(best_score, best_alpha)
print(D_pseudo_Playfair(crypto, best_alpha))
print("*** Meilleure solution ***")
print('score = ', best_score)
print('alphabet déchiffrant :', best_alpha)
print(D_pseudo_Playfair(crypto, best_alpha))
delta = int(time.time()-start)
print('----- terminé en ',delta//60, 'min', delta%60, 'sec')
Honoré de Balzac - Histoire des Treize
http://www.gutenberg.org/files/55860/55860-h/55860-h.htm
Il est dans Paris certaines rues déshonorées autant que peut l’être un homme coupable d’infamie; puis il existe des rues nobles, puis des rues simplement honnêtes, puis de jeunes rues sur la moralité desquelles le public ne s’est pas encore formé d’opinion; puis des rues assassines, des rues plus vieilles que de vieilles douairières ne sont vieilles, des rues estimables, des rues toujours propres, des rues toujours sales, des rues ouvrières, travailleuses, mercantiles. Enfin, les rues de Paris ont des qualités humaines, et nous impriment par leur physionomie certaines idées contre lesquelles nous sommes sans défense.
txt = 'ILESTDANSPARISCERTAINESRUESDESHONOREESAUTANTQUEPEUTLETREUNHOMMECOUPABLEDINFAMIE\
PUISILEXISTEDESRUESNOBLESPUISDESRUESSIMPLEMENTHONNETESPUISDEJEUNESRUESSURLAMORAL\
ITEDESQUELLESLEPUBLICNESESTPASENCOREFORMEDOPINIONPUISDESRUESASSASSINESDESRUESPLU\
SVIEILLESQUEDEVIEILLESDOUAIRIERESNESONTVIEILLESDESRUESESTIMABLESDESRUESTOUJOURSP\
ROPRESDESRUESTOUJOURSSALESDESRUESOUVRIERESTRAVAILLEUSESMERCANTILESENFINLESRUESDE\
PARISONTDESQUALITESHUMAINESETNOUSIMPRIMENTPARLEURPHYSIONOMIECERTAINESIDEESCONTRE\
LESQUELLESNOUSSOMMESSANSDEFENSE'
k1 = C_pseudo_Playfair(txt, 'BOWGTIESXPUFCAMLDYVKNHQZR')
k1
Résolution avec crypto complet :
HC_pseudo_Playfair(k1, nb_iter=10)
On restreint le crypto à 800 caractères (clair de 400 caractères)
HC_pseudo_Playfair(k1[:800], nb_iter=10)
Crypto de 600 caractères (clair de 300 caractères) :
HC_pseudo_Playfair(k1[:600])
Crypto de 400 caractères (clair de 200 caractères) :
HC_pseudo_Playfair(k1[:400], nb_iter=200)
Crypto de 300 caractères (clair de 150 caractères) :
HC_pseudo_Playfair(k1[:300], nb_iter=1000)
k2 = 'BRASMFUOFRXTVUGAKCLIPFTHRVIPNUFYECHYDRHTUSLCHFSBHVMVKLMUNMFQSZZHGBIHTBBTTQNWCGY\
EHYUHYLHTQSTPNKNPZQOHHTGCWRUHLPFNGCMBIFKYYCNHNWHVLYULSANHQHCIBKNCPLTBOSSCYTNLZDM\
HXYORHXWPLGYEIOXRSGSWKCFOHTEXHTIFVTYLVFBNNUAUTWBFSLWOXTBPELIYWOVUAHYVOMSARCTKBNY\
DRYEWVNRNEOVBKXNTXSLSNHCMVBIQUEHRKXFBLPQYNGEOWNLCLHCXSBUPUOSXBNIEBCLZMEHEHUXTIQB\
VPOHCCMNWHCABRVEXNTHVGQOHGQOQBRKIEXYEVFAEWLOCFOHRUMBRBKXDLEFCQZCOKSNUMBBNLTKGHCS\
BILRYDNMHHRCWRVUMTUCRHCKGSRHFUVLKRTNEKRBAUBLXIFTHXTHRSBNVTUEDHTLRYTQABWBUSDRVEFO\
WRYQPFBELGESZUHLPFBTYXWFYPLHVETTRVEHDXCUOFTVUZSCOYENCTWNWHRBNSBFCIDWHWRLNOLRYQSC\
LKMLHHASGPWYCNDRVYDHYETKWCUCXLANZBYLIYENM'
len(k2)
HC_pseudo_Playfair(k2)
O mathématiques sévères, je ne vous ai pas oubliées, depuis que vos savantes leçons, plus douces que le miel, filtrèrent dans mon coeur, comme une onde rafraîchissante. J'aspirais instinctivement, dès le berceau, à boire à votre source, plus ancienne que le soleil, et je continue encore de fouler le parvis sacré de votre temple solennel, moi, le plus fidèle de vos initiés.
Comte de Lautreamont - Les Chants de Maldoror
http://www.gutenberg.org/cache/epub/12005/pg12005.txt
k3 = 'OMLKQBETOYXIEIOFRILQQBVXMZBEFKQCGWDNBIHOVAOPZFGRZFZKVXQOGPPUVNEYUPSCCGIAVFVBDMV\
OMWTYDNVNOGCLGOEPVQGSVUPHGKLITPCUYFXSXLXIAXDIBVEQQCSZUINRNYSQAXEGMNZTVBUXXIQXKYV\
ASUYWQNLINLUYLQQLMTXFWQAKFOLQGEZULKOIVILXWQGTRWVGAZOTUNAWIEVIBKOZKMVIYQCOAPNXCEC\
YHNCILZXZQIRFAHXNUXVNQZITLHZBZPVDWKLCVTKADBDGVZZHMFZPNRDLXILDBNSPZGNKREYQDFZFNPX\
WORXVQPDLXZLCMTLEKUKPNQYVGAGQSMUPIOKUDOBQBELQZYVKFOKFXIRQQTMPUCYDVXDESQAIHFVIVTD\
SUYBNDMLVICTYBQQGAGNEARVTVUUHVOSEIEXIAPGCXBDGYFYEMEBILIKIUNYVGXQGSBGIVPDLVXKFHNB\
VQTWYITSBXL'
len(k3)
HC_pseudo_Playfair(k3, 200)
Ma jument baie cerise était atteinte de coqueluche, et mon alezan hors de service à la suite de chagrins d'amour. Quant à mes robustes percherons, impossible de compter sur eux, totalement abrutis qu'ils sont par la lecture à haute voix, devant eux, de la chronique d'un penseur bien personnel et profond.
Alphonse Allais - Deux et deux font cinq
http://www.gutenberg.org/cache/epub/23444/pg23444.txt
k4 = 'HTLRINAFYLBFKIYCRXXECINECNBVNFHXBYEDNZNVEWLSCNVWCIZVVRINDMZIWBCMGUXLBNDCSFQLKFU\
ZLERQXFTDBMLXDMBFKEFGYBUTNVHAXMCMZIKZZNXMUIKZFXPXBXRBPHMXDASNBHMICGBMQZTIFKWXFNI\
MPZRAHIOYLXPMCNCWNABFGXBIDXQUNHXUHXQBTCXKXHHOBCPOMNPNDWBSWQMETNMXWDWMXOFMLXBETIB\
XINOWNLXZBSBEYOOAINZMVCBNNXGEGVMEOFXZBCFAYDSOFNAVITFUDQCIOERAFIFXAQOGHMWIZMPYXUH\
IORPKMNTIKDXYOPCIPQGYZMQLZDSHZNQSRLBXQBLTKINIFIWMROTIBIDYZILMHRWGFGHMKZXNBFOYDUV\
KWIRUHERYKYUZRQFNXZGZZMHYVLGZVGKXBCRDVFZIGXMEFPZODRPSQFHMQYFGUSLRGMQRFMOEZQNTZTC\
NOWQGUIAVWOZXXYYPQUGNDIAHBNPYAVDLVFKGCUWTZIXTYPFUGZNVNIGECISZBN'
len(k4)
HC_pseudo_Playfair(k4)
Longtemps, je me suis couché de bonne heure. Parfois, à peine ma bougie éteinte, mes yeux se fermaient si vite que je n'avais pas le temps de me dire: «Je m'endors.» Et, une demi-heure après, la pensée qu'il était temps de chercher le sommeil m'éveillait; je voulais poser le volume que je croyais avoir encore dans les mains et souffler ma lumière;
Marcel Proust - Du Côté de Chez Swann
http://www.gutenberg.org/files/2650/2650-0.txt
k5 = 'QBDBAMVUVIPEDXWBBCLBWMXEZWLIUWSTAZXHWUBKZLQPSDTNQIZITZXSVXEIMUODURNPQSNGAWLHUGML\
DHVUZTLZFHRNZFDSWUAGHPWLGSLYAVGYWVQVLOYVAFZMCALKTLXCDMLYTXZUGRWEDGHOYCKXDRWVATVT\
KLLXFUOMDQALZTUPQSHRZPAXTNZUSINALZGNOHWKDNHKXHFIZEBUBNDNQALKSBFCDSYKSXZABUQAUDGR\
FNHGWEVRXETANWNZZBXBWXZBVRFAWXBVLZLILSDWQCAVYTWXOSLHZSQBWSCPWLFTXWWLQVZVQIYOGSZI'
len(k3)
HC_pseudo_Playfair(k5, 500)
Il semble que la nature, qui a si sagement disposé les organes de notre corps pour nous rendre heureux; nous ait aussi donné l'orgueil pour nous épargner la douleur de connaître nos imperfections.
François de La Rochefoucauld - Réflexions ou sentences et maximes morales
http://www.gutenberg.org/cache/epub/14913/pg14913.txt
Malgré l'utilisation d'un grand nombre d'homophones, ce système de chiffrement n'assure pas la sécurité d'un message de plus de 150 caractères.
Le 3/04/2019 - Contact : Rossignol@bribes.org