Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am looking into implementing Pohlig-Hellman exponentation 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?

share|improve this question
2  
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. –  Thomas Mar 2 '13 at 22:58
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
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... –  ThePiachu Mar 3 '13 at 21:42
    
Actually, here is the question about the same thing - crypto.stackexchange.com/a/1366/843 . –  ThePiachu Mar 3 '13 at 21:43
    
@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.] –  D.W. Mar 4 '13 at 1:15
    
The application is mental poker. I asked about the security in a separate question - crypto.stackexchange.com/q/6575/843 . –  ThePiachu Mar 4 '13 at 5:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.