用於加密 1 字節資訊的最短輸出的非對稱加密方案
想像一下，需要定期加密非常短的消息（即布爾值是/否、單個字節，或者在最壞的情況下為 3-4 個字節）。我們假設沒有會話，我們只需要在接收者的公鑰下加密（即，將加密的字節發佈到區塊鏈）。
我知道 ElGamal、Cramer-Shoup、RSA、ECIES 加密等，我正在尋找加密少量資訊時輸出最短的算法。
我想保持至少 128 位的安全性，因此想知道是否存在針對短消息優化的 ElGamal 變體。我們知道橢圓曲線上的 ElGamal 輸出 64 字節的密文（假設我們在使用 256 位橢圓曲線時加密長度高達 32 字節的消息）。
文獻中是否有一種不對稱方案可以輸出比這更少的字節？理想情況下 30-32 字節？
出乎我的意料，我在標準 256 位橢圓曲線上提出了這個 EC-ElGamal 變體，對加密部分使用雜湊和 XOR（與教科書 EC-ElGamal 相比，密文大小幾乎減半），以及簡單的工作/空間交易-off 進一步將消息壓縮成 32 字節的密文 $ m $ 的 $ b $ 位，小固定 $ b $ （例如 $ b=8 $ ).
在場上使用標準橢圓曲線 $ \mathbb F_p $ 帶發電機 $ G $ 有秩序的 $ n $ ， 和 $ p $ 和 $ n $ 256 位素數和（推測的）128 位安全性。secp256r1（又名 NIST P-256）和secp256k1符合條件。我參考Sec1v2的 ECC 數學和符號。
密鑰生成：
- 選擇私鑰 $ d $ 區間內隨機 $ [1,n) $
- 計算公鑰 $ Q\gets d,G $
加密 $ b $ -位明文 $ m $
- 選擇 $ e $ 區間內隨機 $ [1,2^{32}) $
- 計算 $ F\gets e,G $
- 選擇 $ k $ 區間內隨機 $ [1,n) $
- 計算 $ R\gets k,G $
- 儘管 $ R_x\not\equiv0\pmod{2^b} $
- 計算 $ R\gets R+F $ 和 $ k\gets k+e $ ，它保持 $ R=k,G $
- 如果 $ k\ge n $ 選擇的RNG $ k $ 很可能壞了；中止或重新啟動加密
- 如果 $ R_y $ 是奇數，集合 $ R_y\gets p-R_y $ 和 $ k\gets n-k $ ，它保持 $ R=k,G $
- 計算 $ S\gets k,Q $ （共享秘密點）
- 計算 $ u\gets \operatorname{SHA-256}(S_x)\bmod2^b $ ， 在哪裡 $ S_x $ 表示為 32 字節的字節串
- 計算 $ v\gets u\oplus m $
- 輸出256位密文，包括 $ 256-b $ 位 $ R_x $ 與低階 $ b $ 被移除的位（它們在構造上為零），並且 $ b $ 位 $ v $
解密：
- 從密文中提取 $ R_x $ （插入 $ b $ 低位為零）和 $ v $
- 計算一個 $ R_y $ 匹配 $ R_x $ （這是撤消點壓縮的標準技術，請參見Sec1v2 §2.3.4，步驟 2.4.1）；如果失敗，則中止解密。
- 如果 $ R_y $ 是奇數，集合 $ R_y\gets p-R_y $
- 計算 $ S\gets d,R $ （共享秘密點）
- 計算 $ u\gets \operatorname{SHA-256}(S_x)\bmod2^b $ ， 在哪裡 $ S_x $ 表示為 32 字節的字節串
- 計算並輸出解密後的明文 $ m\gets u\oplus v $
我推測IND-CCA1（因此IND-CPA）的安全性為 128 位級別，在合理的假設下（橢圓曲線的決策 Diffie-Hellman 問題的變體的硬度，以及建模為隨機預言的 SHA-256）。對 IND-CCA2 有一個微不足道的攻擊（因此，即使解密 oracle 已將原始密文列入黑名單，對解密 oracle 的訪問也會損害過去消息的機密性；這在實踐中不是問題）。
請注意，密碼具有微弱的延展性。這允許攻擊者通過更改密文中的這些位來翻轉明文中的所需位。這可能是一個實際問題。通過替換可以在一定程度上緩解這種情況 $ u\oplus\ldots $ 通過具有更廣泛的格式保留加密 $ u $ 作為關鍵；或/和更多工作或/和空間。
加密時的 while 循環是時間/空間的權衡，搜尋 $ k $ 通過列舉，它是 $ x $ 協調 $ R_x $ 有 $ b $ 不需要傳輸的低位為零。搜尋已優化為要求 $ \approx2^b $ 點加法，但對於 $ b $ 大約開始 $ 8 $ 這將成為一種痛苦。使用秘密增量 $ e $ 和匹配 $ F=e,G $ 是一個很好的進入決賽 $ k $ 更統一（見註），但我知道如果我們採取 $ e=1 $ 因此 $ F=G $ . 進一步增加秘密可以幫助減輕側通道攻擊。
如果我們想避免部分或全部時間/空間權衡，我們可以
- 簡單地說，增加密文大小。
- 或/和冒險生成自定義曲線，位大小為 $ n $ 和 $ p $ 從 256 減少了幾位。對於我們放棄的每 1 位安全性，我們獲得大約 2 $ n $ 和 $ p $ ，因此在密文位上，或者在 while 循環中減少 4 倍的猜測。而對於 secp256r1，最知名的攻擊可能需要 $ >2^{140} $ 位操作（基於對類似聲明的保守推斷 $ >2^{140} $ 對於 Ed25519）。
注意：在教科書 Diffie-Hellman 或 ElGamal 中，我們選擇 $ k $ 均勻地在 $ [0,n) $ . 我們的變體限制為 $ k $ 和 $ k,G $ 有一個 $ x $ 與它的低階協調 $ b $ 位為零。通過統計論證，大約有 $ n/2^b $ 這樣的 $ k $ . 我們想選擇 $ k $ 均勻地在這個子集中 $ [0,n) $ . 最簡單的是隨機重複 $ k $ ，但這對於點乘法來說具有高昂的計算成本 $ R\gets k,G $ . 我們通過從一名候選人轉移來節省這一點 $ k $ 到下一個固定增量 $ e $ , 允許更新 $ R $ 通過單點加法 $ R\gets R+F $ .
如果我們使用固定 $ e=1 $ ，那麼 $ k $ 由 while 循環選擇將具有可區分的屬性（對於一個知道 $ k $ ): a 的機率 $ k $ 被選中 正比於 $ j $ 可計算自 $ k $ 作為最小的 $ j>0 $ 這樣 $ k-j $ 在子集中（或 $ k+1 $ 如果沒有這樣的 $ j $ , 單次發生 $ k $ 在子集中）。該問題類似於通過選擇隨機起點並蒐索下一個素數獲得的素數的非均勻選擇。
選擇任何公共固定 $ e $ 不能解決問題，因為定義 $ j $ 可以適應 $ k-e,j $ 在子集中。然而，選擇一個隨機的秘密 $ e $ 對於每一個選擇 $ k $ 做。類似的技術用於 RSA 的隨機素數生成器。我沒有參考資料，但有一個論點是對手不知道 $ e $ 不知道什麼 $ e $ 用於測試；他們可以測試所有人 $ e $ 並結合結果，但隨後他們的測試就被噪音淹沒了。
我選擇了區間的上限 $ [1,2^{32}) $ 為了 $ e $ 使得計算 $ F\gets e,G $ 與 $ R\gets k,G $ . 我有信心（沒有證據或參考）這足以使選擇 $ k $ 即使假設的對手知道，實際上也無法檢測到 $ k $ ; 而真正的對手只能得到 $ k $ 通過側通道。
最後的想法：我們可以消除對標準的任何恐懼 $ R_x\equiv0\pmod{2^b} $ 通過將其調整為：低 $ b $ 一點 $ R_x $ 是其他位的一些功能（具有大約均勻分佈） $ R_x $ . 一個 $ b $ -bit CRC 可以。接收器可以重建必要的低位比特 $ R_x $ 通過應用此功能。