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

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

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

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

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