基于格困難問題的公鑰加密算法的設(shè)計與安全性證明.pdf

1、基于大整數(shù)因子分級和離散對數(shù)的傳統(tǒng)公鑰密碼體制運算速度比較慢，這限制了它們的應(yīng)用范圍。隨著量子計算的發(fā)展，基于新型困難問題密碼算法設(shè)計的重要性被提升到了一個前所未有的高度?；诟窭щy問題的快速公鑰算法是新型密碼設(shè)計的一個重要方向，本文對此進行了研究，取得了如下成果： （1）給出了一條NTRU加密算法參數(shù)選擇規(guī)則：要求NTRU的三個參數(shù)n，p，q滿足分圓多項式∑n-1 i=0 xi在GF（p）和GF（q）上不可分解。此時，對于環(huán)R

2、=Z[x]/（xn-1）的任意一個多項式f≠k∑n-1 i=0 xi（k∈Z），只要滿足f（1）≠0，f在模p和模q意義下的逆一定存在。這不僅保證了密鑰生成的效率，而且避免了弱密鑰的產(chǎn)生。 （2）當NTRU的公鑰h與Xn－1的在環(huán)R=Z[x]/（xn-1）上的最大公因式gcd（h，Xn－1）的次數(shù)不為零時，構(gòu)造了一種類似于循環(huán)碼譯碼的方法結(jié)合格基規(guī)約算法破解用h加密產(chǎn)生的密文。進一步的，若gcd（h，Xn-1）的次數(shù)為k，攻擊者

3、只需用格基規(guī)約算法求解（n-k）維格中的SVP問題即可得到明文。 （3）對三輪OAEP明文填充方案進行了分析，指出當攻擊者可以獲得填充方案中的隨機串時，三輪OAEP并不能讓RSA，ELGamal等加密算法達到適應(yīng)性選擇密文攻擊下的語義安全性。對三輪OAEP進行了改進，使其在填充算法中隨機串泄露的情況下仍然可以讓加密算法達到適應(yīng)性選擇密文攻擊下的語義安全性，并在隨機預(yù)言機模型下證明了這個結(jié)論。 （4）為NTRU加密算法設(shè)計

4、了一個明文填充方案。在加密算法選擇適當參數(shù)保證合法加密不會發(fā)生解密失敗的條件下，該填充方案能使NTRU達到適應(yīng)性選擇密文攻擊下的語義安全性。與現(xiàn)有的NTRU明文填充方案NAEP相比，我們的填充算法更簡潔更便于實現(xiàn)。 （5）提出了一種改進的NTRU加密算法。改進算法解密時能精確消除加密過程中所用的工作密鑰，避免了像NTRU那樣公鑰所對應(yīng)的CS格中任意足夠短的向量都可以用來解密的情況。只有原密鑰向量可以用來解密使得格基規(guī)約技術(shù)不能直