RSA陷門置換的更快替代方案
我們正在開發 web3.0 去中心化網際網路，其中很大一部分是去中心化文件儲存系統，客戶將文件上傳到儲存提供商並支付服務費用。儲存提供商返回簽名消息，其中包含內容雜湊，作為保證，如果他們失去文件並且未能響應區塊鏈上的驗證挑戰，則無法提供他們仍在儲存文件的證據，他們將失去抵押品。
客戶端一次將文件上傳到多個儲存提供商以實現冗餘。我們需要確保提供者不能相互勾結/一個提供者不能將自己誤認為是多個提供者並為文件的 N 份副本付款，而只儲存一份副本。同時，原始文件內容應該始終可供儲存提供商使用，因為他們應該通過響應基於其雜湊的內容請求來在網路上公開提供它。這意味著使用 AES 加密多個副本
我最初想出的解決方案是在簽名模式下使用純 RSA（不是混合）算法，即當您使用私鑰加密並使用公鑰解密時（或者更準確地說，使用私鑰簽署消息，並使用其補充從簽名中恢復消息，但數學與加密/解密相同，只是交換了密鑰）。那樣：
- 客戶端可以為每個提供者生成一個密鑰對
F當使用提供者儲存文件時，它可以通過執行並將公鑰發送給提供者來生成特定於該提供者的（包含消息的簽名）N的“加密”副本F``F_N = RSASign(F, k_priv_N)``k_pub_N- 提供商在 上簽署保證
Hash(F_N)，承諾儲存加密副本F = RSARecover(F_N, k_pub_N)提供者可以在任何時候通過執行類似於將公鑰提供給解密算法來提取內容，計算真正的雜湊Hash(F)，並在 DHT 網路上提供這個文件- 但是，所有提供商，即使他們想串通，也必須繼續儲存單獨的加密副本/簽名
F_N，因為每個提供商都在其特定的Hash(F_N). 沒有辦法故意或意外失去，然後僅通過擁有andF_N按需重新創建它，因為這需要了解私鑰（這也解釋了為什麼 RSA 必須處於純模式，而不是混合節點，因為考慮到對稱密鑰，在提供者端執行 AES 加密是微不足道的，他們可以不必將 RSA 簽名儲存在對稱密鑰之上，對稱密鑰的大小要小得多）。F``k_pub_N這很好用，但我們遇到了這種方法的一些問題：
- 純模式下的 RSA 非常慢
- 為每個塊使用適當的填充會減少我們可用於嵌入文件塊的空間，因此生成的文件比原始文件大很多百分比
問：在這種情況下，我們是否可以使用其他類似的加密函式，它們在速度和大小上都優於 RSA 方案？
（例如，我們一直在研究橢圓曲線，但似乎沒有一種方法可以從 EC 簽名中提取消息，甚至是消息的散列，這也很有幫助。）
用私鑰加密，用公鑰解密
該聲明和名稱
privateEncrypt本身與標準術語不相容：“公共”意味著所有人都知道，反對“私人”；而“加密”意味著轉換一些資訊 $ X $ 進入 $ Y $ 在某種程度上，如果 $ Y $ 公開， $ X $ 才不是。根據標準術語，我們使用完全消息恢復簽名，並恢復消息。術語“全部消息恢復”指定了一種簽名方案，其中所有數據都在簽名本身中傳送。這就是 RSA 簽名的引入方式，該術語用於 ISO/IEC 9796 系列標準。
純模式下的 RSA 非常慢
無論名稱和變體如何，
RSASign確實相當緩慢，並且通常會擴大規模。這可以緩解，但仍會有些緩慢。另一方面，
RSARecover它相對較快，並且整數分解（基於）加密（IFC 系列，其中最著名的成員是 RSA）是迄今為止最快的非對稱加密。在應用程序中，如果資訊檢索在數量上占主導地位，那可能是一個優勢。在這種情況下，我們是否可以使用其他類似的加密函式，它們在速度和大小上都優於 RSA 方案？
在與 RSA 密切相關的系統之外，它們屬於 IFC，自從我開始觀看公鑰加密以來，我沒有遇到過任何系統¹。
讓我們看看如何緩解這些問題：
RSASign可以通過
- 使用大小合適的公共模數（並相應地將資訊分成塊²）。目前接受的最低簽名是 $ n=2048 $ -bit public 模數，並且在所有條件相同的情況下，每字節簽名成本的增長僅略慢於 $ n^2 $ .
- 使用中國剩餘定理方法。RSA 簽名的每個速度優化實現都可以做到這一點，因為它通常將計算成本降低了三倍以上。一些實現還使用它將大部分工作負載分散到多個 CPU 核心上，從而進一步減少加密時間。RSA 加密的實現不能使用該方法，因為它需要私鑰。
- 使用公共模數乘積 $ k>2 $ 素數。這被稱為multiprime RSA。在所有條件相同的情況下，當我們使用 3 個素數除以 4 個素數時，執行時間大致減半。如果高度的安全保證不是最重要的，那麼考慮 $ (n,k)=(2048,4) $ .
- 使用高度優化的實現。Shay Gueron 和 Vlad Krasnov 的使用 AVX2 架構的多素數 RSA 的速度記錄（在CIT 2016中）報告 $ (1.9,,1.0,,0.6) $ 百萬Skylake CPU 週期/簽名 $ n=2048 $ , $ k=(2,,3,,4) $ , 轉化為 $ (0.4,,0.7,,1.3) $ MByte/s/core @3GHz（由於填充而忽略時間和大小成本）。然後專用硬體是可能的。
大小成本取決於填充：
- 如果我們想使用標準化的東西並且不走捷徑，我們可以使用ISO/IEC 9796-2方案 2 和與雜湊大小一樣寬的隨機 nonce。大小成本是 $ 3h/2+16 $ 位出 $ n $ ，即 206 字節儲存在 SHA-256 的 256 字節密碼中，並且 $ n=2048 $ （+24.3% 成本）。即使實際儲存的數據完全不變，兩個儲存的塊也不太可能相同，直到有 $ 2^{64} $ ，即>3 ZiB的有效數據。
- 如果我們接受自定義的東西，確定性轉換（允許儲存相同數據塊的單個副本）並放棄加密簽名，則大小成本可以是每個塊一位（只需對數據應用可逆轉換，然後是教科書 RSA簽名，即教科書 RSA 加密），甚至為零（教科書 RSA 僅應用於可逆變換後低於公共模數的值，並生成公鑰/私鑰對，使公共模數的高 64 位為一體）。
RSARecover可以通過¹ 那是在 1980 年法國續約的其中一次罷工期間。根據Martin Gardner 的文章，我的數學 (Spé) 老師放棄了官方程序並展示了她的課程 RSA 。
² 正如評論中所指出的，如果我們只進行拆分，我們會失去整體消息完整性保證（對手可以交換簽名塊）。我不認為這種保證在上下文中是必不可少的。但是，如果我們需要它，我們可以在塊的有效負載前添加一個固定寬度的塊編號，但會增加大小成本。一個註釋建議“使用 CBC 而不是 ECB”，但這似乎不起作用，除非簽名的數據有些多餘。