Cryptanalyze the following cipher using modular exponentiation.

Question

I am given a modulus $p=29$ and the following ciphertext: 04 19 19 11 04 24 09 15 15. I am also given that 24 corresponds to the plaintext letter U (in otherwords, 20).

I know that $C\equiv P^e$ mod $p$ in modular exponentiation. I can use the fact that 24 corresponds to the plaintext 20 so $24 \equiv 20^e$ mod $p$. I can guess and check to find that $e=5$. However, is there a more algorithmic way of finding this to expand to cases when it isn't so easy to guess and check?

Answer 1

This is known as the Discrete Log Problem and the site lists several algorithms to solve it.

The discrete logarithm problem is to find the exponent in the expression $$Base^{Exponent} = Power \pmod{Modulus}$$

In your case, we have

$$20^e \equiv 24 \pmod{29}$$

One of the algorithms listed (learn and try some of the others) on the site (overkill for this small problem) is Pohlig-Hellman. We will use the Discrete logarithm calculator by Dario Alpern and it immediately finds

$$e = 5$$

As an aside, you can see a more detailed and worked example here: Use Pohlig-Hellman to solve discrete log.

For the message, we have

• $04 \equiv P^5 \pmod{29} \implies P = 06 = G$
• $19 \equiv P^5 \pmod{29} \implies P = 14 = O$
• $19 \equiv P^5 \pmod{29} \implies P = 14 = O$
• $11 \equiv P^5 \pmod{29} \implies P = 03 = D$
• $04 \equiv P^5 \pmod{29} \implies P = 06 = G$
• $24 \equiv P^5 \pmod{29} \implies P = 20 = U$
• $09 \equiv P^5 \pmod{29} \implies P = 04 = E$
• $15 \equiv P^5 \pmod{29} \implies P = 18 = S$
• $15 \equiv P^5 \pmod{29} \implies P = 18 = S$