代數體在整數分解及離散對數的應用

Abstract

離散對數的問題首先由Diffie與Hellman在1976年應用到密碼系統上。爾後無論訊息傳送系統、ElGamal 數位簽名系統、DSS ( Digital Signature Standard )都廣泛採用。而各種以大數分解為安全基礎的密碼系統也因網路發達和個人電腦計算力的提升而慢慢地受到重視，如RSA公鑰加密系統、RSA簽名加密系統等。然而一旦離散對數問題和大數分解被有效地破解，即很容易計算密鑰的值，如此一來這些密碼系統就等於完全沒有安全性可言。由此可見離散對數和大數分解在密碼系統應用上的重要性，也奠定了離散對數和大數分解在密碼學上的重大價值。 離散對數和大數分解在數論的領域中已有一段很長的歷史。但直到現在，離散對數和大數分解的問題還是無法有效率的計算出來。在這篇論文中，我們主要著重於介紹Gaussian Integer方法在離散對數以及Number Filed Sieve在大數分解的兩種計算方法做一番清楚描述，並在Gaussian Integer方法用程式寫出一個實例以供比較。

In 1976, Diffie and Hellman first proposed an algorithm that applied the discrete logarithm problem to key distribution on the network. After that, many cryptosystems based on the discrete logarithm were published such as ElGamal digital signature scheme and Digital Signature Standard. Meanwhile, many cryptosystems based on factorization problem are more important as the network grows faster and the PC computing power increases such as RSA public-key encryption cryptosystem and RSA signature cryptosystem. If the factorization and discrete logarithm problems are efficiently solved, there will not be any more security for those cryptosystems. The factorization and discrete logarithm problems have a long history in the field of number theory. However, we still can not efficiently solve these problems. In this thesis, we focus on the Number field Sieve and Gaussian Integer method for factorization and discrete logarithm problems. And we also write a program to implement the Gaussian Integer method for discrete logarithm in section 4.3