Cryptanalyze the following cipher using modular exponentiation.

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?

• @moo yes I figured out what I needed to do. However, I'm now working a problem where $C\equiv P^{37}$ mod 41. I find that 13 is an inverse of 37 mod 40, so I should use $P\equiv C^{13}$ mod 41 to convert a ciphertext to plaintext, but my problem is that I end up with blocks above 25, so any ideas on how to figure out what letter it corresponds to? e.g. I need to convert 05, which in plaintext is 39.
– mmm
Mar 22, 2017 at 1:47
• I'm working a different problem, where p = 41, ciphertext block 12 corresponds to plaintext M (13).
– mmm
Mar 22, 2017 at 1:55
• $M = 12, N = 13$?...... In the above problem, $A = 0, ....Z=25$. has that changed for this problem?
– Moo
Mar 22, 2017 at 1:57
• Wow...okay so in that case if I'm looking at $12\equiv 12^e$ mod 41, then $e \equiv 1$, so the inverse of $e$ is just 1...which means my transformation is $C \equiv P$ mod 41. So I still run into a problem because the ciphertext I need to decrypt involves blocks of text larger than 25 (for example, I need to decrypt 35). What can I do here?
– mmm
Mar 22, 2017 at 2:01
• @moo as it turns out there was a mistake in the wording of the problem. It was supposed to say that ciphertext block 11 corresponds to M, not 12. So I have it figured out.
– mmm
Mar 24, 2017 at 0:16

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}$$

$$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$
• Once you have $e$, decryption just uses the exponent $d$ with $1 \equiv 5d \pmod {28}$, no more discrete roots needed. $19^{17} \pmod {29} = 14$ etc. So only one discrete log (for the known plain text), to find $e$ is needed the rest is trivial, as $d$ is easily computed. Mar 24, 2017 at 19:10
• I agree and that is precisely what I did. The OP asked how one can find this generally and that is what that part of the answer is addressing.
– Moo
Mar 24, 2017 at 19:36