求多項(xiàng)式方程的小值解及其應(yīng)用.pdf

1、RSA密碼體制由Rivest，Shamir及Adleman始創(chuàng)[41]，是目前世界上所知應(yīng)用最廣泛的公鑰密碼體制，使用RSA最主要的缺點(diǎn)是加解密操作的費(fèi)用相當(dāng)大．多素?cái)?shù)RSA為標(biāo)準(zhǔn)RSA密碼體制的一個(gè)推廣，其中模由多于兩個(gè)的素?cái)?shù)相乘得來(lái)，當(dāng)加密操作執(zhí)行時(shí)，模每個(gè)素?cái)?shù)，而后合并使用中國(guó)剩余定理．加密的代價(jià)降到每個(gè)素?cái)?shù)(對(duì)于確定大小的模)．因此，當(dāng)需要降低成本時(shí)，多素?cái)?shù)RSA可能為RSA的一個(gè)現(xiàn)實(shí)的選擇．RSA的安全性自它創(chuàng)造之日起已被很好

2、的研究(參見(jiàn)Boneh[6])．若多素?cái)?shù)RSA現(xiàn)在實(shí)行它的安全性需被更進(jìn)一步的研究． 目前，存在部分私鑰泄露攻擊，攻擊者擁有私鑰比特的某些知識(shí)并用它來(lái)攻破系統(tǒng)，結(jié)果是具有實(shí)際意義的．因?yàn)榭赡芟魅跛借€的比特． 1998年，Boneh，Durfee和Frankel在[2]提出RSA的幾種部分私鑰泄露攻擊，其中的某些攻擊要求知道私鑰的最少有效比特(LSBs)，另—些要求知道最多有效比特(MSBs)．另外，在他們的攻擊中，公鑰必

3、須是相對(duì)小的．Wiener的攻擊[46]及Boneh和Durfee[4]的改進(jìn)可被看作部分私鑰泄露攻擊，其中，已知的最多有效比特均等于0． 在[2]中提出的問(wèn)題是是否存在RSA的密鑰泄露攻擊，可以對(duì)比模的平方根大小大的公鑰起作用．2003年，Blomer和May[1]描述了一些攻擊，允許大一點(diǎn)的公鑰，但仍未達(dá)到模的實(shí)際大小，而后Ernst,Jochemsz等人在[17]中提出攻擊對(duì)實(shí)際大小的公鑰，它可以逐漸達(dá)到實(shí)際的私鑰大小的算

4、法． 在96歐密會(huì)上，Coppersmith提出一種尋找雙變量整系數(shù)多項(xiàng)式方程小值根的算法，該算法基于格基約化算法．在此基礎(chǔ)上發(fā)展了分解因子攻擊，它適用于知道部分因子的與多素?cái)?shù)RSA模相同形式的整數(shù)．該攻擊是Boneh，Durfee和Howgrave-Graham的格基分解因子思想的推廣，模的形式為N=prq對(duì)平衡r素?cái)?shù)RSA假設(shè)知道N的r個(gè)素?cái)?shù)中的v個(gè)1≤v≤r-2，另外對(duì)零或者更多余下的未知素?cái)?shù)和私鑰，知道最多或最少的有效比

5、特． Coppersmith的解決雙變量多項(xiàng)式方程的算法被Howgrave-Graham在[24]中進(jìn)一步簡(jiǎn)化．除了更易于理解和應(yīng)用，Howgrave-Graham的方法的一個(gè)顯著的優(yōu)點(diǎn)是可以啟發(fā)式的延伸到多變量多項(xiàng)式方程．在此基礎(chǔ)上Jean-SébastienCoron在[15]中提出了一項(xiàng)簡(jiǎn)化算法，可以在得知n=pq中p的高位log2n/4比特的前提下分解n． 本論文是應(yīng)用Jean-SébastienCoron的簡(jiǎn)化

6、算法來(lái)求解三變量整系數(shù)多項(xiàng)式方程的小根，可以在得知n=pqr中p,q的高位或低位log2n/5比特的前提下分解n． 本文主要結(jié)論為： 定理3.1令p(x,y,z)為z上三變量不可約多項(xiàng)式，每個(gè)單變量的最高次數(shù)是δ.令X,Y和Z為期望的整數(shù)解(x0,y0,z0)的上界．令W=maxi,j,k︱Pijk︱XiYjZk對(duì)某些ε>0，XYZ

7、y0,z0)=0,︱x0︱≤X,︱y0︱≤Y1,︱z0︱≤Z的所有整數(shù)對(duì)(x0,y0,z0)． 該攻擊如同多素?cái)?shù)RSA的其它格基攻擊一樣建立在代數(shù)獨(dú)立假設(shè)上． 定理3.3對(duì)任意的ε>0，給定N=PQRY及P,Q的高位或低位1/5logN2比特，我們可以在多項(xiàng)式時(shí)間(logN)內(nèi)得到N的分解式． 定理4.1令p(x1,x2,…,xr)為整數(shù)上的r變量多項(xiàng)式，每個(gè)單變量的最高次數(shù)是δ． 令X1,X2,…,Xr

8、為期望的整數(shù)解x1,x2,…,xr的上界． 令W=maxi1,i2,…,ir︱Pi1,i2,…,Xi11Xi2,…Xirrr．對(duì)某些ε>0，Xi11Xi22…XIRR0，對(duì)于N=P1P2…Pr給定其中