對一堆文件中的每一個文件單獨加密，如果已知其中一些文件的明文和密文，是否會導致能推斷出密鑰？

01-18

假設已經有M個文件的明文和密文，請問是否會導致能推斷出密鑰？為什麼？
這種可能性是否會隨著M的數量增加而增長？
更新：
對於非對稱加密，問題中的密鑰指的是解密用密鑰。

佔個坑，晚些時候我會補完答案。

有興趣的知乎er應該可以從下面已有的兩個問題中得到現在這個問題的答案

如何理解語義安全(semantic security)?

多次使用「一次性密鑰」(one-time pad)為什麼不安全？

===================2017年2月更新======================

答案：能。（It"s possible. ）

第一個例子，攻擊者利用已知的明文-密文對做驗證，能暴力破解出密鑰。

有興趣的知乎er可以深入閱讀這篇關於用FPGA暴力破解DES的文章，2006年的，9天能破解出DES密鑰，硬體成本不到10000美刀。https://www.iacr.org/archive/ches2006/09/09.pdfhttps://www.iacr.org/archive/ches2006/09/09.pdf

估計到今年，也就是2017，可能2000 USD以下就能買到同樣計算能力的設備，大約是一台略好的遊戲本的價格。

第二個例子，攻擊者能利用密文「撞」出明文，來自@劉巍然-學酥的知乎專欄

還有，利用公鑰和有問題的RSA簽名，找出RSA私鑰，Black Hat 2016 https://www.blackhat.com/docs/us-16/materials/us-16-Ortisi-Recover-A-RSA-Private-Key-From-A-TLS-Session-With-Perfect-Forward-Secrecy.pdf

以上都是針對是否「能」（possible）進行的解釋。

密碼學演算法研究追求的答案不是「能不能」，而是對應的攻擊是否「可行」(feasible)或者「高效」(efficient)。好的加密演算法，應該是能在加長密鑰之後，使攻擊者所需要的資源以指數（或者至少是超多項式）級別增長，也就是讓攻擊變得「不可行」（infeasible）、「不高效」（inefficient）。

之所以NIST和NSA會不斷更新在接下來20年類用的密鑰長度和加密演算法，就是因為硬體運算速度的增長、新的並行設計和攻擊演算法的改進。去年，NSA對政府top secret的加密建議已然是使用AES-256-GCM。同時建議沒有轉ECC的機構暫停轉換，直接轉換到post-quantum crypto。

下面是對密碼學演算法的兩個性質和TLS的基本科普，為的是澄清一些常見的誤解。與本問題不直接相關。

一. 加密演算法(encryption scheme)的兩個維度：

1. 是對稱還是非對稱加密（symmetric vs. asymmetric/public）

2. 是確定性加密還是非確定性加密 (deterministic vs. non-deterministic)

兩個維度相對獨立，也就是說，「對稱「並不意味著「確定性」。下面是對常見演算法的歸納。

教科書RSA加密（textbook RSA）是個確定性演算法，包括其對應的簽名演算法也是。

而引入了隨機的初始化向量(IV)後，AES-CTR等加密方式此時有著一定的隨機性質。即使加密相同的明文，IV變化後，密文也將隨之變化。

因此，武斷地說對稱演算法都是確定性加密，或者說公鑰演算法都是非確定性加密，都是極其不嚴謹的。

二. TLS的演算法族(cipher suite)怎麼理解

見 The Transport Layer Security (TLS) Protocol Version 1.2 和Cipher suite - Wikipedia

TLS_RSA_WITH_AES_256_CBC_SHA256

這個是指，用RSA做密鑰傳輸（即用server的RSA公鑰加密pms傳給server），也用RSA做簽名演算法(驗證證書和簽名)。payload用AES-256-CBC加密, Hash演算法是SHA256。Hash演算法會用在簽名驗證、PRF和為保護payload完整性所使用的HMAC中。

另一個例子

TLS_DHE_RSA_WITH_AES_256_CBC_SHA

這個是指，用ephemeral Diffie-Hellman做密鑰交換，用RSA數字簽名。payload用AES-256-CBC,Hash演算法是SHA256。同樣，Hash演算法會用在簽名驗證、PRF和為保護payload完整性所使用的HMAC中

以上兩個例子可以說明，TLS里， RSA既可以被用作密鑰交換的手段，也可以被用作鑒權(authentication)所需的簽名演算法。

籠統地說RSA沒有前向安全性(forward secrecy)是不行的，因為TLS_DHE_RSA_XXX 是有前向安全性的 https://eprint.iacr.org/2011/219.pdf

在電影模仿遊戲中，圖靈僅僅通過推測明文中可能會出現weather（天氣）這個詞，就通過密文推算出了密鑰。

事實也如此，對於對稱加密，明文、密文和密鑰（含加密演算法）之間的關係是完全對應的。

所以，和文件都沒有關係，只要有足夠長的密文和明文的對應，理論上密鑰就一定可以破解出來，只是個時間問題。

你這種攻擊方式叫做：「已知明文」。

一般來說，攻擊難度介於「僅知密文」和「選擇明文」之間。

這叫已知明文和密文的密碼攻擊。

題主是不是想問存在一些明文&<--------&>密文映射關係，能不能推導出密鑰？

如果是古代的換字密碼，這個顯而易見就能推導出來，甚至不用推導，明文到密文就是映射表。

但是將換字密碼稍作改動，比如分組後對每組明文進行不同密鑰的替換，也許單獨一個文件比較難看出端倪，但是對大量相同模式的映射進行分析還是可以找出一些共同點的。

到了現代，ECB模式就存在題主所述的情況，對明文進行分塊，使用同一個變換方式進行加密 $C_{0} = Enc(P_{0})$ ，如果能收集到大量（明文-------密文）映射，還是很有可能破解出內容來的。

CBC就防止了ECB出現的問題，具體做法就是將加密後的輸出混入到下一個輸入塊，即明文加密前首先和當前加密結果進行異或：

$egin{align} C_{0} = Enc(P_{0} oplus IV) \ C_{1} = Enc(P_{1} oplus C_{0}) \ C_{2} = Enc(P_{2} oplus C_{1}) end{align}$

在內容有稍許偏差的時候，CBC模式相當於每一個塊都使用了變換過的明文進行加密，保證了不會出現ECB的問題。所以IV並沒有什麼用處。。。胡亂填一個只會影響第一個塊解密。

下面就是非對稱密碼了(比較牽強。。。不看也罷)，不需要大量文件，兩個就夠了。

首先是RSA

RSA的工作原理非常簡潔精彩，加密解密過程就是同一個操作： $C=P^{e} mod N\ P=C^{d} mod N$

原理就是 $C equiv C^{d imes e} mod N$ 由於 $d imes eequiv 1(mod phi(p imes q))$ 即d和e互為模逆

現在存在一種情況，Alice和Bob對同一個消息P使用不同且互質的e進行加密分別得到了 $C_{a} = P^{e_{a}} mod N$ 和 $C_{b} = P^{e_{b}} mod N$ ，千不該萬不該他們共享同一對pq，導致N相同。那麼存在一對xy使得 $e_{a} imes x + e_{b} imes y = 1$ ，使用擴展歐幾里得輾轉相除便可以算出x和y。

現在將兩個密文進行一些運算：

$egin{align} C_{a}^{x} imes C_{b}^{y}= P^{e_{a} imes x} imes P^{e_{b} imes y}\ = P^{e_{a} imes x + e_{b} imes y} \=P^{1} end{align}$ 恢復出明文P。

然後是ECC

直接無恥傳送門：為什麼當年XBOX 360被破解了而PS3沒有？

如果加密文件密鑰是通過KDF(公鑰，輸入文件長度)產生的，那麼破解難度取決於KDF，但是兩個同樣大小的文件，共用了密鑰，便可以隨意破解。

ref:

how to use common modulus attack?

Elliptic Curve Digital Signature Algorithm

隱匿知乎多年，向來不答任何問題。看了這麼多回答，實在不忍心題主被誤導

本人專業相關，但是學藝不精，無法嚴格證明。先給出結論：不能。理論上不能，實際計算上也不能。題主說的便是密碼學中的一個概念「已知明文攻擊」而已，可以參看請解釋一下什麼是選擇明文攻擊及選擇密文攻擊？ - 顧凌峰的回答 - 知乎

舉兩個栗子，DES，一種已經被淘汰的對稱加密演算法。使用linear attack在理論上大約需要 $2^{42}$ 個已知的明文密文對，執行大約 $2^{43}$ 次解密才能恢復密鑰。一般PC無法執行該方案，內存都不夠。

AES-256，一種目前普遍應用的加密演算法。由於構造的微小缺陷，存在一種攻擊：related key attack，理論上需要 $2^{99}$ 個已知明文密文對，執行大約 $2^{99}$ 次解密才能恢復密鑰。試問哪位能夠實際破解？

以上兩個栗子來自Dan Boneh大佬《密碼學》課程，可登陸Coursera自行賞析。

給出明文和密文對，就想恢復出密鑰？簡直是在嘲笑耕耘在密碼學領域眾佬的智商。

在理論上，一個安全的密碼完全可以承受已知明文攻擊。其細節涉及可證明安全，有興趣可自行賞析Dan Boneh的談笑風生。

密碼學是一個NB人群的聚集地，他們把數學玩的出神入化，但由於鄙人數學較差，總是跪著看論文，而且是一臉懵逼。

首先，加密技術可大致分為對稱加密和不對稱加密兩種。這兩種加密方式的破解思路是完全不同的。

對稱加密就是在密匙和演算法確定的情況下，原文和密文的一一對應。就是所謂的「天對地，雨對風。大陸對長空」。因此即使你不知道密匙也不了解演算法的細節，你也能利用大量的密文與原文的對應關係，反推出密鑰和演算法的部分或者全部細節。以此用來解密其他利用該演算法和密鑰加密後的密文。舉個例子，詞頻的利用，基本可以讓任何一個字母替代類的加密演算法形同虛設。加密和沒加密幾乎沒任何區別。

對稱加密演算法中，你怎麼加密就怎麼解密。就是說加密演算法和解密是互逆的。你知道怎麼加密就知道怎麼解密，反之亦然。可非對稱加密就不一樣了，就像它的名字一樣。

非對稱加密演算法中，加密演算法和解密演算法是兩套相互配對但又不互逆的演算法，同時也需要有兩套密匙，一個公開的，用於加密（公鑰）；一個不公開的，用於解密（私鑰）。由於非對稱加密演算法在加密時使用了大量的取模運算和隨機數，這導致雖然演算法的細節都是公開的，且公鑰一般也都是公開的，但公鑰和私鑰依舊是無法相互推導的。加密的人都無法自己解密自己加密的文件。能解密的人自己無法用一樣的原文加密出一樣的密文。此外隨機數的應用導致同一個原文加密2次獲得的密文都是不一樣的。雖然這兩個不一樣的密文解密後得到的是同一個原文。

由於非對稱加密的加密演算法和解密演算法是公開的，因此非對稱加密的破解目的是利用窮舉法破解得到解密使用的私鑰，以此來解密密文。破解思路是利用演算法的缺陷從大量的原文和密文的對應關係中或者是其他相關信息中推算出私鑰的特徵或者排除一些不可能的私鑰組合。從而大大減少窮舉法破解時所需要的時間。（我記得某個加密演算法/設備的破解還需要利用設備斷電來實現）

----------------------------------------------

所以題主的問題需要分兩步來回答

1.針對對稱加密，當M增大，密鑰被破解的可能性X會隨之增大，當M到達一個特定值M"時，X=100%。M"的值取決於演算法的複雜度和密鑰的長度。

2.針對非對稱加密，當M增大，密鑰被破解的可能新X不會必然隨之增大，這取決於演算法的缺陷。此外也取決於執行窮舉破解的速度（比如電腦CPU運算量，及是否有多台機器並行破解）。

作為曾對這種問題有研究的我不邀自來

來答一下

這個問題的回答我想慢慢更～

首先來灰常形象的普及一下題主提到的幾個問題

非對稱密鑰演算法是指一個加密演算法的加密密鑰（公鑰）和解密密鑰（私鑰）是不一樣的。比如，我和粉絲們用非對稱加密演算法進行通信，我會發給每個粉絲一個公鑰，他們可以利用這個公鑰加密他們對我的評價然後發到網上，但別人因為沒有私鑰，沒法看出他們說的是什麼，只有私鑰持有者也就是我，能看到，並作出評論通過私鑰加密發到微博里，但由於非粉絲沒有公鑰，就無法進行解密。

對於以上問題的形象說明如果還是看不懂就自行wiki或百度

高能預警：進階區（可以直接跳過，後面看不懂了再回來研究研究）

對於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.密文和明文不是一一對應的關係

2.公鑰片段和私鑰片段也不是一一對應

3.從理論上來說，M足夠大時，用一定量級的計算機是能夠算出私鑰的

4.由於有密鑰解密需要很長時間，無密鑰解密更需要窮舉，128位的公鑰加上M和窮舉其實需要很大成本

5.（圖靈的Bomba機在解密對稱性加密的Enigma時還花了如此長的時間）事實上，窮舉時運用的原理是通過一個密鑰對密文進行解密，如果解密出來不是牛頭不對馬嘴，那麼這個就是密鑰了，單次解密所需時間再乘一個幾何級數那麼時間成本就相當大了

關鍵點是：由於成本過大，遠高於密鑰的價值（任何一種情況下都是如此）所以除非在尤其特殊一種情況下才會使用窮舉法。

CCA和CPA都不會。

建議題主自己看看密碼學的書籍，這應該是最基本的概念了

這個要看情況。

如果是傳統的移位密碼等，可以推導出來。

如果是現代對稱加密，可以降低破解難度。

如果是如RSA這種非對稱加密，目前還不行。

秘鑰有限長的情況下，隨著已知密文對應明文的數目增多，破解幾率會越來越大

如果是一次一密，那跟m數量無關，破解的難度不會隨著m的值變化而變化