CoCalc -- 4220.sagews

All published worksheets from http://sagenb.org

Project: sagenb.org published worksheets

Views: ¹⁶⁸⁷³³
Image: ubuntu2004

This is our ciphertexts

ct = "KCCPKBGUFDPHQTYAVINRRTMVGRKDNBVFDETDGILTXRGUDDKOTFMBPVGEGLTGCKQRACQCWDNAWCRXIZAKFTLEWRPTYCQKYVXCHKFTPONCQQRHJVAJUWETMCMSPKQDYHJVDAHCTRLSVSKCGCZQQDZXGSFRLSWCWSJTBHAFSIASPRJAHKJRJUMVGKMITZHFPDISPZLVLGWTFPLKKEBDPGCEBSHCTJRWXBAFSPEZQNRWXCVYCGAONWDDKACKAWBBIKFTIOVKCGGHJVLNHIFFSQESVYCLACNVRWBBIREPBBVFEXOSCDYGZWPFDTKFQIYCWHJVLNHIQIBTKHJVNPIST"

We know that it is a Vigenere cipher.

sage: AS = AlphabeticStrings()
sage: VS6 = VigenereCryptosystem(AS, 6)
sage: cipher = AS.encoding(ct)

We define a trigram counter

def trigram_count(str):
    digrams = {}
    for i in range(len(str)):
        digram = str[i:i+3]
        if digram in digrams:
            count = digrams[digram]
            digrams[digram] = count + 1
        else:
            digrams[digram] = 1
            
    return(digrams)

counte trigram here:

trigram_count(ct)

{'KQR': 1, 'CPK': 1, 'JVA': 1, 'JAH': 1, 'DYG': 1, 'NHI': 2, 'TFP': 1, 'VFD': 1, 'CCP': 1, 'WDN': 1, 'ZQQ': 1, 'LKK': 1, 'VYC': 2, 'SIA': 1, 'TIO': 1, 'CKQ': 1, 'BGU': 1, 'EGL': 1, 'DKO': 1, 'XBA': 1, 'CQQ': 1, 'GHJ': 1, 'PON': 1, 'SPZ': 1, 'RAC': 1, 'AON': 1, 'SPR': 1, 'PRJ': 1, 'HKJ': 1, 'PZL': 1, 'KHJ': 1, 'SPK': 1, 'QIY': 1, 'WTF': 1, 'HFP': 1, 'TZH': 1, 'PIS': 1, 'AWC': 1, 'KYV': 1, 'RXI': 1, 'SFR': 1, 'IRE': 1, 'ZXG': 1, 'QQD': 1, 'CQC': 1, 'CHK': 1, 'YVX': 1, 'VXC': 1, 'LNH': 2, 'WRP': 1, 'WET': 1, 'XIZ': 1, 'GIL': 1, 'SVS': 1, 'IAS': 1, 'JVD': 1, 'KAC': 1, 'AHC': 1, 'HJV': 5, 'NPI': 1, 'ZAK': 1, 'FSQ': 1, 'OSC': 1, 'AHK': 1, 'VIN': 1, 'ACQ': 1, 'PBB': 1, 'TYC': 1, 'FFS': 1, 'RHJ': 1, 'KAW': 1, 'BVF': 2, 'PEZ': 1, 'QQR': 1, 'OVK': 1, 'PHQ': 1, 'SQE': 1, 'NAW': 1, 'DTK': 1, 'FDE': 1, 'RGU': 1, 'RWB': 1, 'GUD': 1, 'TDG': 1, 'CRX': 1, 'KQD': 1, 'DET': 1, 'TYA': 1, 'VDA': 1, 'FDP': 1, 'IFF': 1, 'ZLV': 1, 'FDT': 1, 'SKC': 1, 'DZX': 1, 'ZWP': 1, 'LAC': 1, 'CMS': 1, 'XOS': 1, 'TKF': 1, 'PKQ': 1, 'ESV': 1, 'CEB': 1, 'ZQN': 1, 'VLN': 2, 'RTM': 1, 'BIK': 1, 'SVY': 1, 'KBG': 1, 'VLG': 1, 'JUM': 1, 'PKB': 1, 'LSW': 1, 'GEG': 1, 'JUW': 1, 'PTY': 1, 'REP': 1, 'ETM': 1, 'T': 1, 'XRG': 1, 'EPB': 1, 'FTP': 1, 'GCE': 1, 'TRL': 1, 'HCT': 2, 'VGK': 1, 'VGE': 1, 'GCK': 1, 'YCW': 1, 'DDK': 2, 'SHC': 1, 'GKM': 1, 'BDP': 1, 'YCL': 1, 'FTI': 1, 'EWR': 1, 'GCZ': 1, 'YCG': 1, 'FTL': 1, 'VGR': 1, 'JTB': 1, 'KCG': 2, 'NVR': 1, 'KCC': 1, 'CWH': 1, 'SCD': 1, 'YAV': 1, 'CZQ': 1, 'NRW': 1, 'INR': 1, 'CDY': 1, 'TBH': 1, 'VAJ': 1, 'XCV': 1, 'AVI': 1, 'IOV': 1, 'KKE': 1, 'GZW': 1, 'MIT': 1, 'UWE': 1, 'YHJ': 1, 'UMV': 1, 'TMV': 1, 'ACK': 1, 'FSI': 1, 'BIR': 1, 'ISP': 1, 'ACN': 1, 'KMI': 1, 'IST': 1, 'FSP': 1, 'GWT': 1, 'ILT': 1, 'TMC': 1, 'WHJ': 1, 'ETD': 1, 'QIB': 1, 'GLT': 1, 'AKF': 1, 'CTJ': 1, 'GUF': 1, 'VNP': 1, 'KDN': 1, 'ASP': 1, 'VRW': 1, 'CGA': 1, 'CGC': 1, 'DGI': 1, 'TKH': 1, 'NBV': 1, 'CGG': 1, 'QTY': 1, 'QES': 1, 'BSH': 1, 'IKF': 1, 'PVG': 1, 'GSF': 1, 'ONW': 1, 'WPF': 1, 'RRT': 1, 'GGH': 1, 'AFS': 2, 'PDI': 1, 'EBD': 1, 'DNA': 1, 'BBI': 2, 'DNB': 1, 'DKA': 1, 'LTX': 1, 'RJU': 1, 'SJT': 1, 'FRL': 1, 'KJR': 1, 'LTG': 1, 'TLE': 1, 'MVG': 2, 'BBV': 1, 'FMB': 1, 'FEX': 1, 'BAF': 1, 'QNR': 1, 'KEB': 1, 'HKF': 1, 'UFD': 1, 'JRJ': 1, 'JVN': 1, 'SPE': 1, 'JRW': 1, 'ITZ': 1, 'NWD': 1, 'LEW': 1, 'IQI': 1, 'PLK': 1, 'XCH': 1, 'RLS': 2, 'CQK': 1, 'VFE': 1, 'FQI': 1, 'QCW': 1, 'IYC': 1, 'CVY': 1, 'SWC': 1, 'WSJ': 1, 'HQT': 1, 'MSP': 1, 'DPG': 1, 'GAO': 1, 'WBB': 2, 'BPV': 1, 'ZHF': 1, 'KOT': 1, 'CKA': 1, 'DPH': 1, 'QRA': 1, 'KFT': 3, 'RPT': 1, 'KFQ': 1, 'YCQ': 1, 'ONC': 1, 'JVL': 2, 'LSV': 1, 'DAH': 1, 'WDD': 1, 'RKD': 1, 'TGC': 1, 'QKY': 1, 'TJR': 1, 'DYH': 1, 'HIF': 1, 'DIS': 1, 'MBP': 1, 'TXR': 1, 'FPD': 1, 'CNV': 1, 'IZA': 1, 'CTR': 1, 'WCR': 1, 'RJA': 1, 'WCW': 1, 'HIQ': 1, 'TPO': 1, 'FPL': 1, 'CWS': 1, 'AJU': 1, 'CLA': 1, 'RWX': 2, 'HAF': 1, 'WXB': 1, 'WXC': 1, 'LVL': 1, 'IBT': 1, 'VKC': 1, 'CWD': 1, 'PGC': 1, 'TFM': 1, 'MCM': 1, 'PFD': 1, 'BHA': 1, 'NCQ': 1, 'YGZ': 1, 'ST': 1, 'EZQ': 1, 'OTF': 1, 'LGW': 1, 'QRH': 1, 'GRK': 1, 'AWB': 1, 'EXO': 1, 'BTK': 1, 'UDD': 1, 'EBS': 1, 'NRR': 1, 'VSK': 1, 'QDZ': 1, 'XGS': 1, 'QDY': 1}

note that 3 "KFT" appear

for k in range(len(cipher)):
    if cipher[k:k+3]==AS.encoding("KFT"):
        print k

79
97
253

Find the gcd

gcd(97-79,253-97)

6

It is possible that the key length is 6. Now, find more evidence:

for m in range(2,7):
    y = ['','','','','','','','','','']
    for i in range(len(ct)):
        y[i % m] = y[i % m] + ct[i]
    # ^Concatenate i-th letter of ciphertext to its row.
    for k in range(m):
        ylen = len(y[k])
        Y = AS.encoding(y[k])
        cck = Y.character_count()
        Ic = float(0)
        for i in cck.keys():
            Ic += float(cck[i]*(cck[i]-1))
        Ic = Ic / float(ylen*(ylen-1))
        print k, Ic

0.0384615384615
0.047120045623
0.0559418457649
0.0481016731017
0.0482625482625
0.0372549019608
0.0427423981641
0.0375788869765
0.0490533562823
0.0425812115891
0.0430201931519
0.0325644504749
0.0352781546811
0.0429669832655
0.062656641604
0.0837662337662
0.0493506493506
0.0649350649351
0.0428571428571
0.0733766233766

So, key is very likely to be 6. P is the probability vector of the Beker-Piper distribution for English text.

p=[0.082, 0.015, 0.028, 0.043, 0.127, 0.022, 0.02, 0.061, 0.07, 0.002, 0.008, 0.040, 0.024, 0.067, 0.075, 0.019, 0.001, 0.06, 0.063, 0.091,0.028, 0.01, 0.023, 0.001, 0.02, 0.001]

Now, we try to find the key:

for k in range(6):
    cck = AS.encoding(y[k]).character_count()
    M = {}
    for g in range(26):
        M[g] = 0.0
        for i in range(26):
            chari = AS.encoding(chr(65+((i+g)%26)))
            if chari in cck:
                M[g] += p[i]*float(cck[chari])
                
        M[g] = (M[g]/float(len(y[k]))).n(prec=3)
    print k
    print M

0
{0: 0.031, 1: 0.039, 2: 0.062, 3: 0.039, 4: 0.031, 5: 0.039, 6: 0.039, 7: 0.031, 8: 0.039, 9: 0.047, 10: 0.023, 11: 0.031, 12: 0.039, 13: 0.039, 14: 0.039, 15: 0.047, 16: 0.039, 17: 0.039, 18: 0.039, 19: 0.031, 20: 0.031, 21: 0.039, 22: 0.047, 23: 0.031, 24: 0.039, 25: 0.031}
1
{0: 0.039, 1: 0.039, 2: 0.047, 3: 0.039, 4: 0.039, 5: 0.039, 6: 0.047, 7: 0.031, 8: 0.027, 9: 0.039, 10: 0.047, 11: 0.031, 12: 0.031, 13: 0.047, 14: 0.039, 15: 0.031, 16: 0.039, 17: 0.078, 18: 0.039, 19: 0.031, 20: 0.027, 21: 0.039, 22: 0.031, 23: 0.039, 24: 0.047, 25: 0.039}
2
{0: 0.031, 1: 0.039, 2: 0.031, 3: 0.039, 4: 0.039, 5: 0.039, 6: 0.027, 7: 0.039, 8: 0.031, 9: 0.039, 10: 0.039, 11: 0.047, 12: 0.039, 13: 0.039, 14: 0.039, 15: 0.031, 16: 0.031, 17: 0.039, 18: 0.039, 19: 0.031, 20: 0.039, 21: 0.031, 22: 0.031, 23: 0.047, 24: 0.062, 25: 0.047}
3
{0: 0.047, 1: 0.039, 2: 0.047, 3: 0.039, 4: 0.039, 5: 0.039, 6: 0.031, 7: 0.031, 8: 0.039, 9: 0.039, 10: 0.039, 11: 0.055, 12: 0.039, 13: 0.031, 14: 0.031, 15: 0.062, 16: 0.039, 17: 0.031, 18: 0.039, 19: 0.039, 20: 0.023, 21: 0.031, 22: 0.039, 23: 0.031, 24: 0.031, 25: 0.047}
4
{0: 0.039, 1: 0.031, 2: 0.031, 3: 0.039, 4: 0.047, 5: 0.031, 6: 0.047, 7: 0.047, 8: 0.047, 9: 0.031, 10: 0.031, 11: 0.039, 12: 0.031, 13: 0.031, 14: 0.031, 15: 0.047, 16: 0.031, 17: 0.039, 18: 0.031, 19: 0.055, 20: 0.039, 21: 0.039, 22: 0.047, 23: 0.047, 24: 0.031, 25: 0.031}
5
{0: 0.039, 1: 0.039, 2: 0.039, 3: 0.039, 4: 0.039, 5: 0.027, 6: 0.031, 7: 0.039, 8: 0.039, 9: 0.031, 10: 0.047, 11: 0.031, 12: 0.023, 13: 0.039, 14: 0.078, 15: 0.039, 16: 0.031, 17: 0.031, 18: 0.039, 19: 0.031, 20: 0.039, 21: 0.039, 22: 0.039, 23: 0.039, 24: 0.039, 25: 0.047}

Note that 2,17,24,15,19,14 are sepical, we get our key:

sage: K = AS.encoding(chr(65+2) + chr(65+17) + chr(65+24)+chr(65+15)+chr(65+19)+chr(65+14)); K

CRYPTO

Plian text is:

key = AS('CRYPTO')
plaintext = VS6.deciphering(key, cipher);
plaintext

ILEARNEDHOWTOCALCULATETHEAMOUNTOFPAPERNEEDEDFORAROOMWHENIWASATSCHOOLYOUMULTIPLYTHESQUAREFOOTAGEOFTHEWALLSBYTHECUBICCONTENTSOFTHEFLOORANDCEILINGCOMBINEDANDDOUBLEITYOUTHENALLOWHALFTHETOTALFOROPENINGSSUCHASWINDOWSANDDOORSTHENYOUALLOWTHEOTHERHALFFORMATCHINGTHEPATTERNTHENYOUDOUBLETHEWHOLETHINGAGAINTOGIVEAMARGINOFERRORANDTHENYOUORDERTHEPAPER