我正在考虑重新实现 SlowAES 代码 (http://anh.cs.luc.edu/331/code/aes.py) 以尝试利用 numpy 的 native 数组支持。对我来说,我得到的是违反直觉的结果,即 SlowAES 的纯 Python 比使用 numpy 实现的相同功能快得多。这是我所拥有的最清楚的例子。
AES 中的主要操作之一是移位行,其中 4x4 元素字节数组中的每一行都移动了一些位置(0 表示第 0 行,1 表示第 1 行,等等)。原始 Python 代码将这个 4x4 字节状态数组视为一维 16 元素列表,然后使用切片创建要旋转的虚拟行:
def rotate(word, n):
return word[n:] + word [0:n]
def shiftRows(state):
for i in range(4):
state[i*4:i*4+4] = rotate(state[i*4:i*4+4], -i)
使用 16 个整数的列表在 shiftRows 上运行 timeit 得到 3.47 微秒的时间。
在 numpy 中重新实现相同的函数,假设一个 4x4 整数输入数组,将很简单:
def shiftRows(state):
for i in range(4):
state[i] = np.roll(state[i],-i)
但是,timeit 显示其执行时间为 16.3 微秒。
我希望 numpy 的优化数组操作可能会产生更快的代码。我哪里错了?是否有某种方法可以比纯 Python 更快地实现 AES?我想获得一些中间结果,因此 pycrypto 可能不适用(尽管如果这太慢,我可能不得不再看一眼)。
2016 年 9 月 7 日 - 感谢您的回答。为了回答“为什么”这个问题,我正在考虑运行数十万(如果不是数百万)样本明文/密文对。因此,虽然任何单一加密的时间差异都没有什么区别,但从长远来看,我能节省的任何时间都会产生巨大的差异。
请您参考如下方法:
简单的答案是创建数组的开销很大。因此,对小列表的操作通常比对数组的等效操作更快。如果数组版本像列表一样是迭代的,则尤其如此。对于大型数组,使用编译方法的操作会更快。
这 4 个“滚动”时间说明了这一点
对于一个小列表:
In [93]: timeit x=list(range(16)); x=x[8:]+x[:8]
100000 loops, best of 3: 2.75 µs per loop
In [94]: timeit y=np.arange(16); y=np.roll(y,8)
The slowest run took 40.90 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 14.5 µs per loop
对于大的:
In [95]: timeit x=list(range(1000)); x=x[500:]+x[:500]
10000 loops, best of 3: 52.9 µs per loop
In [96]: timeit y=np.arange(1000); y=np.roll(y,500)
The slowest run took 28.91 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 3: 22.2 µs per loop
我们可以通过从计时循环中提取 range 和 arange 步骤来进一步细化问题。
np.roll 操作本质上是:
y[np.concatenate((np.arange(8,16), np.arange(0,8)))]
这构建了 4 个数组,2 个 arange,concatenate,以及最终的索引数组。
