SOLUTION: Carlos wants to send Cecil a message encrypted with RSA. Cecil has published his public encryption exponent $4$ and his public modulus $15$. When Carlos encrypts the number $11$ wi

Algebra ->  Divisibility and Prime Numbers  -> Lessons -> SOLUTION: Carlos wants to send Cecil a message encrypted with RSA. Cecil has published his public encryption exponent $4$ and his public modulus $15$. When Carlos encrypts the number $11$ wi      Log On


   

Question 1207737: Carlos wants to send Cecil a message encrypted with RSA. Cecil has published his public encryption exponent $4$ and his public modulus $15$. When Carlos encrypts the number $11$ with this system, what is the result?
Found 2 solutions by Edwin McCravy, math_tutor2020:
Answer by Edwin McCravy(20054) About Me  (Show Source):
You can put this solution on YOUR website!
I did a little research on cryptography. RSA stands for Rivest=Shamir-Adleman,
the cryptographers who came up with the RSA cryptographic algorithm in 1977.
It's a cookbook formula.

Carlos wants to send Cecil a message encrypted with RSA. Cecil has published his
public encryption exponent $4$ and his public modulus $15$. When Carlos encrypts
the number $11$ with this system, what is the result?

Cecil has published his public encryption exponent as 4 and his public modulus
as 15.
Carlos wants to encrypt the number 11 using this RSA public key.
The formula for RSA encryption is: 

C%22%22=%22%22matrix%281%2C3%2CM%5Ee%2Cmod%2Cn%29, where:
C = the ciphertext (the encrypted message)
M = the plaintext message (in this case, 11)
e = the public encryption exponent (4)
n = the public modulus (15)
Plugging in the values:
C%22%22=%22%22matrix%281%2C3%2C11%5E4%2Cmod%2C15%29
C%22%22=%22%22matrix%281%2C3%2C14641%2Cmod%2C15%29

      976 
 15)14641
    135
     114
     105
       91
       90
        1

The remainder is 1,

so C%22%22=%22%221 

Therefore, the result of encrypting the number 11 with Cecil's public key (exponent 4, modulus 15) is 1.
So the encrypted message that Carlos would send to Cecil is the number 1.

Edwin

Answer by math_tutor2020(3816) About Me  (Show Source):
You can put this solution on YOUR website!

Tutor Edwin has a great solution.
I'll show another way to compute 11^4 (mod 15).
First let's determine 11^2 in mod 15.

11^2 = 121 = 1 (mod 15)

How did I go from 121 to 1?
Well notice that 121/15 = 8 remainder 1
Ignore the quotient. All we care about is the remainder with modular arithmetic.
Both 121 and 1 have the same remainder when dividing over 15.

So that's how 121 = 1 (mod 15)

Side note: If a = b (mod n), then a-b is a multiple of n. In other words, a-b = nk for some integer k.
In the claim above we have 121-1 = 120 as a multiple of 15 (since 15*8 = 120).

Then,
11^2 = 1 (mod 15)
(11^2)^2 = 1^2 (mod 15)
11^(2*2) = 1 (mod 15)
11^4 = 1 (mod 15)

Dividing 11^4 over 15 gives some quotient with remainder 1.
You can use long division to check this claim as Edwin has done.