题目信息

题目给出实现加密的程序，且指出明文是一首诗。

分析

先总结一下有用的信息：

  • 明文是有意义的英文，即明文均为可见字符且明文中的各字母出现的频率接近统计规律(在够长的一段话里，各个字母的占比大致稳定，并且这个稳定值已经用巨大的语料库统计出来了，这就是字母频率)

  • 密钥均为可见字符

  • 加密时对密钥进行了重用

解决方案可分为程序分析与如果人工分析两部分；
(1)程序分析：穷举密钥的长度，对每一长度的密钥，筛选密钥每一位可行的字符集合(要求此密钥位为可见字符，且那些被此密钥位解密出的明文位亦为可见字符)，如果密钥某一位可行的字符集合为空，则说明当前穷举的长度不是密钥的长度，这一步结束之后，可确定密钥的长度，以及密钥每一位可能的字符值；

注：就实际情况来看，如果穷举的长度不是密钥的长度，几乎一定会有密钥某一位可行的字符集合为空。

接下来，利用词频分析对密钥每一位进行爆破：对密钥的每一位，使用上一步得到的候选字符集中不同字符将解密出不同的明文，其中各字母出现的频率也不会相同，计算各字母出现的频率分布与统计规律的相似程度，选择相似程度最高的字符作为此密钥位。

注：相似度计算公式：$score=\sum_{i=1}^{26}p_{i}*q_{i}$，其中$p_{i}$是明文中第$i$个字母出现的频率，$q_{i}$是已统计出的第$i$个字母的频率。$q_{i}$的值见下面的程序。

(2)人工分析：经过(1)，可猜对大部分密钥位，之后再结合解密出的明文对错误的密钥位进行修正。

解题

实现的Python脚本如下：

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
from Crypto.Util.strxor import strxor
from string import printable
from base64 import b64decode

freq={'e':0.12702,'t':0.09056,'a':0.08167,'o':0.07507,
        'i':0.06966,'n':0.06749,'s':0.06327,'h':0.06094,
        'r':0.05987,'d':0.04253,'l':0.04025,'c':0.02782,
        'u':0.02758,'m':0.02406,'w':0.02360,'f':0.02228,
        'g':0.02015,'y':0.01974,'p':0.01929,'b':0.01492,
        'v':0.00978,'k':0.00772,'j':0.00153,'x':0.00150,
        'q':0.00095,'z':0.00074
        }

def frequency(msg):
    global freq
    cnum=[len([s for s in msg if s==cc or s==cc.upper()]) for cc in freq.keys()]
    csum=sum(cnum)
    if csum==0:
        return 0
    return sum([x*y for x,y in zip(freq.values(),cnum)])/csum

def analysis(ks,cip):
    lks=[len(sk) for sk in ks]
    lc=len(cip)
    step=len(lks)
    key=[]
    for ii,sk in enumerate(ks):
        scores=[frequency(''.join([strxor(cip[ind],ik) for ind in range(ii,lc,step)])) for ik in sk]
        key.append(sk[scores.index(max(scores))])
    return key

def guessK(cip,low=4,high=33):
    lc=len(cip)
    for step in range(low,high):
        ks=[]
        for c1 in range(step):
            optK=list(printable[:-6])
            optK=[ik for ik in optK if ik not in "{}'\"`^"]
            for ind in range(c1,lc,step):
                tt=optK[:]
                for ik in tt:
                    if not strxor(cip[ind],ik) in printable:
                        optK.remove(ik)
            if len(optK)==0:
                break
            ks.append(optK[:])
        if len(ks)<step:
            continue
        return analysis(ks,cip)

def enc(data, key):
    key=(key*(len(data)/len(key)+1))[:len(data)]
    return strxor(data,key)

def solve():
    with open('cipher.txt','r') as f:
        cip=b64decode(f.read())
    key=guessK(cip)
    lc=len(cip)
    lk=len(key)
    while 1:
        while 1:
        print('\033[1;31m'+''.join(key)+'\033[0m')
        msg=enc(cip,''.join(key))
        out=['['+str(ii/lk)+']['+msg[ii:(ii+lk)]+']' for ii in range(0,lc-lk,lk)]
        out.append('['+str(lc/lk)+']['+msg[-(lc%lk+lk):-(lc%lk)]+']')
        if lc%lk:
            out.append('['+str(lc/lk+1)+']['+msg[-(lc%lk):]+']')
        print ''.join(out)
        if raw_input('\033[1;31m need correction(y) or not(n)\033[0m')=='n':
            break
        row=int(raw_input('\033[1;31m row \033[0m'))
        col=int(raw_input('\033[1;31m col \033[0m'))
        cor=raw_input('\033[1;31m correction \033[0m')
        key[col]=strxor(cip[row*lk+col],cor)
    with open('msg','w') as f:
        f.write(msg)
    print('\033[1;31m'+''.join(key)+'\033[0m')

if __name__=='__main__':
    print solve()

程序运行结果如下：

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
$ python solve.py
xo7_is_,nte,estingn@f
[0][
L,fe, 1hin~and li(h1][1][-o#f ti(e a0d timeoa"][2][ai+
Fri3olo+s tire#e6][3][s
*ne
Iehea,d the *c-][4][o,efromethe~valley< $][5][ndethe -ear*
Open ;oe][6][th  lon ly -oul ofos,][7][ck)e ha7ves*ing
Re?e$][8][t *utri"htl', but .l6][9][o 7epea1 th; well--e,][10][ngeof
E3ent+ally s8a<][11][in" in 1he :esert  a6][12][isOI be)iev; I am
o7][13][n $s th  br7ght su"m ][14][r #lowe7s
D1 not w&t-][15][er d un!efe?ted fi*r<][16][ d mon 7uleTHeart =a1][17][e $nd b7eat6ing toob ][18][arethe )oad~of theoc0][19][mb rsom 
Bo,ed
TwoEIe][20][he$rd t-e m+sic, f=o(][21][ t-e mo*n a0d carc.s6][22][
A0xili$ry ;xtremeoa ][23][st-etic,sm <ait tooc$][24][pt0re m,styTFillin( 1][25][heeinte+se 2ife, b:te][26][al6o fi)lin9 the p:r ][27][
T-ere $re ?lways "e(][28][or,es t-rou9hout t'ee][29][ea7th
Iebel7eve I .mO][30][Di d asethe~quiet -e$][31][ut< of $utu3n leav*sO][32][Sh ng i6 no* chaosc 6][33][mo.e ge6tur;
Even 8i)][34][t $lso 7eta7ned bo!ee][35][pr*udlyeQin9 Feng "u6][36][cl 
Occ0lt

hree
Ioh ][37][arelovei I <elieveoi+][38][ l*ve
L*ve 7s a po le][39][ofestru"gli0g bluebg7][40][ee+ alg$e
A- desol.t ][41][ m,cro-'urs* of wi!dO][42][Bl edin" th,ough m6 3][43][ei+s
Ye$rs -tation*de][44][inethe 'eli;f
FourEIe][45][be)ieveetha* all c.ne][46][he$r
Ev n a0ticipa;ee][47][di6cret , I~met th* *][48][th r th ir 1wn
Som* &][49][anenot "ras. the m m ][50][ntOLefteto *he Eas; 1][51][o "o We6t, *he dea+ (][52][us1 noteret+rn to !o2][53][he7e
Se , I~wear Z.ne][54][Fl*werseon 3y headc ,][55][n #ull 'loo3 alongot-][56][e 2ay a)l t6e way
	r ][57][qu ntlyemis-ed som*,e][58][bu1 als* de;ply mo9e!][59][ b< win!, f,ost, s!o2][60][ o7 rai+
Fi(e
Praj!ae][61][Pa7amit$, s1on as <o*][62][n $s
li#e b; beaut&f0][63][l )ike 6umm;r flow*r6][64][ a+d de$th 2ike au;u(][65][n )eave6
Al-o careoa'][66][n )eave6
Al-o careoa'][67][ou1 wha1 ha-]
need correction(y) or not(n)y
row: 0
col: 2
correction: i
xor_is_,nte,estingn@f
[0][
Life, 1hin~and li(h1][1][-off ti(e a0d timeoa"][2][ain
Fri3olo+s tire#e6][3][s
one
Iehea,d the *c-][4][o, fromethe~valley< $][5][nd the -ear*
Open ;oe][6][the lon ly -oul ofos,][7][ckle ha7ves*ing
Re?e$][8][t outri"htl', but .l6][9][o repea1 th; well--e,][10][ng of
E3ent+ally s8a<][11][ing in 1he :esert  a6][12][is
I be)iev; I am
o7][13][n as th  br7ght su"m ][14][r flowe7s
D1 not w&t-][15][ered un!efe?ted fi*r<][16][ demon 7uleTHeart =a1][17][e and b7eat6ing toob ][18][ar the )oad~of theoc0][19][mbersom 
Bo,ed
TwoEIe][20][heard t-e m+sic, f=o(][21][ the mo*n a0d carc.s6][22][
Auxili$ry ;xtremeoa ][23][sthetic,sm <ait tooc$][24][pture m,styTFillin( 1][25][he inte+se 2ife, b:te][26][also fi)lin9 the p:r ][27][
There $re ?lways "e(][28][ories t-rou9hout t'ee][29][earth
Iebel7eve I .mO][30][Died asethe~quiet -e$][31][uty of $utu3n leav*sO][32][Sheng i6 no* chaosc 6][33][moke ge6tur;
Even 8i)][34][t also 7eta7ned bo!ee][35][proudlyeQin9 Feng "u6][36][cle
Occ0lt

hree
Ioh ][37][ar lovei I <elieveoi+][38][ love
L*ve 7s a po le][39][of stru"gli0g bluebg7][40][een alg$e
A- desol.t ][41][ micro-'urs* of wi!dO][42][Bleedin" th,ough m6 3][43][eins
Ye$rs -tation*de][44][in the 'eli;f
FourEIe][45][believeetha* all c.ne][46][hear
Ev n a0ticipa;ee][47][discret , I~met th* *][48][ther th ir 1wn
Som* &][49][an not "ras. the m m ][50][nt
Lefteto *he Eas; 1][51][o go We6t, *he dea+ (][52][ust noteret+rn to !o2][53][here
Se , I~wear Z.ne][54][Flowerseon 3y headc ,][55][n full 'loo3 alongot-][56][e way a)l t6e way
	r ][57][quentlyemis-ed som*,e][58][but als* de;ply mo9e!][59][ by win!, f,ost, s!o2][60][ or rai+
Fi(e
Praj!ae][61][Paramit$, s1on as <o*][62][n as
li#e b; beaut&f0][63][l like 6umm;r flow*r6][64][ and de$th 2ike au;u(][65][n leave6
Al-o careoa'][66][n leave6
Al-o careoa'][67][out wha1 ha-]
need correction(y) or not(n)y
row: 0
col: 7
correction: t
xor_is_inte,estingn@f
[0][
Life, thin~and li(h1][1][-off time a0d timeoa"][2][ain
Frivolo+s tire#e6][3][s
one
I hea,d the *c-][4][o, from the~valley< $][5][nd the hear*
Open ;oe][6][the lonely -oul ofos,][7][ckle harves*ing
Re?e$][8][t outrightl', but .l6][9][o repeat th; well--e,][10][ng of
Event+ally s8a<][11][ing in the :esert  a6][12][is
I believ; I am
o7][13][n as the br7ght su"m ][14][r flowers
D1 not w&t-][15][ered undefe?ted fi*r<][16][ demon ruleTHeart =a1][17][e and breat6ing toob ][18][ar the load~of theoc0][19][mbersome
Bo,ed
TwoEIe][20][heard the m+sic, f=o(][21][ the moon a0d carc.s6][22][
Auxiliary ;xtremeoa ][23][stheticism <ait tooc$][24][pture mistyTFillin( 1][25][he intense 2ife, b:te][26][also fillin9 the p:r ][27][
There are ?lways "e(][28][ories throu9hout t'ee][29][earth
I bel7eve I .mO][30][Died as the~quiet -e$][31][uty of autu3n leav*sO][32][Sheng is no* chaosc 6][33][moke gestur;
Even 8i)][34][t also reta7ned bo!ee][35][proudly Qin9 Feng "u6][36][cle
Occult
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
hree
Ioh ][37][ar love, I <elieveoi+][38][ love
Love 7s a po le][39][of struggli0g bluebg7][40][een algae
A- desol.t ][41][ micro-burs* of wi!dO][42][Bleeding th,ough m6 3][43][eins
Years -tation*de][44][in the beli;f
FourEIe][45][believe tha* all c.ne][46][hear
Even a0ticipa;ee][47][discrete, I~met th* *][48][ther their 1wn
Som* &][49][an not gras. the m m ][50][nt
Left to *he Eas; 1][51][o go West, *he dea+ (][52][ust not ret+rn to !o2][53][here
See, I~wear Z.ne][54][Flowers on 3y headc ,][55][n full bloo3 alongot-][56][e way all t6e way
	r ][57][quently mis-ed som*,e][58][but also de;ply mo9e!][59][ by wind, f,ost, s!o2][60][ or rain
Fi(e
Praj!ae][61][Paramita, s1on as <o*][62][n as
life b; beaut&f0][63][l like summ;r flow*r6][64][ and death 2ike au;u(][65][n leaves
Al-o careoa'][66][n leaves
Al-o careoa'][67][out what ha-]
need correction(y) or not(n)y
row: 0
col: 11
correction:  
xor_is_interestingn@f
[0][
Life, thin and li(h1][1][-off time and timeoa"][2][ain
Frivolous tire#e6][3][s
one
I heard the *c-][4][o, from the valley< $][5][nd the heart
Open ;oe][6][the lonely soul ofos,][7][ckle harvesting
Re?e$][8][t outrightly, but .l6][9][o repeat the well--e,][10][ng of
Eventually s8a<][11][ing in the desert  a6][12][is
I believe I am
o7][13][n as the bright su"m ][14][r flowers
Do not w&t-][15][ered undefeated fi*r<][16][ demon rule
Heart =a1][17][e and breathing toob ][18][ar the load of theoc0][19][mbersome
Bored
TwoEIe][20][heard the music, f=o(][21][ the moon and carc.s6][22][
Auxiliary extremeoa ][23][stheticism bait tooc$][24][pture misty
Fillin( 1][25][he intense life, b:te][26][also filling the p:r ][27][
There are always "e(][28][ories throughout t'ee][29][earth
I believe I .mO][30][Died as the quiet -e$][31][uty of autumn leav*sO][32][Sheng is not chaosc 6][33][moke gesture
Even 8i)][34][t also retained bo!ee][35][proudly Qing Feng "u6][36][cle
Occult
Three
Ioh ][37][ar love, I believeoi+][38][ love
Love is a po le][39][of struggling bluebg7][40][een algae
As desol.t ][41][ micro-burst of wi!dO][42][Bleeding through m6 3][43][eins
Years station*de][44][in the belief
FourEIe][45][believe that all c.ne][46][hear
Even anticipa;ee][47][discrete, I met th* *][48][ther their own
Som* &][49][an not grasp the m m ][50][nt
Left to the Eas; 1][51][o go West, the dea+ (][52][ust not return to !o2][53][here
See, I wear Z.ne][54][Flowers on my headc ,][55][n full bloom alongot-][56][e way all the way
	r ][57][quently missed som*,e][58][but also deeply mo9e!][59][ by wind, frost, s!o2][60][ or rain
Five
Praj!ae][61][Paramita, soon as <o*][62][n as
life be beaut&f0][63][l like summer flow*r6][64][ and death like au;u(][65][n leaves
Also careoa'][66][n leaves
Also careoa'][67][out what has]
need correction(y) or not(n)y
row: 0
col: 18
correction: g
xor_is_interesting!@f
[0][
Life, thin and ligh1][1][-off time and time a"][2][ain
Frivolous tirele6][3][s
one
I heard the ec-][4][o, from the valleys $][5][nd the heart
Open toe][6][the lonely soul of s,][7][ckle harvesting
Repe$][8][t outrightly, but al6][9][o repeat the well-be,][10][ng of
Eventually swa<][11][ing in the desert oa6][12][is
I believe I am
Bo7][13][n as the bright summ ][14][r flowers
Do not wit-][15][ered undefeated fier<][16][ demon rule
Heart ra1][17][e and breathing to b ][18][ar the load of the c0][19][mbersome
Bored
Two
Ie][20][heard the music, fro(][21][ the moon and carcas6][22][
Auxiliary extreme a ][23][stheticism bait to c$][24][pture misty
Filling 1][25][he intense life, bute][26][also filling the pur ][27][
There are always me(][28][ories throughout thee][29][earth
I believe I amO][30][Died as the quiet be$][31][uty of autumn leavesO][32][Sheng is not chaos, 6][33][moke gesture
Even wi)][34][t also retained bonee][35][proudly Qing Feng mu6][36][cle
Occult
Three
I h ][37][ar love, I believe i+][38][ love
Love is a poole][39][of struggling blue-g7][40][een algae
As desolat ][41][ micro-burst of windO][42][Bleeding through my 3][43][eins
Years stationede][44][in the belief
Four
Ie][45][believe that all cane][46][hear
Even anticipatee][47][discrete, I met the *][48][ther their own
Some &][49][an not grasp the mom ][50][nt
Left to the East 1][51][o go West, the dead (][52][ust not return to no2][53][here
See, I wear Zane][54][Flowers on my head, ,][55][n full bloom along t-][56][e way all the way
Fr ][57][quently missed some,e][58][but also deeply move!][59][ by wind, frost, sno2][60][ or rain
Five
Prajnae][61][Paramita, soon as so*][62][n as
life be beautif0][63][l like summer flower6][64][ and death like autu(][65][n leaves
Also care a'][66][n leaves
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
Also care a'][67][out what has]
need correction(y) or not(n)y
row: 0
col: 20
correction: t
xor_is_interesting!@#
[0][
Life, thin and light][1][-off time and time ag][2][ain
Frivolous tireles][3][s
one
I heard the ech][4][o, from the valleys a][5][nd the heart
Open to ][6][the lonely soul of si][7][ckle harvesting
Repea][8][t outrightly, but als][9][o repeat the well-bei][10][ng of
Eventually sway][11][ing in the desert oas][12][is
I believe I am
Bor][13][n as the bright summe][14][r flowers
Do not with][15][ered undefeated fiery][16][ demon rule
Heart rat][17][e and breathing to be][18][ar the load of the cu][19][mbersome
Bored
Two
I ][20][heard the music, from][21][ the moon and carcass][22][
Auxiliary extreme ae][23][stheticism bait to ca][24][pture misty
Filling t][25][he intense life, but ][26][also filling the pure][27][
There are always mem][28][ories throughout the ][29][earth
I believe I am
][30][Died as the quiet bea][31][uty of autumn leaves
][32][Sheng is not chaos, s][33][moke gesture
Even wil][34][t also retained bone ][35][proudly Qing Feng mus][36][cle
Occult
Three
I he][37][ar love, I believe in][38][ love
Love is a pool ][39][of struggling blue-gr][40][een algae
As desolate][41][ micro-burst of wind
][42][Bleeding through my v][43][eins
Years stationed ][44][in the belief
Four
I ][45][believe that all can ][46][hear
Even anticipate ][47][discrete, I met the o][48][ther their own
Some c][49][an not grasp the mome][50][nt
Left to the East t][51][o go West, the dead m][52][ust not return to now][53][here
See, I wear Zan ][54][Flowers on my head, i][55][n full bloom along th][56][e way all the way
Fre][57][quently missed some, ][58][but also deeply moved][59][ by wind, frost, snow][60][ or rain
Five
Prajna ][61][Paramita, soon as soo][62][n as
life be beautifu][63][l like summer flowers][64][ and death like autum][65][n leaves
Also care ab][66][n leaves
Also care ab][67][out what has]
need correction(y) or not(n)n
xor_is_interesting!@#