Can Anyone Help with These RSA Encryption Questions?

[buzzmath]

I'm trying to figure out these two questions

1. I have a ciphertext message produced by RSA encryption with key (e,n)=(5,2881) and I'm trying to find the plain text message of
0504 1874 0347 0515 2088 2356 0736 0468
I found the euler-phi function to be 42*66=2772 and found the modular inverse to be 1109 but I'm having trouble finding C^1109(mod2881) for each block of four. can anyone help with this?

2. I'm trying to show that if the encryption exponent 3 is used for the RSA cryptosystem by 3 different people with different moduli, and a plaintext message P encrypted usin each of their keys can be recovered from the resulting 3 ciphertext messages.
I've set it up to the congruences c_i congruent to P^3(mod n_i), i = 1,2,3 but I'm not really sure where to go from here. can anyone help?

thanks

 

[shmoe]

i'm having trouble finding C^1109(mod2881) for each block of four. can anyone help with this?

Use repeated squaring and reduce mod 2881 at each stage. That is find C^2 mod 2881, C^4 mod 2881, C^8 mod 2881, etc. then multiple the appropriate ones to get C^1109, reducing mod 2881 as necessary to keep the numbers small.

2. I'm trying to show that if the encryption exponent 3 is used for the RSA cryptosystem by 3 different people with different moduli, and a plaintext message P encrypted usin each of their keys can be recovered from the resulting 3 ciphertext messages.
I've set it up to the congruences c_i congruent to P^3(mod n_i), i = 1,2,3 but I'm not really sure where to go from here. can anyone help?

small hint- P will be less than each n_i. Do you have any way of first recovering P^3?

 

[tacman]

1. To find the plain text message, you need to calculate each block of four separately using the formula C^d(mod n), where d is the modular inverse and n is the modulus. So for the first block, you would calculate 0504^1109(mod 2881) = 1031. Repeat this for each block and you should get the plain text message.

2. To show that the plaintext message can be recovered, you need to use the Chinese Remainder Theorem. This theorem states that if you have congruences of the form x ≡ a (mod m) and x ≡ b (mod n), where m and n are relatively prime, then the solution is given by x ≡ aM(M^-1)(b-a) (mod mn), where M = n (mod m) and M^-1 is the modular inverse of M (mod mn).

In your case, you have three congruences (c1 ≡ P^3 (mod n1), c2 ≡ P^3 (mod n2), c3 ≡ P^3 (mod n3)) and three different moduli (n1, n2, n3). So you can use the Chinese Remainder Theorem to find the solution for x, which will give you the plaintext message P.

Hope this helps!