Download the .ipynb file for this notebook, and place your solutions where indicated (you can make more cells for each problem), keeping the original problem descriptions. Upload only one file, which contains all your work; it should be named "HW05_firstname_lastname". Please include comments in your code; this can also help you get partial credit if your code doesn't work.
Then upload it to Blackboard under the Assignments tab. See Collaboration Policy in Homework section of course webpage (it's the same as it was for previous homeworks).
To generate an RSA public key, private key pair, Alice chooses two primes $p,q$ (for instance by testing random large numbers using a fast primality testing algorithm) and an integer $e$ that is relatively prime to $(p-1)(q-1)$. Her public key is $(e,n=pq)$, which she publishes to the world. To generate her private key, she computes $d$ such that $ed \equiv 1 \bmod (p-1)(q-1)$ (the Extended Euclidean Algorithm can be used for this). This $d$ is her private key.
If Bob wants to send Alice a message $m$ (which we assume is an integer less than $n$), he computes the encrypted message as $$m^e \bmod n,$$ which can be done efficiently using the repeated squaring trick (which we implemented as exp_mod).
If Alice receives an encrypted message $c$, she decrypts it by computing $$c^d \bmod n,$$ using a fast method such as exp_mod.
(a) Generate an RSA public key, private key pair using $p,q$ of at least 20 digits.
(b) Encrypt the test message $m=1234$ using the public key, giving a ciphertext $c$.
(c) Decrypt the ciphertext $c$ using the private key.
# Your solution goes here
In RSA, if Alice makes the mistake of choosing $p,q$ too small, an eavesdropper Eve, who only sees the public key, can compute the private key, which will allow her to decrypt messages sent to Alice. You are Eve, and Alice's public key is $$(e,n) = (17, 577795578054100501).$$ Find Alice's private key $d$.
# Your solution goes here
In RSA, we will consider what happens when Alice makes the mistake of choosing $p,q$ too close together. Her method is as follows. She chooses $p$ a random large prime, and then chooses $q$ to be the smallest prime greater than $p$. You are Eve, and Alice's public key is $(e,n)$ where $e=13$ and $n$ is
$$4149515568880992958512407863691161151012446232242436899995657329690652811412991293413200434314186514261288537546721977134041420919065144782418033157091025480140853599374890776565691$$
(Make sure to copy all of $n$, which has $181$ digits). Find Alice's private key $d$.
# Your solution goes here
Suppose that Alice has generated an RSA key pair $(e,n)$ where $e=1031$ and $n$ is
$$5164499756173817179311838344006023748659411585858576367865241166444878017076039114129434139209664851217737946715315438073$$
(Make sure to copy all of $n$, which has $121$ digits). Bob has a secret two-digit number $m$, which he RSA encrypts to $c$ using Alice's public key and sends to her. He makes the mistake of not adding any random padding to the end of the message. You are Eve and you intercept $c$, which is
$$4999464775939036153095506504533178466937925964341871078399034090512089129818048817825469388233484527953206781376396815810$$
(Make sure to copy all $121$ digits). Find the secret two-digit number $m$.
# Your solution goes here