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 Task 1 – Get Familiar with RSA (5 points)
The goal of this task is to get you familiar with RSA. You are given a RSA key pair (N, e)
and d, and a unique encrypted message c. You are required to get the decrypted message
m. Each student’s key pair and cipher text can be found in “keys4student task 1.json”.
• TODO: In the provided crypto proj.py file, implement the function decrypt message
1
def decrypt message (self, N, e, d, c):
m = 0
return hex(m). rstrip(’L’)
3 Task 2 – Can I Have Some Salt With My Password? (10
points)
We all know that it is important not to use common passwords. Hackers have long
utilized rainbow tables, which contain hashes of common passwords, to crack vulnerable
passwords. Passwords are often salted before they are hashed in order to thwart a rainbow
table attack. Assuming that your weak password is salted before it is hashed, how much
more protection does this offer you? Lets find out…
You are given the SHA256 hash of a password randomly selected from a list of the 1,000
most commonly-used passwords on the Internet. A salt value was added to the password
before it was hashed. Your job is to decode the original password and salt value from the
hash. (To make your job a little easier, the salt value is another random password from
the same list of common passwords.)
All password hashes can be found in “hashes4student task 2.json”.
The complete list of common passwords can be found in “top passwords.txt”.
• TODO: In the provided crypto proj.py file, implement the function crack password hash
def crack password hash (self, password hash , weak password list ):
password = ’abc’
salt = ’123’
hashed password = hashlib.sha256(password .encode () +
salt.encode ()). hexdigest ()
return password , salt
Reflection In your essay address the following questions:
Is the hash of the salted password still vulnerable? Why or why not?
What steps could be taken to enhance security in this situation?
2
4 Task 3 – Attack A 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 a
unique RSA public key, with a fairly small key size (64 bits). Your goal is to get the private
key. All public keys can be found in “keys4student task 3.json”.
• TODO: In the provided crypto proj.py file, implement the function get factors.
n is the given public key (64 bits), and your goal is to get its factors.
def get factors (self, n):
p = 0
q = 0
return p, q
• TODO: In the provided crypto proj.py file, implement the function get private key from p q e
to get the private key.
def g e t p r i v a t e k e y f r o m p q e (self, p, q, e):
d = 0
return d
Reflection In your essay address the following questions:
What steps did you follow to get the private key?
5 Task 4 – Where’s Waldo? (30 points)
Read the paper “Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices”, which can be found at: https://factorable.net/weakkeys12.extended.
pdf.
You are given a unique RSA public key, but the RNG (random number generator) used
in the key generation is vulnerable. In addition, all of your classmates’ public keys were
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 task 4.json”.
• TODO: In the provided crypto proj.py file, implement the function is waldo. n1
is your own key, n2 is one of your classmate’s key. Try to determine whether this
classmate is Waldo.
3
def is waldo (self, n1 , n2):
result = False
return result
• TODO: Since you’ve successfully found Waldo amongst your classmates, you now
have to implement the function get private key from n1 n2 e to get your own
unique private key. n1 is your public key, n2 is Waldo’s public key.
def g e t p r i v a t e k e y f r o m n 1 n 2 e (self, n1 , n2 , e):
d = 0
return d
Reflection In your essay address the following questions:
What makes the key generated in this situation vulnerable?
What steps did you follow to get the private key?
6 Task 5 – Broadcast RSA Attack (35 points)
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 are given the three pairs of public keys and associated encrypted messages. Your
job is to recover the original message.
All keys and messages can be found in “keys4student task 5.json”.
• TODO: In the provided crypto proj.py file, implement the function recover message.
def recover msg (self, N1 , N2 , N3 , C1 , C2 , C3):
m = 42
# N o t e t h a t ’m ’ s h o u l d b e an i n t e g e r
return m
Reflection In your essay address the following questions:
How does this attack work?
What steps did you follow to recover the message?
4
7 Important Notes
• You must change the student ID within the class constructor in crypto proj.py
to your own student ID!
def i n i t (self):
# TODO : C h ange t h i s t o YOUR G e o r g i a Tech s t u d e n t ID ! ! !
# N o t e t h a t t h i s i s NOT y o u r 9− d i g i t G e o r g i a Tech ID
self. student id = ’bdornier3’
• The crypto proj.py file has all of the modules that you will need imported for you.
You are NOT allowed to alter the import list. You will lose substantial points if you
do so.
• Your entire submission must run in 10 minutes or less.
• You are also given a unit testing file test crypto proj.py to help you test your
program. We encourage you to read up on Python unit tests, but in general, the
syntax should be python -m unittest test crypto proj
• The provided files are written in Python 3 and will be tested on a Python 3 interpreter.
• HINT (as a reward for reading this far): The answers in the test crypto proj.py
unit test file are CORRECT for the student ID bdornier3
8 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. “crypto proj.py”
2. “project3 report.pdf”: An essay with all of your answers to the reflection questions.
When writing your report please preface each section with the associated task (i.e. Task
2, Task 3, etc). There is no need to reproduce the prompts. There is no page count or
word count for the report, but in the past, highly successful reports have been between 2-5
pages.
Please submit the files separately, don’t archive them!
5