帶有消息恢復的簽名描述（如 ISO/IEC 9796-2 和 EMV 簽名）
我想大致了解帶有消息恢復的簽名如何工作，尤其是在 EMV 和其他智能卡系統的情況下。無需閱讀整個 ISO/IEC 9796-2 是否有很好的概述？
我已經看過“ ISO/IEC 9796-2 和 EMV 簽名的實用密碼分析”論文……但那裡只列出了編碼函式，我無法真正理解簽名是如何驗證和恢復的。謝謝！
非正式地，具有消息恢復的簽名方案是將部分或全部消息嵌入簽名中的一種方案。這可以減少簽名消息的大小，有時會減少接近 2 的比例，例如對於 RSA 公鑰證書。
常見做法：帶附件的簽名方案
節省空間：具有完全消息恢復的簽名方案
兩全其美：具有部分消息恢復的簽名方案
$$ \begin{array}{ll} \mathsf{Gen},\mathsf{Sign},\mathsf{Ver}&\text{Key generation, signature, verification algorithms.}\ \operatorname{Pub}, \operatorname{Priv}&\text{Public and private keys (bitsrings).}\ M_r&\text{‘Recoverable’ message.}\ M’_r&\text{‘Recovered’ message, equal to }M_r\text{ on successful verification.}\ M_n&\text{‘Non-recoverable’ message, equivalently ‘clear’ or ‘visible’.}\ S&\text{Signature.}\ \end{array} $$
具有完全消息恢復的簽名方案[一些來源使完全隱含，例如HAC第 11.2.3 節]可以正式定義為三個函式
$$ easily computable, with a compact and public definition $$:
密鑰生成函式
帶輸入
- 一些參數（特別是密鑰大小）
- 一個隨機位串，
輸出一個公鑰/私鑰對 $ (K_\text{pub},K_\text{priv}) $ ,
簽名函式 $ \mathcal S $
帶輸入
- 相同的參數
- $ K_\text{priv} $ 從密鑰生成函式的輸出中獲得
- 任何消息 $ M $ 在一些大子集中 $ \mathbb M $ 位串集的 $ {0,1}^* $
- 一個（可選的）隨機位串[在ISO/IEC 9796-2方案 2 中使用]
輸出指定為簽名消息的位串 $ S=\mathcal S_{K_\text{priv}}(M) $ ,
驗證功能 $ \mathcal V $
帶輸入
- 相同的參數
- $ K_\text{pub} $ 從密鑰生成函式的輸出中獲得
- 任何位串 $ S\in{0,1}^* $
輸出一對 $ (b,M)=\mathcal V_{K_\text{pub}}(S) $ 和
- $ b $ 一個布爾值，要麼 $ \text{false} $ $$ bad signature $$或者 $ \text{true} $ $$ good signature $$
- 一個位串 $ M $
這樣對於所有參數和隨機種子， $ \forall M\in\mathcal M, V_{K_\text{pub}}(S_{K_\text{priv}}(M))=(\text{true},M) $ .
具有完全消息恢復的簽名方案被定義為存在安全的
$$ or equivalently: secure in a chosen-messages setup $$如果一個計算有界的對手，給定 $ K_\text{pub} $ 並訪問一個預言機 $ S_{K_\text{priv}}(M) $ 當給出任何 $ M\in\mathbb M $ , 不能以相當大的機率展示 $ S\in{0,1}^* $ 和 $ V_{K_\text{pub}}(S)=(\text{true},M) $ ，這樣就不會使用 $ M $ . 請注意，在具有完全消息恢復的簽名方案中， $ M $ 是消息驗證函式的輸出；當它是帶有附錄的簽名方案中的*輸入時。*恢復 $ M $ 從簽名的消息中 $ S $ 需要評估 $ \mathcal V_{K_\text{pub}}(S) $ , 特別是知識 $ K_\text{pub} $ .
為了 $ k $ - 位安全，簽名和消息的大小必須服從 $ |M|\le|S|-k $ （對於不查詢預言機並嘗試的微不足道的對手的成功機率 $ S $ 至少是隨機的 $ 2^{|M|-|S|} $ ， 假設 $ |S| $ 對於給定的是固定的 $ |M| $ 和所有大小的消息 $ |M| $ 可以簽名）。
一些方案還提供部分消息恢復：簽名生成會破壞消息 $ M $ 進入 $ M_r $ 和 $ M_n $ 以公開的、方案定義的方式，與 $ |M|=|M_r|+|M_n| $ ; 假設 $ M_n $
$$ the non-recoverable part $$作為簽名驗證功能的附加輸入（如在帶附件的簽名中）；儘管 $ M_r $ $$ the recoverable part $$替換 $ M $ 在驗證函式的輸出中，變為 $ (b,M_r) $ . 正確性要求變成對於所有參數和隨機種子， $ \forall M\in\mathcal M, V_{K_\text{pub}}(S_{K_\text{priv}}(M),M_n)=(\text{true},M_r) $ ， 在哪裡 $ M_r $ 和 $ M_n $ 提取自 $ M $ 以規定的方式，並且可以重新組合成 $ M $ .
安全要求變成了一個計算有界的對手，給定 $ K_\text{pub} $ 並訪問一個預言機 $ S_{K_\text{priv}}(M) $ 當給出任何 $ M\in\mathbb M $ , 不能以相當大的機率展示 $ M_n $ 和 $ S\in{0,1}^* $ 和 $ V_{K_\text{pub}}(S,M_n)=(\text{true},M_r) $ ，這樣就不會使用 $ M $ 通過重組獲得 $ M_r $ 和 $ M_n $ .
通常， $ |S| $ 對於給定的公鑰是固定的，但獨立於 $ |M| $ ; 和 $ |M_n|=0 $ 為了 $ |M| $ 低於某個門檻值。為了 $ k $ -位安全， $ |M_r|\le|S|-k $ 必須持有，或等效地 $ |M_n|\ge|M|-|S|+k $
第一個具有消息恢復功能的標準消息方案是 ISO/IEC 9796:1991
$$ later renamed ISO/IEC 9796-1, but never approved under this name $$. 它沒有使用散列，因為標準散列在哪裡是新奇的。它僅具有完全的消息恢復功能，並且具有約束 $ |M|\le|S|/2 $ （在幾位之內）。它在選擇的消息設置中被破壞[首先在 1 位內；然後是完整的，但有很多資訊；然後用另一個獲得簽名的攻擊 $ k $ 的額外消息 $ k+2 $ 為最實際的論點選擇了其他消息]；並於2000年撤回。 第二個標準消息方案是 ISO/IEC 9796-2:1997，現在稱為 ISO/IEC 9796-2 的方案 1。它通過使用散列改進了 ISO/IEC 9796:1991，允許更緊湊的簽名消息和部分消息恢復。ISO/IEC 9796-2 的方案 1 在選擇的消息設置中被破壞 [最著名的攻擊是在問題中指出的論文（備用連結）中]，但當對手被限制獲得簽名時，在實踐中仍然是安全的未專門建構以啟用攻擊的消息。ISO/IEC 9796-2:2002 強制最小散列寬度為 $ h=160 $ 作為一種緩解措施，增加了旨在永久修復安全性的方案 2 和 3，定義了實踐所需的所謂替代簽名生成和打開功能，並將以前提供資訊的非替代簽名生成和打開功能包括為規範。ISO/IEC 9796-2:2002 的 1:2008 修正案增加了 ASN.1 模組。ISO/IEC 9796-2:2010 僅對 AFAIK 進行純粹的編輯更改，而不是合併該修訂。
在 ISO/IEC 9796-2 中，消息 $ M $ 要簽署的細分為 $ M=M_r|M_n $ . 可恢復部分 $ M_r $ 位於消息的開頭，具有由參數確定的某個最大大小；它被嵌入到簽名中傳輸 $ S $ ，其大小由公鑰參數固定。不可恢復的部分 $ M_n $ 簡稱為空 $ M $ [並且總是一個字節串，即使 $ M $ 不是，因此 $ |M_r|\equiv|M|\pmod 8 $ ]; $ M_n $ 通常沿簽名消息未經修改地傳輸，但可能全部或部分隱含（例如版本號）。什麼時候 $ M_n $ 是空的
$$ resp. non-empty $$, 該方案共執行$$ resp. partial $$恢復模式。 ISO/IEC 9796-2 的方案 1 是確定性的。對於簽名，消息代表是通過連接規定的填充形成的， $ M_r $ , 整個消息的雜湊 $ M $ ，以及其他規定的填充物；底層證券
$$ RSA-like $$然後應用私鑰函式來獲得簽名，該簽名大約是公共模數的大小。對於簽名驗證和消息恢復，經過初步檢查，應用底層公鑰功能；檢查該結果中的填充；恢復的 $ M_r $ 從該結果中提取；並且從該結果中提取的雜湊值與從恢復的消息中重建的雜湊值進行比較 $ M_r $ 並且，對於部分消息恢復，未恢復的 $ M_n $ 通過其他方式獲得。 關於 ISO/ IEC 9796-2方案 1（僅限於 $ n\equiv m\equiv 0\pmod 8 $ , SHA-1 (因此 $ h=160 $ )，隱式雜湊標識符， $ m\gt n+176 $
$$ that is partial message recovery $$，以及 PKCS#1 中所謂的替代簽名生成和開放函式 RSASP1 和 RSAVP1。這種參數化在智能卡中很常見，並且直接支持$$ including with total message recovery $$由Java Card 2.2.x/Classic提供。 ISO/IEC 9796-2 的方案 2 是隨機的
$$ and correspondingly has the signed message larger than scheme 1 in many use cases $$，具有類似於 PKCS#1 的 RSASSA-PSS 的安全參數，適用於包括在選擇消息設置中。方案 3 是方案 2 的一個特例，隨機位串減少為空。將消息拆分為可恢復和不可恢復的部分，使得方案 3 可以用作方案 1 的功能等價物，在選擇的消息設置中恢復了安全性$$ although I know no formal security argument $$. 假設一個 $ n $ - 位公共模數，當發送一個 $ m $ -bit 消息及其簽名，ISO/IEC 9796-2 方案 1 或 3 的簽名消息大約有 $ \min(n,m+h+16) $ 位在哪裡 $ h $ 是散列的寬度 [SHA-1 很流行，給出 $ h=160 $ ]。這允許顯著
$$ at least when considering proportion $$節省消息的大小 $ m $ 相稱 $ n $ ，例如公鑰證書[比較 $ m+n $ 位使用 PKCS#1] 中的方案。例如：與 $ n=1984 $ , $ h=160 $ , $ m=2000 $ $$ 250 bytes $$，簽名的消息可以使用 $ 2176 $ 位$$ 272 bytes, rather than 498 bytes with PKCS#1 $$: $ 1984 $ 位$$ 248 bytes $$對於 RSA 密碼，傳遞 $ 1808 $ 有用的位$$ 226 bytes $$形成消息的可恢復部分；和 $ 192 $ 位$$ 24 bytes $$形成消息的不可恢復部分。 ISO/IEC 9796-2 具有迷宮般的特性和參數：三種方案；許多雜湊；可選的雜湊標識符
$$ intended to allow interoperability in contexts where the signer decides which hash is used, without requiring guesswork on the verifier side $$; 尺寸模數不是 8 的倍數；當雜湊允許時，消息大小不是 8 的倍數；全部或部分消息恢復；RSA 或 Rabin 簽名方案$$ an analog with even public exponent $$; 以及 RSA 簽名生成和打開函式的兩個略有不同的選項：那些未指定為替代簽名的選項 $ x\mapsto \min(x^d\bmod N, N-(x^d\bmod N)) $ 這比替代方案節省了一點：PKCS#1 的 RSASP1。EMV 最初參考 ISO/IEC 9796-2:1997，但僅使用部分消息恢復，本標準中未提及的替代功能，現在參考 ISO/IEC 9796-2:2010，未說明方案、功能或其他選項。歐洲數字行駛記錄儀 $$ annex 1B, appendix 11 $$當它在證書的簽名上下文中引用 ISO/IEC 9796-2 時與 EMV 一樣，但在其身份驗證和密鑰協商方案中也引用 ISO/IEC 9796-2，其中它使用方案 1 和總消息恢復$$ thus different padding than EMV $$以及該標準的非替代簽名生成和打開功能$$ because that enables re-encryption of the signature using a different private key with the same modulus size as the signature key, regardless of which modulus is smaller $$. ISO/IEC 9796:1991、ISO/IEC 9796-2 和 P1363a 的 EMSR3（類似於 ISO/IEC 9796-2）使用 RSA 或 Rabin 作為基礎公鑰密碼系統。還有ISO/IEC 9796-3，類似的 EMSR1 和 EMSR2，它們使用離散對數（可能在橢圓曲線組上）。
關於該問題評論中引用的 ISO/IEC 9796-2:2010 中的註釋：
出於實際目的，應用程序可能希望構造消息 $ M $ 確保將要明確儲存或傳輸的數據（例如地址資訊）分配給不可恢復的消息部分 $ M_n $
這是為了提請注意只有簽名消息的不可恢復部分
$$ if any $$在驗證簽名之前是可理解的。因此，需要在簽名驗證之前或不存在簽名驗證之前隨時可用的資訊最好放在消息的不可恢復部分，而不是可恢復部分。 作為一個真實的例子：與本說明中的建議相反，在上述歐洲數字行駛記錄儀規範中，證書中的消息
$$ defined by Annex 1B, appendix 11, 3.3.1 CSM_017 $$有身份證$$ designated CAR $$生成該證書的權威機構的公鑰放在開頭附近，因此位於消息的可恢復部分，因此在簽名驗證之前無法理解，在沒有上下文的情況下，確定哪個公鑰適合驗證該證書可能是一個問題. 為了避免這種情況，在簽名證書的末尾附加了一個 CAR 的副本，指定為 X.CAR$$ defined in 3.3.2 CSM_018 $$，如果證書是已知的並且其公鑰被記憶體，則允許不讀取證書頒發機構的證書，並有機會知道據稱是什么生成了證書，即使它未能驗證。這種複雜性將證書大小增加了 8 個字節，並且會混淆其 X.CAR 與 CAR 不匹配的假設證書是否被認為是有效的，以及是什麼/誰被認為生成了它；如果 CAR 位於證書數據的末尾，則可以避免這種情況，因此位於不可恢復的部分。
