s3a
- 828
- 8
- Homework Statement
- Consider an RSA system with p=17, q=11 and e=3.
Find m corresponding to c=156.
- Relevant Equations
- C = P^e mod n
P = C^d mod n
n = pq
m = (p-1)(q-1)
1 < e < m
d = e^(-1) mod m
1 < d < m
OFFICIAL SOLUTION:
d=e^(-1) mod 160=107
mp= c^(d) mod p=7
mq:=c^(d) mod q=7
MY THOUGHTS:
I understand how d = 107, but I got that by using m = (17-1)(11-1) = 160.
What I don't understand is the next two lines (from the official solution). I am aware of the P = C^d mod n (decryption) formula. Are the aforementioned two lines somehow using "Fermat's little theorem"?
Put differently, I guess the part of the problem statement that I'm struggling with is the "corresponding to c=156" part.
Could someone please help me fully understand how to solve this problem?
Any input would be GREATLY appreciated!
P.S.
I have another problem that's the same problem, except it requires that the solution be found using the Chinese Remainder Theorem, so I'm supposed to do this particular problem without the Chinese Remainder Theorem.
d=e^(-1) mod 160=107
mp= c^(d) mod p=7
mq:=c^(d) mod q=7
MY THOUGHTS:
I understand how d = 107, but I got that by using m = (17-1)(11-1) = 160.
What I don't understand is the next two lines (from the official solution). I am aware of the P = C^d mod n (decryption) formula. Are the aforementioned two lines somehow using "Fermat's little theorem"?
Put differently, I guess the part of the problem statement that I'm struggling with is the "corresponding to c=156" part.
Could someone please help me fully understand how to solve this problem?
Any input would be GREATLY appreciated!
P.S.
I have another problem that's the same problem, except it requires that the solution be found using the Chinese Remainder Theorem, so I'm supposed to do this particular problem without the Chinese Remainder Theorem.