引用格式：吳昆，胡現剛，張學超，等.橢圓曲線標量乘高效方案設計［J］.網絡安全與數據治理，2024，43（8）：28-34.
引言
相比RSA等算法，ECC的計算量和密鑰長度已經有了很大的降低，但是它的數學結構仍較復雜，對于一些計算能力和存儲資源受限的應用場景如無線傳感器網絡（Wireless Sensor Network，WSN）來說，算法所需的計算時間和計算量會極大地縮短網絡的生命周期［1］。在ECC密碼體制中，標量乘（Q=kP）是算法安全性的關鍵，其運算速度從整體上決定了算法的執行效率［2］。因此，對標量乘法進行輕量化改進，將顯著減少ECC密碼方案的資源消耗。
目前，對標量乘的優化主要集中在兩方面，一是對算法本身進行設計，以減少點加和倍點的運算次數，如Montgomery算法［3］及其改進算法［4-5］，基于非相鄰形式（Non-Adjacent Form，NAF）標量乘快速算法［6］及其改進方案［7-8］。二是對底層域運算進行改進，如文獻［9］通過對多項式乘法和模約減等域運算進行合理優化設計，使得基于二進制域Koblitz曲線的標量乘算法比素數域上計算速度更快、效率更高；文獻［10］針對ATmega128微控制器的特點，對有限域上平方和乘法運算進行了優化；文獻［11］提出使用最優素數域（OPF）作為底層代數結構；文獻［12］提出了一種適用于MICAz電機特點的標量乘計算方案；文獻［13］利用優化的掩碼操作數技術進行模塊加法和減法，以減少掩碼計算的次數和延遲；文獻［14］提出了一種基于乘法器編碼的多項式乘法方法。
結合以上思想，本文以傳感器節點中常用的8 bit ATmega128芯片為目標平臺，通過對二進制域上ECC標量乘法底層的域運算進行研究，針對乘法運算，提出一種聯合區塊相乘的思想，并進一步設計出3級Karatsuba乘法算法；針對減法運算，通過將減法運算與模運算相結合，提出一種模快速約減算法；針對模平方運算，通過預處理的方式建立查找表，并結合模運算同時處理，提出一種快速模平方算法；針對逆運算，結合擴展Euclideam算法，提出一種求模逆算法；最后，基于Montgomery算法設計了二進制域上的標量乘快速實現方案。理論和實驗分析表明，本文方案減少了計算過程的基本運算和內存讀寫次數，提高了標量乘法的計算效率。
本文詳細內容請下載：
http://www.rjjo.cn/resource/share/2000006102
作者信息：
吳昆1，胡現剛2，張學超3，汪曉睿1
(1.91977部隊,北京100071;
2.南部戰區海軍參謀部，廣東湛江524000;
3.中央軍委政法委，北京100000)
