活板門和 RSA（施奈爾）
免責聲明：我是密碼學的新手。
背景：來自 Applied Cryptography (Bruce Schneier)，第 2 版的第30頁
活板門單向功能是一種特殊類型的單向功能，具有秘密活板門。在一個方向上很容易計算，而在另一個方向上很難計算。但是，如果你知道這個秘密，你可以很容易地計算出另一個方向的函式。也就是說，很容易計算 $ f(x) $ 給定 $ x $ ，並且難以計算 $ x $ 給定 $ f(x) $ . 但是，有一些秘密資訊， $ y $ , 這樣給定 $ f(x) $ 和 $ y $ 很容易計算 $ x $ .
問題：從高層次（即更正式地）來看，以下內容是否正確？
m = message i = input (e.g., public key) t = trapdoor (e.g., private key) h = one-way hash f(m,i) = h f(h,t) = m編輯：請參閱 Schneier 在同一參考文獻的第 38 頁上使用“單向雜湊”：
(..) Alice 對文件的雜湊進行簽名。在該協議中，單向雜湊函式和數字簽名算法都是事先約定好的。
- Alice 生成文件的單向雜湊。
- Alice 用她的私鑰加密散列，從而對文件進行簽名。
- Alice 將文件和簽名的雜湊發送給 Bob。
- Bob 生成 Alice 發送的文件的單向雜湊。然後，他使用數字簽名算法，用 Alice 的公鑰解密簽名的散列。如果簽名的雜湊與他生成的雜湊匹配，則簽名有效。
編輯 2：根據建議的答案更新：
x = message i = input (e.g., public key) t = trapdoor (e.g., private key) h = one-way hash f(x) = h g(h,t) = x
不，目前版本的問題中的兩個 6 個等式塊都沒有正確描述陷門單向函式（第一次引用）；或其用於公鑰加密；或使用單向雜湊和 RSA（第二次引用）對消息進行簽名。
這兩個引用只是遙遠的相關。特別是，第二次引用中的*“單向雜湊”不是第一次引用中定義的“陷門單向函式” 。*
我們將僅在 RSA 的上下文中說明第一個引文中的詞彙，然後是第二個引文；在每種情況下，給出問題中嘗試的公式。
假設已經建立了公共/私有 RSA 密鑰對。公鑰是 $ (N,e) $ ，並且正如其名稱所暗示的那樣，假定每個人都知道。
在第一個引用中：
- “陷門單向函式”是函式 $ f $ 改變 $ x $ 進入 $ f(x)=(x^e\bmod N) $ ; 我們會注意到 $ c=f(x) $ .
- “秘密”（也稱為*“一些秘密資訊”*），是私鑰 $ (N,d) $ , 注意到 $ y $ （或等效地：知識允許分解的任何東西 $ N $ ).
- 私鑰知識 $ y=(N,d) $ 允許計算一個 $ x $ 從 $ c $ , 這樣 $ c=f(x) $ ; 可以這樣做 $ x=g(c)=(c^d\bmod N) $ ; 事實證明，如果 $ c $ 通過選擇建立 $ x $ 和 $ 0\le x<N $ 和計算 $ c=f(x) $ , 然後計算 $ g(c) $ 總是給 $ x $ .
- *在沒有“秘密”*的情況下做同樣的事情被認為是棘手的，因為隨機選擇 $ c $ , 或為 $ c $ 選為 $ c=f(x) $ 用於隨機選擇 $ x $ 假定秘密。
- “秘密活板門”（函式）是函式 $ g $ ; 請注意 $ g(f(x))=x $ 如果 $ 0\le x<N $ ; 和 $ f(g(c))=c $ 如果 $ 0\le c<N $ .
在教科書 RSA 公鑰加密中， $ f $ 是加密函式，並且 $ g $ 是解密函式。加密是公開的，而解密需要知道秘密的陷門 $ y $ .
問題等式中使用的符號使用具有兩個參數的函式並導出兩者 $ f $ 和 $ g $ 從此。這是通過將 RSA 函式定義為接受密鑰（一對整數）作為第二個參數來完成的，如下所示：
- $ i=(N,e);; $ （公鑰）
- $ y=(N,d);; $ （私鑰，解鎖活板門）
- $ r(z,(N,k))=(z^k\bmod N);; $ ( $ r $ 是 RSA 函式， $ z $ 和 $ k $ 是變數）
- $ x=\text{message};; $ （明文）
- $ c=r(x,i)=f(x);; $ （根據教科書 RSA 公鑰加密的密文）
- $ x=r(c,y)=g(c);; $ （解密後的明文）
注意：這僅說明了教科書的 RSA 公鑰加密，在許多實際情況下非常不安全（例如 $ x $ 是未知的，但已知屬於已知集合，例如 $ {\text{head},\text{tail}} $ ，或班級卷）。在實際使用 RSA 進行加密時，可以避免這種情況。
在第二個引文中，描述了使用教科書 RSA 和單向雜湊函式簽署（可能很大）消息：
*“單向雜湊函式”*是一種單向函式，注意 $ H $ ，它與 RSA 無關，並且假定不是第一次引用意義上的陷門單向函式；相當， $ H $ 可能類似於SHA-512。
*“文件”*是一條消息 $ m $ ，表示為位串（包括文件）。
“文件的雜湊”（也是步驟 1的“文件的單向雜湊”）是應用的結果 $ H $ 至 $ m $ ， 著名的 $ h=H(m) $ ; 那 $ h $ 被同化為一個整數，並且 $ 0\le h<N $ 持有。
在第 2 步中，“Alice 用她的私鑰加密散列”是一個糟糕的術語：Alice 應用了秘密陷門函式 $ g $ （如我們對第一個引文的分析） $ h $ ; 產生 $ s=g(h) $ .
在第 3 步中，*“簽名雜湊”*是相同的 $ s=g(h) $ .
在第 4 步中：
- Bob 計算*“Alice 發送的文件的單向雜湊”；那將是 $ h $ 當且僅當 Bob 收到的文件完全符合 Alice 最初計算的 $ m $ 正如 Alice 處理的那樣；唯一的如果*部分是因為 $ H $ 是單向的（或者，取決於威脅模型，抗碰撞）。
- （鮑勃）*“用愛麗絲的公鑰解密簽名的雜湊”*是一個糟糕的術語：鮑勃應用陷門單向函式 $ f $ （如我們對第一個引文的分析） $ s $ 它從愛麗絲那裡收到，給 $ f(s) $ ; 在沒有改變的情況下 $ s $ , 那將是 $ f(g(h)) $ ， 那是 $ h $ 最初由 Alice 計算。
- 當這兩個計算 $ h $ 給出相同的結果。
再次堅持問題中的符號
- $ i=(N,e);; $ （愛麗絲的公鑰）
- $ y=(N,d);; $ （愛麗絲的私鑰，打開活板門，只有愛麗絲知道）
- $ r(z,(N,k))=(z^k\bmod N);; $ ( $ r $ 是 RSA 函式， $ z $ 和 $ k $ 是變數）
- $ m=\text{message};; $ （要簽名的消息，由 Alice 批准）
- $ h=H(m);; $ （Alice 計算的消息雜湊值）
- $ s=r(h,y)=g(h);; $ （Alice 計算的簽名）
- $ (m,s);; $ （Alice 發送的簽名消息）
- $ (\tilde m,\tilde s);; $ （Bob 收到的所謂的簽名消息）
- $ \tilde h=H(\tilde m);; $ （由 Bob 計算的所謂消息的雜湊值）
- $ \widehat h=r(\tilde s,i)=f(\tilde s);; $ （Bob 從所謂的簽名計算的雜湊）
- 鮑勃接受 $ \tilde m $ 當且僅噹噹且僅當真實且由 Alice 簽名 $ \tilde h=\widehat h $ .
簽名是通過應用秘密陷門功能，並且只能由 Alice 執行；任何知道 Alice 的公鑰的人都可以執行 Bob 所做的驗證。
注意：這僅說明了帶有散列的教科書 RSA 簽名，它具有已知的安全限制；值得注意的是，如果寬度 $ h $ 足夠小（例如 256 位，好像 SHA-256 用於 $ H $ )，並且 Alice 簽署了許多 Carol 特製的消息，然後 Carol 可以偽造另一條消息及其簽名，即使 Alice 從未簽署過那條消息。在實際使用 RSA 進行簽名時，可以避免這種情況。