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

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

安全和算法

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

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

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

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

加密的基礎(chǔ)知識(shí)

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

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

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

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

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

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

六特征：

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

共享密鑰加密

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

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

公開(kāi)密鑰加密

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

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

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

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

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

整個(gè)過(guò)程沒(méi)有任何問(wèn)題，B和A都不知道自己被假冒和竊聽(tīng)了。

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

混合加密

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

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

迪菲 - 赫爾曼密鑰交換

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

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

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

流程：

首先由A生成密鑰P。然后A把密鑰P發(fā)送給B。接下來(lái)，A 和 B 各自準(zhǔn)備自己的私有密鑰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。這個(gè)密鑰將作為“加密密鑰”和“解密密鑰”來(lái)使用。

消息認(rèn)證碼

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

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

數(shù)字簽名

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

數(shù)字證書(shū)

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

聚類

參考這篇文章哦。 無(wú)廢話的機(jī)器學(xué)習(xí)筆記（七）（聚類: kmeans、GMM、譜聚類）

其他算法

歐幾里得算法

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

素性測(cè)試（費(fèi)馬測(cè)試）

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

網(wǎng)頁(yè)排名

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

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

漢諾塔

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

實(shí)際上，不管需要移動(dòng)多少圓盤，這個(gè)游戲最終都能達(dá)成目標(biāo)。




上一篇 ！加油！