算法與數(shù)據(jù)結(jié)構(gòu)無廢話筆記（四）

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

安全和算法

通過互聯(lián)網(wǎng)交換數(shù)據(jù)時，數(shù)據(jù)要經(jīng)過各種各樣的網(wǎng)絡(luò)和設(shè)備才能傳到對方那里。數(shù)據(jù)在傳輸過程中有可能會經(jīng)過某些惡意用戶的設(shè)備，從而導致內(nèi)容被盜取。

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

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

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

加密的基礎(chǔ)知識

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

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

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

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

哈希函數(shù)?。?！

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

六特征：

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

共享密鑰加密

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

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

公開密鑰加密

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

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

公開密鑰和密文都是通過互聯(lián)網(wǎng)傳輸?shù)?，因此可能會?X 竊聽。但是，使用公開密鑰無法解密密文，因 此X也無法得到原本的數(shù)據(jù)！多人傳輸時，超級方便！

但是！??！道高一尺魔高一丈！

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

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

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

混合加密

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

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

迪菲 - 赫爾曼密鑰交換

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

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

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

流程：

首先由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。這個密鑰將作為“加密密鑰”和“解密密鑰”來使用。

消息認證碼

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

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

數(shù)字簽名

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

數(shù)字證書

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

聚類

參考這篇文章哦。 無廢話的機器學習筆記（七）（聚類: kmeans、GMM、譜聚類）

其他算法

歐幾里得算法

歐幾里得算法（又稱輾轉(zhuǎn)相除法）用于計算兩個數(shù)的最大公約數(shù)，被稱為世界上最古老的算法。

素性測試（費馬測試）

素性測試是判斷一個自然數(shù)是否為素數(shù)的測試。素數(shù)（prime number）就是只能被 1 和其自身整除，且大于 1 的自然數(shù)。素數(shù)從小到大有 2、3、5、7、11、13……目前在加密技術(shù)中被廣泛應(yīng)用的 RSA 算法就會用到大素數(shù)，因此“素性測試”在該算法中起到了重要的作用。

網(wǎng)頁排名

網(wǎng)頁排名（PageRank，也叫作佩奇排名）是一種在搜索網(wǎng)頁時對搜索結(jié)果進行排序的算法。 Google 因在搜索引擎中使用了這個算法而成為了世界知名的大企業(yè)是眾所周知的事情。

瀏覽網(wǎng)頁的人只是在不斷重復著 “在有鏈接指向的頁面之間移動幾次之后，遠程跳轉(zhuǎn)到了完全不相關(guān)的網(wǎng)頁這一過程！

漢諾塔

漢諾塔是一種移動圓盤的游戲，同時也是一個簡單易懂的遞歸算法應(yīng)用示例。

實際上，不管需要移動多少圓盤，這個游戲最終都能達成目標。




上一篇 ！加油！