背包演算法加密

① 非對稱加密演算法有哪些

RSA、Elgamal、背包演算法、Rabin、D-H、ECC橢圓曲線加密演算法。
非對稱加密（公鑰加密）：指加密和解密使用不同密鑰的加密演算法，也稱為公私鑰加密。假設兩個用戶要加密交換數據，雙方交換公鑰，使用時一方用對方的公鑰加密，另一方即可用自己的私鑰解密。如果企業中有n個用戶，企業需要生成n對密鑰，並分發n個公鑰。假設A用B的公鑰加密消息，用A的私鑰簽名，B接到消息後，首先用A的公鑰驗證簽名，確認後用自己的私鑰解密消息。由於公鑰是可以公開的，用戶只要保管好自己的私鑰即可，因此加密密鑰的分發將變得十分簡單。同時，由於每個用戶的私鑰是唯一的，其他用戶除了可以通過信息發送者的公鑰來驗證信息的來源是否真實，還可以通過數字簽名確保發送者無法否認曾發送過該信息。

② 試簡要寫出DES演算法的加密過程。 什麼是背包問題如何用背包問題構造公鑰密碼演算法。

將64位明文經初始換位後,在密鑰的參與下進行了16輪次非線性變換.
再進行和初始換位相逆的位置變換,便得出密文
背包問題簡單說就是給定一堆物品，每種重量不同，然後將這些物品中的幾種放入一個背包中使重量等於一個給定的值，這時求每種物品個數的時間會隨著堆中物品的種數的增長呈幾何指數增長。也就是說背包問題可看作一個單向函數。最初，公鑰密碼學理論的唯一實現途徑是通過背包問題的，後來又有了更先進的數學模型，如大數分解、離開對數，橢圓曲線等等，而背包問題隨著計算機速度的提高，在理論上已有點靠不住了，所以人們現在已慢慢放棄這一模型。
希望能幫到你~~~

③ 公鑰加密的常見演算法

RSA、ElGamal、背包演算法、Rabin(Rabin的加密法可以說是RSA方法的特例)、Diffie-Hellman (D-H) 密鑰交換協議中的公鑰加密演算法、Elliptic Curve Cryptography（ECC,橢圓曲線加密演算法）。使用最廣泛的是RSA演算法（由發明者Rivest、Shmir和Adleman姓氏首字母縮寫而來）是著名的公開金鑰加密演算法，ElGamal是另一種常用的非對稱加密演算法。

④ 非對稱加密演算法 (RSA、DSA、ECC、DH)

非對稱加密需要兩個密鑰：公鑰(publickey) 和私鑰 (privatekey)。公鑰和私鑰是一對，如果用公鑰對數據加密，那麼只能用對應的私鑰解密。如果用私鑰對數據加密，只能用對應的公鑰進行解密。因為加密和解密用的是不同的密鑰，所以稱為非對稱加密。

非對稱加密演算法的保密性好，它消除了最終用戶交換密鑰的需要。但是加解密速度要遠遠慢於對稱加密，在某些極端情況下，甚至能比對稱加密慢上1000倍。

演算法強度復雜、安全性依賴於演算法與密鑰但是由於其演算法復雜，而使得加密解密速度沒有對稱加密解密的速度快。對稱密碼體制中只有一種密鑰，並且是非公開的，如果要解密就得讓對方知道密鑰。所以保證其安全性就是保證密鑰的安全，而非對稱密鑰體制有兩種密鑰，其中一個是公開的，這樣就可以不需要像對稱密碼那樣傳輸對方的密鑰了。這樣安全性就大了很多。

RSA、Elgamal、背包演算法、Rabin、D-H、ECC (橢圓曲線加密演算法)。使用最廣泛的是 RSA 演算法，Elgamal 是另一種常用的非對稱加密演算法。

收信者是唯一能夠解開加密信息的人，因此收信者手裡的必須是私鑰。發信者手裡的是公鑰，其它人知道公鑰沒有關系，因為其它人發來的信息對收信者沒有意義。

客戶端需要將認證標識傳送給伺服器，此認證標識 (可能是一個隨機數) 其它客戶端可以知道，因此需要用私鑰加密，客戶端保存的是私鑰。伺服器端保存的是公鑰，其它伺服器知道公鑰沒有關系，因為客戶端不需要登錄其它伺服器。

數字簽名是為了表明信息沒有受到偽造，確實是信息擁有者發出來的，附在信息原文的後面。就像手寫的簽名一樣，具有不可抵賴性和簡潔性。

簡潔性：對信息原文做哈希運算，得到消息摘要，信息越短加密的耗時越少。

不可抵賴性：信息擁有者要保證簽名的唯一性，必須是唯一能夠加密消息摘要的人，因此必須用私鑰加密 (就像字跡他人無法學會一樣)，得到簽名。如果用公鑰，那每個人都可以偽造簽名了。

問題起源：對1和3，發信者怎麼知道從網上獲取的公鑰就是真的？沒有遭受中間人攻擊？

這樣就需要第三方機構來保證公鑰的合法性，這個第三方機構就是 CA (Certificate Authority)，證書中心。

CA 用自己的私鑰對信息原文所有者發布的公鑰和相關信息進行加密，得出的內容就是數字證書。

信息原文的所有者以後發布信息時，除了帶上自己的簽名，還帶上數字證書，就可以保證信息不被篡改了。信息的接收者先用 CA給的公鑰解出信息所有者的公鑰，這樣可以保證信息所有者的公鑰是真正的公鑰，然後就能通過該公鑰證明數字簽名是否真實了。

RSA 是目前最有影響力的公鑰加密演算法，該演算法基於一個十分簡單的數論事實：將兩個大素數相乘十分容易，但想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰，即公鑰，而兩個大素數組合成私鑰。公鑰是可發布的供任何人使用，私鑰則為自己所有，供解密之用。

A 要把信息發給 B 為例，確定角色：A 為加密者，B 為解密者。首先由 B 隨機確定一個 KEY，稱之為私鑰，將這個 KEY 始終保存在機器 B 中而不發出來；然後，由這個 KEY 計算出另一個 KEY，稱之為公鑰。這個公鑰的特性是幾乎不可能通過它自身計算出生成它的私鑰。接下來通過網路把這個公鑰傳給 A，A 收到公鑰後，利用公鑰對信息加密，並把密文通過網路發送到 B，最後 B 利用已知的私鑰，就能對密文進行解碼了。以上就是 RSA 演算法的工作流程。

由於進行的都是大數計算，使得 RSA 最快的情況也比 DES 慢上好幾倍，無論是軟體還是硬體實現。速度一直是 RSA 的缺陷。一般來說只用於少量數據加密。RSA 的速度是對應同樣安全級別的對稱密碼演算法的1/1000左右。

比起 DES 和其它對稱演算法來說，RSA 要慢得多。實際上一般使用一種對稱演算法來加密信息，然後用 RSA 來加密比較短的公鑰，然後將用 RSA 加密的公鑰和用對稱演算法加密的消息發送給接收方。

這樣一來對隨機數的要求就更高了，尤其對產生對稱密碼的要求非常高，否則的話可以越過 RSA 來直接攻擊對稱密碼。

和其它加密過程一樣，對 RSA 來說分配公鑰的過程是非常重要的。分配公鑰的過程必須能夠抵擋中間人攻擊。假設 A 交給 B 一個公鑰，並使 B 相信這是A 的公鑰，並且 C 可以截下 A 和 B 之間的信息傳遞，那麼 C 可以將自己的公鑰傳給 B，B 以為這是 A 的公鑰。C 可以將所有 B 傳遞給 A 的消息截下來，將這個消息用自己的密鑰解密，讀這個消息，然後將這個消息再用 A 的公鑰加密後傳給 A。理論上 A 和 B 都不會發現 C 在偷聽它們的消息，今天人們一般用數字認證來防止這樣的攻擊。

(1) 針對 RSA 最流行的攻擊一般是基於大數因數分解。1999年，RSA-155 (512 bits) 被成功分解，花了五個月時間（約8000 MIPS 年）和224 CPU hours 在一台有3.2G 中央內存的 Cray C916計算機上完成。

RSA-158 表示如下：

2009年12月12日，編號為 RSA-768 (768 bits, 232 digits) 數也被成功分解。這一事件威脅了現通行的1024-bit 密鑰的安全性，普遍認為用戶應盡快升級到2048-bit 或以上。

RSA-768表示如下：

(2) 秀爾演算法
量子計算里的秀爾演算法能使窮舉的效率大大的提高。由於 RSA 演算法是基於大數分解 (無法抵抗窮舉攻擊)，因此在未來量子計算能對 RSA 演算法構成較大的威脅。一個擁有 N 量子位的量子計算機，每次可進行2^N 次運算，理論上講，密鑰為1024位長的 RSA 演算法，用一台512量子比特位的量子計算機在1秒內即可破解。

DSA (Digital Signature Algorithm) 是 Schnorr 和 ElGamal 簽名演算法的變種，被美國 NIST 作為 DSS (DigitalSignature Standard)。 DSA 是基於整數有限域離散對數難題的。

簡單的說，這是一種更高級的驗證方式，用作數字簽名。不單單只有公鑰、私鑰，還有數字簽名。私鑰加密生成數字簽名，公鑰驗證數據及簽名，如果數據和簽名不匹配則認為驗證失敗。數字簽名的作用就是校驗數據在傳輸過程中不被修改，數字簽名，是單向加密的升級。

橢圓加密演算法（ECC）是一種公鑰加密演算法，最初由 Koblitz 和 Miller 兩人於1985年提出，其數學基礎是利用橢圓曲線上的有理點構成 Abel 加法群上橢圓離散對數的計算困難性。公鑰密碼體制根據其所依據的難題一般分為三類：大整數分解問題類、離散對數問題類、橢圓曲線類。有時也把橢圓曲線類歸為離散對數類。

ECC 的主要優勢是在某些情況下它比其他的方法使用更小的密鑰 (比如 RSA)，提供相當的或更高等級的安全。ECC 的另一個優勢是可以定義群之間的雙線性映射，基於 Weil 對或是 Tate 對；雙線性映射已經在密碼學中發現了大量的應用，例如基於身份的加密。不過一個缺點是加密和解密操作的實現比其他機制花費的時間長。

ECC 被廣泛認為是在給定密鑰長度的情況下，最強大的非對稱演算法，因此在對帶寬要求十分緊的連接中會十分有用。

比特幣錢包公鑰的生成使用了橢圓曲線演算法，通過橢圓曲線乘法可以從私鑰計算得到公鑰， 這是不可逆轉的過程。

https://github.com/esxgx/easy-ecc

Java 中 Chipher、Signature、KeyPairGenerator、KeyAgreement、SecretKey 均不支持 ECC 演算法。

https://www.jianshu.com/p/58c1750c6f22

DH，全稱為"Diffie-Hellman"，它是一種確保共享 KEY 安全穿越不安全網路的方法，也就是常說的密鑰一致協議。由公開密鑰密碼體制的奠基人 Diffie 和 Hellman 所提出的一種思想。簡單的說就是允許兩名用戶在公開媒體上交換信息以生成"一致"的、可以共享的密鑰。也就是由甲方產出一對密鑰 (公鑰、私鑰)，乙方依照甲方公鑰產生乙方密鑰對 (公鑰、私鑰)。

以此為基線，作為數據傳輸保密基礎，同時雙方使用同一種對稱加密演算法構建本地密鑰 (SecretKey) 對數據加密。這樣，在互通了本地密鑰 (SecretKey) 演算法後，甲乙雙方公開自己的公鑰，使用對方的公鑰和剛才產生的私鑰加密數據，同時可以使用對方的公鑰和自己的私鑰對數據解密。不單單是甲乙雙方兩方，可以擴展為多方共享數據通訊，這樣就完成了網路交互數據的安全通訊。

具體例子可以移步到這篇文章： 非對稱密碼之DH密鑰交換演算法

參考：
https://blog.csdn.net/u014294681/article/details/86705999

https://www.cnblogs.com/wangzxblog/p/13667634.html

https://www.cnblogs.com/taoxw/p/15837729.html

https://www.cnblogs.com/fangfan/p/4086662.html

https://www.cnblogs.com/utank/p/7877761.html

https://blog.csdn.net/m0_59133441/article/details/122686815

https://www.cnblogs.com/muliu/p/10875633.html

https://www.cnblogs.com/wf-zhang/p/14923279.html

https://www.jianshu.com/p/7a927db713e4

https://blog.csdn.net/ljx1400052550/article/details/79587133

https://blog.csdn.net/yuanjian0814/article/details/109815473

⑤ 非對稱加密的代表例子有哪些

非對稱加密主要演算法：RSA、Elgamal、背包演算法、Rabin、D-H、ECC（橢圓曲線加密演算法）。
使用最廣泛的是RSA演算法，Elgamal是另一種常用的非對稱加密演算法。
經典的非對稱加密演算法如RSA演算法等安全性都相當高.
非對稱加密的典型應用是數字簽名。

⑥ 十大常見密碼加密方式

一、密鑰散列

採用MD5或者SHA1等散列演算法，對明文進行加密。嚴格來說，MD5不算一種加密演算法，而是一種摘要演算法。無論多長的輸入，MD5都會輸出一個128位（16位元組）的散列值。而SHA1也是流行的消息摘要演算法，它可以生成一個被稱為消息摘要的160位（20位元組）散列值。MD5相對SHA1來說，安全性較低，但是速度快；SHA1和MD5相比安全性高，但是速度慢。

二、對稱加密

採用單鑰密碼系統的加密方法，同一個密鑰可以同時用作信息的加密和解密，這種加密方法稱為對稱加密。對稱加密演算法中常用的演算法有：DES、3DES、TDEA、Blowfish、RC2、RC4、RC5、IDEA、SKIPJACK等。

三、非對稱加密

非對稱加密演算法是一種密鑰的保密方法，它需要兩個密鑰來進行加密和解密，這兩個密鑰是公開密鑰和私有密鑰。公鑰與私鑰是一對，如果用公鑰對數據進行加密，只有用對應的私鑰才能解密。非對稱加密演算法有：RSA、Elgamal、背包演算法、Rabin、D-H、ECC（橢圓曲線加密演算法）。

四、數字簽名

數字簽名（又稱公鑰數字簽名）是只有信息的發送者才能產生的別人無法偽造的一段數字串，這段數字串同時也是對信息的發送者發送信息真實性的一個有效證明。它是一種類似寫在紙上的普通的物理簽名，但是在使用了公鑰加密領域的技術來實現的，用於鑒別數字信息的方法。

五、直接明文保存

早期很多這樣的做法，比如用戶設置的密碼是「123」，直接就將「123」保存到資料庫中，這種是最簡單的保存方式，也是最不安全的方式。但實際上不少互聯網公司，都可能採取的是這種方式。

六、使用MD5、SHA1等單向HASH演算法保護密碼

使用這些演算法後，無法通過計算還原出原始密碼，而且實現比較簡單，因此很多互聯網公司都採用這種方式保存用戶密碼，曾經這種方式也是比較安全的方式，但隨著彩虹表技術的興起，可以建立彩虹表進行查表破解，目前這種方式已經很不安全了。

七、特殊的單向HASH演算法

由於單向HASH演算法在保護密碼方面不再安全，於是有些公司在單向HASH演算法基礎上進行了加鹽、多次HASH等擴展，這些方式可以在一定程度上增加破解難度，對於加了「固定鹽」的HASH演算法，需要保護「鹽」不能泄露，這就會遇到「保護對稱密鑰」一樣的問題，一旦「鹽」泄露，根據「鹽」重新建立彩虹表可以進行破解，對於多次HASH，也只是增加了破解的時間，並沒有本質上的提升。

八、PBKDF2

該演算法原理大致相當於在HASH演算法基礎上增加隨機鹽，並進行多次HASH運算，隨機鹽使得彩虹表的建表難度大幅增加，而多次HASH也使得建表和破解的難度都大幅增加。

九、BCrypt

BCrypt 在1999年就產生了，並且在對抗 GPU/ASIC 方面要優於 PBKDF2，但是我還是不建議你在新系統中使用它，因為它在離線破解的威脅模型分析中表現並不突出。

十、SCrypt

SCrypt 在如今是一個更好的選擇：比 BCrypt設計得更好（尤其是關於內存方面）並且已經在該領域工作了 10 年。另一方面，它也被用於許多加密貨幣，並且我們有一些硬體（包括 FPGA 和 ASIC）能實現它。 盡管它們專門用於采礦，也可以將其重新用於破解。

⑦ 非對稱加密演算法的主要演算法

RSA、Elgamal、背包演算法、Rabin、D-H、ECC（橢圓曲線加密演算法）。
使用最廣泛的是RSA演算法，Elgamal是另一種常用的非對稱加密演算法。
Elgamal由Taher Elgamal於1985年發明，其基礎是DiffieˉHellman密鑰交換演算法，後者使通信雙方能通過公開通信來推導出只有他們知道的秘密密鑰值[DiffieˉHellman]。DiffieˉHellman是Whitfield Diffie和Martin Hellman於1976年發明的，被視為第一種 非對稱加密演算法，DiffieˉHellman 與RSA的不同之處在於，DiffieˉHellman不是加密演算法，它只是生成可用作對稱密鑰的秘密數值。在DiffieˉHellman密鑰交換過程中，發送方和接收方分別生成一個秘密的隨機數，並根據隨機數推導出公開值，然後，雙方再交換公開值。DiffieˉHellman演算法的基礎是具備生成共享密鑰的能力。只要交換了公開值，雙方就能使用自己的私有數和對方的公開值來生成對稱密鑰，稱為共享密鑰，對雙方來說，該對稱密鑰是相同的，可以用於使用對稱加密演算法加密數據。
與RSA相比，DiffieˉHellman的優勢之一是每次交換密鑰時都使用一組新值，而使用RSA演算法時，如果攻擊者獲得了私鑰，那麼他不僅能解密之前截獲的消息，還能解密之後的所有消息。然而，RSA可以通過認證（如使用X.509數字證書）來防止中間人攻擊，但Diff ieˉHellman在應對中間人攻擊時非常脆弱。

⑧ 背包演算法為什麼無法實現數字簽名

數字簽名採用了雙重加密的方法來實現防偽、防賴。其原理為：

（1） 被發送文件用SHA編碼加密產生128bit的數字摘要（見上節）。

（2） 發送方用自己的私用密鑰對摘要再加密，這就形成了數字簽名。

（3） 將原文和加密的摘要同時傳給對方。

（4） 對方用發送方的公共密鑰對摘要解密，同時對收到的文件用SHA編碼加密產生又一摘要。

（5） 將解密後的摘要和收到的文件在接收方重新加密產生的摘要相互對比。如兩者一致，則說明傳送過程中信息沒有被破壞或篡改過。否則不然。

所謂"數字簽名"就是通過某種密碼運算生成一系列符號及代碼組成電子密碼進行簽名，來代替書寫簽名或印章，對於這種電子式的簽名還可進行技術驗證，其驗證的准確度是一般手工簽名和圖章的驗證而無法比擬的。"數字簽名"是目前電子商務、電子政務中應用最普遍、技術最成熟的、可操作性最強的一種電子簽名方法。它採用了規范化的程序和科學化的方法，用於鑒定簽名人的身份以及對一項電子數據內容的認可。它還能驗證出文件的原文在傳輸過程中有無變動，確保傳輸電子文件的完整性、真實性和不可抵賴性。

數字簽名在ISO7498-2標准中定義為："附加在數據單元上的一些數據，或是對數據單元所作的密碼變換，這種數據和變換允許數據單元的接收者用以確認數據單元來源和數據單元的完整性，並保護數據，防止被人（例如接收者）進行偽造"。美國電子簽名標准（DSS，FIPS186-2）對數字簽名作了如下解釋："利用一套規則和一個參數對數據計算所得的結果，用此結果能夠確認簽名者的身份和數據的完整性"。按上述定義PKI（Public Key Infrastructino 公鑰基礎設施）提供可以提供數據單元的密碼變換，並能使接收者判斷數據來源及對數據進行驗證。

⑨ Merkle-Hellman背包演算法的分類

背包加密分為加法背包和乘法背包。
1、加法背包：我們知道，1<2,1+2<4,1+2+4<8,1+2+4+8<16,……，那麼如果我們選擇這樣一些數，這些數從小到大排列，如果前面所有的數加起來的值總小於後面的數，那麼這些數就可以構成一個背包，我們給一個這個背包裡面的某些數的和，這個數就是被加密的數，由這個背包組成這個數只有一種組合方式，這個方式就是秘密了，例如給大家一個封包（2，3，6，12，24，48），由這個背包里的某些數構成的數：86，你知道86怎麼來的嗎？當然，你看著背包裡面的內容，可以知道是由2+12+24+48得到的，如果你沒有這個背包，而是直接得到這個86，你知道組成這個86的最小的數是多少嗎？你無法知道，因為加起來等於86的數非常多：85+1=86，84+2=86等等，你是無法知道的，所以，背包加密非常難破。
2、乘法背包：乘法背包比加法背包更復雜，不僅是運算量大了很多，更重要的是你得到的一個被加密了的數據更大，一般都是上億的，而且在許多機密的機關裡面，背包的數據都不是有這個單位，而是用位。我們知道，1<2,1*2<3,1*2*3<7,1*2*3*7<43,1*2*3*7*42<1765, 數字的增長還是很快的，之所以復雜，就是因為數字很大啊！背包的特點是：如果背包裡面的數據按小到大排列，那麼，前面所有數據的乘積小於後面的任何一個元素，這個就是背包的特點，是不是很簡單，但是要知道乘積的數字的增長是非常快的！