算法與數據結構無廢話筆記（四）

??算法與數據結構是計算機專業(yè)學生的必修課，基礎中的基礎，所以快速上手，找到學習方向和感覺十分重要。我在學習過程中遇到一本好書，《我的第一本算法書》，把算法講得很淺顯易懂，所以基于這本書的內容，提煉出其中的精華，再加上個人的理解，旨在把最干的干貨分享給大家。推薦大家去閱讀原書！

安全和算法

通過互聯網交換數據時，數據要經過各種各樣的網絡和設備才能傳到對方那里。數據在傳輸過程中有可能會經過某些惡意用戶的設備，從而導致內容被盜取。

因此，要想安全地使用互聯網，安全技術是不可或缺的。本章將要學習的就是保障安全的 各種算法和利用了這些算法的機制。

這些問題不光發(fā)生在用戶之間交流的時候，也有可能發(fā)生在用戶瀏覽網頁的時候。

“數字簽名”技術存在“無法確認公開密鑰的制作者”這一問題。要想解決這個問題，可以使用“數字證書”技術。

加密的基礎知識

在現代互聯網社會中，加密技術變得十分重要。給想要保密的數據加密。加密后的數據被稱為“密文”。把密文發(fā)送給B。B收到密文后，需要解除加密才能得到原本的數據。把密文恢復為原本數據的操作就叫作“解密”。

計算機會用由 0 和 1 這兩個數字表示的二進制來管理所有數據。如上圖所示，數據雖然有文本、音頻、圖像等不同的形式，但是在計算機中都是用二進制來表示的。

對計算機來說，數據就是一串有意義的數字羅列。密文也是數字羅列，只不過它是計算機無法理解的無規(guī)律的數字羅列。也就是說，加密就是數據經過某種運算后，變成計算機無法理解的數的過程。

在加密運算上會用到“密鑰”。所以加密就是用密鑰對數據進行數值運算，把數據變成第三者無法理解的形式的過程。反過來，解密就是通過密鑰進行數值計算，把密文恢復成原本數據的過程。

哈希函數?。?！

哈希函數可以把給定的數據轉換成固定長度的無規(guī)律數值。轉換后的無規(guī)律數值可以作為數據摘要應用于各種各樣的場景。輸出的無規(guī)律數值就是“哈希值”。哈希值雖然是數字，但多用十六進制來表示。

六特征：

1. 輸出的哈希值數據長度不變。
2. 輸入相同則輸出相同（同一個算法下）。
3. 輸入相似的數據并不會導致輸出的哈希值也相似。
4. 即使輸入的兩個數據完全不同，輸出的哈希值也有可能是相同的，雖然出現這種情況的概率比較低。這種情況叫作“哈希沖突”。
5. 求哈希值的計算容易。
6. 反算不可能，不可能從哈希值反向推算出原本的數據。

共享密鑰加密

共享密鑰加密是加密和解密都使用相同密鑰的一種加密方式。由于使用的密鑰相同，所以這種算法也被稱為“對稱加密”。

我們先從整體上來了解一下共享密鑰加密的處理流程。假設 A 準備通過互聯網向 B 發(fā)送數據。由于有被竊聽的風險，所以需要把想要保密的數據加密后再發(fā)送。A使用密鑰加密數據。A將密文發(fā)送給B。B收到密文后，使用相同的密鑰對其進行解密。這樣，B就取得了原本的數據。只要是加密好的數據，就算被第三者惡意竊聽也無須擔心。

公開密鑰加密

公開密鑰加密是加密和解密使用不同密鑰的一種加密方法。由于使用的密鑰不同，所以這種算法也被稱為“非對稱加密”。加密用的密鑰叫作“公開密鑰”，解密用的叫作“私有密鑰”。

然后把公開密鑰發(fā)送給A。A使用B發(fā)來的公開密鑰加密數據。A 將密文發(fā)送給 B，B 再使用私有密鑰對密文進行解密。這樣，B就得到了原本的數據。

公開密鑰和密文都是通過互聯網傳輸的，因此可能會被 X 竊聽。但是，使用公開密鑰無法解密密文，因 此X也無法得到原本的數據！多人傳輸時，超級方便！

但是?。。?strong>道高一尺魔高一丈！

在B把公開密鑰PB發(fā)給A的時候，X把公開密鑰PB替換成自己的公開密鑰PX， 于是公開密鑰PX傳到了A那里。

整個過程沒有任何問題，B和A都不知道自己被假冒和竊聽了。

這種通過中途替換公開密鑰來竊聽數據的攻擊方法叫作“中間人攻擊”（man-in-the-middle attack）。

混合加密

共享密鑰加密存在無法安全傳輸密鑰的密鑰分配問題，公開密鑰加密又存在加密解密速度較慢的問題。結合這兩種方法以實現互補的一種加密方法就是混合加密。

在混合加密中，要用處理速度較快的共享密鑰加密對數據進行加密。不過，加密時使用的密鑰，則需要用沒有密鑰分配問題的公開密鑰加密進行處理。 就是頻繁傳輸的數據，用共享密鑰加密傳輸，但是第一次傳密鑰時，用公開密鑰加密傳輸。

迪菲 - 赫爾曼密鑰交換

迪菲 - 赫爾曼（Diffie-Hellman）密鑰交換是一種可以在通信雙方之間安全交換密鑰的方法。這種方法通過將雙方共有的秘密數值隱藏在公開數值相關的運算中，來實現雙方之間密鑰的安全交換。很絕的一個方法

假設有一種方法可以合成兩個密鑰。使用這種方法來合成密鑰P和密鑰S，就會得到由這兩個密鑰的成分所構成的密鑰P-S。這種合成方法有三個特征：

1. 即使持有密鑰P和合成的密鑰P-S，也無法把密鑰S單獨取出來。
2. 不管是怎樣合成而來的密鑰，都可以把它作為新的元素，繼續(xù)與別的密鑰進行合成。
3. 密鑰的合成結果與合成順序無關，只與用了哪些密鑰有關。

流程：

首先由A生成密鑰P。然后A把密鑰P發(fā)送給B。接下來，A 和 B 各自準備自己的私有密鑰SA和SB。A利用密鑰P和私有密鑰SA合成新的密鑰P-SA。B也利用密鑰P和私有密鑰SB合成新的密鑰P-SB。A將密鑰P-SA 發(fā)送給B，B也將密鑰 P-SB發(fā)送給A。A將私有密鑰SA和收到的密鑰P-SB合成為新的密鑰SA-P-SB。同樣地，B也將私有密鑰SB和收到的密鑰P-SA合成為新的密鑰P-SA-SB。 于是A和B都得到了密鑰P-SA-SB。這個密鑰將作為“加密密鑰”和“解密密鑰”來使用。

消息認證碼

消息認證碼可以實現“認證”和“檢測篡改”這兩個功能。密文的內容在傳輸過程中可能會被篡改，這會導致解密后的內容發(fā)生變化，從而產生誤會。消息認證碼就是可以預防這種情況發(fā)生的機制。

一句話說明白，還記得哈希函數吧，以共享密鑰加密為例，將密文和密鑰進行哈希運算得到一個數，叫做消息認證碼（MAC），發(fā)送密文的同時帶上MAC，因為雙方密鑰相同，所以對方收到密文后，也把密文和密鑰進行哈希運算，若得到的數跟收到的MAC相同，則數據沒有被篡改！

數字簽名

首先由A準備好需要發(fā)送的消息、私有密鑰和公開密鑰。由消息的發(fā)送者來準備這兩個密鑰，這一點與公開密鑰加密有所不同。A將公開密鑰發(fā)送給B。A使用私有密鑰加密消息。加密后的消息就是數字簽名。A將消息和簽名都發(fā)送給了B。B使用公開密鑰對密文（簽名）進行解密。B對解密后的消息進行確認，看它是否和收到的消息一致。流程到此結束。

數字證書

一句話，數字證書就是帶有認證中心數字簽名和發(fā)送者信息（包含公開密鑰）的文件。其中數字簽名就是認證中心使用自己私有密鑰對發(fā)送者信息進行加密的結果。就是認證中心給你的發(fā)送的公開密鑰蓋了個章，證明這是你發(fā)的?。。?/strong>