Transcribed Text
Crypto Have fun with RSA
1
Intro RSA
RSA s one the widely used public key cryptosystem in real world It's composed
of three algorithms key generation (Gen) encryption (Enc). and decryption (Dec). In
RSA the public key is pair of integers (e,N), and the private key s an integer d.
Gen The key pair generated by the following steps:
1. Choose two distinct big prime numbers with the same bit sizesay and
q.
2. Let N p*q and o(N) (p- 1) ( (g -
3. Pick up an integer such that
4. Get the modular inverse ofe: mod d*c=l moo ((N)).
5. Return (N,c) public key, and das private key.
Enc Conerypt integer m with public key the cipher integer m² mod N
Dec To decrypt cipher d,the integer emod N.
2
Taskl Get Familiar with RSA
The goal of this familiar with RSA.
You're given RSA key and unique message You're
required toget the student key pair cipher text can be
found in
You're
only
required
3
Task2 Attack Small Key Space
In real world. he commonly used RSA key size 1024 bits. which Is hard for attackers
traversal the whole space with limited Now you're given unique RSA
public which pretty small (64 bits). your goal is to get the private
key.
All
public
found
in
You're required write some in get the private key:
. TODOI: implement get factors. n s the given public key (64 bits). your
goali get its factors. You this subtask (i.e., search engine pencil
and paper) as long you get the right
def get ,factors(n):
# your starts here
# your code ends here
return (p. q)
. TODO2: implement function get the private key.
def get key(p. 9. e):
d = 0
# your code starts here
# your code ends here
return
You're required osubmit: (1)your unique private keyi hex format (2) the "get_pri_key.py"
file;(3) briefdescriptionabout your private key.
4
Task3 Where Is Waldo?
Read paper "Mining Your Ps and Qs: Detection of Widespread Weak Keys in
Network Devices"
You're given unique RSA public key the RNG (random number generator) used in
the key Also. all your classmates's public kevs are generated by
the same RNG o the same system. Your goal is to get your unique private key. All keys
can found in
You're required to complete some code in "find. toget the private key:
. TODOI: implement function nl your own key. n21 one of your class-
mate's key tryto find out whether this classmate Waldo,
def is .waldo(n1 n2):
result False
#your code stert here
#your code ends here
return result
TODO2: since you've successfully found your Waldo among your classmates now
you have implement function get,private.key toget your own unique private
key. nlis your public key, n2is Waldo's public key
def get_privatekey (nl, n2, e):
#your code sterts here
#your code ends here
return
You're required submit (1) your unique private key in hex format; (2) your class-
(Walde) name: (3) the areldo.pg file: your about weak
key problem caused by Ps and Qs: (5) simple description about your steps get
the
private kev.
5
Task4 Broadcasting RSA Attack
A message was encrypted with three different 1024 bit RSA public keys, all of them
have public exponent resulting thrve different encrypted messages You'regiven
three pairs ofpublic kevs and encrypter messages, pleasi the original message
You're required implement the frecover msg function "recover .py":
def recover msg(nl, n2, n3, c1, c2, c3):
-
42
# your code sterts here: to calculate the original message
m
. Nole "m' should be en integer
# your code ends here
# comvert the iml 10 message string
ISS = hex(m).rstripC'L')[2:].decode('hex')
return msg
You're required submit the original message, your understanding about the attack
and brief explanation about how you recover the message.
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.
#!/usr/bin/python
import sys, hashlib, json
def usage():
print """usage: python get_name_hash.py student_id
for example:
python get_name_hash.py qchenxiong3"""
sys.exit(1)
if len(sys.argv) != 2:
usage()
print hashlib.sha224(sys.argv[1]).hexdigest()
with open("keys4student.json", 'r') as f:
all_keys = json.load(f)
name = hashlib.sha224(sys.argv[1].strip()).hexdigest()
if name not in all_keys:
print sys.argv[1], "not in keylist"
usage()
keys = all_keys[name]
n1 = int(keys['N'], 16)
e = int(keys['e'], 16)
d = int(keys['d'], 16)
c = int(keys['c'], 16)
m = pow(c, d, n1)
print ("Your message is:", hex(m).rstrip('L')[2:].decode('hex'))
print ("Your message in Hex format:", hex(m).rstrip('L'))...