Low-Complexity Cryptographic Algorithm Design Based on Addition Chain and Signed Recoding Technique

運用加法鍊與符號元編碼技術設計低複雜度演算法研究

吳嘉龍(C.-L. Wu)

《危機管理學刊》 5卷2期 (2008/09) Pp. 31-38

https://doi.org/10.6459/JCM.200809_5(2).0004

摘要

由於網際網路成功發展與快捷便利的特性，已讓網路和我們的日常生活緊密結合，而所影響的層面也正急遽快速的伸展開來。而正由於資訊流通如此的便利並且相當受到重視，因此如何保障網路管理，身份認證，電子交易等應用上具有相當保密性與安全性，是一個刻不容緩的議題。在資訊安全傳輸運用中許多計算的問題上，模指數是一個常見的問題，舉例說明：包括密碼學中金鑰交換機制的應用，針對公開金鑰密碼系統需例如1024大位元計算量的加解密計算過程而言，更是相當重要。在本論文中所提出快速二元模指數的方法，結合了加法鍊法，模指數算術法以及符號元編碼法。本文並且針對提出的方法應用數論分析詳探討如何有效降低計算複雜度，這個方法可以實現在以符號元為計算基礎的機器，亦適用在平行處理的運算上，運用所提快速指數運算的研究技術可以應用在公開金鑰密碼系統上以加速密碼系統的計算速度。

關鍵字

資訊安全 ； 指數運算 ； 演算法設計 ； 密碼系統 ； 數論分析

並列摘要

Modular arithmetic is the most dominant part of the computation which is performed in the RSA public-key cryptosystem and key exchange scheme for cryptographic applications. Namely, most modern cryptographic protocols, which require a large number of multiplications, are based on modular arithmetic. Efficient algorithm design, redundancy elimination and numerical analyses for performing modular multiplication operation, which is crucial to cryptosystem and authentication schemes, are important in today's needs of secure communications .Modular exponentiation of long integers is required in a number of public-key cryptosystem. The operands are considerably large. Performing modular exponentiation is computationally very complexity. In several public-key cryptosystems, the main operation consists of the modular exponentiation, which is performed using successive modular multiplications. In order to better reduce the execution time in these cryptosystems, the total number of modular multiplications must be reduced. In this paper, we propose an efficient method for computing modular exponentiation with the addition chain technique and a different base recoding. This algorithm can be proved useful and practical for information security usage such as key-exchange scheme and public-key cryptosystems.

並列關鍵字

Information security ； exponentiation ； complexity analysis ； algorithm ； cryptography

參考文獻

A. Kooshesh,B. Ravikumar(2008).Efficient implementation of algorithms for approximate exponentiation.Information Processing Letters.105(4),131-13715.

C.-C. Chang,Y.-T. Kuo,C.-H. Lin(2003).Fast algorithms for common-multiplicand multiplication and exponentiation by performing complements.Proceedings of AINA 17th International Conference on Advanced Information Networking and Applications.(Proceedings of AINA 17th International Conference on Advanced Information Networking and Applications).

C.-L. Wu,D.-C. Lou,J.-C. Lai,T.-J. Chang(2006).Fast parallel exponentiation algorithm for RSA public-key cryptosystem.Informatica.17(3),445-462.

C.-L. Wu,D.-C. Lou,J.-C. Lai,Te-Jen Chang(2007).Fast modular multi-exponentiation using modified complex arithmetic.Applied Mathematics and Computation.186(2),1065-1074.

C.-L. Wu,D.-C. Lou,T.-J. Chang(2006).An efficient modular exponentiation binary algorithm using shortest addition chain.Mathematical meeting and annual meeting of the mathematical society.(Mathematical meeting and annual meeting of the mathematical society).