Rabin-Williams 簽名及其對因式分解的簡化
Rabin 簽名被正確地稱為具有可證明的因式分解簡化的簽名方案。我們如何證明 Rabin-Williams 簽名是標準化的，在攻擊者可以訪問簽名預言的共同和現實假設下？
我將根據 ISO/IEC 9796-2:2010 附錄 B 或幾乎等效的 ISO/IEC 14888-2:2008 RW 或 IEEE P1363-2000 IFSP-RW/IFVP 詳細描述 Rabin-Williams 簽名中的標準化模運算-RW¹。我假設每個全域雜湊都帶有附錄簽名，因為我不想深入研究填充和消息恢復，但推理也適用於這些標準中的確定性填充。
安全參數 $ k $ 是以位為單位的公共模數大小。對於填充，我們假設一個雜湊函式 $ H_k:{0,1}^*\to{0,1}^{k-5} $ 結果同化為整數 $ [0,2^{k-5}) $ ，並且此雜湊與隨機 Oracle 無法區分。
密鑰生成 $ \mathsf{Gen} $ : 在輸入 $ 1^k $
- 繪製隨機素數 $ p,q\in[2^{(k-1)/2},2^{k/2}] $ 和 $ p\equiv3\pmod8 $ 和 $ q\equiv7\pmod8 $ , 事實證明這是可能的 $ \forall k>10 $
- 計算 $ n\gets p,q $ , 這正是 $ k $ -少量
- 放 $ e\gets2 $ 併計算 $ d\gets e^{-1}\bmod(\operatorname{lcm}(p-1,q-1)/2) $
- 輸出 $ \mathrm{Pub}=(n,e) $ 和 $ \mathrm{Priv}=(n,d) $ .
簽名 $ \mathsf{Sign} $ : 在輸入 $ \mathrm{Priv}=(n,d) $ 和留言 $ M $
- 計算 $ k\gets\left\lceil,\log_2(n)\right\rceil $
- 計算消息代表 $ m\gets16,H_k(M)+12 $ [因此 $ m\in[0,2^{k-1}) $ 和 $ m\equiv12\pmod{16} $ ]
- 計算² Jacobi 符號 $ j\gets\left(\frac m n\right) $
- 計算 $ g\gets\begin{cases}m/2&\text{if },j=-1\m&\text{otherwise}\end{cases}\quad $ [因此 $ \left(\frac g n\right)\ge0 $ ]
- 計算 $ r\gets g^d\bmod n $
- 計算並輸出簽名 $ s\gets\min(r,n-r) $ .
確認 $ \mathsf{Ver} $ : 在輸入 $ \mathrm{Pub}=(n,e) $ ， 資訊 $ M $ 和簽名 $ s $
- 放 $ k\gets\left\lceil,\log_2(n)\right\rceil $
- 計算消息代表 $ m\gets16,H_k(M)+12 $ [因此 $ m\in[0,2^{k-1}) $ 和 $ m\equiv12\pmod{16} $ ]
- 如果 $ s\not\in[0,(n+1)/2) $ 然後輸出 $ \mathtt{Invalid} $ 並停止
- 計算 $ t\gets s^e\bmod n $ 和 $ u\gets t\bmod8 $
- 如果 $ u\not\in{1,4,6,7} $ 然後輸出 $ \mathtt{Invalid} $ 並停止
- 放 $ v\gets\begin{cases}t&\text{if },u=4\n-t&\text{if },u=1\ 2,t&\text{if },u=6\2,(n-t)&\text{if },u=7\end{cases} $
- 如果 $ m\ne v $ 然後輸出 $ \mathtt{Invalid} $ 並停止
- 輸出 $ \mathtt{Valid} $ .
可以用它來證明所有人的健全性 $ x\in\mathbb Z,,x^2\equiv{\left({\left(x^2\right)}^d\right)}^e\pmod n $ .
的價值觀 $ u $ 允許在 $ \mathsf{Ver}_5 $ 和案件在 $ \mathsf{Ver}_6 $ 相當於 $ m\equiv12\pmod{16} $ 後 $ \mathsf{Sign}_2 $ 和 $ \mathsf{Ver}_2 $ ，根據這張表（其中大 $ k $ 在實踐中不可能找到 $ M $ 觸發四種正確情況中的任何一種）：
$$ \begin{array}{c|rrrr|rrrr} \left(\frac m p\right)&+1&-1&-1&+1&+1& 0&-1& 0\ \left(\frac m q\right)&+1&-1&+1&-1& 0&+1& 0&-1\ \hline \left(\frac m n\right)&+1&+1&-1&-1& 0& 0& 0& 0\ u & 4& 1& 6& 7& 4& 4& 1& 1 \end{array} $$
觀察：可以訪問已知任意消息簽名的對手可以計算 $ u\gets (s^e\bmod n)\bmod 8 $ , 從而推導出 $ \left(\frac m p\right) $ 和 $ \left(\frac m q\right) $ 對於已知的偽隨機 $ m\equiv12\pmod{16} $ . 當無法訪問這些簽名時，我只能看到他們可以獲得較少的資訊 $ \left(\frac m n\right)=\left(\frac m p\right),\left(\frac m q\right) $ .
問題[請忽略1和3，我解決了！]
- 是否有一種論點認為，上述觀察不能讓可以訪問簽名（或簽名預言機）的對手對分解的因式有一些見解 $ n $ ?
- 假設分解為 $ n $ 作為輸出 $ \mathsf{Gen} $ 很難？
- 這些因式分解的減少都是為了方案的安全性，還是在某種程度上違背了它（省略了側通道和其他特定於實現的攻擊）？我擔心的是，簽名預言機⟹因式分解⟹完全中斷的存在性中斷在直覺上並不令人放心。
更新：也許 2 的答案是在 Bernstein 的Proving strict security for Rabin-Williams signatures中，最初是在Eurocrypt 2008 的程序中，但我很難遵循那篇論文³，甚至確定問題的方案是他的 α-|principal| B = 0（因此固定）。
¹ IEEE P1363-2000 引用了 ISO/IEC 9796:1991 和 Hugh C. Williams’ A modify of the RSA public-key encryption procedure（在IEEE TIT, 1980中）作為其來源。ISO/IEC 9796:1991 使用 $ m\equiv6\pmod{16} $ 在 $ \mathsf{Sign}_2 $ 和 $ \mathsf{Ver}_2 $ ，這需要在 $ \mathsf{Ver}_5 $ 和 $ \mathsf{Ver}_6 $ ，請參閱應用密碼學的修改拉賓簽名方案手冊（11.27 之後的起始頁標記為 439）。
² 一個可以計算 $ j\gets\left(\frac m n\right) $ 根據應用密碼學手冊中的算法 2.149。Bernstein 給出了一種避免 Jacobi 符號的方法： $ p $ 和 $ q $ 私鑰的一部分，重用使用中國提醒定理加速私鑰操作時所需的計算，以及使用預計算值的其他優化。
³ 我恭敬地在一個方面不同意： $ \min $ 介入;涉足 $ \mathsf{Sign}_6 $ 表述為：
關鍵是（ $ s $ ) 佔用的空間比 ( $ r $ )
但這缺少另一個目標：通過允許簽入來擁有 sEF-CMA 而不是 EF-CMA $ \mathsf{Ver}_3 $ ，這可以防止對手改變 $ s $ 成一個同樣有效的簽名 $ n-s $ ，這會破壞 sEF-CMA。
我還在拼湊東西，所以請耐心等待，因為這可能會被修改。
- 訪問簽名預言機要麼是零知識資源，要麼打破隨機預言機模型 $ H_k $ . 為了看到這一點，我們觀察到任何人都可以生成有效的 $ (m,s) $ 對的隨機值 $ H_k $ . 他們通過任意選擇來做到這一點 $ s $ 在要求的範圍內，平方得到 $ t $ 並丟棄或通過驗證步驟 6 來獲得 $ m $ 價值。他們唯一不知道的是 $ M $ 產生的 $ H_k $ ，但隨機預言機意味著此資訊無助於因式分解 $ n $ .
- 沒有特殊的偽造可以為給定的生成單獨的簽名 $ M $ 因為這個過程是確定性的。因此，顯示 EUF-CMA 就足夠了。假設攻擊者可以展示偽造品 $ (M,s) $ 那麼他們的方法必須要麼產生 $ s $ 前 $ M $ 完全指定或 $ M $ 前 $ s $ 是完全指定的。如果是前者，他們可以重建 $ H_k(M) $ 在知道之前 $ M $ （它不能是重複的消息），因此有更高的找到機會 $ M $ 給定 $ H_k(M) $ 這違反了我們的隨機預言。如果 $ M $ 之前完全指定 $ s $ ，那麼攻擊者就有辦法構造一個 $ \sqrt m $ , $ \sqrt{-1}\sqrt m $ , $ \sqrt 2\sqrt m $ 或者 $ \sqrt{-2}\sqrt m $ （根據步驟 6 中的選擇） $ m=16H_k+12 $ 隨機 $ H_k $ 有更好的機會。我們隨機選擇許多 $ x $ ，將它們平方並查看表格是否匹配 $ u $ 然後讓我們的攻擊者構造相應的平方根。在案例 1 中，我們得到一個隨機平方根，這給了我們一對全等平方，我們有機會按照通常的方法進行分解。在案例 2 中，我們可以計算一個值 $ \sqrt{-1} $ 案例 2 的未來實例將為我們提供另一個實例 $ \sqrt{-1} $ 和一對全等的正方形。同樣，案例 3 和 4 為我們提供了 $ \sqrt{2} $ 和 $ \sqrt{-2} $ 進一步的例子又給了我們全等的正方形。這與預期 $ O(1) $ 打電話給 $ \sqrt{u} $ 提取器，我們將考慮 $ n $ .
- 簽名預言機的零知識性質確實保證了因式分解問題是等價的。
這回答了我自己的 Q1 和 Q3。Q2 仍然飛過我的頭頂，但越來越近了。
Q1 問了一個論點，為什麼它不能幫助分解 $ n $ 通過檢查已知或選定消息的 Rabin-Williams 簽名 $ M $ ，對手可以找到大量偽隨機 $ m=16,H_k(M)+12 $ 與已知 $ \left(\frac m p\right) $ 和 $ \left(\frac m q\right) $ ; 當給定的 $ m $ ，沒有已知的方法可以找到這兩個數量（只有它們的乘積）。
一個論點是，對手有有效的替代方法，不需要簽名或對簽名預言的查詢，以找到偽隨機 $ m $ 與非零的任何組合 $ \left(\frac m p\right) $ 和 $ \left(\frac m q\right) $ 他們認為合適（見下文）。從而具有使用簽名（或使用隨機預言機準備的簽名預言機）相同的能力 $ m $ ) 在因式分解中不能有很大的用處。
從隨機開始 $ x\in[1,n) $ . 除非 $ \gcd(n,x) $ 是一個因素 $ n $ $$ \begin{array}{llclcl} m_0&\gets x^2\bmod n&\text{verifies}&\left(\frac{m_0}p\right)=+1&\text{and}&\left(\frac{m_0}q\right)=+1\ m_1&\gets n-m_0&\text{verifies}&\left(\frac{m_1}p\right)=-1&\text{and}&\left(\frac{m_1}q\right)=-1\ m_2&\gets2,m_0\bmod n&\text{verifies}&\left(\frac{m_2}p\right)=-1&\text{and}&\left(\frac{m_2}q\right)=+1\ m_3&\gets-2,m_0\bmod n&\text{verifies}&\left(\frac{m_3}p\right)=+1&\text{and}&\left(\frac{m_3}q\right)=-1\ \end{array} $$
擁有這樣一個 $ m_i $ 適當的類型，很容易做更多：只需乘以一個平方並減少模數 $ n $ . 經過幾個平方的預計算，我們可以產生近一個新的 $ m\equiv12\pmod{16} $ 每個模乘，通過根據前面的幾個高位選擇我們這次使用哪個方格 $ m $ .
Q3 問我們為什麼要考慮是否可以通過訪問簽名預言來展示存在簽名偽造的論點*，那麼我們可以考慮它 $ n $* 作為信任簽名系統的充分理由。
我在
- 如果可以訪問簽名預言機的對手可以展示存在簽名偽造，他們也可以考慮 $ n $ （並徹底休息）
- 如果可以訪問簽名預言機的對手可以展示存在簽名偽造，他們也可以考慮 $ n $ 無法訪問簽名預言機（並且僅使用公鑰進行完全破解）。
1 個州 [break (s)EUF-CMA for $ n $ ] ⟹ [因子 $ n $ 給定 $ n $ 和簽名下 $ n $ 很多]。2 個州 [打破 EUF-CMA 為 $ n $ ] ⟹ [因子 $ n $ 給定 $ n $ ]。因此 2 是嚴格更好的保證。
差異是微妙的。我被指出的文獻（正確地）指出 1 成立但並不令人放心，並且沒有指出 2 成立且令人放心。當我問 Q3 時，那是我的錯誤。
2 的證明（我確信，它適用於 $ H_k $ per FDH) 是使用 Rabin 而不是 RSA 的一個很好的理由（除了更快的公鑰操作），如果我們忽略潛在的邊通道、由於增加的複雜性而導致的實現錯誤以及由於選擇不當而導致的完全中斷 $ H_k $ . 後一個問題發生在 ISO/IEC 9796(-1):1991 中，其中一次攻擊導致 4 條選定消息的簽名完全中斷，而 ISO/IEC 9796-2:1997 中另一個問題是針對可能的許多消息和散列這樣做的實用尺寸。