流加密算法XOR解密

本周有个比较有趣的内容:利用重复使用key的流加密密文,来破解目标密文。 经过分析和代码实现,收获颇丰。

1. 理解加密解密算法

题目是要求我们利用多条密文( $c_{i}$ ,i∈[1,10])来破译目标密文(p),而已有的密文是利用stream cypher($E_k$)来进行加密,加密用的密钥(k)是重复使用的。
同时,stream cypher是理论课上讲的XOR(异或)运算的加密,即利用一个足够长的key与我们的明文p进行一一异或,得到最后的c。即关系如下:
$$c=p ⨁ k$$

2. 分析加密、解密过程的突破口

突破口1:利用XOR(异或)运算的性质

我们已知异或运算有以下性质:
$$A⨁B=C ⇒A⨁C=B或B⨁C=A$$
那么套入我们上面的加密/解密算法中:
$$C⨁P=K和K⨁C=P$$
这表明如果我们获得了密文C,通过一定方式解密出来明文P,那么即可简单得到我们的密钥K,接下来只要密钥不变,我们就可以无障碍地破解密文C
同时还可以得到
$$C_1⨁C_2=(P_1⨁K)⨁(P_2⨁K)= P_1⨁P_2$$
这一条特性,使得我们对密文的处理可以跳过了密钥K的处理,使得结果变成明文的异或结果,一旦我们利用明文的相关特点,即可破解明文,实际效果即是我们的突破口3

突破口2:利用重复利用key

重复利用key体现在两个方面:

  • 体现在我们的突破口1中,即所有密文都是用相同的key进行加密解密。 利用相同的key,我们可以利用这个特性结合异或的特性,使得我们忽略key加密的效果。
  • 多次使用相同的key,为我们破译提供了更多的可能,即丰富了更多的信息,也反映了更多密钥K的特征,降低我们的破解难度。

突破口3:“空格”字符特性

结合我们本次破解的实际例子,密码的字符利用ASCII码来表示。我们已知ASCII码的长度为8个比特,可以表示$2^{8}=256$个字符,而我们本次的大部分字符为我们常用的字母:A-Z和a-z,不排除有别的字符。 而A-Z和a-z字符的字符范围分别为65~90和97~122。 其次,单词与单词之间常用空格来分隔,空格的ASCII编码为32。
因此,对于任意字符X如果是字母的话,有如下特性:
$$X⨁32=x, 其中x是X相应的大小写转换$$
那么,我们即可得出结论:只要两个字符异或后的结果还是字母的字符,我们可以确定当中有一个空格。即:
$$ A⨁B=C,C∈Z_{字母} ⇒A或B中仅有一个是空格字符 $$
实现代码后,本结论只限于限定字符(字母、数字),不能有其他特殊的字符

3. 根据突破口制定相关策略方案或算法

a. 利用突破口3寻找出可以确定的空格:

首先将密文C_i的一个字符X与剩余的密文的相同位置字符进行异或运算,如果这个字符X能够使得这些位置的字符的异或结果都是字母,那么即可以判断这个字符X是空格。表达如下:

$$对于第i个密文的第t个字符C_{i,t},∀j∈[1,10]且j≠i,满足关系C_{i,t} ⨁ C_{j,t}=X,X为字母时,则字符C_{i,t} 为空格$$

但是因为有些空格因为异或运算的时候,可能遇到自身同样是空格的其他密文,因此会使得结果并非是字母,所以产生了遗漏,因此这部分的确定是最保险的确定,空格的个数会是不少于这个数量,所以后面猜解的时候也不能遗漏空格的可能性。

b. 利用突破口1获得部分$K_{space}$:

利用突破口1可以利用公式获得$K_{space}$:

$$ K_{space}=C_{space}⨁P_{space} $$

c. 利用b)得到的$K_{space}$完成解密:

利用b)得到部分密钥$K_{space}$解密与$K_{space}$同位置的其他密文的部分字符$C_{part}$,并进而猜出上下文的明文$P_{part}$,再利用突破口1获得剩下的$K_{rest}$,一直循环过程c),直到得到所有的$K_{all}$
利用得到的$K_{all}$破译目标密文$C_{target}$
$P_{target}$=$C_{targe}$ ⨁$K_{all}$

4. 实现方案(Python2.X实现)

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
# -*- coding:utf-8 -*-
# Author: Jason Ye
# Time: 2016/03/15
import sys
def readInCypherText(fileName):
"""
Read in cypher texts
"""
cypherText = []
with open(fileName) as f:
for line in f:
cypherText.append(line)
return cypherText
def initialKey(cypherText):
maxLen = 0
key = []
for text in cypherText:
maxLen = max(maxLen, (len(text)-1)/2)
for i in range(maxLen):
key.append("*")
return key
def printKey(key):
print "[Key]" + str(len(key)/2)
for index, key in enumerate(key):
if(key == "*"):
sys.stdout.write("** ")
else:
sys.stdout.write(hex(int(key)).replace("0x",'')+" ")
if((index+1)%16==0):
print ''
print''
def decrypt(key, ct):
pt = ''
lenOfCT = len(ct) - 1
for ptr in range(0,lenOfCT,2):
c = ct[ptr] + ct[ptr+1]
c = int(c,16)
if(key[ptr/2] != "*"):
sys.stdout.write(chr(c^int(key[ptr/2])))
else:
sys.stdout.write("*")
print ''
sys.stdout.flush()
def getKey(ct, pos, p):
a = int(ct[pos*2] + ct[pos*2+1],16)
k = a ^ ord(p)
return k
def main():
cypherText = readInCypherText("cypherText.txt")
key = initialKey(cypherText)
printKey(key)
#Find K(space)
for i in cypherText:
lenOfText = len(i) - 1
print "[Length] " + str(cypherText.index(i)) + ": " +str(lenOfText/2)
for ptr in range(0,lenOfText,2):
# sys.stdout.write(i[ptr]+i[ptr+1]+" ")
isSpace = True
a = int(i[ptr] + i[ptr+1],16)
for j in cypherText:
jLen = len(j)
if(i!=j and ptr+1 < jLen):
b = int(j[ptr] + j[ptr+1],16)
c = a ^ b
if(not str.isalpha(chr(c))):
isSpace = False
elif(ptr+1>jLen):
isSpace = False
if(not isSpace):
# sys.stdout.write(i[ptr]+i[ptr+1]+" ")
pass
else:
# sys.stdout.write("__ ")
key[ptr/2] = str(a ^ 0x20)
if((ptr+2) % 32 == 0):
print''
print ''
printKey(key)
# Print current plaintext deciphered
for i in range(190):
sys.stdout.write(str(i%10))
print ''
for ct in cypherText:
decrypt(key, ct)
print "\n"
sys.stdout.flush()
# Guess
with open("log.txt",'w') as log: # Log down the decryption to file in case some guesses are not right
try:
while(True):
try: # Preventing invalid input
line, pos, p = raw_input().split()
except:
print "Invalid input! Input again"
sys.stdout.flush()
continue
if(p == "*"): # Undo the guess
key[int(pos)] = "*"
print "Key revised\n\n"
continue
elif(p == "done"):
break
sys.stdout.write(line + "line: " + pos+" "+p +'\n')
log.write(line + " " + pos + " " + p + "\n")
key[int(pos)] = getKey(cypherText[int(line)], int(pos), p)
# Print the header of number
for i in range(190):
sys.stdout.write(str(i%10))
print ''
# Print current plain text deciphered
for ct in cypherText:
decrypt(key, ct)
print "\n\n"
# Print current key
printKey(key)
sys.stdout.flush()
except:
pass
targetCypherText = "32510ba9babebbbefd001547a810e67149caee11d945cd7fc81a05e9f85aac650e9052ba6a8cd8257bf14d13e6f0a803b54fde9e77472dbff89d71b57bddef121336cb85ccb8f3315f4b52e301d16e9f52f904"
print "Target CypherText:"
decrypt(key, targetCypherText)
raw_input()
if __name__ == '__main__':
main()

下面是加密的密文,用于猜解密钥

cypheredText.txt
1
2
3
4
5
6
7
8
9
10
11
315c4eeaa8b5f8aaf9174145bf43e1784b8fa00dc71d885a804e5ee9fa40b16349c146fb778cdf2d3aff021dfff5b403b510d0d0455468aeb98622b137dae857553ccd8883a7bc37520e06e515d22c954eba5025b8cc57ee59418ce7dc6bc41556bdb36bbca3e8774301fbcaa3b83b220809560987815f65286764703de0f3d524400a19b159610b11ef3e
234c02ecbbfbafa3ed18510abd11fa724fcda2018a1a8342cf064bbde548b12b07df44ba7191d9606ef4081ffde5ad46a5069d9f7f543bedb9c861bf29c7e205132eda9382b0bc2c5c4b45f919cf3a9f1cb74151f6d551f4480c82b2cb24cc5b028aa76eb7b4ab24171ab3cdadb8356f
32510ba9a7b2bba9b8005d43a304b5714cc0bb0c8a34884dd91304b8ad40b62b07df44ba6e9d8a2368e51d04e0e7b207b70b9b8261112bacb6c866a232dfe257527dc29398f5f3251a0d47e503c66e935de81230b59b7afb5f41afa8d661cb
32510ba9aab2a8a4fd06414fb517b5605cc0aa0dc91a8908c2064ba8ad5ea06a029056f47a8ad3306ef5021eafe1ac01a81197847a5c68a1b78769a37bc8f4575432c198ccb4ef63590256e305cd3a9544ee4160ead45aef520489e7da7d835402bca670bda8eb775200b8dabbba246b130f040d8ec6447e2c767f3d30ed81ea2e4c1404e1315a1010e7229be6636aaa
3f561ba9adb4b6ebec54424ba317b564418fac0dd35f8c08d31a1fe9e24fe56808c213f17c81d9607cee021dafe1e001b21ade877a5e68bea88d61b93ac5ee0d562e8e9582f5ef375f0a4ae20ed86e935de81230b59b73fb4302cd95d770c65b40aaa065f2a5e33a5a0bb5dcaba43722130f042f8ec85b7c2070
32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd2061bbde24eb76a19d84aba34d8de287be84d07e7e9a30ee714979c7e1123a8bd9822a33ecaf512472e8e8f8db3f9635c1949e640c621854eba0d79eccf52ff111284b4cc61d11902aebc66f2b2e436434eacc0aba938220b084800c2ca4e693522643573b2c4ce35050b0cf774201f0fe52ac9f26d71b6cf61a711cc229f77ace7aa88a2f19983122b11be87a59c355d25f8e4
32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd90f1fa6ea5ba47b01c909ba7696cf606ef40c04afe1ac0aa8148dd066592ded9f8774b529c7ea125d298e8883f5e9305f4b44f915cb2bd05af51373fd9b4af511039fa2d96f83414aaaf261bda2e97b170fb5cce2a53e675c154c0d9681596934777e2275b381ce2e40582afe67650b13e72287ff2270abcf73bb028932836fbdecfecee0a3b894473c1bbeb6b4913a536ce4f9b13f1efff71ea313c8661dd9a4ce
315c4eeaa8b5f8bffd11155ea506b56041c6a00c8a08854dd21a4bbde54ce56801d943ba708b8a3574f40c00fff9e00fa1439fd0654327a3bfc860b92f89ee04132ecb9298f5fd2d5e4b45e40ecc3b9d59e9417df7c95bba410e9aa2ca24c5474da2f276baa3ac325918b2daada43d6712150441c2e04f6565517f317da9d3
271946f9bbb2aeadec111841a81abc300ecaa01bd8069d5cc91005e9fe4aad6e04d513e96d99de2569bc5e50eeeca709b50a8a987f4264edb6896fb537d0a716132ddc938fb0f836480e06ed0fcd6e9759f40462f9cf57f4564186a2c1778f1543efa270bda5e933421cbe88a4a52222190f471e9bd15f652b653b7071aec59a2705081ffe72651d08f822c9ed6d76e48b63ab15d0208573a7eef027
466d06ece998b7a2fb1d464fed2ced7641ddaa3cc31c9941cf110abbf409ed39598005b3399ccfafb61d0315fca0a314be138a9f32503bedac8067f03adbf3575c3b8edc9ba7f537530541ab0f9f3cd04ff50d66f1d559ba520e89a2cb2a83
Result
1
2
3
4
5
6
7
8
9
10
We can factor the number 15 with quantum computers. We can also factor the number 15 with a dog trained to bark three times - Robert Harley
Euler would probably enjoy that now his theorem becomes a corner stone of crypto - Annonymous on Euler's theorem
The nice thing about Keeyloq is now we cryptographers can drive a lot of fancy cars - Dan Boneh
The ciphertext produced by a weak encryption algorithm looks as good as ciphertext produced by a strong encryption algorithm - Philip Zimmermann
You don't want to buy a set of car keys from a guy who specializes in stealing cars - Marc Rotenberg commenting on Clipper
There are two types of cryptography - that which will keep secrets safe from your little sister, and that which will keep secrets safe from your government - Bruce*Schn****
There are two types of cyptography: one that allows the Government to use brute force to break the code, and one that requires the Government to use brute force to*brea******************
We can see the point where the chip is unhappy if a wrong bit is sent and consumes more power from the environment - Adi Shamir
A (private-key) encryption scheme states 3 algorithms, namely a procedure for generating keys, a procedure for encrypting, and a procedure for decrypting.
The Concise OxfordDictionary (2006) de铿乶es crypto as the art of writing o r solving codes.

最后Key及目标密文的明文

key
pt