[SIMD]单指令多数据指令集（二）—— SIMD指令集在非对称算法中的应用

       非对称算法也叫公开秘钥算法，是通过两个数学相关的秘钥对信息进行编码的加密算法。目前应用最为广泛的是RSA和椭圆曲线密码学（国密算法中SM2与之对应）。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥；椭圆曲线密码学(ECC, Elliptic curve cryptography）是基于椭圆曲线数学的一种公钥密码的方法，和RSA相比，ECC能够在相同长度的秘钥前提下，提供更高的安全等级。

       相同的是，RSA和ECC算法均是通过大数运算实现，大数运算在这两个算法中占用了90%以上的时间。更加神奇的是，大数运算中的大数蒙哥马利模乘运算，均占用了70%左右的时间。于是，一种基于SIMD指令集的大数运算模型变得尤为关键。

       去年我写了一篇文章《一种基于NEON引擎的向量化Montgomery模乘器》，已被第”十三届保密通信与信息安全技术年会“收录。不同模长的向量化的Montgomery模乘器性能提高7-9倍不等，将256bit的向量化Montgomery模乘器应用到256bit的ECDSA，签名和验签的速率均提高6倍以上。如果对此感兴趣可以给我留言，可以提供文章原稿。从实验结果可以看出这一次是成功的，不仅很好的兼容了传统大数Montgomery模乘的软件接口，也很好的提升了运算性能。进一步针对256bit的ECDSA中的其他大数运算行了”向量化“，性能则是一般，一般到什么程度呢？和普通汇编优化一个级别！有的甚至不如-O2 -O3。分析原因如下：1、模长太小，流水线根本排不满已经完成运算了；2、长度参数不固定，无法软件流水；3、为了兼容传统软件接口，不得不做大量的数据打包工作。至此基于NEON引擎的非对称算法向量化告一段落，至于RSA，Montgomery模乘已经可以大幅提升其运算性能，如果有项目需要，再对其他大数运算进行向量化改造，应该会有一定的效果。

       对于非对称算法，我又花了一些时间在SSE和AVX上。先说结论吧：此路不通。SSE指令集已经是比较老旧的版本了，128bit的扩展寄存器，虽然和NEON的128bit寄存器长度上相当，但是灵活性上就差远了；指令集上SSE算是很丰富了，但是偏偏少了一些很好用的，比如NEON提供了一个非常好用的”乘加“指令VMLA，在大数运算中该指令往往可以起到事半功倍的效果；AVX也不怎么样，虽说它那256bit的寄存器看着诱人，但是大多数的指令集目前只支持浮点运算。我的天哪！其实大多数的服务器、云端基本上还是x86的架构，研究SSE和AVX是有一定的前景的，先等等看下一代的AVX吧。

       算法的向量化就像玩儿游戏，很有意思！只是往往要向量化的不只是算法本身，数据结构也需要相应的改变才能达到最佳的效果。