CoCalc Shared FilesMisc / Préparation Kryptos.sagewsOpen in CoCalc with one click!
Author: Gabriel Chênevert
Views : 17

Préparation défi Kryptos 2015

La science / l'art des messages secrets se divise en deux grandes branches:

Stéganographie

Cryptographie

  • Code secret
  • Chiffrement
    • Transposition
    • Substitution

Cryptanalyse

4 grands types d'attaques:

  • Message chiffré seulement
  • Message initial connu
  • Message initial choisi
  • Message chiffré choisi

Outil de base: analyse fréquentielle (voir e.g. Wikipedia)

from collections import Counter Counter("Number of occurences of each character in this string")
Counter({' ': 8, 'c': 6, 'e': 5, 'r': 5, 'a': 3, 'i': 3, 'h': 3, 'o': 3, 's': 3, 't': 3, 'n': 3, 'f': 2, 'u': 2, 'b': 1, 'g': 1, 'm': 1, 'N': 1})

1) Chiffre de substitution monoalphabétique

On se donne un alphabet (ordonné) et une permutation de celui-ci.

alpha = "".join([chr(97 + i) for i in range(26) ] + [" "]) alpha
'abcdefghijklmnopqrstuvwxyz '
key = "".join(Permutations(alpha.upper()).random_element()) key
'XLGKY JQFWTDONACVPSBRMUZHEI'
plaintext = "substitution ciphers preserve the statistical properties of the plaintext" ciphertext = "".join([ key[alpha.index(c)] for c in plaintext ]) ciphertext
'SRLSBFBRBFANIGFCQYPSICPYSYPMYIBQYISBXBFSBFGXDICPACYPBFYSIA IBQYICDXFNBYZB'
Counter(plaintext)
Counter({'t': 11, 'e': 9, ' ': 8, 'i': 7, 's': 7, 'p': 5, 'r': 5, 'a': 3, 'h': 3, 'o': 3, 'c': 2, 'l': 2, 'n': 2, 'u': 2, 'b': 1, 'f': 1, 'v': 1, 'x': 1})
Counter(ciphertext)
Counter({'B': 11, 'Y': 9, 'I': 8, 'F': 7, 'S': 7, 'C': 5, 'P': 5, 'A': 3, 'Q': 3, 'X': 3, 'D': 2, 'G': 2, 'N': 2, 'R': 2, ' ': 1, 'M': 1, 'L': 1, 'Z': 1})

Défi: le message suivant a été chiffré par substitution pure. Sauriez-vous récupérer le message initial ?

B PMPGK'L'RLZU'J OGK'KFMP'LRR'B LB'NRSBB
PMK'SK'NORZ'LYZ'K PGK'EFUSYN'L'KBLSMJLU'
BO' PLQPY'J PY'K P'NPBK'B PMP'K P'AYOJK'
SI'B P'KBOMPK'LMP'LRR'DROKPZ'JSB 'L'JOMZ
'K P'DLY'NPB'J LB'K P'DLWP'IOM'OO 'LYZ'K
 PGK'EFUSYN'L'KBLSMJLU'BO' PLQPY'B PMPGK
'L'KSNY'OY'B P'JLRR'EFB'K P'JLYBK'BO'EP'
KFMP'GDLFKP'UOF'AYOJ'KOWPBSWPK'JOMZK' LQ
P'BJO'WPLYSYNK'SY'L'BMPP'EU'B P'EMOOA'B 
PMPGK'L'KOYNESMZ'J O'KSYNK'KOWPBSWPK'LRR
'OI'OFM'B OFN BK'LMP'WSKNSQPY'OO 'SB'WLA
PK'WP'JOYZPM
Cas dégénéré: la permutation est un simple décalage cyclique de l'alphabet (chiffre de César). On peut facilement essayer toutes les clés (voire automatiser le processus).

2) Chiffre de substitution polyalphabétique

On utilise différents chiffres de substitution monoalphabétique en fonction de la position du caractère. Une fois qu'on a déterminé comment les différents constituants sont multiplexés, on se ramnène au cas précédent pour chacun d'entre eux. Le chiffre de Vigenère est le cas où les substitutions monoalphabétiques sont des chiffres de César qui se répètent périodiquement.
alpha = "".join([chr(97 + i) for i in range(26) ] + [" "]) plaintext = "this will be encrypted with a vigenere cipher" key = "isen" ciphertext = "".join( alpha[ (alpha.index(plaintext[i]) + alpha.index(key[i % len(key)])) % len(alpha) ] for i in range(len(plaintext)) ).upper() ciphertext
'AZMEHNMYTRFRHWRPZPTFMVDIQKLMIRZVOWRRZWDPQGLRZ'

Défi: le message suivant récupéré sur un droïde échoué sur une planète désertique a été chiffré avec Vigenère. Saurez-vous retrouver le message original ?

UVTE4AZMQE0OPZC .EO8Y NG2M4O7 6VXVRDJ34 
SA7YKRII1MZHR Q2UNR  RXSJ 152 UEJSKG5 ,5
0 6OJYKL2 VZS VNJYOSIS780GTLSMGGNI19Z 6H
SMKM2I5VC V 5VMRRTJ NA6 WMGMIU1RHLR 75BC
1N9V4 ZYJWGTUE5PY 4E4.KS6 75BY1UJZT 2E59
UNK P.Z ZYJ9NI2 VRY SAZ2KNIU1UKRIA7 GCX,
JRTDIIM3BASROZJ ZYJ3OS5I24BT1 P8ONT ,50 
6OJRRDRRORT UA6MLAVLSUC V VR1EIPZRIEQ W4
LO4MO OO0 9ZZAY 75BTUEJ90R8I9RR 1FJ NEIR
SSKLYI24BI0T2MZHR 0VSO4YJ94S6E09BOS 7YOS
IRBM0NVTKMSYIFO NE4  ZRLIK152 UO MZOIRS 
XIRVSMOTJ ,50 ZU6 BSREJ NI5 R8UIQ 6RLEYY
JUKLVVS8KDIT2MNIZ 24BAYDS8GA0.J NI5 W9BO
7RJ3US6 RVYPRRO K UO88C UEZ6BMR,J5HIMWO4
BKRN2SO.IY2.ERR 0ABO0L,MNO2EK

Stratégie suggérée:

  • Commencer par déterminer la longueur de la clé
  • Puis récupérer chacun des caractères de celle-ci comme plus haut