資訊安全應用之演算法設計與快速運算複雜度分析

EFFICIENT COMPUTER ARITHMETIC AND REDUCED COMPLEXITY ALGORITHM DESIGN AND ANALYSES FOR INFORMATION SECURITY APPLICATIONS

　　因應電子商務的快速發展與電腦科技的技術演變，各種密碼系統與資訊安全相關理論也隨之因應而生，密碼學也儼然成為現代電腦科學與應用數論中極為重要的一門學問與研究其中應用包括RSA公開金鑰密碼學與Diffie-Hellman交換金鑰機制。其中計算密碼系統之模指數運算（ ，其中A, E, N 近年來已發展到 512 至 1024位元），因為複雜度影響了密碼系統的安全性，因此特別受到重視。本論文深入探討資訊安全應用相關的模運算計算與複雜度分析，我們運用所提快速指數運算的研究技術可以應用在RSA公開金鑰密碼系統上以加速密碼系統的計算速度。

　　In the recent years, we have witnessed to an increasing deployment of techniques for providing security function, such as RSA public-key cryptosystem and Diffie-Hellman key exchange scheme. Among the existing techniques the RSA algorithm is by far the most widely adopted public-key cryptography algorithm. Fast modular exponentiation algorithms are often considered of practical significance in RSA cryptosystem. The main task of the encryption and decryption engine of RSA cryptosystem is to compute modular exponentiation where A is message, E is exponent and N is the modulus. The RSA cryptosystem is one of the most widely used technologies for achieving security. Nowadays, the bit-length of the numbers A, E, N would be about 512 to 1024 bits now. As we know the need for security becomes more widespread, especially for hardware-based implementations such as smart cards chips for wireless applications, cryptographic accelerators and other users. The computations for RSA cryptosystem are time-consuming. Many publications about implementations are ad-hoc and not very well researched. Most importantly, we can use this method to implement the computation of exponentiation to accelerate the speed of the public-key cryptosystems.