Problem $2$:

Alice$$s RSA public key is P $=($e$,$ n$)=(7,4453).$ Bob sends Alice the message by encoding it as follows.

First he assigns numbers to characters: A is $7,$ B is $8,...,$ Z is $32,$ a blank is $33,$ quotation marks: $34,$ a coma:

$35,$ a period: $36,$ an apostrophe: $37.$ Then he uses RSA to encode each number separately.

Bob$$s encoded message is:

$14002218992088419184843994191378076441912979226999764$

$22182269208884330159929701443165599323729799944714433237$

$103223828718431655998711443994242843994191226999843$

$419122692979998711443992382226984399419122699932372979$

$99871843378084310322088144329628432916993237297999764$

$2218226920889920884191226999447144332378439987116552382$

$843994242843447419123822269843992218994474191296299$

$2962144399378014432962129484316559929702218129423821655843$

$99144323828719920881443764998711443992382226984399$

$32372979998718433780843103220881443296284329161400$

Decode Bob$$s message. Notice that you only know Alice$$s public key, but don$$t know the private key. So

you need to $$break$$ RSA to decrypt Bob$$s message. For the solution, you need to provide the following:

$($a$)$ Describe step by step how you arrived at the solution: show how to find p and q$,($n$)$ and d$.$

$($b$)$ Show your work for one integer in the message $($M $=2218)$: the expression, the decrypted integer, the

character that it is mapped to$.$

$($c$)$ To decode the remaining numbers, you need to write a program in C$++($see below$),$ test it in Gradescope, and append the code to HW $2,$ Problem $2$ solutions.

$($d$)$ Give the decoded message $($in integers$).$

$($e$)$ Give Bob$$s message in plaintext. What does it mean and who said it$?$

For part $($c$).$ Your program should :

$($i$)$ Take three integers, e$,$ n $($the public key for RSA$),$ and m $($the number of characters in the message$)$ as

input to your program. Next, input the ciphertext.

$($ii$)$ Test whether the public key is valid. If not, output a single line $$Public key is not valid!$$ and quit the

program.

$($iv$)$ If the public key is valid, decode the message.

$($v$)$ Output p and q$,($n$)$ and d$.$

$1$

$($vi$)$ On a new line, output the decoded message in integers.

$($vii$)$ On a new line, output the decoded message in English. The characters should be all uppercase. You

can assume that the numbers will be assigned to characters according to the mapping above.