RSA Encryption Homework

by Prof. Holden and Prof. Rickert

To send a message using the public keys e=5 and n=1,022,117=1009 * 1013 we first translate the message into a number; e.g. "HI"=104105.

(In Maple, this may be done by

 
mess:= convert( "hi", bytes);
len:=nops(mess);
numbr:= sum( mess[k]*1000^(len-k) , k=1..len);
)

This number is then raised to the e power (e.g. by using the Maple command 104105&^5 mod 1022117 ). The number 923261 is then transmitted.

The person receiving the message knows the prime factorization of n and hence, knows phi(n)=1008* 1012=1,020,096. The receiver then solves the congruence 5d == 1 (mod 1020096) (e.g. by using Maple's msolve command: msolve(5*d=1,1020096);) to determine the decryption exponent, d=816077. The message is then raised to the d power (e.g. by 923961&^816077 mod 1022117;) to retrieve the original message 104105.

This may be reconverted to characters in Maple by using the commands

rongway:=convert( mess, base,1000); 
len:=nops(rongway); 
thisisit:= [seq( rongway[len-k], k=0..(len-1))]; 
convert(thisisit,bytes);

  1. Your public key is: e=5
    n = 1000000000000000000000000000000000000000000000000000000000000000000099900000010890000000000000000000000000000000000000000000000000000000000000001087911

    You know that n's prime factors are 1070+999 and 1080+1089. You receive the following encrypted message:
    333206888762676008273805169833546377779976826736822026744150253715736530159521128389341780957334053084975706757256238615712837297070425567140018430247
    Decrypt the message.


  2. Supppose you intercept a message which was sent using the public key: e=961
    n = 80658175170943878571660636856403766975289505440883277824155589621483750741764733368496002866495333455995463842922496000003045891
    The encrypted message is:
    52664783391726759217137117445017046314549043478094596694970429669921499754751022123346769060906731520727055532242695657953702869
    What is the original message?


  3. The following problem appeared on an earlier version of this homework:
    Your public key is: e=5
    n = 10000000000000000000000000000000000000000000000000000000000000000000999000000108 90000000000000000000000000000000000000000000000000000000000000001087911

    You know that n's prime factors are 1070+999 and 1080+1089. You receive the following encrypted message:
    84104101032109097103105099032119111114100115032097114101032115113117101097109105 115104032111115115105102114097103101046
    Decrypt the message.

    What went wrong when this message was sent, what was the original message, and what should you do?