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

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

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

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

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