# RSA system with p=17, q=11 and e=3. Find m corresponding to c=156

• Comp Sci
• s3a
In summary, the solution involves solving for d = e^(-1) mod 160 = 107, and then using exponentiation by repeated squaring to calculate mp = c^(d) mod p = 7 and mq = c^(d) mod q = 7. This method does not require the use of Fermat's little theorem or the Chinese Remainder Theorem.
s3a
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.

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.

You can calculate c^d mod p or c^d mod q using exponentiation by repeated squaring. Use the iterative example in the wiki article, except there no need to deal with negative exponent (since d is positive), and the math operations would be performed mod p or mod q.

https://en.wikipedia.org/wiki/Exponentiation_by_squaring

## 1. What is the RSA system and how does it work?

The RSA system is a popular encryption algorithm used for secure communication over the internet. It works by using two large prime numbers, p and q, to generate a public key and a private key. The public key is used to encrypt messages, while the private key is used to decrypt them.

## 2. How do you find the public key in the RSA system?

In the RSA system, the public key is generated by multiplying the two prime numbers, p and q. In this case, p=17 and q=11, so the public key would be 17*11=187.

## 3. How do you find the private key in the RSA system?

The private key is calculated using a mathematical formula involving the prime numbers p and q, as well as a number e, which is relatively prime to (p-1)*(q-1). In this case, e=3, so the private key would be 3*123=369.

## 4. How do you encrypt a message using the RSA system?

To encrypt a message using the RSA system, you first need to convert the message into a number. Then, you raise that number to the power of the public key and take the remainder when divided by the product of p and q. This remainder is the encrypted message, also known as the ciphertext.

## 5. How do you decrypt a message using the RSA system?

To decrypt a message using the RSA system, you raise the ciphertext to the power of the private key and take the remainder when divided by the product of p and q. This remainder will be the original message, also known as the plaintext.

• Engineering and Comp Sci Homework Help
Replies
7
Views
2K
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Precalculus Mathematics Homework Help
Replies
2
Views
2K
• Precalculus Mathematics Homework Help
Replies
2
Views
2K
• Math Proof Training and Practice
Replies
71
Views
10K
• Calculus and Beyond Homework Help
Replies
1
Views
2K
• Math Proof Training and Practice
Replies
175
Views
21K
• General Discussion
Replies
1
Views
3K
• Math Proof Training and Practice
Replies
67
Views
11K
• MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
2K