CODEWITHSUNDEEP
mathrsa
user3422146
user3422146

Reputation: 57

RSA private key and public key

Little stuck on how to approach this question:

Xavier and Yvonne are in love. They both set up their own RSA keys: 
Xavier’s public key     is (eX , nX ) = (887, 15833), and Yvonne’s public key 
is (eY , nY ) = (977, 13019). For each of the following, do not factor nX nor 
nY , show the set up of the calculations and the results. You should use a 
computer to perform the calculations.

(a) Yvonne wants to send Xavier a private message of love, which is
    M = 3141. What is the ciphertext that Yvonne needs to send to Xavier?

(b) In return, Yvonne received three mysterious messages: C1 = 10889, 
    C2 = 2622, C3 = 4061. All three senders claim to be Xavier, and all 
    claim to have sent the message Ci ≡ MdX (mod nX) where M = 3141 and dX 
    is Xavier’s private key. However, only Xavier himself knows the actual 
    value of dX , and the other two are imposters trying to steal Yvonne away 
    from him. Help Yvonne determine which message is actually from Xavier, 
    and explain why your method works.

Any tips would be great thanks!

Upvotes: 1

Views: 565

Answers (1)

Iridium
Iridium

Reputation: 23721

a) In order to send an RSA-encrypted message such that only the private key holder can decrypt it, it must be encrypted using the recipient's public key. In this case, the recipient is Xavier, so the message is encrypted using his public key: (eX, nX) = (887, 15833):

Message: M = 3141
Ciphertext: C = MeX mod nX
C = 3141887 mod 15833
C = 2054

b) This is essentially a signature verification of a message signed using Xavier's private key, which requires the use of the signer's public key. It is necessary to find which of the three messages, when decrypted using Xavier's public key results in the message that was sent (3141):

Ciphertext 1: C1 = 10889
Message 1: M1 = C1eX mod nX
M1 = 10889887 mod 15833
M1 = 6555 (mismatch)

Ciphertext 2: C2 = 2622
Message 2: M2 = C2eX mod nX
M2 = 2622887 mod 15833
M2 = 1466 (mismatch)

Ciphertext 3: C3 = 2622
Message 3: M3 = C3eX mod nX
M3 = 4061887 mod 15833
M3 = 3141 (match!)

Only C3 matches the message when decrypted using Xavier's public key, and so is the only authentic message.

Note: I used WolframAlpha to perform the modular exponentiation above, but it's easy enough (though rather more time-consuming) to do manually using repeated multiplication then reduction modulo n.

Upvotes: 2

Related Questions