# Math Help - Simple RSA message decryption

1. ## Simple RSA message decryption

Ok So I am given:

(e,N) = (7,33)

The Received message s = 2. What is the original message (m) sent?

So I start out by calculating my p and q.
N = p*q -> p = 11 q = 3
phi(n) = (p-1)(q-1)

Then using this formula
ed = 1(mod(phi(n)))
and that results in a d = 3. But I am starting to think that this is the encryption formula. Our teacher did not really specify which formula to use with what part. Am I at all on the right track?

2. Hello,
Originally Posted by jskill
Ok So I am given:

(e,N) = (7,33)

The Received message s = 2. What is the original message (m) sent?

So I start out by calculating my p and q.
N = p*q -> p = 11 q = 3
phi(n) = (p-1)(q-1)

Then using this formula
ed = 1(mod(phi(n)))
and that results in a d = 3. But I am starting to think that this is the encryption formula. Our teacher did not really specify which formula to use with what part. Am I at all on the right track?
Let m be your message.

You know that $m^e=s (\bmod n)$ (this is the encryption formula)

Now, you've found d.
From Euler's theorem, we know that $m^{\varphi(n)}=1 (\bmod n)$
So once you've found d, the aim is this :

$s^d=m^{ed}=m^{1+k \varphi(n)} (\bmod pq)$, because $ed=1 (\bmod \varphi(n)) \Leftrightarrow \exists k \in \mathbb{Z} ~ :~ed=1+k \varphi(n)$

So $m^{1+k \varphi(n)}=m \cdot \left(m^\varphi(n)\right)^k=m (\bmod n)$ (using basic properties of exponents)

Therefore, finding d will let you decrypt a message, namely s.

You can see that $s^d=m (\bmod n)$
So from the message your receive, you can get the message that was sent !

Does it look clear to you ?

3. Originally Posted by jskill
Ok So I am given:

(e,N) = (7,33)

The Received message s = 2. What is the original message (m) sent?

So I start out by calculating my p and q.
N = p*q -> p = 11 q = 3
phi(n) = (p-1)(q-1)

Then using this formula
ed = 1(mod(phi(n)))
and that results in a d = 3. But I am starting to think that this is the encryption formula. Our teacher did not really specify which formula to use with what part. Am I at all on the right track?
Hi jskill,

It does look like the encryption formula to me.

Try $m = s^{e}\mod n$ instead.

4. Ok thanks for the help I follow how you got to those equations and so I wind up with

Try $m = s^{e}\mod n$
m = 2^3 (mod33)
m = 8 mod 33
m = 41

I am assuming I followed that all correctly. Also I am still kinda confused on how the professor expected us to decrypt a message without supplying any information about the decryption formula. Owell Thanks again