Enigma

On utilise le module Py-Enigma pour simuler la machine Enigma.
Le module itertools est commode pour énumérer les permutations d'objets : il évite les boucles imbriquées.

In [1]:
from enigma.machine import EnigmaMachine
import itertools
import time 

Score

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.

In [2]:
from math import log10
In [3]:
f4g ={}
f = open('brut4g_fr.txt')     # statistiques des quadrigrammes français
total = 0  # effectif total
for line in f:
    (w, c) = line.split(sep= ' ')
    f4g[w] = int(c)
    total += int(c)
for w in f4g:
    f4g[w] = -log10(f4g[w]/total)  # calcul des -log fréquences des 4-grammes
f.close()
In [4]:
def logscore(s):
    logsum = 0
    min_freq = 100          # logscore d'un 4gramme inexistant
    for i in range(len(s)-3):
        logsum += f4g.get(s[i:i+4], min_freq)
    return logsum
In [5]:
logscore('TOUTVABIEN')
Out[5]:
31.960850601208996
In [6]:
logscore('NEIBAVTUOT')
Out[6]:
606.7253432899247

On est ramené à un problème d'optimisation : il faut obtenir la clé qui donne le logscore minimum.

Échauffement 1

------------------------------------------------------------------------
Echauffement 1 : Le message ci-dessous a été chiffré avec une machine
ENIGMA qui utilise le réflecteur B et les rotors I-II-III réglés sur
la position par défaut 1-1-1. Aucune fiche de connectée au plugboard.
------------------------------------------------------------------------
/i B-I-II-III 01-01-01
/e ???
------------------------------------------------------------------------
TVDOT JZXGW YPFFQ KTAUN YJLEQ NDXKZ ALYSH WHHMI MOWBW ZHHBY KUJDD URRGO
IPUHN VFJZE PAGVM JBYYA NGHCV DIJDL MGCIP FJODL ZJFNH VGPGU RFZLV ZOWMT
ZBNXM UZZRB NSVIN FLUXZ GTZZM FPYPE RKHJG ZYYQO SLZGM CQUNS VHXDM KNLRJ
QLSJK KZNNO YBKBX FMWKB FONTM HZGTQ WJ
------------------------------------------------------------------------
In [7]:
k1 = 'TVDOT JZXGW YPFFQ KTAUN YJLEQ NDXKZ ALYSH WHHMI MOWBW ZHHBY KUJDD URRGO\
IPUHN VFJZE PAGVM JBYYA NGHCV DIJDL MGCIP FJODL ZJFNH VGPGU RFZLV ZOWMT\
ZBNXM UZZRB NSVIN FLUXZ GTZZM FPYPE RKHJG ZYYQO SLZGM CQUNS VHXDM KNLRJ\
QLSJK KZNNO YBKBX FMWKB FONTM HZGTQ WJ'.replace(' ', '')

Work factor : $26^3 = 17576$.

In [8]:
start = time.time()
best_score = float('inf')
machine = EnigmaMachine.from_key_sheet(
   rotors = ['I', 'II', 'III'],
   reflector = 'B',
   ring_settings = 'A A A',
   plugboard_settings = '')
for init in itertools.permutations('ABCDEFGHIJKLMNOPQRSTUVWXYZ', 3):
    machine.set_display(init)      # position initiale des rotors
    txt = machine.process_text(k1)
    score = logscore(txt)
    if score < best_score:
        best_score = score
        print(best_score, init)
        print(txt)
delta = int(time.time()-start)
print('----- terminé en ',delta//60, 'min', delta%60, 'sec')
17706.416266979642 ('A', 'B', 'C')
PFWTSAEUXTVGNOKEWNJBVUVHCCVESNHWGOXGRYXQDAPRSBGEERGDGICCFNNPFQYTQTAVAAGQSOABCHWWYYLHNRSYNYFBQGNJDEXQLQRMGWHRCPMJXCGWIROCRQPVZHTXCOBCBQLRXDNYYPEAQZLKHSXITPEFDELGNKSWOYYXZLOWFBGGAQDRZNBQHCWPWZVASRUOIIJQUPTKFIUHUIJG
16846.90241120171 ('A', 'B', 'I')
XWCFXDMINJBSXSBBBXLCEFZTVXXFQOZFEAYVBKYFQTTCVRFGRZICFXMEONANBLKBKRHMPOEJIBKBSDEFFAKMLUAFSPVPOHRDAXSISENDOXMIVEUHQADYASZBTMJGOFXPQAOFMUPNANZFURIGEBNEOYPRIIUXTDTSPZNOCGETFHEONHGVXIQZXXHTDPNXGFGMJQPXGZGCSIPWROGLACMY
16761.38297252448 ('A', 'B', 'N')
EUMXMPIFJDNWOIAFVOPYFTYPUXOMJVOCCWMJEQTTVTFRMQGVSCNYIBQTGTJWURWYWOPUGOOCLNYVNZLQRSLYGJXROZEXLPOLEJNQULSTOBLXMLSIAASTYPKRXVUBPDBIGEFUBWROGXLYWHUSOKQPABHGBUKBFOKVENEMVFLWAKKDKEUSPIIREPFRHLOTCYNOTEYSTYUEENZAIXAEZXLW
16749.207248171817 ('A', 'B', 'V')
RYZFVNUWSTOLYONQAZJBNLIZUCGSJYOFEIGNDMQPHNVDEOYREVOSZENBHNMPTBQLRNAVISUQBKQHACJNSDZMPSLIORHVEBIYMIXBKTAPGTFHUTVIXKATCALPYEFTQRFHTTJWDRAYXQLJOAXSEIRQJLIPWWQCUSLGERFQVZRMPHAUOATPYKKKBZTWTGKGSXXETUFKIMNACNMELSNPVAFV
16654.25737653889 ('A', 'C', 'Q')
EWMERNYZFZPWHWSTELLLCTKWNOZOUUEHMEYNIYZTKPQILGBRALDDXKSZFAZDKNPRMWLEWKNPMDKMVOULEICMTRLAYDOYYQARTXYWTLPUFDUQVHXBXIBFAFONHOCLOZBLJFQESYFJUJNVMQWNIHJVFHJPOANQGPGATAIQFBCVPNCOAAQBORXXXWVFFLAJFHQDBJFWVSILJLEFGSLESOMR
16653.571259621345 ('A', 'C', 'W')
OEXFXVREJDNJOXKPESIYHGCOIJEZOWDIDPEMMGQJDSVGUERYCVNIZNCDNDIYDOKCVLNYYBRCSALFAJICXRKLABJETXRQSPLIHYVARUIBYSATIWTUXJDENEVVTHYFQMHSQKUXGLXZTDKKUESJOHSFVYHRURMNSKLCKNWPIKXGWKYCVOLHFUIRDADPGZUSPRIDHIUHWVLEWJMSLJAUKUUC
16370.304404741411 ('A', 'D', 'C')
OUCPEYWDHVUOECGURESOMMROGZTHMVCGEEBSKWFKNUQAPCEIMWHAZBAMLOVHBIROPSNURXNZPSSAZAAQJXSOEUZMQJOIPJLNSIBJXPYBCTUAUCUNGEFLYCCUDDFWBJEVLRXWJYFKIFLLMMWQIVVWXQUTQONYWXZHYGWRWGZVORSOBTISFBGCHUEUCPDYRLUAFQKNEEPIPCDDEYBVIOPZ
15912.39558334763 ('A', 'E', 'W')
NOCELAMHFEGZTAPCRXWROFMKXWXPIHJCLKGBVMRLGHZCLMCEPZMJERQGCVXVSZIUORSMTSFZDDKMTWZTPCTAMUHIRKPWNDSYRGUPDRNZIGOUMAUBCVOCYDIGNRGCILDHHWTYNHGDBKTYZRWAWEOLLQPISHPMZJYZEUBAVIFCRJSIILYAPPURGUIAUEBOXQAVDDCVBISNKQZOBOKPMNDL
15897.986391900678 ('C', 'N', 'B')
QZSMVFYHKAUMIDBTLUVYMXXFULNQSXPSGDVURSVATMHCNTXFKIIBVMMETESBSEQCXLPRJDRCPUFOYJDHTLSGAMALHOGJTGRDEZMQBXCSJRHTEYABOXIMPZZCHCBYSSJKBVIECFEAQAALPAXLIWYOGROWRHESEDEGNWNDFLKEGKKRGBTDHMIAARZHPOJCRBQLBHOKAOYAEYXOXTMSSAMY
15612.036914525157 ('C', 'Q', 'M')
SYTYKSOLESIXBCIYODALUCCCHFPMGMPAPIPAVDHWTLBXCDTXLUBSIEPRBASAUVNRPOWSSQTFPIRSFWFCFURTWYODEMKUBYENXPPCLAGFBHERVMTESSCHPNQSOZPZXNAQDWIZXMWLTOONRCGCWIXVERSXYTIXUNOEVJGHEUZQEISOKYAUUJBTBPXMBSTQVAUNVDGTQAUMUHEOBSHTXFJH
15606.720793980972 ('D', 'W', 'Y')
ZZZQRZAVYUEOKRPMRETLNXATLAVKHGDIDDVCELBPTHEKCQVERSDGCHUQUDKICHKTEBKERPVEUEDLYJAMBJVQMNYTQNUARHRNCIEEEMOCSARDRYOUKRXFFHZFPATRTEDUCWJOKQJTKOSMENPYCBBXCUGWVPPLEZKXNMXTAVOCLIARTHLCVQQHKTHSAAHSVRCCPCEWRSROISKZPIVJPTUI
14371.543516868747 ('E', 'N', 'K')
BEBNNZBKWDLHAQIOZJTYDVQCDSRLOYDEOYGEREFNEEKLNYMILESMAXZTADFQEVOEBZITVJBDCBWVHVQIINEDNELDISTYHUZUWGNZTQUERMPKZIXUMVSINSDOLYDANVICZDJREGRBOLAESSHRQHYHABTTLADECOWZJUHOCRWFFPOUEROQJEVBMAWKLMYCILVOASQUBXIGXPMBBMOEBFAQ
1142.3811977651108 ('P', 'A', 'F')
ECHAUFFEMENTLESROTORSAINSIQUELEURCONFIGURATIONSONTCONNUSETILNYAPASDEFICHESILSUFFITALORSDETROUVERLAPOSITIONDEDEPARTDESTROISROTORSPARMIDIXSEPTMILLECINQCENTSOIXANTESEIZEAVECLAPUISSANCEDESMACHINESACTUELLESPIECEOFCAKE
----- terminé en  0 min 23 sec

C'est du gâteau !

Échauffement 2

------------------------------------------------------------------------
Echauffement 2 : Le message ci-dessous a été chiffré dans les mêmes
conditions le précédent, à la différence que les rotors ne sont pas
dans le même ordre... à vous de le trouver.
------------------------------------------------------------------------
/i B-?-?-? 01-01-01
/e ???
------------------------------------------------------------------------
SQAJI BVZLB PYNOC CMNJX KMASC FKOPR BJTJB WXKHP JXJFK NVSQX RUDQW DDOAB
JIXFJ NBBTY WQQUF IDRGL WUBZX XWQJR DBAVB AWHVD JZTZW QBWQY TWNQA RZJVD
XECVE GVGFQ JVZRQ NOCTZ ERJDY AHVJD OKLBC WEODN UYBXO NZPSK DQKCZ IV
------------------------------------------------------------------------
In [9]:
k2 = 'SQAJI BVZLB PYNOC CMNJX KMASC FKOPR BJTJB WXKHP JXJFK NVSQX RUDQW DDOAB\
JIXFJ NBBTY WQQUF IDRGL WUBZX XWQJR DBAVB AWHVD JZTZW QBWQY TWNQA RZJVD\
XECVE GVGFQ JVZRQ NOCTZ ERJDY AHVJD OKLBC WEODN UYBXO NZPSK DQKCZ IV'.replace(' ', '')

Work factor : $3!\times 26^3 = 105456$.

In [10]:
start = time.time()
best_score = float('inf')
for r in itertools.permutations(['I', 'II', 'III'], 3):
    print('Rotors = ', r)
    machine = EnigmaMachine.from_key_sheet(
       rotors = r,
       reflector = 'B',
       ring_settings = 'A A A',
       plugboard_settings = '')
    for init in itertools.permutations('ABCDEFGHIJKLMNOPQRSTUVWXYZ', 3):
        machine.set_display(init)      # position initiale des rotors
        txt = machine.process_text(k2)
        score = logscore(txt)
        if score < best_score:
            best_score = score
            print(best_score, init)
            print(txt)
delta = int(time.time()-start)
print('----- terminé en ',delta//60, 'min', delta%60, 'sec')
Rotors =  ('I', 'II', 'III')
15140.051862581015 ('A', 'B', 'C')
FDTRWRJEBDMIFFLRDAUQRHRLQYFBHMEPJRAGNXPBLFQSEJKWHEODYMNHUPCSUBZAYOIERVOAKWTMMDIDUQSPMTXVXVKGIAEBPFUOHHSBRUCBSGWDKKDAKNDYKXHXJFRUVEQOXFRINHPYBGBHVCZXSAKIJDJTWATTGQALMWBJKQUFIPCOE
14198.231640152046 ('A', 'B', 'D')
IHGFUOWTYWGLTXROUEGUBSXYNKAAUKKTIDDDKRUQGNPDXUUAGNZQISMUZRYRTAMESCECLTSKGBTHRKZJEKICTWSGIPUWVFABNEYGQQKJVTWZSCMDEORUMIFVEGMTJAHISJDBPQDOXAVTSVCGGBIGNBHEIVAEYMXSCTHSSXLVLPBEOZNHG
14192.198965802378 ('A', 'C', 'Q')
XKSPQZKXUCYEPRDUHRFDTLICRCJXDDQZNMUNJBVFLKXUHHJWGAPDFMQHJENZHOGQZZCWDGTGOGYFYWAAAJUAFAENNVPHPAXBACMHCUXAITABRWHGPWRUNSAXOTNAWKFIDKLMDJBZJAAVBBOOTGAYDWQPPRABRZZCFNONSEUXVUHVHEWMI
13902.335272308084 ('A', 'C', 'Z')
LCQQQVAGWADVXFVTWGGNHYOXDGHRWVEMKVTZDTGEILSAUMYUALIBUGITLEFSTSTNYDEIOOZWTOHYOPRWGFDSZUFLFPVJRBQGXCOQUMBTLKOSACDYIYNHYCICFOATOVPIBBPBFPPSGQESMYTCFGVOXZKUBMAUSIOXTTPQJWOFUSOBHTORU
12795.384148797135 ('A', 'E', 'S')
DTBYYZTHWZIAPDGJRRLYMJMVHVXVNFREZAZUGIOZMVTSEFAEGFUMCPEABHSDCHIWZTEOYDEMYXDRUKBNVYMMNBDTOHEPHYCVACXORQCOSBMBKSCVGCROQGMAUTYWGATUARUEABAPLJMFSLPXTOAAAYDIZHKEIKKGAUDIEOBRTPKHRJEWA
12685.752902240274 ('A', 'K', 'F')
QKFVRAAPRQRFHCOQJLHAQOXNNWSRMUYEQBJMYFRMLLLXPTEEPPEDTUMKGTKRCYAQHJOHPRNTMQTAINEACTSFWGUYFSWCWHJOVJGZWEGHLOFCVUUJGATVDSHOSTODDHWFPUIFAUFFEQUCNDWYJMCXEMBUPJZLHCASEHMOXXROXEQSMNMFK
12504.658094863822 ('F', 'H', 'G')
GASKTDGUEUKFHNDAEUIYLOUNXOYWWZDFVNZOSAFIVWBUBORDIZELZASUTHBQQKTJBATDOATMZMQLLYOHANFOUMHTSYLEROIUVPGXBSSVJLXNYAVFIWIFWIXIKJNOFAIPSPBBQIDRHWFBSOPYGQPWPALLOYAIAMFELSHTKVAJJAELCKJXO
12115.427932789024 ('L', 'K', 'J')
MGGZRINAAVDATYKFRDAUEFWEKUOEDIVTOUPNRYSTZMMPAATWSQGITUMRNSIVEKIKSACALMUTXNKHOBRKXTUJNAQGYNBSYOCMLKKYOAQGISSEDUVNUELOIEQQPPTGSSXORYAREESRKWBLHSXYSCPRBFLEIUNVUFUIRPSVHWRQNCWGGVRTX
11735.788260602953 ('T', 'A', 'H')
JGKWEOQCISOJSNWNVZYOUXMTDIWPXAIEHYYLVOGBEARNWKAFHCGFTFIHELLLSONUNSEINOQIZGSHELCESAMBISRIXDOUJXCEMOAHEAFOIGHXPTLUOWETUPEZGHTJBRYQREBQUDEBENYNWFFOOLDYFMMYVWGBMEYDTZZSKBIFJBOLDMEFP
Rotors =  ('I', 'III', 'II')
Rotors =  ('II', 'I', 'III')
Rotors =  ('II', 'III', 'I')
812.3684060598446 ('B', 'A', 'M')
ECHAUFFEMENTMAINTENANTLORDREDESROTORSNESTPASCONNUCAMULTIPLIEPARSIXLENOMBREDECASATRAITERLETEMPSDECALCULAUGMENTEMAISRIENDINSURMONTABLECENESTPASENCOREDUVRAIENIGMAMAISCASENRAPPROCHE
Rotors =  ('III', 'I', 'II')
Rotors =  ('III', 'II', 'I')
----- terminé en  1 min 58 sec

Pour aller plus loin...

Tester tous les cas possibles dans le cas général prend beaucoup trop de temps. Il faut raffiner.

Voir l'article original de Jim Gillogly Ciphertext-Only Cryptanalysis Of Enigma

Pour des méthodes plus récentes, lire l'article de O. Ostwald & F. Weierud Modern Breaking of Enigma Ciphertexts


Le 5/12/2018 - Contact : Rossignol@bribes.org