3
$\begingroup$

To encrypt a message $M$, we compute $C=M^k \bmod p$ and to decrypt a Cipher-text we compute $M=C^{k^{−1} \bmod (p−1)} \bmod p$

But if we use Pohlig Hellman twice like $C_1=M^k \bmod p$, and then $C_2=C_1^k \bmod p$, So is this more secure than doing it just once or not.

And what if we do it multiple times like a Cascade?

$\endgroup$
2
$\begingroup$

So is this more secure than doing it just once or not.

TL;DR; No, multiple encryptions are equal to single encryption and this is not better than single encryption

Pohlig-Hellman Cipher

In setting up of Pohlig-Hellman Cipher;

  • Select a large prime modulus, let say $p$,
  • then select a public modulus $e$ with $\gcd(e,\varphi(p))=1$ otherwise no unique decryption.
  • so, we have a public key as $(e,p)$.
  • Your private key is the tuple $(d,p)$ such that $e \cdot d \equiv 1 \bmod \varphi(p)$.

To encrypt a message Alice take a message $m < p$, then encrypt you with $$c = m^e \pmod p$$

Once, you get the message you decrypt by $$ c^d = m^{e\cdot d} \equiv m \pmod p$$ with the help of the Little Fermat Theorem.

Example:

  • p = 3001
  • e = 37
  • d = 973

    let $m = 57$ then $c = 57^{37} \equiv 2778 \pmod{3001}$

    with $c = 2778$ then $ m = 2778^{973} = 57 \pmod{3001} $

Cascade Property: Double encryption is single encryption

To show the cascade property we will use the same modulus with different parameters. This will show that double encryption is equal to single encryption.

Let $p$ is the modulus, $(e_1,p)$ and $(d_1,p)$ be corresponding pairs and $(e_2,p)$ and $(d_2,p)$ be another pair. Let encrypt a message $m$ with the first public key then with the second.

$$c_1 = m^{e_1} \pmod p$$ then $$c_2 = c_1^{e_2} = (m^{e_1})^{e_2} = m^{e_1 \cdot e_2} \bmod p$$

Let call $e' = e_1 \cdot e_2 \pmod{\varphi(p)}$ and $d = e'^{-1} \pmod{\varphi(p)}$

Therefore $(e',d')$ will be the single key for the double encryption

Example:

Continue the previous example with $(31,3001)$ and $(871,3001)$ as second public and private keys.

$$2778^{31} \equiv 197 \pmod{3001}$$

$$e' = 31*37 \equiv 1147 \pmod{3000}$$

$$d' = 1483 \pmod{3000}$$

Now, decrypt with $d'$

$$ 197^{1483} \equiv 57 \pmod{3001}$$


Some notes on Pohlig-Hellman Cipher

  • It is vulnerable to KPA.
  • It is not IND-CPA secure
  • It is Multiplicative
  • No probabilistic Encryption.
  • Security relies on the discrete logarithm
  • The prime $p$ must be chosen properly, safe prime*, against Pohlig-Hellmans' algorithm for finding a discrete log.

*A safe prime is a prime number of the form 2p + 1, where p is also a prime

| improve this answer | |
$\endgroup$
1
$\begingroup$

No, double-encryption with (textbook) Pohlig-Hellman does not improve security, if we use the same public prime $p$. This is even if we use different keys $k_1$, $k_2$ for the two encryptions (as in the question's title).

Justification: if $C_1=M^{k_1} \bmod p$, and $C_2={C_1}^{k_2} \bmod p$, then $C_2=M^{k_1\,k_2\bmod(p-1)} \bmod p$, hence the two encryptions are equivalent to a single encryption under key $k'=k_1\,k_2\bmod(p-1)$. Another way to state the same fact is that Pohlig-Hellman encryption transformations form a group isomorphic to $\Bbb Z_{p-1}^*$.

If we double-encrypt with $k_1=k=k_2$ (as in the question's body), security is even slightly reduced, because the number of possible encryption transformations tends to decrease. This increases the chance that encryption leaves $C_2=M$, or that repeatedly submitting the ciphertext to an encryption oracle ends up deciphering it, which is an issue for artificially small parameters.


Notes: (textbook) Pohlig-Hellman is vulnerable to Chosen-Plaintext Attack and Known-Plaintext Attack, since it is multiplicatively homomorphic and deterministic. It's mostly useful as a building block in other cryptographic primitives or protocols. For standard 128-bit security (within the above limitations), $p$ should be a prime at least 2048 or 3072-bit (depending on estimates) not of a special form $r^e\pm s$ where $r$ and $s$ are small, and with $p-1$ having an at-least 256-bit prime factor (the later is insured when the former is and $p$ is a safe prime).

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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