[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吧。

       算法的向量化就像玩兒遊戲，很有意思！隻是往往要向量化的不隻是算法本身，資料結構也需要相應的改變才能達到最佳的效果。