Description
1 Intro – RSA
RSA is one of the most widely used public key cryptosystems in the world. It’s composed of three algorithms: key generation (Gen), encryption (Enc), and decryption (Dec).
In RSA, the public key is a pair of integers (e, N), and the private key is an integer d.
Gen The key pair is generated by the following steps:
1. Choose two distinct big prime numbers with the same bit size, say p and q.
2. Let N = p ∗ q, and φ(N) = (p − 1) ∗ (q − 1).
3. Pick up an integer e, such that 1 < e < φ(N) and gcd(e, φ(N)) = 1.
4. Get the modular inverse of e: d ≡ e
−1 mod φ(N) (i.e., d ∗ e ≡ 1 mod φ(N)).
5. Return (N, e) as public key, and d as private key.
Enc To encrypt integer m with public key (N, e), the cipher integer c ≡ me mod N.
Dec To decrypt cipher integer c with private key d, the plain integer m ≡ c
d mod N.
2 Task1 – Get Familiar with RSA (10 points)
The goal of this task is to get you familiar with RSA.
You’re given a RSA key pair (N, e) and d, and an unique encrypted message c. You’re
required to get the decrypted message m. Each student’s key pair and cipher text can be
found in “keys4student.json”.
You’re only required to submit your decrypted message in hex format.
1
3 Task2 – Attack Small Key Space (20 points)
In the real world, a commonly used RSA key size is 1024 bits, which makes it hard
for attackers to traverse the whole key space with limited resources. Now, you’re given an
unique RSA public key, of which the key size is pretty small (64 bits), your goal is to get
the private key. All public keys can be found in “keys4student.json”.
You’re required to write some code in “get pri key.py” to get the private key:
• TODO1: implement function get factors, n is the given public key (64 bits), your
goal is to get its factors. You can cheat on this subtask (i.e., search engine, pencil
and paper), as long as you can get the right p and q.
def get factors (n):
p = 0
q = 0
# y o u r c o d e s t a r t s h e r e
# y o u r c o d e e n d s h e r e
return (p, q)
• TODO2: implement function get key to get the private key.
def get key (p, q, e):
d = 0
# y o u r c o d e s t a r t s h e r e
# y o u r c o d e e n d s h e r e
return d
You’re required to submit: (1) your unique private key in hex format; (2) the “get pri key.py”
file; (3) a brief description about your steps to get the private key.
4 Task3 – Where Is Waldo? (30)
Read the paper “Mining Your Ps and Qs: Detection of Widespread Weak Keys in
Network Devices” (https://factorable.net/weakkeys12.extended.pdf).
You’re given an unique RSA public key, and the RNG (random number generator) used
in the key generation is vulnerable. Also, all your classmates’ public keys are generated by
the same RNG on the same system. Your goal is to get your unique private key. All keys
can be found in “keys4student.json”.
2
You’re required to complete some code in “find waldo.py” to get the private key:
• TODO1: implement function is waldo, n1 is your own key, n2 is one of your classmate’s key, try to find out whether this classmate is Waldo.
def is waldo (n1 , n2):
result = False
#y o u r c o d e s t a r t s h e r e
#y o u r c o d e e n d s h e r e
return result
• TODO2: since you’ve successfully found your Waldo among your classmates, now
you have to implement function get private key to get your own unique private
key. n1 is your public key, n2 is Waldo’s public key.
def get private key (n1 , n2 , e):
d = 0
#y o u r c o d e s t a r t s h e r e
#y o u r c o d e e n d s h e r e
return d
You’re required to submit: (1) your unique private key in hex format; (2) your classmate’s (Waldo) name; (3) the “find waldo.py” file; (4) your understanding about the weak
key problem caused by Ps and Qs; (5) a simple description about your steps to get the
private key.
5 Task4 – Broadcasting RSA Attack (40)
A message was encrypted with three different 1024 bit RSA public keys, all of them
have the public exponent e = 3, resulting in three different encrypted messages. You’re
given the three pairs of public keys and encrypted messages, please recover the original
message. You’re required to implement the ‘recover msg’ function in “recover.py”:
def recover msg (n1 , n2 , n3 , c1 , c2 , c3):
m = 42
# y o u r c o d e s t a r t s h e r e : t o c a l c u l a t e t h e o r i g i n a l m e s s a g e − m
3
# N o t e ’m ’ s h o u l d b e an i n t e g e r
# y o u r c o d e e n d s h e r e
# c o n v e r t t h e i n t t o m e s s a g e s t r i n g
msg = hex(m). rstrip(’L’)[2:]. decode(’hex’)
return msg
You’re required to submit the original message, your understanding about the attack
and a brief explanation about how you recover the message.
6 Submission
Note that all students’ keys are different, so don’t copy and paste answers from your
classmates. In total, please submit the following files:
1. “studentid submission.json”.
2. “get pri key.py”, “find waldo.py” and “recover.py”.
3. “report.pdf”: a brief explanation about how you get the private key in task2; your
understanding about the Ps and Qs problem in task3; a brief explanation about how
you get the private key and waldo in task3; your understanding about the attack in
task4; a brief explanation about how you recover the message in task 4.
Please submit the files separately, don’t archive them!
4