幾類快速公鑰密碼的設(shè)計(jì)與分析.pdf

1、傳統(tǒng)的公鑰密碼算法速度比較慢，這制約了公鑰密碼的廣泛應(yīng)用。國(guó)內(nèi)外密碼學(xué)界都在加強(qiáng)快速密碼算法的研制與開(kāi)發(fā)，以便使公鑰密碼能夠應(yīng)用到更廣泛的環(huán)境辛。在快速公鑰密碼這一研究領(lǐng)域，本文取得了如下成果： (1)找到了一類新的易解背包問(wèn)題，并用此問(wèn)題構(gòu)造了一個(gè)背包型加密算法。該算法是第一個(gè)基于背包問(wèn)題的概率加密方案。證明了該算法能夠抵抗低密度攻擊和聯(lián)立丟番圖逼近攻擊等。而且該算法的加解密計(jì)算復(fù)雜度是二次的。 (2)找到了RSA公鑰

2、密碼算法的一類弱密鑰，指出如果RSA數(shù)的兩個(gè)素因子的比值能夠被一個(gè)小分?jǐn)?shù)有效逼近的話，則RSA數(shù)是容易分解的。 (3)使用中國(guó)剩余定理構(gòu)造了一個(gè)快速公鑰加密算法，證明了攻擊者重構(gòu)陷門(mén)信息等價(jià)于求解兩個(gè)數(shù)論困難問(wèn)題，即整數(shù)分解和聯(lián)立丟番圖逼近問(wèn)題。 (4)對(duì)RSA問(wèn)題進(jìn)行了推廣，提出了廣義RSA問(wèn)題，給出了廣義RSA問(wèn)題與RSA問(wèn)題之間的聯(lián)系。并用此問(wèn)題構(gòu)造了一個(gè)具有雙重陷門(mén)解密機(jī)制的公鑰密碼算法GRSA．證明了GRSA是

3、單向的當(dāng)且僅當(dāng)廣義RSA計(jì)算問(wèn)題是困難的，GRSA是選擇明文攻擊下語(yǔ)義安全的當(dāng)且僅當(dāng)廣義RSA判定問(wèn)題是困難的。 (5)構(gòu)造了一個(gè)安全性基于兩個(gè)數(shù)學(xué)困難問(wèn)題的公鑰密碼算法，該算法的安全性同時(shí)基于整數(shù)分解和聯(lián)立丟番圖逼近困難問(wèn)題，而且該密碼算法的加解密計(jì)算復(fù)雜度是二次的。 (6)使用矩陣環(huán)上的一個(gè)特殊的組合問(wèn)題構(gòu)造了一個(gè)公鑰加密算法，其安全性與整數(shù)分解問(wèn)題有關(guān)，但并不直接依賴于整數(shù)分解問(wèn)題，而是依賴于一類特殊的矩陣組合問(wèn)題

4、。 (7)從辮群上求根問(wèn)題的困難性出發(fā)構(gòu)造了一個(gè)數(shù)字簽名方案，證明了攻擊者能夠成功地偽造一個(gè)簽名當(dāng)且僅當(dāng)他能夠求解辮群上的求根問(wèn)題。而且從該數(shù)字簽名方案出發(fā)構(gòu)造了一個(gè)基于身份的數(shù)字簽名方案。 (8)對(duì)公鑰密碼算法Naccache-Stern進(jìn)行了安全性分析，指出該算法的解密可以看作一個(gè)群分解問(wèn)題，并說(shuō)明了該攻擊算法攻擊成功的概率依賴于把一個(gè)隨機(jī)的自然數(shù)轉(zhuǎn)化成一個(gè)光滑數(shù)的概率。 (9)對(duì)2000年ACISP會(huì)議上的