I am looking into implementing Pohlig-Hellman exponentiation cipher and I would like to know how secure that algorithm is? I am guessing it's security relates greatly to the prime number used in it. Does anyone have some reference that might be helpful in determining the minimal prime number one should use in order to ensure the algorithm is safe enough for various applications?
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ Looking at the requirements for the hardness of the discrete logarithm problem (DLP) would be a good start. Indeed, $p$ needs to be chosen with care, a large random prime simply won't do. Size is only half of the story. As in $\log{(p)}$, I mean. $\endgroup$– ThomasCommented Mar 2, 2013 at 22:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
You need a large random prime modulus where the discrete log is hard. Read about how to choose a prime so the discrete log is hard. Also, you want $p-1$ to have as few small factors as possible. Therefore, the short version is, I suggest you choose a large random 2048-bit prime $p$ such that $(p-1)/2$ is prime.
However, Pohlig-Hellman has some serious issues. It has very poor performance, compared to other symmetric-key ciphers. Also, it has no randomization, so it is not semantically-secure (it is not IND-CPA secure) in its standard form. I don't know of anyone who uses the Pohlig-Hellman cipher in practice, in its standard form; it is more of theoretical interest than practical interest.
What exactly do you want to do with the Pohlig-Hellman cipher? What exactly is your application? Why do you want to use the Pohlig-Hellman cipher? There might be better solutions.
-
$\begingroup$ I need a commutative cipher for an application where two or more peers need to encrypt and decrypt data out of order. I can only find information on two algorithms, with this being the better one apparently. I guess I should ask about commutative ciphers in a separate question... $\endgroup$ Commented Mar 3, 2013 at 21:42
-
$\begingroup$ Actually, here is the question about the same thing - crypto.stackexchange.com/a/1366/843 . $\endgroup$ Commented Mar 3, 2013 at 21:43
-
1$\begingroup$ @ThePiachu, I encourage you to ask you to ask a question about your particular application, instead of asking about Pohlig-Hellman. Don't assume Pohlig-Hellman is the best solution; let us advise you on the best solution. There may be better solutions to your problem. [The question you link to is an excellent example of that: for that problem, Pohlig-Hellman is the wrong solution (for some reason the OP has become focused on it, but it's not the best solution); the right solution is based upon private set-intersection protocols, which solve exactly the problem that OP had.] $\endgroup$– D.W.Commented Mar 4, 2013 at 1:15
-
$\begingroup$ The application is mental poker. I asked about the security in a separate question - crypto.stackexchange.com/q/6575/843 . $\endgroup$ Commented Mar 4, 2013 at 5:52