Discrepancy in modular encryption

Question

I'm trying to work through an encryption assignment and the instructions aren't particularly clear because they don't go hand in hand with the lecture video.

Using encryption key e = 9 in modulo 23, perform the following calculations:

1. Take the secret message M = 21, encrypt this message as a number E. Note down the value of E.
2. Let d be the decryption key for this encryption system. Compute d. Complete the following sentence: e × d ≡ a(mod b). Note down the value of a, b and d.
3. Use the results above (or an alternative approach) to decrypt the secret message M that was encrypted as E = 15. Note down the value of M.

I was sorta able to do the first one but I have my doubts. So e = 9, p = 23(got this from a classmate) and M = 21. The encryption algorithm given in the lecture was E ≡ M^e (mod p) and that turned out to be 17. So the message 21 was encrypted to 17. I am going off of p = 23 from a classmate but I don't quite get she got that value from.

The 2nd issue that I'm having is E = 15 in #2. The value is suppose to be 17.

The 3rd issue I'm having is the value of a. I know the value for e and I can find d by isolating it but I don't know what to make of a.

I'm not asking anyone to do my homework for me. My problem is that this is super unclear and half-assed. I was wondering if those well-versed in encryption can break this down for me and highlight my mistakes.

Answer 1

This is a toy system that is used in didactic contexts as an introduction to RSA, in a way.

We have some prime $p$ (we are going to do the power operations modulo this prime). If $m$ is the message (an integer in $\{1,\ldots,p-1\}$), we have some encryption exponent $e$, and encryption indeed works as $$E(m) = m^e \pmod{p}$$.

So for $p=23$, $e=9$ we indeed have $E(21)=17$, as $21^{9} = 17 \pmod{23}$.

The decryption exponent $d$ can be found by solving $ e \times d = 1 \pmod{p-1}$ (the $p-1$ is $\phi(p)$ and Euler's/Fermat's theorem tells us that $m^{\phi(p)} = m \pmod{p}$ for all non-zero $m$.) So exponentiation with $d$: $$D(m)=m^d \pmod{p}$$ is the inverse of $E$ and vice versa.

In your number example with $p=23, m=21, e=9$ we have $p-1=22$ and $9 \times 5 = 1\pmod{22}$ and indeed $D(17)=17^{5}=21\pmod{p}$ as expected: we get back our starting value $m$.

In #3 you know $E(m)=15$ so $m=D(15)=15^5 \pmod{23}= 7$. You should distinguish $E = E(m)$ from the exponent $e$.

So this system crucially depends on $e$ being kept secret, otherwise $d$ is pretty trivial to compute via Euclid's algorithm (that's how I found $d=5$ too) and anyone can decrypt. RSA depends on the fact that given $n$ of the form $pq$, with large unknown $p$ and $q$, makes it hard to find $\phi(n)$ and hence $d$ from $e$, as we find $d$ by solving $e \times d = 1 \pmod{\phi(n)}$ where $n$ is the modulus we are using, like $p$ in your case.

Answer 2

Encryption key "e = 9 in modulo 23" means $e=n\mod{p}$, or $e=9\mod23$. The given encryption algorithm is $E=M^e(\mod{p})$. Do you see how your classmate got $p=23$ now?

The value you get for $E$ is wrong. $E=(21^9)(\mod{23})$. Always check your work with a calculator, don't trust doing math by hand. I got this drilled into me at a young age by my father, who is a mathematician. It's too easy to screw up, and errors propagate, so having a sanity check is always a good idea.

For finding $d$, this is a simplified version of RSA, so $e\times d=1(\mod{p-1})$

The missing information from the question (a bit about how RSA works) is stuff you're probably expected to have read about in a textbook or learned in a lecture. You should be able to figure out the answer from this. If not the other answer has a bit more of the work done.