Solving a periodic polyalphabetic substitution¶
Initial cryptogram. We replace spaces with _ (underscore)
k0 = 'YN×#NS ⴽΔUVꓭⴽU+ΞN ꓥꓷXUAO +ꓭX YZ#ꓭ#⊕ꓥ VY ×VYꓥꓘ×Δ ×XꓷOΞꓥ Z+ꓭU XPXMOꓥYY+ⴽ +ꓘꓥ N×#ΔI OꓭOⴽ ꓘΞ Iⵁ+ ⴽꓘTTUꓘO UXS YZ#ꓘIYΞ \
M++ꓘ ⴽY⊕ꓷꓷΞ+P+ ⊕ꓭNXꓥ ꓷ ꓭꓭYꓥ ꓭ ZꓘPS UYZZ⊕⌖ ꓘP U×Δ ⌖V×⊕N N+Y+ ꓘZPꓷ ⴽꓘIꓷΔO ZPꓷ Iⵁ+ꓷ UꓥꓘΔNꓘPꓥ PⵁZ ⊕ꓘAY ꓭ Ξ++S⌖Δ # \
ꓘPⴽXYSꓥΞ Z+Δ ZTPY⌖Δ ꓘ⊕Ξ TXΔOꓥΞ #⊕ +ꓭX ⵁTⴽ ꓭ#N ΔⴽVꓭIΞPΔ ZYVꓭ +ꓘꓥ ⊕⌖UOYXY XZS+YΞ U×Δ ×⌖ꓭMY +V YNꓥ+X⊕N ꓷⵁP ×Oꓥꓥ⊕⊕+ΞN \
ΞZⴽꓭ#ꓭꓥ VY +ꓘꓥ Y×SO M++ꓘΞP ⊕ꓷΔIZΔY ꓭY×ꓷ +ꓭX OꓥY+ T ⴽꓭ⌖ Nꓘ⌖ YΔ⊕ UPSPⵁꓥⵁ# O ?'.replace(' ', '_')
print(k0)
YN×#NS_ⴽΔUVꓭⴽU+ΞN_ꓥꓷXUAO_+ꓭX_YZ#ꓭ#⊕ꓥ_VY_×VYꓥꓘ×Δ_×XꓷOΞꓥ_Z+ꓭU_XPXMOꓥYY+ⴽ_+ꓘꓥ_N×#ΔI_OꓭOⴽ_ꓘΞ_Iⵁ+_ⴽꓘTTUꓘO_UXS_YZ#ꓘIYΞ_M++ꓘ_ⴽY⊕ꓷꓷΞ+P+_⊕ꓭNXꓥ_ꓷ_ꓭꓭYꓥ_ꓭ_ZꓘPS_UYZZ⊕⌖_ꓘP_U×Δ_⌖V×⊕N_N+Y+_ꓘZPꓷ_ⴽꓘIꓷΔO_ZPꓷ_Iⵁ+ꓷ_UꓥꓘΔNꓘPꓥ_PⵁZ_⊕ꓘAY_ꓭ_Ξ++S⌖Δ_#_ꓘPⴽXYSꓥΞ_Z+Δ_ZTPY⌖Δ_ꓘ⊕Ξ_TXΔOꓥΞ_#⊕_+ꓭX_ⵁTⴽ_ꓭ#N_ΔⴽVꓭIΞPΔ_ZYVꓭ_+ꓘꓥ_⊕⌖UOYXY_XZS+YΞ_U×Δ_×⌖ꓭMY_+V_YNꓥ+X⊕N_ꓷⵁP_×Oꓥꓥ⊕⊕+ΞN_ΞZⴽꓭ#ꓭꓥ_VY_+ꓘꓥ_Y×SO_M++ꓘΞP_⊕ꓷΔIZΔY_ꓭY×ꓷ_+ꓭX_OꓥY+_T_ⴽꓭ⌖_Nꓘ⌖_YΔ⊕_UPSPⵁꓥⵁ#_O_?
Transliteration of k0 --> k1
alpha26 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
k1 = ''
alpha = {}
idx = 0
for c in k0:
if c == '?':
continue
if c == '_':
k1 += '_'
continue
if c not in alpha:
alpha[c] = alpha26[idx]
idx += 1
k1 += alpha[c]
print(k1)
ABCDBE_FGHIJFHKLB_MNOHPQ_KJO_ARDJDSM_IA_CIAMTCG_CONQLM_RKJH_OUOVQMAAKF_KTM_BCDGW_QJQF_TL_WXK_FTYYHTQ_HOE_ARDTWAL_VKKT_FASNNLKUK_SJBOM_N_JJAM_J_RTUE_HARRSZ_TU_HCG_ZICSB_BKAK_TRUN_FTWNGQ_RUN_WXKN_HMTGBTUM_UXR_STPA_J_LKKEZG_D_TUFOAEML_RKG_RYUAZG_TSL_YOGQML_DS_KJO_XYF_JDB_GFIJWLUG_RAIJ_KTM_SZHQAOA_OREKAL_HCG_CZJVA_KI_ABMKOSB_NXU_CQMMSSKLB_LRFJDJM_IA_KTM_ACEQ_VKKTLU_SNGWRGA_JACN_KJO_QMAK_Y_FJZ_BTZ_AGS_HUEUXMXD_Q_
Histogram of k1 without spaces¶
import matplotlib.pyplot as plt
def histo(s, alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'):
eff = [0]*len(alpha)
for i in range(0, len(s)):
if s[i] not in alpha:
continue
eff[alpha.index(s[i])] += 1
plt.bar(range(len(alpha)), eff, width=.5)
plt.xticks(range(len(alpha)), list(alpha))
plt.show()
histo(k1.replace('_', '')) # histogram without spaces
Search for the period: the Kullback's Method¶
Solomon Kullback presents his method using an example in Statistical Methods in Cryptanalysis, pp. 41-47.
To test for a period of length p, the cryptogram is written in rows of p characters. If p is equal to the period, then each column is encrypted with the same alphabet, and the coincidence index is close to 0.065 (monoalphabetic distribution). If, on the other hand, p is not equal to the period, each column is made up of characters encrypted with different alphabets, and the coincidence index is close to 0.038 (random distribution of letters).
To smooth out random deviations, the column coincidence indices are averaged.
The Kullback test is different from the Kappa test and it is better.
For a discussion see F. L. Bauer Decrypted Secrets p. 345 sq.
def IndexC(s):
""" Returns the index of coincidence of the string s.
"""
h = {}
for c in s:
if c in h:
h[c] += 1
else:
h[c] = 1
n = 0
ic = 0
for c in h:
ic += h[c]*(h[c]-1)
n += h[c]
return ic/n/(n-1)
def Kullback(crypto, nmax = 20):
"""Find the key length using the IC (S. Kullback method)
nmax = maximum key length
"""
print(' n : average ic \t[ ic min : ic max ] standard deviation')
for n in range(1, nmax+1):
c = {}
for i in range(len(crypto)):
if i%n in c:
c[i%n] += crypto[i]
else:
c[i%n] = crypto[i]
ic = 0
var = 0
ic_min = float('inf')
ic_max = 0.0
for i in c:
ici = IndexC(c[i])
ic += ici
var += ici**2
if ici < ic_min:
ic_min = ici
if ici > ic_max:
ic_max = ici
ic = ic/n
var = var/n - ic**2
print(format(n, '3d'), ':', format(ic, '.10f'), '\t[', format(ic_min, '.5f'), ':',
format(ic_max, '.5f'), ']', format(var**0.5, '.5f'))
Kullback(k1.replace('_', ''))
n : average ic [ ic min : ic max ] standard deviation 1 : 0.0442075338 [ 0.04421 : 0.04421 ] 0.00000 2 : 0.0442686056 [ 0.04341 : 0.04512 ] 0.00086 3 : 0.0549656800 [ 0.03941 : 0.07642 ] 0.01567 4 : 0.0425272519 [ 0.04016 : 0.04590 ] 0.00221 5 : 0.0412855509 [ 0.03844 : 0.04387 ] 0.00239 6 : 0.0550865801 [ 0.03636 : 0.08506 ] 0.01992 7 : 0.0433130699 [ 0.03103 : 0.05408 ] 0.00753 8 : 0.0428281069 [ 0.03020 : 0.05343 ] 0.00726 9 : 0.0670495056 [ 0.04805 : 0.08559 ] 0.01127 10 : 0.0387143494 [ 0.02674 : 0.04924 ] 0.00666 11 : 0.0455590387 [ 0.02989 : 0.06437 ] 0.01206 12 : 0.0500440917 [ 0.02910 : 0.09524 ] 0.02104 13 : 0.0427416174 [ 0.02154 : 0.07385 ] 0.01347 14 : 0.0411490683 [ 0.02174 : 0.05797 ] 0.01109 15 : 0.0514084949 [ 0.01976 : 0.11858 ] 0.02696 16 : 0.0419642857 [ 0.01429 : 0.07619 ] 0.01450 17 : 0.0449604403 [ 0.02105 : 0.07895 ] 0.01484 18 : 0.0625501663 [ 0.02924 : 0.11696 ] 0.02136 19 : 0.0430856553 [ 0.01471 : 0.07190 ] 0.01448 20 : 0.0369607843 [ 0.02206 : 0.06618 ] 0.01152
The first maximum greater than 0.65 is obtained for p=9 so the cipher is periodic with period p = 9.
Which confirms the hint given by the author of the cryptogram: the keyword is SECRETKEY of length 9.
Let's attack!¶
The score function¶
A dictionary is filled with the precalculated scores of the quadrigrams of the English language.
f4g ={} # 4-gram score dictionary
with open('logf4g_space_en.txt', 'r') as file:
for line in file:
line = line.strip()
quadgram, score = line.split()
f4g[quadgram] = float(score)
This function returns the score of a string.
def logscore(s):
logsum = 0
min_freq = 6.982298374176025 # score of a non-existent quadrigram
for i in range(len(s)-3):
logsum += f4g.get(s[i:i+4], min_freq)
return logsum
The logscore is minimum for an English string.
logscore('HELLO_WORLD')
34.95519033182733
logscore('OLLEH_DLROW')
51.92937710122753
Polyalphabetic substitution with independent alphabets¶
def sub_polyalpha(crypto, liste_alpha):
""" Polyalphabetic substitution on 'crypto'.
The letters of 'crypto' are sequentially encrypted by the alphabets in 'alpha_list'.
"""
idx = 0
clair = ''
for c in crypto:
if c in alpha26:
clair += liste_alpha[idx][alpha26.index(c)]
idx = (idx+1)%len(liste_alpha)
else:
clair += c
return clair
Solving by simulated annealing¶
We have an optimization problem: finding the list of alphabets that minimizes the logscore of the text obtained with sub_polyalpha.
We use the simulated annealing algorithm.
This function returns an alphabet slightly different from the alphabet passed as an argument:
import random
def new_alpha(alpha):
c = list(alpha)
i, j, k, m = random.sample(range(len(alpha)), 4)
choice = random.random()
if choice < 0.7:
c[i], c[j] = c[j], c[i] # permutation of two elements
elif choice < 0.8:
c[i], c[j], c[k] = c[j], c[k], c[i] # circular permutation of 3 elements
elif choice < 0.9:
c[i], c[j], c[k], c[m] = c[j], c[k], c[m], c[i] # same with 4 elements
else:
if i > j:
i, j = j, i # we want i < j
m = c[i:j]
m.append(m.pop(0)) # rotation of segment c[i:j]
c[i:j] = m
return ''.join(c)
The Metropolis criterion:
from math import exp
def Metropolis_criterion(delta, T):
if delta <= 0: return True
if random.random() < exp(-delta/T) and delta/T < 0.05:
return True
return False
Finally the solving function:
import time
def SA_PolyAlpha(crypto, period, max_iter = 0, cool_ratio = 0.8, trace=False):
start = time.time()
if max_iter == 0: # valeur par défaut
max_iter = period*10_000
myalphas = [] # liste des alphabets courants
a = list(alpha26)
for i in range(period):
random.shuffle(a)
myalphas.append(''.join(a))
plain = sub_polyalpha(crypto, myalphas)
old_score = logscore(plain)
T = 100
best_plain = plain
best_alphas = myalphas.copy()
best_score = old_score
idx_alpha = 0
while True:
nb_iter = 0
while nb_iter < max_iter:
nalphas = myalphas.copy()
nalphas[idx_alpha] = new_alpha(nalphas[idx_alpha])
plain = sub_polyalpha(crypto, nalphas)
new_score = logscore(plain)
delta = new_score - old_score
if Metropolis_criterion(delta, T): # transition accepted
myalphas = nalphas.copy()
old_score = new_score
if old_score < best_score:
best_score = old_score
best_alphas = myalphas.copy()
best_plain = plain
if trace:
print(best_score) # trace
nb_iter += 1
idx_alpha = (idx_alpha+1)%period
T *= cool_ratio
if T < 20: # stopping condition
break
print("*** Best solution ***")
print('score = ', best_score)
print('alphabets :', best_alphas)
print(best_plain)
delta = int(time.time()-start)
print('----- Elapsed time ',delta//60, 'min', delta%60, 'sec')
SA_PolyAlpha(k1[:-1], 9)
*** Best solution *** score = 1493.675380305335 alphabets : ['SVBMWTKZPFCIEQOJYAHDGUXNRL', 'RHLGPXEWVATDSIKYMZCONUQJBF', 'QNOIXRGUJWPFBDKLMTEAZCVYSH', 'EDGLOWUAVRHQXMKJYFNIPCTZSB', 'RLUGZXEWFATDSBQPMCVINYKHOJ', 'MXFQYVZTOHELGIAKPCRDJWNUBS', 'FYHPSDJGAMIZUNELWCVBTXQKOR', 'RLPZQCESGITBKAWXDFMONJUHYV', 'DBPFTJZSAMGYINCWREQHKXLVOU'] SHOLLY_DESPARATLY_KNOWLY_THE_REMAINS_OF_PASSAGE_FEARIS_THAT_ENCUMBERED_THE_HOLEN_WIRT_OF_THE_DOORWAY_WAS_REMOVED_WITH_TREMBLING_HANKS_I_MIDE_A_TINY_GREACH_IN_THE_UPLED_LEFT_HAND_WINNER_AND_THEN_SIDENING_THE_HOLE_A_LITTLE_I_INVERTED_THE_CONDLE_AND_BEERED_IN_THE_HOT_AID_EVAILING_FROM_THE_CHAMMER_CAPPED_THE_PLACE_TO_FLICKED_BUT_PRESENTLY_BETAIRS_OF_THE_ROOM_WITHIN_EMENCED_FROM_THE_DIST_S_WAS_YOU_SEE_ANYTHING_M ----- Elapsed time 1 min 8 sec
The result is not perfect but we can guess the plain text.
By restarting the program several times, I obtained:
score = 1510.901123046875
alphabets : ['SZBMXTVGPFCIEKOJWAHDQUYNRL', 'RLPGUBEWZAHDSVKFMICONXTQJY', 'XNOIZRGKUQSFBDYLPTEAJCVWMH', 'EDVWOCJAGRHBZMKLYPNIFSTQXU', 'RLVJCGEWIATDSBXQMYFONUKHPZ', 'PCSFYDJTOHELGIAZVMKQXWRUBN',
'FYHQSDPGWMIBLNEOCRXZTJKUAV', 'RUPJGQESXATBKZCYDWFONVIHML', 'DLBXTPWSAFGKINCQREVHJMYZOU']
SLOWLY_DESPARATLY_KNOWLY_THE_REMAINS_OF_PASSAVE_SEZRIS_THAT_ENCUMBERED_THE_LOWER_CART_OF_
THE_DOORWAY_WAS_REMOVED_WITH_TREMBLING_HANKS_I_MADE_A_TINY_GREACH_IN_THE_UPPED_LEFT_HAND_
CORNER_AND_THEN_SIDENING_THE_HOLE_A_LITTLE_I_INDERTED_THE_MANDLE_AND_BEERED_IN_THE_HOT_
AID_EDWAYING_PROM_THE_CHAMPER_CAUSED_THE_BLACE_TO_FUICKED_BUT_PRESENTLY_BETAIRS_OF_THE_
ROOM_WITHIN_EMERRED_FROM_THE_DISH_M_CAN_YOU_SEE_ANYTHING_P
We recognize the text of the Kryptos K3 cryptogram:
SLOWLY, DESPARATLY SLOWLY, THE REMAINS OF PASSAGE DEBRIS THAT ENCUMBERED THE LOWER PART OF THE DOORWAY WAS REMOVED. WITH TREMBLING HANDS I MADE A TINY BREACH IN THE UPPER LEFT-HAND CORNER. AND THEN, WIDENING THE HOLE A LITTLE, I INSERTED THE CANDLE AND PEERED IN. THE HOT AIR ESCAPING FROM THE CHAMBER CAUSED THE FLAME TO FLICKER, BUT PRESENTLY DETAILS OF THE ROOM WITHIN EMERGED FROM THE MIST. X CAN YOU SEE ANYTHING?
Verification¶
Since we are in the Kryptos universe, we can assume that the author of the cryptogram used the table given in the sculpture.
K1 and K2 are encrypted with a quagmire3.
We can assume that the crypto is encrypted with the same quagmire, but with the keyword SECRETKEY and followed by a simple substitution to obtain odd symbols.
def E_Quagmire3(plain, alpha, key):
""" Quagmire 3 Encryption function
"""
numkey = [alpha.find(c) for c in key]
i = 0
crypto = ''
for c in plain:
if c in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
idx = alpha.find(c)
crypto += alpha[(idx+numkey[i])%26]
i = (i+1)%len(key)
else:
crypto += c
return crypto
def D_Quagmire3(crypto, alpha, key):
""" Quagmire 3 Decryption function
"""
numkey = [alpha.find(c) for c in key]
i = 0
plain = ''
for c in crypto:
if c in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
idx = alpha.find(c)
plain += alpha[(idx-numkey[i])%26]
i = (i+1)%len(key)
else:
plain += c
return plain
The putative plain text is
txt = 'SLOWLY DESPARATLY SLOWLY THE REMAINS OF PASSAGE DEBRIS THAT ENCUMBERED THE LOWER PART OF THE DOORWAY WAS REMOVED \
WITH TREMBLING HANDS I MADE A TINY BREACH IN THE UPPER LEFT HAND CORNER AND THEN WIDENING THE HOLE A LITTLE I INSERTED \
THE CANDLE AND PEERED IN THE HOT AIR ESCAPING FROM THE CHAMBER CAUSED THE FLAME TO FLICKER BUT PRESENTLY DETAILS OF THE \
ROOM WITHIN EMERGED FROM THE MIST X CAN YOU SEE ANYTHING'.replace(' ', '_')
print(txt)
SLOWLY_DESPARATLY_SLOWLY_THE_REMAINS_OF_PASSAGE_DEBRIS_THAT_ENCUMBERED_THE_LOWER_PART_OF_THE_DOORWAY_WAS_REMOVED_WITH_TREMBLING_HANDS_I_MADE_A_TINY_BREACH_IN_THE_UPPER_LEFT_HAND_CORNER_AND_THEN_WIDENING_THE_HOLE_A_LITTLE_I_INSERTED_THE_CANDLE_AND_PEERED_IN_THE_HOT_AIR_ESCAPING_FROM_THE_CHAMBER_CAUSED_THE_FLAME_TO_FLICKER_BUT_PRESENTLY_DETAILS_OF_THE_ROOM_WITHIN_EMERGED_FROM_THE_MIST_X_CAN_YOU_SEE_ANYTHING
If we encrypt this text with the key SECRETKEY we should obtain a crypto isomorphic to the original crypto
kk = E_Quagmire3(txt, 'KRYPTOSABCDEFGHIJLMNQUVWXZ', 'SECRETKEY')
print(kk)
FYHXYS_DVBCMDBIUY_LNEBKP_IME_FGXMXQL_CF_HCFLJHV_HENPUL_GIMB_ETERPLFFID_IJL_YHXVO_PMPD_JU_OZI_DJAABJP_BES_FGXJOFU_RIIJ_DFQNNUITI_QMYEL_N_MMFL_M_GJTS_BFGGQW_JT_BHV_WCHQY_YIFI_JGTN_DJONVP_GTN_OZIN_BLJVYJTL_TZG_QJKF_M_UIISWV_X_JTDEFSLU_GIV_GATFWV_JQU_AEVPLU_XQ_IME_ZAD_MXY_VDCMOUTV_GFCM_IJL_QWBPFEF_EGSIFU_BHV_HWMRF_IC_FYLIEQY_NZT_HPLLQQIUY_UGDMXML_CF_IJL_FHSP_RIIJUT_QNVOGVF_MFHN_IME_PLFI_A_DMW_YJW_FVQ_BTSTZLZX
Let's test if there is a simple substitution between k0 and kk:
subs = {}
for i in range(len(kk)):
if k0[i] in subs:
if subs[k0[i]] != kk[i]:
print('error', i, subs[k0[i]], kk[i])
continue
subs[k0[i]] = kk[i]
for c in subs:
print(c, '-->', subs[c])
Y --> F N --> Y × --> H # --> X S --> S _ --> _ ⴽ --> D Δ --> V U --> B V --> C ꓭ --> M + --> I Ξ --> U ꓥ --> L ꓷ --> N X --> E A --> K O --> P Z --> G ⊕ --> Q ꓘ --> J P --> T M --> R I --> O ⵁ --> Z T --> A ⌖ --> W
No error, it's OK. We have the substitution!
original = 'YN×#NS ⴽΔUVꓭⴽU+ΞN ꓥꓷXUAO +ꓭX YZ#ꓭ#⊕ꓥ VY ×VYꓥꓘ×Δ ×XꓷOΞꓥ Z+ꓭU XPXMOꓥYY+ⴽ +ꓘꓥ N×#ΔI OꓭOⴽ ꓘΞ Iⵁ+ \
ⴽꓘTTUꓘO UXS YZ#ꓘIYΞ M++ꓘ ⴽY⊕ꓷꓷΞ+P+ ⊕ꓭNXꓥ ꓷ ꓭꓭYꓥ ꓭ ZꓘPS UYZZ⊕⌖ ꓘP U×Δ ⌖V×⊕N N+Y+ ꓘZPꓷ ⴽꓘIꓷΔO ZPꓷ Iⵁ+ꓷ \
UꓥꓘΔNꓘPꓥ PⵁZ ⊕ꓘAY ꓭ Ξ++S⌖Δ # ꓘPⴽXYSꓥΞ Z+Δ ZTPY⌖Δ ꓘ⊕Ξ TXΔOꓥΞ #⊕ +ꓭX ⵁTⴽ ꓭ#N ΔⴽVꓭIΞPΔ ZYVꓭ +ꓘꓥ ⊕⌖UOYXY \
XZS+YΞ U×Δ ×⌖ꓭMY +V YNꓥ+X⊕N ꓷⵁP ×Oꓥꓥ⊕⊕+ΞN ΞZⴽꓭ#ꓭꓥ VY +ꓘꓥ Y×SO M++ꓘΞP ⊕ꓷΔIZΔY ꓭY×ꓷ +ꓭX OꓥY+ T ⴽꓭ⌖ Nꓘ⌖ \
YΔ⊕ UPSPⵁꓥⵁ# O ?'
table = str.maketrans(subs)
D_Quagmire3(original.translate(table), 'KRYPTOSABCDEFGHIJLMNQUVWXZ', 'SECRETKEY')
'SLOWLY DESPARATLY SLOWLY THE REMAINS OF PASSAGE DEBRIS THAT ENCUMBERED THE LOWER PART OF THE DOORWAY WAS REMOVED WITH TREMBLING HANDS I MADE A TINY BREACH IN THE UPPER LEFT HAND CORNER AND THEN WIDENING THE HOLE A LITTLE I INSERTED THE CANDLE AND PEERED IN THE HOT AIR ESCAPING FROM THE CHAMBER CAUSED THE FLAME TO FLICKER BUT PRESENTLY DETAILS OF THE ROOM WITHIN EMERGED FROM THE MIST X CAN YOU SEE ANYTHING Q ?'
I don't know what this Q does at the end! (Question mark ?)
Le 6/6/2025 - Contact : Rossignol@bribes.org