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

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

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

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

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