短CRT指數RSA密碼系統之研究

Abstract

RSA是目前最被為廣泛使用的公開金鑰密碼系統，此密碼系統主要是植基於大數因數分解的困難度上，所以具有相當高的安全性。然而，由於其加密與解密的過程，需要做大指數模乘法的運算，這使得在使用RSA密碼系統時，加解密花費過長的時間成為其最大的缺點。因此，如何改善RSA加密與解密的運算速度，一直是許多密碼學家研究的重要問題。一般的方法都是選擇較短位元數的公鑰或私鑰指數。可惜的是，在傳統的RSA演算法裡，並不能同時選擇短指數的公鑰與私鑰，兩者只能取其一。1982年，Quisquater和Couvreur提出一種快速RSA解密的辯讀方法，這樣的技巧主要是基於中國餘式定理(CRT)，我們稱之為CRT解密。其解密速度比傳統RSA密碼系統的解密速度約快了四倍。隨後在1990年，Wiener建議可以使用基於短CRT指數作解密的RSA密碼系統，我們稱之為短CRT指數RSA密碼系統。CRT指數即私密金鑰指數d模掉p-1 或q-1 後的餘數。而這樣的技巧可以更加提升解密的速度，且能防止短私鑰指數的攻擊；但相對的卻不能控制公開金鑰指數的長度，反而使得加密的時間變得較費時。

有鑑於之前的發展，本論文首先提出在CRT指數被洩漏情況下的三種攻擊方法。另一方面，本論文欲利用歐幾里得演算法，設計新的短CRT指數RSA密碼系統。在我們的密碼系統下，加密可比Wiener所提出的短CRT指數RSA密碼系統快了一倍，而解密仍然是利用短CRT指數的特性作解密動作。在參數方面，我們的RSA模數p跟q分別為平衡狀態的512位元、公開金鑰指數e為512位元、私鑰的CRT指數為160位元。我們並將所提出的密碼系統與傳統的RSA密碼系統作比較，包括加密與解密所使用的模乘法數，加密與解密所花費的單位時間估計等等…。另外，我們並分析目前短指數攻擊法及短CRT指數攻擊法對其所造成的安全性問題。