ARM 處理器上準梅森質數體的快速運算程式碼產生器

Code Generation for Fast Pseudo-Mersenne Prime Field Arithmetic on ARM Processors

楊上逸(Shang-Yi Yang)

指導教授 ： 鄭振牟

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2013年)

https://doi.org/10.6342/NTU.2013.02444

摘要

近期高速密碼學研究中，往往透過電腦指令的排列組合來提升運算效率，但如果少了自動化工具，則需要耗費相當大的人力。

使用我們提出的工具，只需要準梅森質數作為輸入，就能透過窮舉找出在ARM11上最高效率的模乘法程式。窮舉的參數包含大數的表示方示及程式碼產生器參數，而提出的模乘法演算法則混合了乘法與模餘兩部份，特別適合提升準梅森質數體上的計算效率。

使用提出的演算法，自動產生出的高質量程式碼運行時間較GCC編譯器的結果快16.4%，且為GMP模乘法的4至8倍。

關鍵字

多精度乘法 ； 模乘法 ； 準梅森質數 ； 快速密碼學 ； ARM11

並列摘要

Recent research on high-speed cryptography has been striving for performance by twiddling with instructions, but without an automated tool, writing fast software takes much precious labor effort.

We present a tool with a simple interface for crypto developers to generate fast modular multiplication routines in a few keystrokes: you provide the prime as the modulus and it produces several candidate results or enumerates them all for benchmark.

Specifically, we automatized the choice of number representation and the code generation for multiplication modulo a pseudo-Mesenne prime on ARM11, using the proposed convolved multiplication method, which interleaves multiplication and modular reduction.

The high-quality code generated runs up to 16.4% faster than the convolved multiplication compiled by defacto-standard compilers such as gcc, and is 4 to 8 times faster than the GMP modular multiplication.

並列關鍵字

multi-precision multiplication ； modular multiplication ； pseudo-Mersenne primes ； high-speed cryptography ； ARM11 ； convolved multiplication

參考文獻

[BDL+ 12] Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. High-speed high-security signatures. Jour- nal of Cryptographic Engineering, 2(2):77–89, 2012. Document- ID: a1a62a2f76d23f65d622484ddd09caf8, http://cryptojedi.org/ papers/#ed25519.

[Ber00] Daniel J. Bernstein. Floating-point arithmetic and message authentica- tion, 2000.

[Ber05] Daniel J. Bernstein. The poly1305-aes message-authentication code. In In Proc. FSE, pages 32–49, 2005.

[CFR+ 91] Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Trans. Program. Lang. Syst., 13(4):451–490, October 1991.

[Com90] P. G. Comba. Exponentiation cryptosystems on the ibm pc. IBM Syst. J., 29(4):526–538, October 1990.