植基於數論的公開金匙密碼系統之特性與應用研究

Abstract

這篇博士論文主要研究 RSA 密碼系統和 ElGamal密碼系統，這種植基數 論的公開密碼系統之特性與應用。 RSA 密碼系統的安全性是基於因數分 解的難題，而 ElGamal 密碼系統是基於離散對數的困難度。在 RSA 密碼 系統中，選擇私密指數 d 時，必須滿足私密指數不能太小的特性。令公 開指數為 e 模數為 N 。若 e < N 且 d < N^1/4，則私密數d 將可被連 分數法解出來。為了防止此類的攻擊，有些人就選擇很大的私密指數。但 是大的私密指數d仍然是不安全。令 RSA 模數為兩個私密質數 p 和 q 的 乘積。我們發現，若e< N 且 0 < X(N) - d < N^1/4，則亦可使用連分數 法找出該私密指數 d 。這□的 X(N) 表示 p - 1和q- 1 的最小公倍數。 另外，我們也發現私密指數 d 太接近 X(N)/2或者某一特定值時，均可 用連分數法解出私密指數。因此，在選擇私密數時，這些特性都必須加以 考慮。根據原始 RSA 密碼系統的建議，私密質數最好是強質數。但是我 們從歷年來有關於RSA的文獻中，並沒有發現有一種攻擊法能夠直接支持 選擇強質數的原因。這裡我們提出一種因數分解法，當X(p-1)或 X(q-1) 只包含小質數的乘積時，將可輕易地解出該私密質數 p 和 q。由此看來 ，強質數的特性是不可或缺的。指數運算是植基於數論的公開密碼系統之 一個重要運算，將直接影響到加解密的速度。而針對指數運算，ElGamal 密碼系統顯然比RSA密碼系統有較好的特性。在ElGamal密碼系統中，指數 運算的基底是固定的，允許事先儲存一些中間運算的結果，以加快指數運 算。根據這個特性，我們利用3-5位元混合數字系統，提出一種加快指數 運算的新方法。令n為模數的長度。指數運算最新的結果是Dimitrov 和 Cooklev 在 1995 年所提出的2-3位元混合法。該方法平均計算一次指數 運算需要 0.338n次乘法，而我們的方法只需要0.324n 次乘法。另外，值 得一提的是，當 n=512 時，我們所提的方法需要的儲存空間比 Dimitrov 和 Cooklev的方法約少 56.8%。在應用方面，我們在類似RSA 之 Fiat-Shamir 數值簽章法上，建構一個暗道。此暗道，避免了建構在 ElGamal 數值簽章法之暗道的缺點。尤其是消除暗道接收者偽造數值簽章 的可能性。另外，我們也建立一不用傳遞明文之數值簽章法，比 Piveteau 所提的數值簽章法更快，而且沒有機率性問題。更值得一提的 是沒有 Piveteau 數值簽章法之偽造簽章的可能性。 In this dissertation, some properties and applications of two number-theoretic public key cryptoschemes: the RSA cryptoscheme and the ElGamal cryptoscheme, have been explored. Here the RSA cryptoscheme is based on the factoring problem and the ElGamal cryptoscheme is based on the discrete logarithm problem. In the RSA cryptoscheme, one property of the secret exponent is that the short secret exponent cannot be chosen due to Wiener's method. The short secret exponent d will be discoveredif e < N and d < N^1/4, where e is the public exponent and N themodulus. One may choose a large secret exponent d to avoid the attack of Wiener,s method. However, the large secret exponent is not secure. Let N be the product of two large primes p and q. If e < N and 0 < X(N) - d) < N^1/4, where where X(N) means lcm(p -1, q -1), the large secret exponent d can discovered by using the continued fraction method. Here lcm(a,b) denotes the least common multiple of a and b. Besides, if the secret exponent d is approximately near X(N)/2 or some other critical values, the RSA cryptoscheme will also be cracked. Therefore, when selecting the secret exponent, we must consider these properties. In addition to the secret exponent, the secret primes also satisfy some properties. One is that the secret primes are strong primes. In fact, from the literature about the RSA cryptoscheme, no attack can completely break the RSA cryptoscheme even if the secret primes are not strong Primes. Here, we improve Pollard,s method to factor the modulus N. If X(p-1) or X(q-1) has only small prime factors, the secret primes p and q are discovered . So, the property that the secret primes should be strong primes is needed. In the ElGamal cryptoscheme, the property of computing exponentiation is that the base is fixed. Due to the fixed base, exponentiation can be speeded up at the cost of the space. Using this property, We present a new hybrid method for performing modular exponentiation using a hybrid