Project 3: Crypto All Things Cryptography Solution

Intro { RSA



RSA is one of the most widely-used public key cryptosystems in the world. It’s com-posed 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).




Pick up an integer e, such that 1 < e < (N) and gcd(e; (N)) = 1.



Get the modular inverse of e: d e 1 mod (N) (i.e., d e 1 mod (N)).



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 cd mod N.




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 le, implement the function decrypt message



















1









def decrypt message (self , N, e, d, c):




m = 0




return hex(m). rstrip (’L’)













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 o er you? Lets nd 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 le, 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










Re ection 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






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 le, 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 le, 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










Re ection In your essay address the following questions:




What steps did you follow to get the private key?




Task 4 { Where’s Waldo? (30 points)



Read the paper \Mining Your Ps and Qs: Detection of Widespread Weak Keys in Net-work 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 le, 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










Re ection 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?




Task 5 { Broadcast RSA Attack (35 points)



A message was encrypted with three di erent 1024-bit RSA public keys. All of them have the public exponent e = 3, resulting in three di erent 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 le, 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
















Re ection In your essay address the following questions:




How does this attack work?




What steps did you follow to recover the message?




4






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 a n g e 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 le 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 le 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 les are written in Python 3 and will be tested on a Python 3 inter-preter.




HINT (as a reward for reading this far): The answers in the test crypto proj.py unit test le are CORRECT for the student ID bdornier3







Submission



Note that all students’ keys are di erent, so don’t copy and paste answers from your classmates.




In total, please submit the following les:




\crypto proj.py"



\project3 report.pdf": An essay with all of your answers to the re ection 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 les separately, don’t archive them!
















5