實現 Pohlig-Hellman 密碼
出於此處解釋的原因，我需要使用 Pohlig-Hellman 指數密碼。但是，我似乎無法在任何地方找到該密碼的實現。從頭開始實施似乎並不太難 - 所以，我想嘗試一下。
我確實有以下問題：
- 我該如何選擇素數？根據這個，我應該選擇一個大的隨機素數，使得**(p-1)/2**是素數。但是我應該使用什麼算法來做到這一點？此外，2048 位是否足以滿足我的目的（下面的一些上下文）？
- 我該如何選擇鑰匙？我認為這些應該是很大的隨機數，但是有多大呢？我想讓加密與其他更常用的密碼一樣安全。
提供更多背景資訊：我將加密相對較小的消息。我的絕大多數消息都將小於 32 字節，並且沒有消息將大於 64 字節。我將在加密消息之前使用鹽填充和加擾消息以避免確定性輸出。
公共模數的選擇 $ p $
用於 $ p $ 一個大的安全素數（即，一個素數 $ p=2q+1 $ 和 $ q $ 也是素數）是使用 Pohlig-Hellman 密碼的方法，因為
- 簡化了加密密鑰的選擇 $ k $ : 隨機奇數 $ k $ 在範圍內 $ [1,q-2] $ 會做，因為這樣可以確保 $ \gcd(k,p-1)=1 $ （Pohlig-Hellman 密碼中指數的有效性條件）；
- 使恢復 $ k $ 來自範例明文/密文對 $ (m,c=m^k\bmod p) $ 推測起來很難，特別是避免了以下情況 $ p-1 $ 會很順利，可以找到 $ k $ 通過Pohlig-Hellman 離散對數算法快速。
為了防止SNFS 算法的離散對數變體，還建議使用 $ p $ 不是特殊形式 $ r^e\pm s $ 對於小 $ r,s $ .
假設這一點，人們一致認為，除非出現可用於密碼分析或驚人算法進展的量子電腦，否則 3072 位 $ p $ 幾十年內很可能沒問題（例如，舒適的 128 位安全性），而 2048 位可能沒問題。
因為要求 $ p $ 與Diffie-Hellman密鑰交換相同，有現成的，無異議的 $ p $ . 這 $ p=2^{3072}-2^{3008}-1+2^{64}\cdot(\lfloor2^{2942}\pi\rfloor+1690314) $ 適用於RFC 3526的 3072 位 MODP 組（以下十六進制值）
FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6BF12FFA06D98A0864D87602733EC86A64521F2B18177B200CBBE117577A615D6C770988C0BAD946E208E24FA074E5AB3143DB5BFCE0FD108E4B82D120A93AD2CAFFFFFFFFFFFFFFFF故意為此 $ p $ 及其 1536 到 8192 位的類似物：
- 最左邊的 66 位是 1，這簡化了經典模約簡中的商估計；
- 最右邊的 64 位是 1，這同樣簡化了蒙哥馬利算術；
- 大多數中心位是從 $ \pi $ ，並且幾位數的常數對於達到安全的素數來說是最小的，所以這些都是我袖手旁觀的數字。
加密密鑰的選擇 $ k $ 和解密密鑰 $ k’ $
要求是 $ k $ 是一個秘密的互質數 $ p-1 $ ; 也就是說，隨著我們的選擇 $ p=2q+1 $ 和 $ q $ 素數，那個 $ k $ 是奇數而不是的倍數 $ q $ . 這確保存在匹配的解密密鑰 $ k’ $ 和 $ k\cdot k’\equiv1\pmod{p-1} $ ，這反過來確保（通過直接應用費馬小定理）對於任何消息代表 $ m $ 和 $ 0\le m<p $ , $ {(p^k\bmod p)}^{k’}\bmod p=m $ ; 也就是加密 $ m $ 和 $ k $ 其次是解密 $ k’ $ 會回到 $ m $ .
選擇就夠了 $ k $ 作為範圍內的真正隨機奇數 $ [1,(p-3)/2] $ ，或其中的某個子範圍（至少約為 $ 2^{2b} $ 可能的值 $ b $ -bit 安全性，沒有足夠的建設性證據）。例如，如果 $ p $ 是 $ n $ -bit，畫得很好 $ n-4 $ 隨機位，在左側和右側附加一個位以形成一個 $ (n-2) $ -bit 奇數整數（無論字節順序如何都有效）。關鍵是生成器使用了一些無法猜測的熵，而關鍵 $ k $ （和匹配 $ k’ $ ) 保密，包括在使用期間。對側通道的保護將是一個嚴重的問題。
解密密鑰 $ k’=k^{-1}\bmod(p-1) $ 可以用（半）擴展歐幾里得算法計算。另一種方法給 $ k’ $ 正在計算 $ k^{q-2}\bmod q $ 並添加 $ q $ 當結果是偶數時。
注意：如問題中所述，建構消息代表 $ m $ 從實際數據到傳輸應小心謹慎。一個安全的選擇是重用 RSA 的OAEP結構。