0%

密码学课程设计之古典密码

发表于 更新于 分类于
本文字数： 23k 阅读时长 ≈ 21 分钟

密码学课程设计之古典密码

弱鸡的代码，看看就好。

仿射密码

仿射密码为单表加密的一种，字母系统中所有字母都藉一简单数学方程加密，对应至数值，或转回字母。

输入内容

输入的内容可能包含大写，小写和特殊字符，此时可以分别进行加解密，通过调用python的isupper(),islower()函数来判断。

大写字母加密/解密后的结果仍是大写字母，小写字母加密/解密后的结果仍是小写字母 。特殊字符不做处理，直接照搬。

加密算法

$$
c_i=(k_1⋅m_i+k_2)mod26
$$

前提条件：
$$
gcd(k_1,26)=1
$$
假如不满足该条件，则不同的密文字符可以对应多个明文字符。

所以我们首先需要写一个求两个数最大公因数的函数，此处用辗转相除法。

1
2
3
4
5
#辗转相除法
def gcd(a,b):
    if a%b==0:
        return b
    return gcd(b,a%b)

判断条件可以写在主函数中，到时候直接在完整代码里看叭。

如果满足不满足条件，就请求重新执行该程序。

加密函数如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#加密函数
def encrypt(plaintext,key1,key2):
    key2%=26
    #根据加密公式ci=(k1⋅mi+k2)mod26开始加密
    l=len(plaintext)
    ans=""
    for i in range(l):
        #小写字母加密
        if plaintext[i].islower():
            x=ord(plaintext[i])-ord('a')
            ans+=chr((key1*x+key2)%26+ord('a'))
        #大写字母加密
        elif plaintext[i].isupper():
            x=ord(plaintext[i])-ord('A')
            ans+=chr((key1*x+key2)%26+ord('A'))
        #其余字符
        else:
            ans+=plaintext[i]
    return ans

解密算法

$$
m_i=k_1^{−1}⋅(c_i−k_2)mod26
$$

同样需要先判断k1是否与26互素。

与加密的步骤不同的是这里多了一个求逆的过程。

此处使用扩展欧几里得算法。

附代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#求a关于m的逆元
def findReverse(a,m):
    if gcd(a,m)!=1:
        return 
    r1,r2=a,m
    s1,s2=1,0
    t1,t2=0,1
    while(r2 > 0):
        q=r1//r2
        r= r1-q*r2
        r1=r2
        r2=r
        s=s1-q*s2
        s1=s2
        s2=s
        t=t1-q*t2
        t1=t2
        t2=t
    return s1%m

那么，解密函数如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#解密函数
def decrypt(ciphertext,key1,key2):
    key2%=26
    #根据解密公式mi=k1的逆⋅(ci−k2)mod26开始解密
    key1=findReverse(key1,26)
    l=len(ciphertext)
    ans=""
    for i in range(l):
        #小写字母解密
        if ciphertext[i].islower():
            y=ord(ciphertext[i])-ord('a')+26-key2
            ans+=chr((key1*y)%26+ord('a'))
        #大写字母解密
        elif ciphertext[i].isupper():
            y=ord(ciphertext[i])-ord('A')+26-key2
            ans+=chr((key1*y)%26+ord('A'))
        #其余字符
        else:
            ans+=ciphertext[i]
    return ans

仿射密码加密解密完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#辗转相除法
def gcd(a,b):
    if a%b==0:
        return b
    return gcd(b,a%b)

#求a关于m的逆元
def findReverse(a,m):
    if gcd(a,m)!=1:
        return 
    r1,r2=a,m
    s1,s2=1,0
    t1,t2=0,1
    while(r2 > 0):
        q=r1//r2
        r= r1-q*r2
        r1=r2
        r2=r
        s=s1-q*s2
        s1=s2
        s2=s
        t=t1-q*t2
        t1=t2
        t2=t
    return s1%m

#加密函数
def encrypt(plaintext,key1,key2):
    key2%=26
    #根据加密公式ci=(k1⋅mi+k2)mod26开始加密
    l=len(plaintext)
    ans=""
    for i in range(l):
        #小写字母加密
        if plaintext[i].islower():
            x=ord(plaintext[i])-ord('a')
            ans+=chr((key1*x+key2)%26+ord('a'))
        #大写字母加密
        elif plaintext[i].isupper():
            x=ord(plaintext[i])-ord('A')
            ans+=chr((key1*x+key2)%26+ord('A'))
        #其余字符
        else:
            ans+=plaintext[i]
    return ans

#解密函数
def decrypt(ciphertext,key1,key2):
    key2%=26
    #根据解密公式mi=k1的逆⋅(ci−k2)mod26开始解密
    key1=findReverse(key1,26)
    l=len(ciphertext)
    ans=""
    for i in range(l):
        #小写字母解密
        if ciphertext[i].islower():
            y=ord(ciphertext[i])-ord('a')+26-key2
            ans+=chr((key1*y)%26+ord('a'))
        #大写字母解密
        elif ciphertext[i].isupper():
            y=ord(ciphertext[i])-ord('A')+26-key2
            ans+=chr((key1*y)%26+ord('A'))
        #其余字符
        else:
            ans+=ciphertext[i]
    return ans
    
def main():
    print("1.加密")
    print("2.解密")
    mode=input()
    if mode=='1':
        print("请输入你要加密的明文")
        plaintext=input()
        print("请输入你选择加密的密钥key1")
        Key1=input()
        key1=int(Key1)
        print("请输入你选择加密的密钥key2")
        Key2=input()
        key2=int(Key2)
        if gcd(key1,26)!=1:
            print("您输入的密钥key1与26不互素，无法完成加密，请重新开始")
            return main()
        else:
            ans=encrypt(plaintext,key1,key2)
            print(ans)
    if mode=='2':
        print("请输入你要解密的密文")
        plaintext=input()
        print("请输入你选择解密的密钥key1")
        Key1=input()
        key1=int(Key1)
        print("请输入你选择解密的密钥key2")
        Key2=input()
        key2=int(Key2)
        if gcd(key1,26)!=1:
            print("您输入的密钥key1与26不互素，无法完成加密，请重新开始")
            return main()
        else:
            ans=decrypt(plaintext,key1,key2)
            print(ans)

if __name__ == '__main__':
    main()

枚举法破解

暴力破解直接附代码叭

1
2
3
4
5
6
7
def EnumerationMethod(cipher):
    for key1 in range(26):
        if gcd(key1,26)==1:
            for key2 in range(26):
                print("key1="+str(key1).zfill(2)+\
                    ", key2="+str(key2).zfill(2)+\
                    ": "+decrypt(cipher,key1,key2))

统计分析法破解

最好截取的密文长度足够长，同时已知的自然语言字符统计规律。

img

由图已知使用频率最高的字母为e，那么我们就可以先找出密文当中出现次数最多的那个字母。

1
2
3
4
5
6
7
8
9
#字典方式找出现次数最多的字母
def FindMostLetter(s):
	count ={}
	for i in set(s.replace(" ", "")):#repalce除去空格最多的情况
		count[i]=s.count(i)
		max_value=max(count.values())
	for k,v in count.items():
		if v==max_value:
			return k

用字典方法有一个缺陷就是可能输入的密文带空格，最后可能找到的是空格，所以用replace()函数把空格删去，再进行统计。

然后用两个循环找key1和key2满足出现次数最多的那个字母对应明文为e的情况。

1
2
3
4
5
6
7
8
9
10
11
#统计分析法
def StatisticalAnalysisMethod(cipher):
    l=len(cipher)
    cipher1=cipher.lower()#为了方便，将所有英文字母转成为小写
    for key1 in range(26):
        if gcd(key1,26)==1:
            for key2 in range(26):
                if chr((4*key1+key2)%26+ord('a')) == FindMostLetter(cipher1):
                    print("key1="+str(key1).zfill(2)+\
                    ", key2="+str(key2).zfill(2)+\
                    ": "+decrypt(cipher,key1,key2))

最后可以在运行结果中找到合乎语法的正确明文。

仿射密码暴力与分析解密完整代码

由于截获的密文可能比较长，所以这里使用了文件输入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
def gcd(a,b):
    if a%b==0:
        return b
    return gcd(b,a%b)

def findReverse(a,m):
    if gcd(a,m)!=1:
        return 
    r1,r2=a,m
    s1,s2=1,0
    t1,t2=0,1
    while(r2 > 0):
        q=r1//r2
        r= r1-q*r2
        r1=r2
        r2=r
        s=s1-q*s2
        s1=s2
        s2=s
        t=t1-q*t2
        t1=t2
        t2=t
    return s1%m

def decrypt(ciphertext,key1,key2):
    key2%=26
    key1=findReverse(key1,26)
    l=len(ciphertext)
    ans=""
    for i in range(l):
        if ciphertext[i].islower():
            y=ord(ciphertext[i])-ord('a')+26-key2
            ans+=chr((key1*y)%26+ord('a'))
        elif ciphertext[i].isupper():
            y=ord(ciphertext[i])-ord('A')+26-key2
            ans+=chr((key1*y)%26+ord('A'))
        else:
            ans+=ciphertext[i]
    return ans

#枚举法
def EnumerationMethod(cipher):
    for key1 in range(26):
        if gcd(key1,26)==1:
            for key2 in range(26):
                print("key1="+str(key1).zfill(2)+\
                    ", key2="+str(key2).zfill(2)+\
                    ": "+decrypt(cipher,key1,key2))

#字典方式找出现次数最多的字母
def FindMostLetter(s):
	count ={}
	for i in set(s.replace(" ", "")):#repalce除去空格最多的情况
		count[i]=s.count(i)
		max_value=max(count.values())
	for k,v in count.items():
		if v==max_value:
			return k

#统计分析法
def StatisticalAnalysisMethod(cipher):
    l=len(cipher)
    cipher1=cipher.lower()#为了方便，将所有英文字母转成为小写
    for key1 in range(26):
        if gcd(key1,26)==1:
            for key2 in range(26):
                if chr((4*key1+key2)%26+ord('a')) == FindMostLetter(cipher1):
                    print("key1="+str(key1).zfill(2)+\
                    ", key2="+str(key2).zfill(2)+\
                    ": "+decrypt(cipher,key1,key2))

def main():
    print("1.枚举破解")
    print("2.统计分析破解")
    mode=input()
    if mode=='1':
        try:
            f=open('E:\Cryptology\Affine\Affine.txt','r',encoding = 'utf-8')
            cipher=f.read()
            f.close()
            print("文件读取成功！")
            EnumerationMethod(cipher)
        except IOError:
            print('文件读取失败！！！')
    if mode=='2':
        try:
            f=open('E:\Cryptology\Affine\Affine.txt','r',encoding = 'utf-8')
            cipher=f.read()
            f.close()
            print("文件读取成功！")
            StatisticalAnalysisMethod(cipher)
        except IOError:
            print('文件读取失败！！！')

if __name__ == '__main__':
    main()

测试样例

1
Orfka, vmo fxr, fer tveoh tdkavnk f prfsdsx, kafk yfhh iz nh mdjr kar domr fde tadla tr erxfeo svk. Vkareh pfz afqr nsorexvsr, ve pfz hkdmm ir mdfimr kv karp--tr “irfe f lafepro mdur”, tadla mfnxah kvhlves fmm hnla hdljmz ufsldrh. Fh ds hrkkdsx vnk vs ormdxakunm gvnesrz, tr hkefds vne rfxre xfcr uvetfeo.

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#枚举法（这里只列了key1=3，key2=0-25的情况，因为正确明文在这里面）
key1=03, key2=00: Wxtma, hew tzx, tkx phkwl pbmahnm t fxtgbgz, matm itll ur nl ebdx max bwex tbk pabva px kxztkw ghm. Hmaxkl ftr atox ngwxkzhgx, hk ftr lmbee ux ebtuex mh maxf--px “uxtk t vatkfxw ebyx”, pabva etnzal mhlvhkg tee lnva lbvder ytgvbxl. Tl bg lxmmbgz hnm hg wxebzamyne chnkgxr, px lmktbg hnk xtzxk ztsx yhkptkw.
key1=03, key2=01: Nokdr, yvn kqo, kbo gybnc gsdryed k wokxsxq, drkd zkcc li ec vsuo dro snvo ksb grsmr go boqkbn xyd. Ydrobc wki rkfo exnobqyxo, yb wki cdsvv lo vsklvo dy drow--go “lokb k mrkbwon vspo”, grsmr vkeqrc dycmybx kvv cemr csmuvi pkxmsoc. Kc sx coddsxq yed yx novsqrdpev tyebxoi, go cdbksx yeb okqob qkjo pybgkbn.
key1=03, key2=02: Efbui, pme bhf, bsf xpset xjuipvu b nfbojoh, uibu qbtt cz vt mjlf uif jemf bjs xijdi xf sfhbse opu. Puifst nbz ibwf voefshpof, ps nbz tujmm cf mjbcmf up uifn--xf “cfbs b dibsnfe mjgf”, xijdi mbvhit uptdpso bmm tvdi tjdlmz gbodjft. Bt jo tfuujoh pvu po efmjhiugvm kpvsofz, xf tusbjo pvs fbhfs hbaf gpsxbse.
key1=03, key2=03: Vwslz, gdv syw, sjw ogjvk oalzgml s ewsfafy, lzsl hskk tq mk dacw lzw avdw saj ozauz ow jwysjv fgl. Glzwjk esq zsnw mfvwjygfw, gj esq kladd tw dastdw lg lzwe--ow “twsj s uzsjewv daxw”, ozauz dsmyzk lgkugjf sdd kmuz kaucdq xsfuawk. Sk af kwllafy gml gf vwdayzlxmd bgmjfwq, ow kljsaf gmj wsywj ysrw xgjosjv.
key1=03, key2=04: Mnjcq, xum jpn, jan fxamb frcqxdc j vnjwrwp, cqjc yjbb kh db urtn cqn rmun jra fqrlq fn anpjam wxc. Xcqnab vjh qjen dwmnapxwn, xa vjh bcruu kn urjkun cx cqnv--fn “knja j lqjavnm uron”, fqrlq ujdpqb cxblxaw juu bdlq brltuh ojwlrnb. Jb rw bnccrwp xdc xw mnurpqcodu sxdawnh, fn bcajrw xda njpna pjin oxafjam.
key1=03, key2=05: Death, old age, are words without a meaning, that pass by us like the idle air which we regard not. Others may have undergone, or may still be liable to them--we “bear a charmed life”, which laughs toscorn all such sickly fancies. As in setting out on delightful journey, we strain our eager gaze forward.
key1=03, key2=06: Uvrky, fcu rxv, riv nfiuj nzkyflk r dvrezex, kyrk grjj sp lj czbv kyv zucv rzi nyzty nv ivxriu efk. Fkyvij drp yrmv leuvixfev, fi drp jkzcc sv czrscv kf kyvd--nv “svri r tyridvu czwv”, nyzty crlxyj kfjtfie rcc jlty jztbcp wretzvj. Rj ze jvkkzex flk fe uvczxykwlc aflievp, nv jkirze fli vrxvi xrqv wfinriu.
key1=03, key2=07: Lmibp, wtl iom, izm ewzla eqbpwcb i umivqvo, bpib xiaa jg ca tqsm bpm qltm iqz epqkp em zmoizl vwb. Wbpmza uig pidm cvlmzowvm, wz uig abqtt jm tqijtm bw bpmu--em “jmiz i kpizuml tqnm”, epqkp ticopa bwakwzv itt ackp aqkstg nivkqma. Ia qv ambbqvo wcb wv lmtqopbnct rwczvmg, em abziqv wcz miomz oihm nwzeizl.
key1=03, key2=08: Cdzsg, nkc zfd, zqd vnqcr vhsgnts z ldzmhmf, sgzs ozrr ax tr khjd sgd hckd zhq vghbg vd qdfzqc mns. Nsgdqr lzx gzud tmcdqfnmd, nq lzx rshkk ad khzakd sn sgdl--vd “adzq z bgzqldc khed”, vghbg kztfgr snrbnqm zkk rtbg rhbjkx ezmbhdr. Zr hm rdsshmf nts nm cdkhfgsetk intqmdx, vd rsqzhm ntq dzfdq fzyd enqvzqc.
key1=03, key2=09: Tuqjx, ebt qwu, qhu mehti myjxekj q cuqdydw, jxqj fqii ro ki byau jxu ytbu qyh mxysx mu huwqht dej. Ejxuhi cqo xqlu kdtuhwedu, eh cqo ijybb ru byqrbu je jxuc--mu “ruqh q sxqhcut byvu”, mxysx bqkwxi jeisehd qbb iksx iysabo vqdsyui. Qi yd iujjydw ekj ed tubywxjvkb zekhduo, mu ijhqyd ekh uqwuh wqpu vehmqht.
key1=03, key2=10: Klhao, vsk hnl, hyl dvykz dpaovba h tlhupun, aoha whzz if bz sprl aol pksl hpy dopjo dl ylnhyk uva. Vaolyz thf ohcl buklynvul, vy thf zapss il sphisl av aolt--dl “ilhy h johytlk spml”, dopjo shbnoz avzjvyu hss zbjo zpjrsf mhujplz. Hz pu zlaapun vba vu klspnoambs qvbyulf, dl zayhpu vby lhnly nhgl mvydhyk.
key1=03, key2=11: Bcyrf, mjb yec, ypc umpbq ugrfmsr y kcylgle, rfyr nyqq zw sq jgic rfc gbjc ygp ufgaf uc pceypb lmr. Mrfcpq kyw fytc slbcpemlc, mp kyw qrgjj zc jgyzjc rm rfck--uc “zcyp y afypkcb jgdc”, ufgaf jysefq rmqampl yjj qsaf qgaijw dylagcq. Yq gl qcrrgle msr ml bcjgefrdsj hmsplcw, uc qrpygl msp cyecp eyxc dmpuypb.
key1=03, key2=12: Stpiw, das pvt, pgt ldgsh lxiwdji p btpcxcv, iwpi ephh qn jh axzt iwt xsat pxg lwxrw lt gtvpgs cdi. Diwtgh bpn wpkt jcstgvdct, dg bpn hixaa qt axpqat id iwtb--lt “qtpg p rwpgbts axut”, lwxrw apjvwh idhrdgc paa hjrw hxrzan upcrxth. Ph xc htiixcv dji dc staxvwiuja ydjgctn, lt higpxc djg tpvtg vpot udglpgs.
key1=03, key2=13: Jkgzn, urj gmk, gxk cuxjy coznuaz g skgtotm, zngz vgyy he ay roqk znk ojrk gox cnoin ck xkmgxj tuz. Uznkxy sge ngbk atjkxmutk, ux sge yzorr hk roghrk zu znks--ck “hkgx g ingxskj rolk”, cnoin rgamny zuyiuxt grr yain yoiqre lgtioky. Gy ot ykzzotm uaz ut jkromnzlar puaxtke, ck yzxgot uax kgmkx mgfk luxcgxj.
key1=03, key2=14: Abxqe, lia xdb, xob tloap tfqelrq x jbxkfkd, qexq mxpp yv rp ifhb qeb faib xfo tefze tb obdxoa klq. Lqebop jxv exsb rkabodlkb, lo jxv pqfii yb ifxyib ql qebj--tb “ybxo x zexojba ifcb”, tefze ixrdep qlpzlok xii prze pfzhiv cxkzfbp. Xp fk pbqqfkd lrq lk abifdeqcri glrokbv, tb pqoxfk lro bxdbo dxwb clotxoa.
key1=03, key2=15: Rsohv, czr ous, ofs kcfrg kwhvcih o asobwbu, hvoh dogg pm ig zwys hvs wrzs owf kvwqv ks fsuofr bch. Chvsfg aom vojs ibrsfucbs, cf aom ghwzz ps zwopzs hc hvsa--ks “psof o qvofasr zwts”, kvwqv zoiuvg hcgqcfb ozz giqv gwqyzm tobqwsg. Og wb gshhwbu cih cb rszwuvhtiz xcifbsm, ks ghfowb cif sousf uons tcfkofr.
key1=03, key2=16: Ijfym, tqi flj, fwj btwix bnymtzy f rjfsnsl, ymfy ufxx gd zx qnpj ymj niqj fnw bmnhm bj wjlfwi sty. Tymjwx rfd mfaj zsijwltsj, tw rfd xynqq gj qnfgqj yt ymjr--bj “gjfw f hmfwrji qnkj”, bmnhm qfzlmx ytxhtws fqq xzhm xnhpqd kfshnjx. Fx ns xjyynsl tzy ts ijqnlmykzq otzwsjd, bj xywfns tzw jfljw lfej ktwbfwi.
key1=03, key2=17: Zawpd, khz wca, wna sknzo sepdkqp w iawjejc, pdwp lwoo xu qo hega pda ezha wen sdeyd sa nacwnz jkp. Kpdano iwu dwra qjzanckja, kn iwu opehh xa hewxha pk pdai--sa “xawn w ydwniaz heba”, sdeyd hwqcdo pkoyknj whh oqyd oeyghu bwjyeao. Wo ej oappejc kqp kj zahecdpbqh fkqnjau, sa opnwej kqn awcan cwva bknswnz.
key1=03, key2=18: Qrngu, byq ntr, ner jbeqf jvgubhg n zrnavat, gung cnff ol hf yvxr gur vqyr nve juvpu jr ertneq abg. Bguref znl unir haqretbar, be znl fgvyy or yvnoyr gb gurz--jr “orne n punezrq yvsr”, juvpu ynhtuf gbfpbea nyy fhpu fvpxyl snapvrf. Nf va frggvat bhg ba qryvtugshy wbhearl, jr fgenva bhe rntre tnmr sbejneq.
key1=03, key2=19: Hiexl, sph eki, evi asvhw amxlsyx e qiermrk, xlex teww fc yw pmoi xli mhpi emv almgl ai vikevh rsx. Sxlivw qec lezi yrhivksri, sv qec wxmpp fi pmefpi xs xliq--ai “fiev e glevqih pmji”, almgl peyklw xswgsvr epp wygl wmgopc jergmiw. Ew mr wixxmrk syx sr hipmklxjyp nsyvric, ai wxvemr syv iekiv kedi jsvaevh.
key1=03, key2=20: Yzvoc, jgy vbz, vmz rjmyn rdocjpo v hzvidib, ocvo kvnn wt pn gdfz ocz dygz vdm rcdxc rz mzbvmy ijo. Joczmn hvt cvqz piyzmbjiz, jm hvt nodgg wz gdvwgz oj oczh--rz “wzvm v xcvmhzy gdaz”, rcdxc gvpbcn ojnxjmi vgg npxc ndxfgt avixdzn. Vn di nzoodib jpo ji yzgdbcoapg ejpmizt, rz nomvdi jpm zvbzm bvuz ajmrvmy.
key1=03, key2=21: Pqmft, axp msq, mdq iadpe iuftagf m yqmzuzs, ftmf bmee nk ge xuwq ftq upxq mud ituot iq dqsmdp zaf. Aftqde ymk tmhq gzpqdsazq, ad ymk efuxx nq xumnxq fa ftqy--iq “nqmd m otmdyqp xurq”, ituot xmgste faeoadz mxx egot euowxk rmzouqe. Me uz eqffuzs agf az pqxustfrgx vagdzqk, iq efdmuz agd qmsqd smlq radimdp.
key1=03, key2=22: Ghdwk, rog djh, duh zrugv zlwkrxw d phdqlqj, wkdw sdvv eb xv olnh wkh lgoh dlu zklfk zh uhjdug qrw. Rwkhuv pdb kdyh xqghujrqh, ru pdb vwloo eh oldeoh wr wkhp--zh “ehdu d fkduphg olih”, zklfk odxjkv wrvfruq doo vxfk vlfnob idqflhv. Dv lq vhwwlqj rxw rq gholjkwixo mrxuqhb, zh vwudlq rxu hdjhu jdch iruzdug.
key1=03, key2=23: Xyunb, ifx uay, uly qilxm qcnbion u gyuhcha, nbun jumm vs om fcey nby cxfy ucl qbcwb qy lyaulx hin. Inbylm gus bupy ohxylaihy, il gus mncff vy fcuvfy ni nbyg--qy “vyul u wbulgyx fczy”, qbcwb fuoabm nimwilh uff mowb mcwefs zuhwcym. Um ch mynncha ion ih xyfcabnzof diolhys, qy mnluch iol yuayl auty zilqulx.
key1=03, key2=24: Oples, zwo lrp, lcp hzcod hteszfe l xplytyr, esle aldd mj fd wtvp esp towp ltc hstns hp cprlco yze. Zespcd xlj slgp fyopcrzyp, zc xlj detww mp wtlmwp ez espx--hp “mplc l nslcxpo wtqp”, hstns wlfrsd ezdnzcy lww dfns dtnvwj qlyntpd. Ld ty dpeetyr zfe zy opwtrseqfw uzfcypj, hp declty zfc plrpc rlkp qzchlco.
key1=03, key2=25: Fgcvj, qnf cig, ctg yqtfu ykvjqwv c ogcpkpi, vjcv rcuu da wu nkmg vjg kfng ckt yjkej yg tgictf pqv. Qvjgtu oca jcxg wpfgtiqpg, qt oca uvknn dg nkcdng vq vjgo--yg “dgct c ejctogf nkhg”, yjkej ncwiju vqueqtp cnn uwej ukemna hcpekgu. Cu kp ugvvkpi qwv qp fgnkijvhwn lqwtpga, yg uvtckp qwt gcigt icbg hqtyctf.
1
2
3
4
5
6
7
8
9
10
11
12
13
#统计分析法
key1=01, key2=13: Besxn, izb ske, sre girbu gqxniax s cesfqfk, xnsx lsuu vm au zqwe xne qbze sqr gnqyn ge reksrb fix. Ixneru csm nsde afberkife, ir csm uxqzz ve zqsvze xi xnec--ge “vesr s ynsrceb zqhe”, gnqyn zsaknu xiuyirf szz uayn uqywzm hsfyqeu. Su qf uexxqfk iax if bezqknxhaz tiarfem, ge uxrsqf iar esker kspe hirgsrb.
key1=03, key2=05: Death, old age, are words without a meaning, that pass by us like the idle air which we regard not. Others may have undergone, or may still be liable to them--we “bear a charmed life”, which laughs toscorn all such sickly fancies. As in setting out on delightful journey, we strain our eager gaze forward.
key1=05, key2=23: Temnl, kdt mae, mre ukrtc uwnlkyn m oemzwza, nlmn vmcc xq yc dwse nle wtde mwr ulwil ue reamrt zkn. Knlerc omq lmje yzterakze, kr omq cnwdd xe dwmxde nk nleo--ue “xemr m ilmroet dwpe”, ulwil dmyalc nkcikrz mdd cyil cwisdq pmziwec. Mc wz cennwza kyn kz tedwalnpyd hkyrzeq, ue cnrmwz kyr emaer ambe pkrumrt.
key1=07, key2=15: Legdj, mhl gqe, gre imrlk icdjmwd g aegtctq, djgd fgkk zu wk hcoe dje clhe gcr ijcsj ie reqgrl tmd. Mdjerk agu jgpe wtlerqmte, mr agu kdchh ze hcgzhe dm djea--ie “zegr g sjgrael hcxe”, ijcsj hgwqjk dmksmrt ghh kwsj kcsohu xgtscek. Gk ct keddctq mwd mt lehcqjdxwh vmwrteu, ie kdrgct mwr egqer qgne xmrigrl.
key1=09, key2=07: Veujf, qpv uwe, ure kqrva kojfqsj u yeuhohw, jfuj zuaa dc sa poge jfe ovpe uor kfomf ke rewurv hqj. Qjfera yuc fube shverwqhe, qr yuc ajopp de poudpe jq jfey--ke “deur u mfuryev pone”, kfomf puswfa jqamqrh upp asmf aomgpc nuhmoea. Ua oh aejjohw qsj qh vepowfjnsp xqsrhec, ke ajruoh qsr euwer wule nqrkurv.
key1=11, key2=25: Zekbt, cnz koe, kre qcrzw qybtcgb k sekxyxo, btkb hkww pa gw nyie bte yzne kyr qtyut qe reokrz xcb. Cbterw ska tkle gxzerocxe, cr ska wbynn pe nykpne bc btes--qe “pekr k utkrsez nyje”, qtyut nkgotw bcwucrx knn wgut wyuina jkxuyew. Kw yx webbyxo cgb cx zenyotbjgn dcgrxea, qe wbrkyx cgr ekoer okfe jcrqkrz.
key1=15, key2=09: Jeyhp, gvj yue, yre sgrjm skhpgch y qeylklu, hpyh bymm ti cm vkae hpe kjve ykr spkop se reuyrj lgh. Ghperm qyi pyxe cljerugle, gr qyi mhkvv te vkytve hg hpeq--se “teyr y opyrqej vkze”, spkop vycupm hgmogrl yvv mcop mkoavi zylokem. Ym kl mehhklu gch gl jevkuphzcv fgcrlei, se mhrykl gcr eyuer uyde zgrsyrj.
key1=17, key2=01: Neozd, stn ome, ore ysrni yuzdsqz o keobubm, zdoz joii fg qi tuce zde unte our yduwd ye remorn bsz. Szderi kog dohe qbnermsbe, sr kog izutt fe tuofte zs zdek--ye “feor o wdorken tuve”, yduwd toqmdi zsiwsrb ott iqwd iuwctg vobwuei. Oi ub iezzubm sqz sb netumdzvqt lsqrbeg, ye izroub sqr eomer moxe vsryorn.
key1=19, key2=19: Xecfz, wbx cse, cre awrxy agfzwmf c iecpgps, fzcf dcyy jo my bgue fze gxbe cgr azgqz ae rescrx pwf. Wfzery ico zcte mpxerswpe, wr ico yfgbb je bgcjbe fw fzei--ae “jecr c qzcriex bgle”, azgqz bcmszy fwyqwrp cbb ymqz ygqubo lcpqgey. Cy gp yeffgps wmf wp xebgszflmb nwmrpeo, ae yfrcgp wmr ecser scve lwracrx.
key1=21, key2=11: Pewvx, yfp wie, wre oyrpg omvxykv w uewjmji, vxwv nwgg ls kg fmqe vxe mpfe wmr oxmax oe reiwrp jyv. Yvxerg uws xwze kjperiyje, yr uws gvmff le fmwlfe vy vxeu--oe “lewr w axwruep fmte”, oxmax fwkixg vygayrj wff gkax gmaqfs twjameg. Wg mj gevvmji ykv yj pefmixvtkf bykrjes, oe gvrwmj ykr ewier iwhe tyrowrp.
key1=23, key2=03: Feipb, uxf ice, ire murfq mapbuop i weivavc, pbip tiqq hk oq xaye pbe afxe iar mbagb me recirf vup. Upberq wik bine ovfercuve, ur wik qpaxx he xaihxe pu pbew--me “heir i gbirwef xade”, mbagb xiocbq puqgurv ixx qogb qagyxk divgaeq. Iq av qeppavc uop uv fexacbpdox zuorvek, me qpriav uor eicer cije durmirf.
key1=25, key2=21: Heqlv, ajh qye, qre carho cslvail q geqdsdy, lvql xqoo nw io jsme lve shje qsr cvskv ce reyqrh dal. Alvero gqw vqfe idheryade, ar gqw olsjj ne jsqnje la lveg--ce “neqr q kvqrgeh jsbe”, cvskv jqiyvo laokard qjj oikv oskmjw bqdkseo. Qo sd oellsdy ail ad hejsyvlbij pairdew, ce olrqsd air eqyer yqte barcqrh.

正确解密出的明文为

1
2
key1=03, key2=05
Death, old age, are words without a meaning, that pass by us like the idle air which we regard not. Others may have undergone, or may still be liable to them--we “bear a charmed life”, which laughs toscorn all such sickly fancies. As in setting out on delightful journey, we strain our eager gaze forward.

安全性分析

仿射密码属于单表代换密码，单表代换密码的密钥空间很小，同时它没有将字母出现的统计规律隐藏起来，因此使用统计分析法很快就可以进行破解。从这一点来说，汉语在加密方面的特性要远远优于英语，汉语中常用汉字就有3755个，而英语只有26个英文字母。
仿射密码加密算法为
$$
ye(x){\equiv}ax+b(mod26) 其中要求gcd(a，26)=1
$$
满足条件的a有12个，而b有26个，所以仿射加密的密钥空间大小为12*26=312。对于312种情况，现在的计算机通过暴力枚举的方法求解出正确的明文简直是小菜一碟。如果选择使用统计分析法，破解的速度应该会更快。
但对于普通置换密码和乘法密码相比之下，已经有了很大的改进与提高。

多表代换密码分析

多表代换密码打破了原语言的字符出现规律，故其分析比单表代换密码的分析要复杂得多。

维吉尼亚密码是多表代换密码得经典代表，此处以维吉尼亚密码分析为例。

多表代换密码体制得分析方法主要分为3步

1
2
3
确定密钥长度（常用方法：卡希斯基测试法和重合指数法）；
确定密钥（常用方法：拟重合指数测试法）；
根据第二步确定得密钥恢复出明文，如果条件允许可以验证结论得正确性。

为了方便，我还把密文中的非字母去掉了

1
2
3
4
5
6
def cleanunalpha(cipher):
    CipherAlpha = ''
    for i in range(len(cipher)):
        if (cipher[i].isalpha()):
            CipherAlpha += cipher[i]
    return CipherAlpha

确定密钥长度

现在进行第一步确定密钥长度，这里使用重合指数法

指数重合法利用随即文本和英文文本的统计概率差别来分析密钥长度。

假设某种语言由n个字母组成，每个字母i发生的概率为pi,1≤i≤n , 则重合指数就是指两个随机字母相同的概率：
$$
IC=\sum_{i=1}^{n}{p_i^2}
$$
值得注意的是，在单表代换的情况下， 明文与密文的IC值是相同的。

由于在现实世界中密文的长度有限，一般采用IC的无偏估计值来近似计算IC。
$$
IC′=\sum_{i=1}^{n}{\frac{x_i(x_i−1)}{L(L−1)}}
$$
其中xi表示密文符号i出现的次数，L表示密文长度，n表示某门语言包含的字母数，如该语言是英文字母，则n=26。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def length(cipher):
    CipherList = list(cipher)#密文转换为列表
    Keylength = 1

    while True:
        # 指数初始化为０
        CoincidenceIndex = 0

        # 使用切片分组
        for i in range(Keylength):
            Numerator = 0
            PresentCipherList = CipherList[i::Keylength]#分组

            # 使用集合去重，计算每一子密文组的拟重合指数
            for Letter in set(PresentCipherList):
                Numerator += PresentCipherList.count(Letter) * (PresentCipherList.count(Letter) - 1)
            CoincidenceIndex += Numerator / (len(PresentCipherList) * (len(PresentCipherList) - 1))

        # 求各子密文组的拟重合指数的平均值
        Average = CoincidenceIndex / Keylength
        Keylength += 1

        # 均值＞0.065即可退出循环
        if Average > 0.065:
            break

    Keylength -= 1
    return Keylength

确定密钥

第二步使用拟重合指数测试法确定密钥。

设某种语言由n个字母组成，每个字母i在第一个分布中发生的概率为ri，在第二个分布中发生的概率为qi，则拟重合指数定义为
$$
x=\sum_{i=1}^{n}r_iq_i
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# 使用重合指数法确定秘钥内容：遍历重合指数的最大值为标志
def keyword(cipher, keylength):
    CipherList = list(cipher)
    Standard = {'A': 0.08167, 'B': 0.01492, 'C': 0.02782, 'D': 0.04253, 'E': 0.12702, 'F': 0.02228, 'G': 0.02015,
                'H': 0.06094, 'I': 0.06966, 'J': 0.00153, 'K': 0.00772, 'L': 0.04025, 'M': 0.02406, 'N': 0.06749,
                'O': 0.07507, 'P': 0.01929, 'Q': 0.00095, 'R': 0.05987, 'S': 0.06327, 'T': 0.09056, 'U': 0.02758,
                'V': 0.00978, 'W': 0.02360, 'X': 0.00150, 'Y': 0.01974, 'Z': 0.00074}

    while True:
        KeyResult = []

        for i in range(keylength):
            # 使用切片分组
            PresentCipherList = CipherList[i::keylength]

            # 初始化重合指数最大值为０，检验移动位数对应字符以＊代替
            QuCoincidenceMax = 0
            KeyLetter = "*"

            # 遍历移动的位数
            for m in range(26):
                # 初始化当前移动位数的重合指数为０
                QuCoincidencePresent = 0

                # 遍历计算重合指数：各个字符的频率＊对应英文字符出现的标准频率－－－的和
                for Letter in set(PresentCipherList):
                    LetterFrequency = PresentCipherList.count(Letter) / len(PresentCipherList)

                    # 标准频率
                    k = chr((ord(Letter) - 65 - m) % 26 + 65)
                    StandardFrequency = Standard[k]

                    # 计算重合指数
                    QuCoincidencePresent = QuCoincidencePresent + LetterFrequency * StandardFrequency

                # 保存遍历过程中重合指数的最大值，同时保存对应应对的位数，即对应key的字符
                if QuCoincidencePresent > QuCoincidenceMax:
                    QuCoincidenceMax = QuCoincidencePresent
                    KeyLetter = chr(m + 65)

            # 保存当前位置key的值，退出循环，进行下一组子密文移动位数的尝试
            KeyResult.append(KeyLetter)
        # 列表转为字符串
        Key = "".join(KeyResult)
        break
    return Key

恢复明文

最后恢复明文，使用维吉尼亚解密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def VigenereDecrypt(cipher,key):
    k=key.upper()
    lc=len(cipher)
    lk=len(key)
    j=0
    ans=""
    for i in range(lc):
        if cipher[i].isupper():
            ans+=chr(((ord(cipher[i])-ord('A'))%26+26-(ord(k[j%lk])-ord('A'))%26)%26+ord('A'))
            j+=1
        elif cipher[i].islower():
            ans+=chr(((ord(cipher[i])-ord('a'))%26+26-(ord(k[j%lk])-ord('a'))%26)%26+ord('a'))
            j+=1
        else:
            ans+=cipher[i]
    return ans

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
def cleanunalpha(cipher):  # 去掉非字母后的密文
    CipherAlpha = ''
    for i in range(len(cipher)):
        if (cipher[i].isalpha()):
            CipherAlpha += cipher[i]
    return CipherAlpha

def length(cipher):
    CipherList = list(cipher)#密文转换为列表
    Keylength = 1

    while True:
        # 指数初始化为０
        CoincidenceIndex = 0

        # 使用切片分组
        for i in range(Keylength):
            Numerator = 0
            PresentCipherList = CipherList[i::Keylength]#分组

            # 使用集合去重，计算每一子密文组的拟重合指数
            for Letter in set(PresentCipherList):
                Numerator += PresentCipherList.count(Letter) * (PresentCipherList.count(Letter) - 1)
            CoincidenceIndex += Numerator / (len(PresentCipherList) * (len(PresentCipherList) - 1))

        # 求各子密文组的拟重合指数的平均值
        Average = CoincidenceIndex / Keylength
        Keylength += 1

        # 均值＞0.06即可退出循环
        if Average > 0.06:
            break

    Keylength -= 1
    return Keylength

# 使用重合指数法确定秘钥内容：遍历重合指数的最大值为标志
def keyword(cipher, keylength):
    CipherList = list(cipher)
    Standard = {'A': 0.08167, 'B': 0.01492, 'C': 0.02782, 'D': 0.04253, 'E': 0.12702, 'F': 0.02228, 'G': 0.02015,
                'H': 0.06094, 'I': 0.06966, 'J': 0.00153, 'K': 0.00772, 'L': 0.04025, 'M': 0.02406, 'N': 0.06749,
                'O': 0.07507, 'P': 0.01929, 'Q': 0.00095, 'R': 0.05987, 'S': 0.06327, 'T': 0.09056, 'U': 0.02758,
                'V': 0.00978, 'W': 0.02360, 'X': 0.00150, 'Y': 0.01974, 'Z': 0.00074}

    while True:
        KeyResult = []

        for i in range(keylength):
            # 使用切片分组
            PresentCipherList = CipherList[i::keylength]

            # 初始化重合指数最大值为０，检验移动位数对应字符以＊代替
            QuCoincidenceMax = 0
            KeyLetter = "*"

            # 遍历移动的位数
            for m in range(26):
                # 初始化当前移动位数的重合指数为０
                QuCoincidencePresent = 0

                # 遍历计算重合指数：各个字符的频率＊对应英文字符出现的标准频率－－－的和
                for Letter in set(PresentCipherList):
                    LetterFrequency = PresentCipherList.count(Letter) / len(PresentCipherList)

                    # 标准频率
                    k = chr((ord(Letter) - 65 - m) % 26 + 65)
                    StandardFrequency = Standard[k]

                    # 计算重合指数
                    QuCoincidencePresent = QuCoincidencePresent + LetterFrequency * StandardFrequency

                # 保存遍历过程中重合指数的最大值，同时保存对应应对的位数，即对应key的字符
                if QuCoincidencePresent > QuCoincidenceMax:
                    QuCoincidenceMax = QuCoincidencePresent
                    KeyLetter = chr(m + 65)

            # 保存当前位置key的值，退出循环，进行下一组子密文移动位数的尝试
            KeyResult.append(KeyLetter)
        # 列表转为字符串
        Key = "".join(KeyResult)
        break
    return Key

def VigenereDecrypt(cipher,key):
    k=key.upper()#密钥转换为大写
    lc=len(cipher)
    lk=len(key)
    j=0
    ans=""
    for i in range(lc):
        if cipher[i].isupper():#大写字母
            ans+=chr(((ord(cipher[i])-ord('A'))%26+26-(ord(k[j%lk])-ord('A'))%26)%26+ord('A'))
            j+=1
        elif cipher[i].islower():#小写字母
            ans+=chr(((ord(cipher[i])-ord('a'))%26+26-(ord(k[j%lk])-ord('a'))%26)%26+ord('a'))
            j+=1
        else:#其他字符
            ans+=cipher[i]
    return ans

def main():
    try:
        f=open('E:\Cryptology\Vigenère\Vigenère.txt','r',encoding = 'utf-8')
        cipher=f.read()
        f.close()
        print("文件读取成功！")
        Cipher=cipher.upper()
        cipher = cleanunalpha(Cipher)
        Keylength = length(cipher)
        print("密钥长度最可能为：", Keylength)
        KeyResult = keyword(cipher, Keylength)
        print("秘钥最可能为：", KeyResult)
        ClearText = VigenereDecrypt(Cipher, KeyResult)
        print("解密结果为：", ClearText)
    except IOError:
        print('文件读取失败！！！')

if __name__ == '__main__':
    main()

安全性分析

维吉尼亚密码属于多表代换密码，多表代换密码打破了原语言的字符出现规律，故其分析比单表代换密码的分析要复杂得多。维吉尼亚加密的密钥空间大小为26m，对于一个相对小的m穷举也需要很长时间。

相较于单表代换，多表代换的安全性有了显著提高，需要猜测更多的字母表，并且频率分布特性也变得平坦。但多表代换密码也可以使用统计分析法破解，使用统计方法破解多表代换密码的前提是拦截到足够多的密文，这样才具备了统计分析的前提，所以对于传输量较小的明文加密，可以选择多表代换，比较安全。