Question

Let the letters of the alphabet be A=01, B=02, . . , Z=26. For RSA encryption let n=119 and e=5.

What letter is encrypted as 44? You must answer this question by "cracking" the code, that is, by decrypting rather than by trial and error. You must show or explain your work, however you accomplish obtaining an answer. (Hint: modular exponentiation may come in handy.)

Answer 1

what do you mean what letter is encrypted as 44?

Answer 2

\[n=p \cdot q =119\]
\[e=5 \]
okay so have someone's public key
x is the message
the encryption function is
\[E(x)=x^e \mod n=c\]
the decryption function is
\[D(c)=c^d \mod n=x\]

Answer 3

so what you mean the ciphertext is 44?

Answer 4

ok and we want to decrypt this ciphertext

Answer 5

so let's put it in the decryption function

Answer 6

\[D(44)=44^d \mod n \]

Answer 7

but wait we don't know d

Answer 8

\[44^d \mod 119\]

so i don't understand
it says to break the code
but it also says use the decryption
ok we are suppose to do both

Answer 9

we need to factor n

Answer 10

n=119=7(17)=pq

Answer 11

\[\phi(n)=(7-1)(17-1)=6(16)=96\]

Answer 12

now we know e which is 5
so we can find d by solving
\[de \equiv 1 \mod \phi(n)\]

Answer 13

\[5d \equiv 1 \mod 96\]

Answer 14

\[5d-96k=1 \text{ for some integer k }\]

Answer 15

we need to use euclidean algorithm

Answer 16

\[96=5(19)+1\]
\[19=5(3)+4\]
\[5=\]
=> 96-5(19)=1
=>5(-19)-96(-1)=1
so d=-19+96=77
see
5(77)-96(4)=1
okay so we have d=77 :)

Answer 17

so back to the decryption function

Answer 18

\[D(44)=44^d \mod n=44^{77} \mod 119\]

Answer 19

\[44^2 \mod 119=32\]
\[44^4 \mod 119 =32 \cdot 32 \mod 119=72\]
\[44^8 \mod 118=72 \cdot 72 \mod 119=67\]
\[44^{16} \mod 119 =67 \cdot 67 \mod 119=86\]
\[44^{32} \mod 119 =86 \cdot 86 \mod 119=18\]
\[44^{64} \mod 119=18 \cdot 18 \mod 119 =86\]
\[44^{77} \mod 119=44^{64} \cdot 44^{13} \mod 119=(86) \cdot 44^{8} \cdot 44^{4} \cdot 44 \mod 119\]

Answer 20

\[=86 \cdot 67 \cdot 72 \cdot 44 \mod 119\]

Answer 21

\[=11\]

Answer 22

and you said 11 equals k
:)

Answer 23

i see a type-0

Answer 24

all of those are suppose to be mod 119

Answer 25

I don't really know much about it, but looks like it took some effort out of you. So, you deserved the medal!

Answer 26

lol you're so sweet

Answer 27

true that, good job (I'm guessing)
what is this math called?

Answer 28

its cryptography

Answer 29

encryption/decryption stuff
network security

Answer 30

right, I thought maybe there was a name for this kind of math with "modulus" in general
thx

Answer 31

number theory

Answer 32

ahh...

Answer 33

this is all number theory stuff

Answer 34

thanks!

Answer 35

np

Answer 36

i think they even talked about RSA in my discrete math book

Answer 37

we never talked about in class though