1. 數字簽名”（Digital Signature）

1.1. 單詞數字化（digital）意味著其“由數字字串組成”

1.2. 任何數字化的東西都能被拷貝

1.3. “簽名”的全部意義在于能被讀取，但不能被除了作者的任何人拷貝（也就是偽造）

1.4. 軟體簽名是數字簽名最明顯的應用

1.5. 一個數字簽名同時依賴一個只有簽名者知道的秘密和被簽署的訊息

1.6. 沒有數字簽名，我們所知的互聯網就不會存在

2. 用掛鎖簽名

2.1. 上鎖的箱子就是檔案的簽名

2.1.1. 加鎖的箱子透明，這一機制的效果就會更好

2.1.2. 數字簽名提供的是可靠性，而非隱秘性

2.2. 一個受信第三方

2.2.1. 參與者不是給銀行一份簽名，而是給銀行一把能打開自己掛鎖的物體鑰匙

2.3. 如果弗朗索瓦絲需要證明拉維寫了欠條，她只要和一些目擊證人把鎖箱帶到銀行，在銀行用拉維的鑰匙打開箱子即可，

2.4. 掛鎖能打開就證明只有拉維能對箱中內容負責，而箱中正好是弗朗索瓦絲能試圖驗證的那份檔案

3. 用乘法掛鎖簽名

3.1. 上鎖或開鎖動作將由鐘算乘法（Multiplication in Clock Arithmetic）代表

3.2. 計算機使用的鐘大小非常大——鐘大小長度基本在數十或數百位數

3.3. 示例

3.3.1.

3.3.1.1. 鐘大小為11的乘法表

3.3.2. 拉維選擇11作為鐘大小，選擇6作為掛鎖

3.3.3. 拉維的訊息是“5”

3.3.4. “上鎖”訊息會是6×5，通過鐘算得到結果為8

3.3.5. 最終結果“8”就是拉維給原始訊息的數字簽名

3.3.6. 歐幾里得演算法得到鑰匙為2

3.3.7. 將8用鐘算乘以鑰匙2，就能得到結果5

3.3.8. 拉維可以公開宣布自己選擇的鐘大小和鑰匙值

3.4. 數字掛鎖是私有的，而數字鑰匙和鐘大小則是公開的

3.4.1. 掛鎖值是私有的（或秘密的）

3.5. 乘法方法的缺陷

3.5.1. 用于從掛鎖生成鑰匙的同樣把戲——基本上是指歐幾里得演算法——能非常完美地逆向運行：同樣的技術能讓計算機生成與已有鑰匙值對應的掛鎖值

3.5.2. 敵人無須依靠暴力破解就能逆轉程序

3.5.2.1. 歐幾里得演算法也能根據鑰匙值計算出掛鎖值，而這一演算法要比暴力破解高效得多，這也是乘法方法被認為不安全的原因

4. 用指數掛鎖簽名

4.1. 著名數字簽名機制RSA

4.2. 示例

4.2.1.

4.2.1.1. 鐘大小為22時n的三次方和七次方的值

4.2.2. 拉維選擇3作為掛鎖值

4.2.3. 訊息是“4”，簽名是“20”

4.2.4. 鑰匙值為7

4.2.5. 20^7鐘算結果為4，為原始訊息

4.3. 通過試錯總有可能算出某人的掛鎖值

4.3.1. 暴力破解（Brute Force）

4.3.2. 我們知道掛鎖值要小于鐘大小，因此我們可以簡單地逐一嘗試所有可能的掛鎖值，直到找到一個能生成正確簽名的掛鎖值

4.4. 訣竅是RSA機制使用絕對大的鐘大小

4.4.1. 數千位數長

4.4.2. 現存最快的超級計算機，也要花數萬億年才能嘗試所有可能的掛鎖值

4.5. 對敵人是否能用某種方法計算出掛鎖值不感興趣

4.5.1. 想知道敵人是否能足夠高效地這么做，從而造成實際威脅

4.5.1.1. 發明一種高效的分解因子演算法只會破壞類RSA機制

4.6. 鐘大小的兩個素數因子仍然保密

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/554452.html

標籤：其他

上一篇：前端八股文everybody準備好了沒

下一篇：返回列表

讀改變未來的九大演算法筆記05_數字簽名

1. 數字簽名”（Digital Signature）

1.1. 單詞數字化（digital）意味著其“由數字字串組成”

1.2. 任何數字化的東西都能被拷貝

1.3. “簽名”的全部意義在于能被讀取，但不能被除了作者的任何人拷貝（也就是偽造）

1.4. 軟體簽名是數字簽名最明顯的應用

1.5. 一個數字簽名同時依賴一個只有簽名者知道的秘密和被簽署的訊息

1.6. 沒有數字簽名，我們所知的互聯網就不會存在

2. 用掛鎖簽名

2.1. 上鎖的箱子就是檔案的簽名

2.1.1. 加鎖的箱子透明，這一機制的效果就會更好

2.1.2. 數字簽名提供的是可靠性，而非隱秘性

2.2. 一個受信第三方

2.2.1. 參與者不是給銀行一份簽名，而是給銀行一把能打開自己掛鎖的物體鑰匙

2.3. 如果弗朗索瓦絲需要證明拉維寫了欠條，她只要和一些目擊證人把鎖箱帶到銀行，在銀行用拉維的鑰匙打開箱子即可，

2.4. 掛鎖能打開就證明只有拉維能對箱中內容負責，而箱中正好是弗朗索瓦絲能試圖驗證的那份檔案

3. 用乘法掛鎖簽名

3.1. 上鎖或開鎖動作將由鐘算乘法（Multiplication in Clock Arithmetic）代表

3.2. 計算機使用的鐘大小非常大——鐘大小長度基本在數十或數百位數

3.3. 示例

3.3.1.

3.3.1.1. 鐘大小為11的乘法表

3.3.2. 拉維選擇11作為鐘大小，選擇6作為掛鎖

3.3.3. 拉維的訊息是“5”

3.3.4. “上鎖”訊息會是6×5，通過鐘算得到結果為8

3.3.5. 最終結果“8”就是拉維給原始訊息的數字簽名

3.3.6. 歐幾里得演算法得到鑰匙為2

3.3.7. 將8用鐘算乘以鑰匙2，就能得到結果5

3.3.8. 拉維可以公開宣布自己選擇的鐘大小和鑰匙值

3.4. 數字掛鎖是私有的，而數字鑰匙和鐘大小則是公開的

3.4.1. 掛鎖值是私有的（或秘密的）

3.5. 乘法方法的缺陷

3.5.1. 用于從掛鎖生成鑰匙的同樣把戲——基本上是指歐幾里得演算法——能非常完美地逆向運行：同樣的技術能讓計算機生成與已有鑰匙值對應的掛鎖值

3.5.2. 敵人無須依靠暴力破解就能逆轉程序

3.5.2.1. 歐幾里得演算法也能根據鑰匙值計算出掛鎖值，而這一演算法要比暴力破解高效得多，這也是乘法方法被認為不安全的原因

4. 用指數掛鎖簽名

4.1. 著名數字簽名機制RSA

4.2. 示例

4.2.1.

4.2.1.1. 鐘大小為22時n的三次方和七次方的值

4.2.2. 拉維選擇3作為掛鎖值

4.2.3. 訊息是“4”，簽名是“20”

4.2.4. 鑰匙值為7

4.2.5. 20^7鐘算結果為4，為原始訊息

4.3. 通過試錯總有可能算出某人的掛鎖值

4.3.1. 暴力破解（Brute Force）

4.3.2. 我們知道掛鎖值要小于鐘大小，因此我們可以簡單地逐一嘗試所有可能的掛鎖值，直到找到一個能生成正確簽名的掛鎖值

4.4. 訣竅是RSA機制使用絕對大的鐘大小

4.4.1. 數千位數長

4.4.2. 現存最快的超級計算機，也要花數萬億年才能嘗試所有可能的掛鎖值

4.5. 對敵人是否能用某種方法計算出掛鎖值不感興趣

4.5.1. 想知道敵人是否能足夠高效地這么做，從而造成實際威脅

4.5.1.1. 發明一種高效的分解因子演算法只會破壞類RSA機制

4.6. 鐘大小的兩個素數因子仍然保密