Cryptography I 第一周作业解题报告

Published at 22nd September, 2014

Cryptography I 第一周作业:已知 11 条使用了相同的 Stream Cipher key 加密的密文(cipher text),尝试解出第 11 条的明文(plain text)。

Steam Cipher 加密的方式是将 Key 与明文按位异或得出密文:CT_i = PT_i XOR K_i,为了书写方便,下文中的整串异或都代表按位异或,即将其缩写为 CT = PT XOR K

破解原理:

(设 PT1 是第一条明文,PT2 是第二条明文,CT1 是第一条密文,CT2 是第二条密文,K 是 Key)
由于 CT1 = PT1 XOR KCT2 = PT2 XOR K
那么 CT1 XOR CT2 = PT1 XOR PT2
即可以在只知道密文 CT1, CT2 的情况下,知道有关明文的信息: PT1 XOR PT2

首先先预处理一下这些密文。由于 Stream Cipher 是按位异或的,并且我们只需要还原 #11,因此对于#1 ~ #10密文,超出 #11 密文长度的部分可以全部截断不需要考虑。(注,本文中所有代码都是 CoffeeScript + Node.js)

hexToBinary = (str) ->
    ( parseInt(str.substr(i, 2), 16) for i in [0...str.length] by 2 )

target = hexToBinary '32510ba9babebbbefd001547a810e67149caee11d945cd7fc81a05e9f85aac650e9052ba6a8cd8257bf14d13e6f0a803b54fde9e77472dbff89d71b57bddef121336cb85ccb8f3315f4b52e301d16e9f52f904'
ciphersHex = [
    '315c4eeaa8b5f8aaf9174145bf43e1784b8fa00dc71d885a804e5ee9fa40b16349c146fb778cdf2d3aff021dfff5b403b510d0d0455468aeb98622b137dae857553ccd8883a7bc37520e06e515d22c954eba5025b8cc57ee59418ce7dc6bc41556bdb36bbca3e8774301fbcaa3b83b220809560987815f65286764703de0f3d524400a19b159610b11ef3e'
    '234c02ecbbfbafa3ed18510abd11fa724fcda2018a1a8342cf064bbde548b12b07df44ba7191d9606ef4081ffde5ad46a5069d9f7f543bedb9c861bf29c7e205132eda9382b0bc2c5c4b45f919cf3a9f1cb74151f6d551f4480c82b2cb24cc5b028aa76eb7b4ab24171ab3cdadb8356f'
    '32510ba9a7b2bba9b8005d43a304b5714cc0bb0c8a34884dd91304b8ad40b62b07df44ba6e9d8a2368e51d04e0e7b207b70b9b8261112bacb6c866a232dfe257527dc29398f5f3251a0d47e503c66e935de81230b59b7afb5f41afa8d661cb'
    '32510ba9aab2a8a4fd06414fb517b5605cc0aa0dc91a8908c2064ba8ad5ea06a029056f47a8ad3306ef5021eafe1ac01a81197847a5c68a1b78769a37bc8f4575432c198ccb4ef63590256e305cd3a9544ee4160ead45aef520489e7da7d835402bca670bda8eb775200b8dabbba246b130f040d8ec6447e2c767f3d30ed81ea2e4c1404e1315a1010e7229be6636aaa'
    '3f561ba9adb4b6ebec54424ba317b564418fac0dd35f8c08d31a1fe9e24fe56808c213f17c81d9607cee021dafe1e001b21ade877a5e68bea88d61b93ac5ee0d562e8e9582f5ef375f0a4ae20ed86e935de81230b59b73fb4302cd95d770c65b40aaa065f2a5e33a5a0bb5dcaba43722130f042f8ec85b7c2070'
    '32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd2061bbde24eb76a19d84aba34d8de287be84d07e7e9a30ee714979c7e1123a8bd9822a33ecaf512472e8e8f8db3f9635c1949e640c621854eba0d79eccf52ff111284b4cc61d11902aebc66f2b2e436434eacc0aba938220b084800c2ca4e693522643573b2c4ce35050b0cf774201f0fe52ac9f26d71b6cf61a711cc229f77ace7aa88a2f19983122b11be87a59c355d25f8e4'
    '32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd90f1fa6ea5ba47b01c909ba7696cf606ef40c04afe1ac0aa8148dd066592ded9f8774b529c7ea125d298e8883f5e9305f4b44f915cb2bd05af51373fd9b4af511039fa2d96f83414aaaf261bda2e97b170fb5cce2a53e675c154c0d9681596934777e2275b381ce2e40582afe67650b13e72287ff2270abcf73bb028932836fbdecfecee0a3b894473c1bbeb6b4913a536ce4f9b13f1efff71ea313c8661dd9a4ce'
    '315c4eeaa8b5f8bffd11155ea506b56041c6a00c8a08854dd21a4bbde54ce56801d943ba708b8a3574f40c00fff9e00fa1439fd0654327a3bfc860b92f89ee04132ecb9298f5fd2d5e4b45e40ecc3b9d59e9417df7c95bba410e9aa2ca24c5474da2f276baa3ac325918b2daada43d6712150441c2e04f6565517f317da9d3'
    '271946f9bbb2aeadec111841a81abc300ecaa01bd8069d5cc91005e9fe4aad6e04d513e96d99de2569bc5e50eeeca709b50a8a987f4264edb6896fb537d0a716132ddc938fb0f836480e06ed0fcd6e9759f40462f9cf57f4564186a2c1778f1543efa270bda5e933421cbe88a4a52222190f471e9bd15f652b653b7071aec59a2705081ffe72651d08f822c9ed6d76e48b63ab15d0208573a7eef027'
    '466d06ece998b7a2fb1d464fed2ced7641ddaa3cc31c9941cf110abbf409ed39598005b3399ccfafb61d0315fca0a314be138a9f32503bedac8067f03adbf3575c3b8edc9ba7f537530541ab0f9f3cd04ff50d66f1d559ba520e89a2cb2a83'
    '32510ba9babebbbefd001547a810e67149caee11d945cd7fc81a05e9f85aac650e9052ba6a8cd8257bf14d13e6f0a803b54fde9e77472dbff89d71b57bddef121336cb85ccb8f3315f4b52e301d16e9f52f904'
]
ciphers = ( hexToBinary(hex)[0...target.length] for hex in ciphersHex )

在代码中,前 10 条密文按照 8 位一组存放在了 ciphers 数组中,第 11 条存放在了 target 中。

首先复习一下基本知识有个大致方向:由于 CT = PT XOR K,所以 K = PT XOR CT,即如果已知明文和密文,可以还原出 Key,而 Key 可以进一步解开其他密文。所以现在要做的是尝试还原这 11 条密文中的一部分明文。

注意到作业中给出了 Hint:观察 空格 XOR [a-zA-Z] 的结果,那么就先计算一下 字母 XOR 字母字母 XOR 空格,看看能出现什么惊喜。

seq = 'abcABC '

for i, pi in seq
    for j, pj in seq when pj > pi
        console.log '%s XOR %s = %s', i, j, i.charCodeAt(0)^j.charCodeAt(0)
a XOR b = 3
a XOR c = 2
a XOR A = 32
a XOR B = 35
a XOR C = 34
a XOR   = 65
b XOR c = 1
b XOR A = 35
b XOR B = 32
b XOR C = 33
b XOR   = 66
c XOR A = 34
c XOR B = 33
c XOR C = 32
c XOR   = 67
A XOR B = 3
A XOR C = 2
A XOR   = 97
B XOR C = 1
B XOR   = 98
C XOR   = 99

可以发现,每一个大写或小写字母与空格异或都会得到一个唯一值,即,如果已知 A XOR B 的值,就可以确定 AB 是否分别为空格与字母。

为了使得结果更清晰,我们生成一个表,表示由哪些 AB 可以得出某一个 A XOR B 的值:

map = {}
seq = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ '

for i in seq
    for j in seq
        xor = i.charCodeAt(0)^j.charCodeAt(0)
        map[xor] = [] if not map[xor]?
        map[xor].push i, j

for xor, results of map
    map[xor] = _.unique(results)
    map[xor].sort()
    console.log "%s <= %s", xor, map[xor].join ','
0 <=  ,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
1 <= B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y
2 <= A,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Z,a,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,z
3 <= A,B,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,Y,Z,a,b,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,y,z
...
61 <= D,E,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,d,e,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
62 <= D,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,d,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
63 <= E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
65 <=  ,a
66 <=  ,b
67 <=  ,c
...
88 <=  ,x
89 <=  ,y
90 <=  ,z
97 <=  ,A
98 <=  ,B
99 <=  ,C
...
120 <=  ,X
121 <=  ,Y
122 <=  ,Z

从如上表格中更清晰可见,在将字符限定在字母和空格的情况下,若异或结果落在 [65,90][97,122] 区间上,则可以很容易知道是由什么字母和空格异或得来。不妨先试一试 CT1 XOR CT2,看 PT1PT2 中哪几个字节可能是空格:

binaryXOR = (a, b) ->
    ( a[i]^b[i] for i in [0...Math.min(a.length, b.length)] )

hex = binaryXOR(ciphers[0], ciphers[1])
possibleSpace = new Array(ciphers[0].length)
for bin, index in hex
    if bin in [65..90] or bin in [97..122]
        possibleSpace[index] = 1
    else
        possibleSpace[index] = 0

console.log JSON.stringify(possibleSpace)
[0,0,1,0,0,1,1,0,0,0,0,1,0,1,0,0,0,1,0,0,1,0,0,0,1,1,0,1,0,0,0,1,1,0,0,1,0,0,0,1,1,0,0,0,0,0,0,1,0,0,1,1,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,1,0,0]

1 代表该字节可能为空格。然而为了还原这一字节的 Key,还需要确认该字节为空格。确认方法很简单,先假设这些可能的空格都是 PT1 的,接下来依次计算 CT1 XOR CT3, CT1 XOR CT4, .... 如果该字节确实为空格,那它与其他密文该字节异或后的结果也应当落在 [65,90][97,122] 中,或等于 0 (空格异或空格)。确定完 CT1 中哪些字节是空格以后,以此类推可以确定 CT2CT11 中哪些字节是空格。确定了空格,就确定了该字节的 Key。最终也许大部分 Key 就可以被解出来了,从而解出 PT11

然而有个问题:目前的假设基于明文由字母和空格构成,这才使得和字母ASCII差别较大的空格与字母异或后出现了唯一值。如果原文中还包含ASCII与空格相近的数字和符号等,那么它们与字母异或后的结果也可能落在 [65,90][97,122] 区间上。另一方面,空格 XOR 数字空格 XOR 特殊符号 也不会落在这两个区间上。

很简单就可以验证加入数字以后的分布结果:

65 <=  ,0,1,2,3,4,5,6,7,8,9,a,p,q,r,s,t,u,v,w,x,y
66 <=  ,0,1,2,3,4,5,6,7,8,b,p,q,r,s,t,u,v,w,z
67 <=  ,0,1,2,3,4,5,6,7,9,c,p,q,r,s,t,u,v,w,z
....
120 <=  ,0,1,2,3,4,5,6,7,9,A,H,I,J,K,L,M,N,O,X
121 <=  ,0,1,2,3,4,5,6,7,8,A,H,I,J,K,L,M,N,O,Y
122 <=  ,0,1,2,3,4,5,6,7,8,9,B,C,H,I,J,K,L,M,N,O,Z

原本只有两个候选值,现在有很多候选值,难以做出选择。因此这里对算法做一些修正,确认某一字节是空格时,不需要满足每一条密文异或后该字节都在区间上,而只要满足有多次 (k),就认为这一字节的明文是空格(基于特殊字符或数字出现概率远小于字母的假定)。基于此,对 11 个 cipher text 进行处理:

decryptedKey = new Array(target.length)
for srcCipher, srcIndex in ciphers
    possibleSpace = new Array(target.length)
    for cmpCipher, cmpIndex in ciphers when cmpIndex isnt srcIndex
        hex = binaryXOR srcCipher, cmpCipher
        for bin, index in hex
            if bin in [65..90] or bin in [97..122]
                possibleSpace[index] = 0 if not possibleSpace[index]?
                possibleSpace[index]++
    for count, index in possibleSpace
        decryptedKey[index] = srcCipher[index]^(' '.charCodeAt(0)) if count >= 5  # k = 5

result = ''
for key, index in decryptedKey
    if key?
        result += String.fromCharCode(key^target[index])
    else
        result += "?"

console.log result

取阈值 k = 5 可得出初步结果:

Thm secuet mes age is  Whtn usi|g wsstream cipher, nevir use the key more than once

注意,这里 k 的取值会对结果产生不小影响,因此可以多测试几个不同的 k

其实到了这一步,已经可以恢复出完整的目标明文了。不过现在的代码还原效果不是非常好,因此改进一下代码。

之前的算法通过猜测可能的空格位置来还原 Key,然而可以猜测的不只是空格。

显然,若已知 PT1_i,PT2_i ∈ C_1, PT1_i,PT3_i ∈ C_2, ..., PT1_i,PTn_i ∈ C_n-1, ... 那么 PT1_i ∈ C_1 ∩ C_2 ∩ ... ∩ C_n-1。所以我们可以直接对每一次异或时该字节可能的原始值的集合取交集,得到可能的结果。

由于原始值集合 (reverse map) 没有覆盖到所有可能的字符,所以在算法实现的时候不使用取交集来避免由于个别字符遗漏导致该字节交集最后变成空集。在这里,我使用计数统计,取出现次数较多的值作为猜测的值。

keys = ([] for x in target)

# try restore the key
for srcCipher, si in ciphers

    counter = ({} for x in target)
    candidate = ([] for x in target)

    for tmpCipher, ti in ciphers when ti isnt si
        xorPT = binaryXOR(srcCipher, tmpCipher)
        for xor, i in xorPT
            possiblePT = map[xor]
            if possiblePT
                for choice in possiblePT
                    counter[i][choice] = 0 if not counter[i][choice]?
                    counter[i][choice]++

    for occurs, i in counter
        for choice, occur of occurs
            # 只取出现次数大于 80% 的
            candidate[i].push [choice, occur] if occur >= ciphers.length * 0.8
        candidate[i].sort (a, b) -> b[1] - a[1]

    # try to restore the key
    for c, i in candidate
        if c.length is 1
            # 只有一个候选,则选择这个
            keys[i].push c[0][0].charCodeAt(0)^srcCipher[i]
        else if c.length > 1 and c[0][1] >= 9 and c[1][1] < c[0][1]
            # 有多个候选,并且有次数最高的那个
            keys[i].push c[0][0].charCodeAt(0)^srcCipher[i]

keys[i] = _.unique(key) for key, i in keys

targetPT = ''
for bin, i in target
    if keys[i].length is 1
        targetPT += String.fromCharCode(keys[i]^bin)
    else
        targetPT += '?'

console.log targetPT

通过这样的算法,可以生成效果更好的明文:

The secuet message is: Wh?n using ? stream cipher, never use the key more than once

经过简单修正(只需要修正三个 Key),最后的明文是:

The secret message is: When using a stream cipher, never use the key more than once

Comments