基于NPC和ECDLP的陷門背包公鑰密碼體制設計與分析.pdf

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

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

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

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