Lamport Diffie 一次性簽名
我正在通過Lamport Diffie One-time 簽名。我很難理解
- 如何通過單向函式將長消息（大於 100 位）映射為短消息（100 位）並且只有短消息簽名？有人可以舉個例子來解釋一下嗎？（請參閱附件中的第 13 頁。）
- “消息可以在簽名之前由簽名者使用新生成的隨機密鑰進行加密，並將隨機密鑰附加到消息中。因此，簽名的消息將是隨機的（假設使用隨機密鑰加密將有效地使消息隨機化，現代加密功能普遍承認的事實
$$ 11 $$）。這些步驟將滿足屬性 2 的條件。因此，我們可以在不失一般性的情況下假設所有消息都是固定長度的，例如 100 位“有人可以向我解釋一下嗎？（請參閱第 13 - 第 14 頁在附件中。） 3. “到目前為止所描述的方法存在缺陷，即 B 可以通過將 1 的位更改為 D 來更改 m。B 只是否認他曾經收到過 xj ‘（儘管他確實收到了）。但是，D 不能更改為1’s. Lamport 和 Diffie 通過簽署新消息 m’ 克服了這個問題，該消息 m’ 正好是 m 的兩倍，並且通過將 m 與 m 的按位補碼連接起來計算得到。也就是說，J 原始消息中的每個位 m. 是在新消息 m’ 中由兩個位 mj 和 m 的補碼表示。顯然，一個或另一個 J 位必須是 O。要更改消息，B 必須將 0 變成 1，他無法做到。” 有人可以解釋這是如何解決問題的。（請參閱第 14 頁）
我現在正在嘗試閱讀有關加密空間的技術。我從隨附的文件開始，因為這裡提到了它。如果您覺得有資源可以詳細解釋所附論文，但以初學者會理解的方式，我將不勝感激。
我正在通過 Lamport Diffie One-time 簽名。
作為旁注；這項工作是一項早期努力，最終形成了所謂的“基於狀態雜湊的簽名方法”；現代設計包括XMSS和LMS，並且與 Merkle 論文中的內容驚人地接近。您可能會發現 Wiki 連結更平易近人…
無論如何，為了解決您的問題：
- 如何通過單向函式將長消息（大於 100 位）映射為短消息（100 位）並且只有短消息簽名？
不要聽起來過於簡單：
- 我們採取長消息簽名
- 我們將其用作“單向函式”（現代術語：散列函式）的輸入，該函式生成固定大小的輸出（在本例中為 100 位）
- 我們採用 100 位輸出，並對其應用簽名算法。
這並不特定於基於雜湊的簽名；基本上所有的簽名算法（至少，任何我聽說過的）都使用這個的變體作為第一步。唯一的區別是 100 位不會被認為足夠長。我們通常堅持更長的雜湊輸出（因為攻擊者的能力自 1979 年以來已經大大提高，因此我們需要讓我們的系統更強大）。
不明顯的問題是“為什麼這是安全的”？好吧，如果我們假設攻擊者找不到另一條單向函式映射到相同 100 位的消息，並且攻擊者無法為攻擊者的消息映射到的不同的 100 位集合生成簽名，那麼它是安全的.
實際上，在實踐中，我們擔心碰撞攻擊，攻擊者可以控制正在簽名的有效消息（但他仍然需要產生偽造，即對未簽名消息的有效簽名）；Merkle 確實考慮到了這一點，但是讓我們暫時保持簡單。
- “消息可以用新生成的隨機密鑰加密……”有人可以向我解釋一下嗎？
好吧，這部分可能可以跳過——這是現代加密不遵循的論文的一部分。
Merkle 試圖定義一個“經過驗證的加密函式”，並使用特定的假設來做到這一點，包括隨機輸入；被簽名的消息不是隨機的，因此他插入了一個加密函式（使用隨機密鑰）以使其符合他的假設。
在現代加密中，我們不這樣做——我們通常使用現成的散列函式（例如 SHA-2 或 SHAKE）並使用它——它們的設計（和密碼分析）是為了滿足加密的各種假設雜湊函式；因此我們（作為簽名設計師）不必擔心這一點。
公平地說，這可能是第一次有人試圖弄清楚“抗碰撞雜湊函式”會是什麼樣子，他做了一個相當不錯的嘗試——這不是後來密碼學家所採用的方向。
- “到目前為止所描述的方法存在缺陷，即 B 可以通過將 1 的位更改為 0 來改變 m ……”有人可以解釋這是如何解決問題的。
好吧，讓我們考慮最簡單的情況；簽署一個位。在“迄今為止描述的方法”中，要生成私鑰，我們會選擇一個隨機值 $ x $ ，並應用隨機函式 $ F $ 為它創造公共價值 $ F(x) $ . 然後，要簽署一個“1”位，我們將產生一個簽名 $ x $ （驗證者將能夠驗證 $ F $ 將其映射到公鑰）。然而，要簽署一個“0”位，我們不會透露任何內容。很明顯，看到“1”的有效簽名的人可以將其轉換為“0”的簽名（或者，就此而言，生成一個“0”的簽名而沒有看到任何東西）。
在 Lamport 方案中，為了對單個位進行簽名，我們生成兩個隨機值 $ x $ 和 $ x’ $ ，並將值作為公鑰發布 $ F(x) $ 和 $ F(x’) $ . 為了簽署一個 0，我們產生 $ x $ ; 簽署一個 1，我們產生 $ x’ $ ; 簽名為 1 的人不能生成簽名 0（因為他們必須生成 $ x $ ，他們不知道）。
現在，這是可行的，但是它非常昂貴（您最終需要一個具有兩倍於雜湊函式產生的位的雜湊輸出的公鑰 - 例如，如果您的雜湊函式輸出 100 位，則它的公鑰包含200 個雜湊值）。正如本文第 4 節和第 5 節（在實踐中使用的）所提到的，該論文確實繼續展示了減少它的方法。