优化Python的DES加密程序有感
此文来自本人原JavaEye博客，发表时间2009年3月24日，可能有些东西现在看来是过时的，甚至是错误的，不过为了保证原来写的时候的感觉，所以没有修改。只在括号中注明了现在的看法。原文地址
最近信息安全的老师布置了作业。要求实现DES算法。。写了1天，优化了1天。。。小有些心得。。
首先感慨一下DES算法。。真是对人对机器都不友好的算法。。竟然还有诡异的S-BOX操作。。。
第二感慨一下Python对2进制不那么方便的支持。。连bin函数都没有。。虽然3.0有了。。可惜2.5没有。。只能自己实现，一大损失效率的地方啊。
好，接下来说说优化过程。
首先是单线程改多线程。。原来是将明文分成64bit一块的序列，每块单独加密。改成每一个64bit的块开一个线程操作。（这个在今天看来完全搞笑）
单线程加密解密一个1000长度的字符串所需时间大致和多线程加密10000长度的相等。效率提升明显。（提升效率很奇怪，忘了自己当初怎么测试的了）
其次是优化异或过程。原来的异或是整体将字符串转成整数然后再异或，发现效率很低。第一次修改为将2个字符串的每一位单独取出转成整形以后异或，效率提升不明显。后来上课时候突然想到，异或操作其实完全可以抛弃整数。1位的2个字符串的异或操作只有4种，写一个字典，用想要异或的2个字符串作为key，结果作为value。简单实现了一下。
def Xor(s1, s2):
"""
字符串xor
s1 -- 第一个字符串
s2 -- 第二个字符串
"""
data={}
data['0','1']=data['1','0']='1'
data['0','0']=data['1','1']='0'
s=[data[s1[x],s2[x]] for x in range(0,s1.__len__())]
return ''.join(s)
三就是优化10进制转2进制。因为python没有提供 bin 函数。于是自己实现了一个。
dec2bin = lambda n:''.join([hex2bin(x) for x in hex(n)[2:].rstrip('L')]
但是在用profile做测试的时候发现的。程序运行中大量的用到了这个函数。很占cpu时间。经过观察发现主要是2个地方使用很多，第一就是异或操作的时候，因为python提供的异或只能在整数之间进行，第二就是在S_BOX运算的时候。
异或操作已经优化了。不需要10进制转2进制了。。剩下就是S_BOX运算了。经过观察发现，S_BOX里面最大的数也不过 15,于是想到可以穷举所有S_BOX里面的数字的值对应的二进制。更改代码如下。
def easyDec2Bin(s):
"""
简单的10进制转2进制,用于简化s_box操作
s -- 10进制数
"""
data={0:'0000',1:'0001',2:'0010',3:'0011',4:'0100',
5:'0101',6:'0110',7:'0111',8:'1000',9:'1001',
10:'1010',11:'1011',12:'1100',13:'1101',14:'1110',
15:'1111'}
return data[s]
第四步优化也是通过profile发现的。。发现程序运行过程中，大量的时间消耗在一个lambda函数上。
b= ''.join(map(lambda x:data[x],s))
这个函数的作用是生成一个字符串。。尝试着把这个lambda函数改成列表操作。
b= ''.join([data[x] for x in s]
效率提升明显。。。原来一直以为map操作比较快。看来并非如此。难怪Guido大叔要推广列表操作了。。
最后一步优化就是用了psyco模块，将程序变成JIT的。。效率提升很大。。。（现在看来其实这一步是最关键的。自己当初好傻）
最终优化的结果就是，加密解密1个40k的文件，原本需要将近50秒的时间，现在10秒不到就完成了。。。。
效果提升明显。不过总觉得还有提升的空间。。尝试把多线程改成Stackless版本的试试看。。。。希望能有更大的提高 。。。。（这句话现在看来完全是搞笑，看来当时的自己还是很稚嫩啊）
