Homework 05
¶
Due Tue, March 24, 11:59pm
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_lastname_firstname”. 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).
Overview of RSA
To generate an RSA public key, private key pair, Alice chooses two large primes $p,q$ (for instance by testing random large numbers using a fast primality testing algorithm, such as Sage’s is_prime) and an integer $b$ (we used $b=17$) that is relatively prime to $(p-1)(q-1)$. She also computes $n=pq$. Her public key is $(b,n)$, which she publishes to the world. To generate her private key, she computes $e$ such that $be \equiv 1 \bmod (p-1)(q-1)$ (using the Extended Euclidean Algorithm, implemented in Sage as xgcd). This $e$ 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^b \bmod n,$$ which can be done efficiently using the repeated squaring trick (using Sage’s power_mod).
If Alice receives an encrypted message $c$, she decrypts it by computing $$c^e\bmod n,$$ using power_mod.
Problem 1
(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.
In [1]:
# Your solution goes here
Problem 2
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$.
HINT: Use the builtin factor function to factor the $n$ above, and then use this to decrypt.
In [1]:
# Your solution goes here
Problem 3
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$.
In [3]:
# Your solution goes here