Implementing Pohlig-Hellman Exponentiation chiper

I need to use Pohlig-Hellman exponentiation cipher for reasons explained here. However, I can't seem to find an implementation of this cipher anywhere. It doesn't seem to be too difficult to implement from scratch - so, I want to try.

I do have the following questions:

1. How do I go about choosing primes? According to this, I should choose a large random prime such that (p−1)/2 is prime. But what algorithm should I use to do that? Also, is 2048 bits enough for my purposes (some context below)?
2. How do I go about choosing keys? I think these should be large random numbers, but how large? I would like to make the encryption as secure as with other more commonly used ciphers.

To give a bit more context: I would be encrypting relatively small messages. Vast majority of my messages will be under 32 bytes, and no message will be larger than 64 bytes. I will be padding and scrambling messages using salts before encrypting them to avoid deterministic output.

Choice of public modulus $p$

Using for $p$ a large safe prime (that is, a prime $p=2q+1$ with $q$ also prime) is the way to go for the Pohlig-Hellman cipher, because that

• simplifies the choice of encryption key $k$: a random odd $k$ in range $[1,q-2]$ will do, because that ensures that $\gcd(k,p-1)=1$ (the condition for validity of an exponent in the Pohlig-Hellman cipher);
• makes recovering $k$ from sample plaintext/ciphertext pairs $(m,c=m^k\bmod p)$ conjecturally hard, and in particular avoids the case where $p-1$ would be smooth, allowing to find $k$ quickly by the Pohlig-Hellman Discrete Logarithm algorithm.

To guard against the Discrete Logarithm variant of the SNFS algorithm, it is also recommendable that $p$ is not of the special form $r^e\pm s$ for small $r,e,s$.

Provided this, there is consensus that, baring apparition of Quantum Computers usable for cryptanalysis or spectacular algorithmic progress, a 3072-bit $p$ is most likely fine for some decades (say, comfortable 128-bit security), and 2048-bit likely fine .

Because the requirements for $p$ are the same as for Diffie-Hellman key exchange, there are ready-made, unobjectionable $p$. The $p=2^{3072}-2^{3008}-1+2^{64}\cdot(\lfloor2^{2942}\pi\rfloor+1690314)$ of the 3072-bit MODP Group of RFC 3526 is suitable (hex value below)

FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6BF12FFA06D98A0864D87602733EC86A64521F2B18177B200CBBE117577A615D6C770988C0BAD946E208E24FA074E5AB3143DB5BFCE0FD108E4B82D120A93AD2CAFFFFFFFFFFFFFFFF


Intentionally, for this $p$ and its 1536 to 8192-bit analogs:

• leftmost 66 bits are ones, which simplifies quotient estimation in classical modular reduction;
• rightmost 64 bits are ones, which similarly eases Montgomery arithmetic;
• most center bits are borrowed from $\pi$, and the few-digits constant is minimal to reach a safe prime, so these are nothing-up-my-sleeves numbers.

Choice of encryption key $k$ and decryption key $k'$

The requirement is that $k$ is a secret coprime with $p-1$; that is, with our choice of $p=2q+1$ with $q$ prime, that $k$ is odd and not a multiple of $q$. This ensures there exists a matching decryption key $k'$ with $k\cdot k'\equiv1\pmod{p-1}$, which in turn insures (by a straightforward application of Fermat's little theorem) that for any message representative $m$ with $0\le m<p$, ${(p^k\bmod p)}^{k'}\bmod p=m$ ; that is, encryption of $m$ with $k$ followed by decryption with $k'$ will get back to $m$.

It is enough to choose $k$ as a truly random odd integer in range $[1,(p-3)/2]$, or some sub-range of that (with a bare minimum of about $2^{2b}$ possible values for $b$-bit security, with no constructive proof that's enough). For example, if $p$ is $n$-bit, it is fine to draw $n-4$ random bits, append a one bit on the left and on the right to form an $(n-2)$-bit odd integer (that works regardless of endianness). What's critical is that the generator uses some unguessable entropy, and that the key $k$ (and matching $k'$ ) are kept secret, including during use. Protection against side channels is going to be a serious issue.

The decryption key $k'=k^{-1}\bmod(p-1)$ can be computed with the (half) extended Euclidean algorithm. Another method giving $k'$ is computing $k^{q-2}\bmod q$ and adding $q$ when the result is even.

Note: as stated in the question, constructing the message representative $m$ from the actual data to transmit should be done with care. A safe option would be to reuse the OAEP construction of RSA.

• Exactly what I was looking for! Thank you! I might have some follow-up questions - but this is awesome. – irakliy Apr 6 '18 at 17:34
• One follow-up question: I ran some tests and it seems like size of the ciphertext ends up being very close to the size of p, regardless of the size of the plaintext. For example, when I used 2048 bit prime, the cipher text was always in the range between 2040 and 2048 bits for plaintexts ranging from 1 bit to 2000 bits. Is this to be expected? Is there any way to reduce the size of the ciphertext without compromising security? – irakliy Apr 7 '18 at 3:43
• @Irakliy: what you are observing is expected, because in PH cipher, ciphertext is essentially random-like in $[0,p)$. That's inherent to PH, and similar to RSA, where ciphertext is essentially random-line in $[0,N)$. Shorter ciphertext would require use of a different group, as discussed here. – fgrieu Apr 7 '18 at 5:25
• One more follow-up. Is there a reason to make $k$ bigger than 256 bits? I read somewhere that having exponent over 256 bits doesn't add any security from a practical standpoint. – irakliy Apr 7 '18 at 18:02
• @Irakliy: I know no compelling reason to make $k$ greater that 256-bit (for 128-bit security), at least with proper padding; I edited to reflect that. On the other hand, we can't make both the encryption and decryption exponent short, so the overall gain reducing the exponent achieves, both in space and speed, is <2. – fgrieu Apr 7 '18 at 18:23