1
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ @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. $\endgroup$
    – mmm
    Mar 22, 2017 at 1:47
  • $\begingroup$ I'm working a different problem, where p = 41, ciphertext block 12 corresponds to plaintext M (13). $\endgroup$
    – mmm
    Mar 22, 2017 at 1:55
  • $\begingroup$ $M = 12, N = 13$?...... In the above problem, $A = 0, ....Z=25$. has that changed for this problem? $\endgroup$
    – Moo
    Mar 22, 2017 at 1:57
  • $\begingroup$ 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? $\endgroup$
    – mmm
    Mar 22, 2017 at 2:01
  • 1
    $\begingroup$ @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. $\endgroup$
    – mmm
    Mar 24, 2017 at 0:16

1 Answer 1

0
$\begingroup$

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$
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Mar 24, 2017 at 19:10
  • $\begingroup$ 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. $\endgroup$
    – Moo
    Mar 24, 2017 at 19:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .