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,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.
