基于NPC和ECDLP的陷門背包公鑰密碼體制設(shè)計(jì)與分析.pdf

1、基于背包問題的公鑰密碼算法是密碼學(xué)歷史上最早被設(shè)計(jì)出來的幾個公鑰密碼算法之一。由于背包密碼具有快速加、解密的優(yōu)勢和背包問題的NP完全性，在很長一段時間內(nèi)背包算法受到普遍的關(guān)注。在背包型密碼算法的發(fā)展歷史中，密碼學(xué)界提出了很多背包型加密算法。然而，這些背包算法容易遭受低密度子集和攻擊、GCD攻擊、聯(lián)立丟番圖逼近攻擊以及正交格攻擊等。
　　根據(jù)公鑰密碼體制所依賴的困難問題，大多數(shù)公鑰密碼體制可以分為兩大類：一類是建立在數(shù)論問題基礎(chǔ)之上

2、，另一類則以背包問題為基礎(chǔ)。這兩種類型的公鑰密碼體制各有利弊?；跀?shù)論難題的公鑰密碼系統(tǒng)保密性較強(qiáng)，但加、解密速度比較慢；基于背包問題的公鑰密碼系統(tǒng)的加、解密速度較快，但在實(shí)踐過程中，大多數(shù)的背包方案都已被破解，或者證明存在缺陷?；诖?，為了兼顧加、解密算法的速度和安全性，本文對基于背包問題的現(xiàn)有公鑰密碼算法和GF(p)上橢圓曲線密碼體制進(jìn)行了深入的研究，本文所做的主要工作與創(chuàng)新處如下：
　　1.對背包型公鑰密碼體制的研究狀況進(jìn)行

3、了系統(tǒng)的研究，總結(jié)出了背包型公鑰體制存在的問題。
　　2.認(rèn)真學(xué)習(xí)橢圓曲線密碼體制的相關(guān)知識；研究了橢圓曲線上的基本算法及橢圓曲線的基本密碼學(xué)性質(zhì)、討論了有限域的確定、安全橢圓曲線的選取算法以及明文映射到橢圓曲線上的算法等。
　　3.提出三種基于NP完全問題的背包公鑰密碼體制方案。三種方案的安全性是基于背包的難解性以及分解兩個大素?cái)?shù)的積的難解性。方案1是一個加密/解密都很快的系統(tǒng)，缺點(diǎn)是密鑰尺寸依賴于所需要的安全水平；由于方

4、案1密鑰量較大，提出了方案2，該方案僅僅改變私鑰且采用一列超遞增向量代替可逆矩陣，減少了密鑰尺寸；最后，在對前面兩種方案進(jìn)行優(yōu)化的基礎(chǔ)上提出了方案3，該方案中的矩陣ε利用了方案1中的線性性來仔細(xì)隱蔽了超遞增向量從而提高了該方案的安全性。
　　4.提出一個基于橢圓曲線對數(shù)問題的背包公鑰密碼體制。通過選擇適當(dāng)?shù)膮?shù)，就能控制在ECC中元素的數(shù)量與它們的比特大小，這對掩飾脆弱的背包起到很好的效果。利用現(xiàn)有的對橢圓曲線密碼體制的攻擊算法分