啟動密鑰和非對稱加密
在我看來，創建啟動密鑰的一種非常安全的方法是使用非對稱加密，因此最終使用者只能對驗證方法進行逆向工程。通過這種方式，公司可以保證生成算法（和密鑰）的安全。
假設使用 1024 位密鑰的 RSA 加密。他們用私鑰對一些數據進行簽名，結果是 128 字節長。
他怎麼能把它裝進一個比這短得多的啟動密鑰中呢？例如 16 或 20 個字元左右。
驗證算法現在必須使用公鑰解密，並查看消息是否真的來自公司。當完整的加密消息未知時，它是如何完成的？
我上面的假設是否有錯誤，或者實際上是這樣完成的？
您不能將 RSA 簽名壓縮到遠低於私有模數大小。在前一個或兩個幾乎免費提供之後，我所知道的所有方法都會使每個額外的修剪位的簽名或驗證成本增加一倍。
可以修剪 RSA 簽名的高位：只需使用填充方案，以便填充的消息 $ R $ 驗證 $ 2R<N $ （PKCS#1的兩種填充方案都有這個屬性）；通常簽名是 $ S=R^d\bmod N $ ，而是使用 $ \tilde S=\min(S,N-S) $ , 至少比 $ N $ 是。在驗證者端，經過計算 $ \tilde R=\tilde S^e\bmod N $ ，取回原來的 $ R=\min(\tilde R,N-\tilde R) $ .
以更多工作為代價，簽名者可以通過使用隨機簽名方案來修剪更多位（即，使用相同密鑰的同一消息的多個簽名是不同的，因為消息代表存在隨機性；例如是 PKCS#1 的 RSASSA-PSS），並多次簽名，直到簽名恰好適當小（比如小於 16 位） $ N $ 是）。
以驗證者更多工作為代價，我們可以修剪更多位，驗證者可以通過反複試驗找到這些位（即低位 24 位）。
因此，將所有這些技巧結合在一起，簽名者將需要按照 $ 2^{13} $ 簽名（我假設公共模數是在由模數大小定義的區間的低端選擇的），以及驗證者 $ 2^{23} $ 檢查（這仍然是可以忍受的，尤其是 $ e=3 $ . 問題是我們節省了不到 4%（對於 1024 位模數）。
需要考慮的一件事是帶有消息恢復的 RSA 簽名方案，它在簽名中壓縮消息。一個例子是 ISO/IEC 9796-2，它允許大約 $ n-h-16 $ 簽名中的消息位 $ n $ -bit 公共模數 $ N $ , 和一個 $ h $ -位雜湊；對於 1024 位 RSA 和 SHA-256，它是 94 字節的消息（其中一些必須被刪除以保持與上述技巧兼容）。如果要傳達的消息接近或超過可恢復大小，並且在驗證簽名之前該消息是不可理解的並不重要，那麼在緊湊性方面，沒有什麼比 RSA（或 Rabin）更能恢復消息了。
然而，對於一個非常短的簽名，當消息恢復不適用時（包括當要簽名的消息不需要與簽名一起傳輸時，包括例如驗證者知道的客戶標識符），我們需要遠離基於整數分解的密碼學
長期以來，給出較短簽名的系統一直是 Schnorr 簽名方案（此處的描述和參考資料），基於離散對數問題，該方案具有 $ 3b $ -位（分別。 $ 4b $ -bit) 推測的簽名（分別證明） $ b $ 位安全。例如，對於 80 位推測安全性（有時與 1024 位 RSA 相比），簽名可以是 30 個字節。
有消息恢復變體（參考這裡）允許嵌入 $ b $ -bit 消息中的 $ 4b $ 具有可證明安全性的位簽名。
我們可以通過與 RSA 相同的技巧來修剪一些位，並且每個位修剪的相同詛咒使簽名者或驗證者之一的努力加倍。
還有更好的，尤其是Boneh-Lynn-Shacham 簽名，它接近 $ 2b $ -位簽名 $ b $ 位安全。但是，要使用的參數並不容易找到（因此這個問題），我的理解是計算要求並非微不足道。