hoxede的QQ填充算法和TEA 加解密的python实现

xichen

1. """
   
2. The MIT License
   
3. 
   
4. Copyright (c) 2005 hoxide
   
5. 
   
6. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
   
7. 
   
8. The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
   
9. 
   
10. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
    
11. 
    
12. 
    
13. QQ Crypt module.
    
14. 
    
15. """
    
16. 
    
17. from struct import pack as _pack
    
18. from struct import unpack as _unpack
    
19. from binascii import b2a_hex, a2b_hex
    
20. 
    
21. from random import seed
    
22. from random import randint as _randint
    
23. 
    
24. __all__ = ['encrypt', 'decrypt']
    
25. 
    
26. seed()
    
27. 
    
28. op = 0xffffffffL
    
29. 
    
30. 
    
31. def xor(a, b):
    
32.     a1,a2 = _unpack('>;LL', a[0:8])
    
33.     b1,b2 = _unpack('>;LL', b[0:8])
    
34.     r = _pack('>;LL', ( a1 ^ b1) & op, ( a2 ^ b2) & op)
    
35.     return r
    
36. 
    
37. 
    
38. def code(v, k):
    
39.     """
    
40.     TEA coder encrypt 64 bits value, by 128 bits key,
    
41.     QQ do 16 round TEA.
    
42.     To see:
    
43.     http://www.ftp.cl.cam.ac.uk/ftp/papers/djw-rmn/djw-rmn-tea.html .
    
44.    
    
45.     TEA 加密,  64比特明码, 128比特密钥, qq的TEA算法使用16轮迭代
    
46.     具体参看
    
47.     http://www.ftp.cl.cam.ac.uk/ftp/papers/djw-rmn/djw-rmn-tea.html
    
48. 
    
49.     >;>;>; c = code('abcdefgh', 'aaaabbbbccccdddd')
    
50.     >;>;>; b2a_hex(c)
    
51.     'a557272c538d3e96'
    
52.     """
    
53.     n=16  #qq use 16
    
54.     delta = 0x9e3779b9L
    
55.     k = _unpack('>;LLLL', k[0:16])
    
56.     y, z = _unpack('>;LL', v[0:8])
    
57.     s = 0
    
58.     for i in xrange(n):
    
59.         s += delta
    
60.         y += (op &(z<<4))+ k[0] ^ z+ s ^ (op&(z>;>;5)) + k[1] ;
    
61.         y &= op
    
62.         z += (op &(y<<4))+ k[2] ^ y+ s ^ (op&(y>;>;5)) + k[3] ;
    
63.         z &= op
    
64.     r = _pack('>;LL',y,z)
    
65.     return r
    
66. 
    
67. def encrypt(v, k):
    
68.     """
    
69.     Encrypt Message follow QQ's rule.
    
70.     用QQ的规则加密消息
    
71. 
    
72.     v is the message to encrypt, k is the key
    
73.     参数 v 是被加密的明文, k是密钥
    
74.     fill char is some random numbers (in old QQ is 0xAD)
    
75.     填充字符数是随机数, (老的QQ使用0xAD)
    
76.     fill n char's n = (8 - (len(v)+2)) %8 + 2
    
77.     填充字符的个数 n = (8 - (len(v)+2)) %8 + 2
    
78.     ( obviously, n is 2 at least, n is 2-9)
    
79.     ( 显然, n至少为2, 取2到9之间)
    
80. 
    
81.     then insert (n - 2)|0xF8 in the front of the fill chars
    
82.     然后在填充字符前部插入1字节, 值为 ((n - 2)|0xF8)
    
83.     to record the number of fill chars.
    
84.     以便标记填充字符的个数.
    
85.     append 7 '\0' in the end of the message.
    
86.     在消息尾部添加7字节'\0'
    
87.    
    
88.     thus the lenght of the message become filln + 8 + len(v),
    
89.     因此消息总长变为 filln + 8 + len(v),
    
90.     and it == 0 (mod 8)
    
91.     他模8余0(被8整除)
    
92. 
    
93.     Encrypt the message .
    
94.     加密这段消息
    
95.     Per 8 bytes,
    
96.     每8字节,
    
97.     the result is:
    
98.     规则是
    
99.    
    
100.     r = code( v ^ tr, key) ^ to   (*)
     
101. 
     
102.     code is the QQ's TEA function.
     
103.     code函数就是QQ 的TEA加密函数.
     
104.     v is 8 bytes data to encrypt.
     
105.     v是被加密的8字节数据
     
106.     tr is the result in preceding round.
     
107.     tr是前次加密的结果
     
108.     to is the data coded in perceding round, is v_pre ^ r_pre_pre
     
109.     to是前次被加密的数据, 等于 v_pre ^ r_pre_pre
     
110. 
     
111.     For the first 8 bytes 'tr' and 'to' is zero.
     
112.     对头8字节, 'tr' 和 'to' 设为零
     
113.    
     
114.     loop and loop,
     
115.     不断循环,
     
116.     that's end.
     
117.     结束.
     
118.    
     
119.     >;>;>; en = encrypt('', b2a_hex('b537a06cf3bcb33206237d7149c27bc3'))
     
120.     >;>;>; decrypt(en,  b2a_hex('b537a06cf3bcb33206237d7149c27bc3'))
     
121.     ''
     
122.     """
     
123.     ##FILL_CHAR = chr(0xAD)
     
124.     END_CHAR = '\0'
     
125.     FILL_N_OR = 0xF8
     
126.     vl = len(v)
     
127.     filln = (8-(vl+2))%8 + 2;
     
128.     fills = ''
     
129.     for i in xrange(filln):
     
130.         fills = fills + chr(_randint(0, 0xff))
     
131.     v = ( chr((filln -2)|FILL_N_OR)
     
132.           + fills
     
133.           + v
     
134.           + END_CHAR * 7)
     
135.     tr = '\0'*8
     
136.     to = '\0'*8
     
137.     r = ''
     
138.     o = '\0' * 8
     
139.     #print 'len(v)=', len(v)
     
140.     for i in xrange(0, len(v), 8):
     
141.         o = xor(v[i:i+8], tr)
     
142.         tr = xor( code(o, k), to)
     
143.         to = o
     
144.         r += tr
     
145.     return r
     
146. 
     
147. def decrypt(v, k):
     
148.     """
     
149.     DeCrypt Message
     
150.     消息解密
     
151.    
     
152.     by (*) we can find out follow easyly:
     
153.     通过(*)式,我们可以容易得发现(明文等于):
     
154.    
     
155.     x  = decipher(v[i:i+8] ^ prePlain, key) ^ preCyrpt
     
156.    
     
157.     prePlain is pre 8 byte to be code.
     
158.     perPlain 是被加密的前8字节
     
159.    
     
160.     Attention! It's v per 8 byte value xor pre 8 byte prePlain,
     
161.     注意! 他等于前8字节数据异或上前8字节prePlain,
     
162.     not just per 8 byte.
     
163.     而不只是前8字节.
     
164.     preCrypt is pre 8 byte Cryped.
     
165.     perCrypt 是前8字节加密结果.
     
166. 
     
167.     In the end of deCrypte the raw message,
     
168.     在解密完原始数据后,
     
169.     we have to cut the filled bytes which was append in encrypt.
     
170.     我们必须去除在加密是添加的填充字节.
     
171. 
     
172.     the number of the filling bytes in the front of message is
     
173.     填充在消息头部的字节数是
     
174.     pos + 1.
     
175.    
     
176.     pos is the first byte of deCrypted --- r[0] & 0x07 + 2
     
177.     pos等于解密后的第一字节 --- r[0] & 0x07 + 2
     
178. 
     
179.     the end of filling aways is 7 zeros.
     
180.     尾部填充始终是7字节零.
     
181.     we can test the of 7 bytes is zeros, to make sure it is right.
     
182.     我们可以通测试最后7字节是零, 来确定它是正确的.
     
183.    
     
184.     so return r[pos+1:-7]
     
185.     所以返回 r[pos+1:-7]
     
186. 
     
187.     >;>;>; r = encrypt('', b2a_hex('b537a06cf3bcb33206237d7149c27bc3'))
     
188.     >;>;>; decrypt(r, b2a_hex('b537a06cf3bcb33206237d7149c27bc3'))
     
189.     ''
     
190.     >;>;>; r = encrypt('abcdefghijklimabcdefghijklmn', b2a_hex('b537a06cf3bcb33206237d7149c27bc3'))
     
191.     >;>;>; decrypt(r, b2a_hex('b537a06cf3bcb33206237d7149c27bc3'))
     
192.     'abcdefghijklimabcdefghijklmn'
     
193.     >;>;>; import md5
     
194.     >;>;>; key = md5.new(md5.new('python').digest()).digest()
     
195.     >;>;>; data='8CE160B9F312AEC9AC8D8AEAB41A319EDF51FB4BB5E33820C77C48DFC53E2A48CD1C24B29490329D2285897A32E7B32E9830DC2D0695802EB1D9890A0223D0E36C35B24732CE12D06403975B0BC1280EA32B3EE98EAB858C40670C9E1A376AE6C7DCFADD4D45C1081571D2AF3D0F41B73BDC915C3AE542AF2C8B1364614861FC7272E33D90FA012620C18ABF76BE0B9EC0D24017C0C073C469B4376C7C08AA30'
     
196.     >;>;>; data = a2b_hex(data)
     
197.     >;>;>; b2a_hex(decrypt(data, key))
     
198.     '00553361637347436654695a354d7a51531c69f1f5dde81c4332097f0000011f4042c89732030aa4d290f9f941891ae3670bb9c21053397d05f35425c7bf80000000001f40da558a481f40000100004dc573dd2af3b28b6a13e8fa72ea138cd13aa145b0e62554fe8df4b11662a794000000000000000000000000dde81c4342c8966642c4df9142c3a4a9000a000a'
     
199.    
     
200.     """
     
201.     l = len(v)
     
202.     #if l%8 !=0 or l<16:
     
203.     #    return ''
     
204.     prePlain = decipher(v, k)
     
205.     pos = (ord(prePlain[0]) & 0x07L) +2
     
206.     r = prePlain
     
207.     preCrypt = v[0:8]
     
208.     for i in xrange(8, l, 8):
     
209.         x = xor(decipher(xor(v[i:i+8], prePlain),k ), preCrypt)
     
210.         prePlain = xor(x, preCrypt)
     
211.         preCrypt = v[i:i+8]
     
212.         r += x
     
213.     if r[-7:] != '\0'*7: return None
     
214.    
     
215. 
     
216.     return r[pos+1:-7]
     
217. 
     
218. def decipher(v, k):
     
219.     """
     
220.     TEA decipher, decrypt  64bits value with 128 bits key.
     
221.     TEA 解密程序, 用128比特密钥, 解密64比特值
     
222. 
     
223.     it's the inverse function of TEA encrypt.
     
224.     他是TEA加密函数的反函数.
     
225. 
     
226.     >;>;>; c = code('abcdefgh', 'aaaabbbbccccdddd')
     
227.     >;>;>; decipher( c, 'aaaabbbbccccdddd')
     
228.     'abcdefgh'
     
229.     """
     
230. 
     
231.     n = 16
     
232.     y, z = _unpack('>;LL', v[0:8])
     
233.     a, b, c, d = _unpack('>;LLLL', k[0:16])
     
234.     delta = 0x9E3779B9L;
     
235.     s = (delta << 4)&op
     
236.     for i in xrange(n):
     
237.         z -= ((y<<4)+c) ^ (y+s) ^ ((y>;>;5) + d)
     
238.         z &= op
     
239.         y -= ((z<<4)+a) ^ (z+s) ^ ((z>;>;5) + b)
     
240.         y &= op
     
241.         s -= delta
     
242.         s &= op
     
243.     return _pack('>;LL', y, z)
     
244. 
     
245. def _test():
     
246.     import doctest, tea
     
247.     return doctest.testmod(tea)
     
248. 
     
249. 
     
250. if __name__ == "__main__":
     
251.     _test()
     
252. 
     

复制代码