快速模運算與複雜度分析應用於現代公開金鑰密碼系統及資訊安全應用管理

Efficient Modular Arithmetic and Complexity Analyses for Modern Cryptographic Systems and Information Security Management

吳嘉龍
C. L. Wu

空軍航空技術學院 
一般學科部航空通訊電子系

摘要

  由於符號元編碼表示法相較於一般二元表示法其特性可以減少非零位元的出現,利用這個優點,我們得以有效的減少在模指數運算過程中的冗餘模乘運算量。而當我們運用將對摺指數部份加以記錄共同乘法的部份時,則可以改進傳統二元掃瞄演算法的運算效率,進而減少了模指數運算的計算複雜度。針對於所提出的改進式符號元編碼演算法我們可以運用平行處理技術加以平行有效的執行模指數的運算。若配合使用高根位符號元編碼演算法與改進蒙哥馬利法,配合平行演算,數論分析加速運算與硬體的設計分析,透過驗證說明,我們可以預期得到模指數運算最佳的整體計算複雜度,這些成果將可有效運用在通訊系統應用與密碼資訊安全領域上。

關鍵字:資訊安全、複雜度分析、密碼系統、數論、演算法。

ABSTRACT

  As we know the “signed-digit recoding algorithm” has less occurrence probability of the nonzero digit than original binary number representation. By taking this advantage, I can effectively decrease modular multiplications. By using both the“binary method”and  “common-multiplicand multiplication method”of recording the common parts in the folded substrings, the “folding-exponent algorithm” can improve the efficiency of the binary algorithm, thus can further decrease the redundancy computation of modular exponentiation. As the modular squaring operation in finite field can be done by a simple shift operation when a normal basis is used, and the modular multiplications and modular squaring operations in our proposed signed-digit recoding scheme can be executed in parallel, by using our proposed generalized r-radix signed-digit folding algorithm, hardware design and parallel technique, we can effectively decrease the computational complexity.

Keywords: Information security; Complexity analyses; Cryptographic system; Number theory; Algorithm