RSA cryptography

Assignment

1 Intro – RSA

RSA is one of the widely used public key cryptosystem in real world. It’s composedof three algorithms: key generation (Gen), encryption (Enc), and decryption (Dec). InRSA, 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.
EncTo 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.

2 Task1 – Get Familiar with RSA

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’rerequired to get the decrypted message m. Each student’s key pair and cipher text can befound in \keys4student.json”.
You’re only required to submit your decrypted message in hex format.

#!/usr/bin/python

import sys, hashlib

def usage():

print “””usage: python get_name_hash.py student_id

for example:

python get_name_hash.py qchenxiong3″””

sys.exit(1)

iflen(sys.argv) != 2:

usage()

print hashlib.sha224(sys.argv[1]).hexdigest()

3 Task2 – Attack Small Key Space


In real world, the commonly used RSA key size if 1024 bits, which is hard for attackersto traversal the whole key space with limited resources. Now, you’re given an unique RSApublic key, of which the key size is pretty small (64 bits), your goal is to get the privatekey. 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), yourgoal is to get its factors.
defget 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.
defget 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

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.

#!/usr/bin/python

importjson, sys, hashlib

 

def usage():

print “””Usage:

python get_pri_key.py student_id (i.e., qchenxiong3)”””

sys.exit(1)

# TODO — get n’s factors

# reminder: you can cheat ;-), as long as you can get p and q

defget_factors(n):

p = 0

q = 0

# your code starts here

# your code ends here

return (p, q)

# TODO: write code to get d from p, q and e

defget_key(p, q, e):

d = 0

# your code starts here

# your code ends here

return d

def main():

iflen(sys.argv) != 2:

usage()

n = 0

e = 0

all_keys = None

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:

printsys.argv[1], “not in keylist”

usage()

pub_key = all_keys[name]

n = int(pub_key[‘N’], 16)

e = int(pub_key[‘e’], 16)

print “your public key: (“, hex(n).rstrip(“L”), “,”, hex(e).rstrip(“L”), “)”

(p, q) = get_factors(n)

d = get_key(p, q, e)

print “your private key:”, hex(d).rstrip(“L”)

if __name__ == “__main__”:

main()

4 Task3 – Where Is Waldo?

Read the paper \Mining Your Ps and Qs: Detection of Widespread Weak Keys inNetwork Devices”.
You’re given an unique RSA public key, the RNG (random number generator) used inthe key generation is vulnerable. Also, all your classmates’s public keys are generated bythe same RNG on the same system. Your goal is to get your unique private key. All keyscan be found in “keys4student.json”.

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.
defis waldo(n1, n2):
result = False
#y o u r c o d e s t a r t 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 privatekey. n1 is your public key, n2 is Waldo’s public key.
defget 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 weakkey problem caused by Ps and Qs; (5) a simple description about your steps to get theprivate key.

#!/usr/bin/python

importjson, sys, hashlib

def usage():

print “””Usage:

python find_waldo.py student_id (i.e., qchenxiong3)”””

sys.exit(1)

#TODO — n1 and n2 share p or q?

defis_waldo(n1, n2):

result = False

#your code start here

#your code ends here

return result

#TODO — get private key of n1

defget_private_key(n1, n2, e):

d = 0

#your code starts here

#your code ends here

return d

def main():

iflen(sys.argv) != 2:

usage()

all_keys = None

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:

printsys.argv[1], “not in keylist”

usage()

pub_key = all_keys[name]

n1 = int(pub_key[‘N’], 16)

e = int(pub_key[‘e’], 16)

d = 0

waldo = “dolores”

print “your public key: (“, hex(n1).rstrip(“L”), “,”, hex(e).rstrip(“L”), “)”

for classmate in all_keys:

if classmate == name:

continue

n2 = int(all_keys[classmate][‘N’], 16)

ifis_waldo(n1, n2):

waldo = classmate

d = get_private_key(n1, n2, e)

break

print “your private key: “, hex(d).rstrip(“L”)

print “your waldo: “, waldo

if __name__ == “__main__”:

main()

5 Task4 – Broadcasting RSA Attack

A message was encrypted with three different 1024 bit RSA public keys, all of themhave the public exponent e = 3, resulting three different encrypted messages. You’re giventhe 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”:
defrecover 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
# Note ’m ’ s h o u l d be an i n t e g e r
# your 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 message 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 attackand a brief explanation about how you recover the message.
#!/usr/bin/python

importjson, sys, hashlib

def usage():

print “””Usage:

python recover.py student_id (i.e., qchenxiong3)”””

sys.exit(1)

#TODO

defrecover_msg(N1, N2, N3, C1, C2, C3):

m = 42

# your code starts here: to calculate the original message – m

# Note ‘m’ should be an integer

# your code ends here

# convert the int to message string

msg = hex(m).rstrip(‘L’)[2:].decode(‘hex’)

returnmsg

def main():

iflen(sys.argv) != 2:

usage()

all_keys = None

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:

printsys.argv[1], “not in keylist”

usage()

data = all_keys[name]

N1 = int(data[‘N0’], 16)

N2 = int(data[‘N1’], 16)

N3 = int(data[‘N2’], 16)

C1 = int(data[‘C0’], 16)

C2 = int(data[‘C1’], 16)

C3 = int(data[‘C2’], 16)

msg = recover_msg(N1, N2, N3, C1, C2, C3)

printmsg

if __name__ == “__main__”:

main()

Solution

  decrypt.py

 #!/usr/bin/python

importjson

def f(x,e,m):

X = x

E = e

Y = 1

while E > 0:

if E % 2 == 0:

X = (X * X) % m

E = E/2

else:

Y = (X * Y) % m

E = E – 1

return Y

def main():

mykey = “6bc165a2b89bfa8be524f4287c61a418a63d62e172c4bc53534b2dde”

jfile = open(“keys4student.json”,’r’)

keys = json.load(jfile)

c = keys[mykey][‘c’]

e = keys[mykey][‘e’]

d = keys[mykey][‘d’]

N = keys[mykey][‘N’]

c = int(c,16)

e = int(e,16)

d = int(d,16)

N = int(N,16)

m = f(c,d,N)

print hex(m).rstrip(“L”)

if __name__ == “__main__”:

main()

task1

get_name_hash.py

#!/usr/bin/python

import sys, hashlib

def usage():

print “””usage: python get_name_hash.py student_id

for example:

python get_name_hash.py qchenxiong3″””

sys.exit(1)

iflen(sys.argv) != 2:

usage()

print hashlib.sha224(sys.argv[1]).hexdigest()

task2

get_pri_key.py

 #!/usr/bin/python

importjson, sys, hashlib

def usage():

print “””Usage:

python get_pri_key.py student_id (i.e., qchenxiong3)”””

sys.exit(1)

# TODO — get n’s factors

# reminder: you can cheat ;-), as long as you can get p and q

defget_factors(n):

p = 0

q = 0

# your code starts here

import math

r = int(math.sqrt(n))   # Calculate square root of N, use as upper bound

if r%2==0: r+=1         # Round root to nearest odd number

# Find p,q using brute force

while(r>3):

r = r-2

ifn%r == 0:

p = r

q = n/p

break

# your code ends here

return (p, q)

# TODO: write code to get d from p, q and e

defget_key(p, q, e):

d = 0

# your code starts here

phi = (p-1)*(q-1) # Calculate phi

# Use extended-Euclidean algorithm to solve modular multiplicative inverse

defextended_gcd(a, b):

if a == 0:

return (b, 0, 1)

else:

g, y, x = extended_gcd(b % a, a)

return (g, x – (b // a) * y, y)

g, x, y = extended_gcd(e, phi)

if g != 1: raise Exception(‘Unable to calculate modular inverse’)

d = x % phi

# your code ends here

return d

def main():

iflen(sys.argv) != 2:

usage()

n = 0

e = 0

all_keys = None

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:

printsys.argv[1], “not in keylist”

usage()

pub_key = all_keys[name]

n = int(pub_key[‘N’], 16)

e = int(pub_key[‘e’], 16)

print “your public key: (“, hex(n).rstrip(“L”), “,”, hex(e).rstrip(“L”), “)”

(p, q) = get_factors(n)

d = get_key(p, q, e)

print “your private key:”, hex(d).rstrip(“L”)

if __name__ == “__main__”:

main()

 task3

find_waldo.py

 #!/usr/bin/python

importjson, sys, hashlib

def usage():

print “””Usage:

python find_waldo.py student_id (i.e., qchenxiong3)”””

sys.exit(1)

#TODO — n1 and n2 share p or q?

defis_waldo(n1, n2):

result = False

#your code start here

from fractions import gcd

# Calculategcd of p and q

g = gcd(n1,n2)

if g != 1: result = True

#your code ends here

return result

#TODO — get private key of n1

defget_private_key(n1, n2, e):

d = 0

#your code starts here

from fractions import gcd

p = gcd(n1,n2)      # Calculate p

q = n1/p            # Calculate q

phi = (p-1)*(q-1)   # Calculate phi

# Use extended-Euclidean algorithm to solve modular multiplicative inverse

defextended_gcd(a, b):

if a == 0:

return (b, 0, 1)

else:

g, y, x = extended_gcd(b % a, a)

return (g, x – (b // a) * y, y)

g, x, y = extended_gcd(e, phi)

if g != 1: raise Exception(‘Unable to calculate modular inverse’)

d = x % phi

#your code ends here

return d

def main():

iflen(sys.argv) != 2:

usage()

all_keys = None

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:

printsys.argv[1], “not in keylist”

usage()

pub_key = all_keys[name]

n1 = int(pub_key[‘N’], 16)

e = int(pub_key[‘e’], 16)

d = 0

waldo = “dolores”

print “your public key: (“, hex(n1).rstrip(“L”), “,”, hex(e).rstrip(“L”), “)”

for classmate in all_keys:

if classmate == name:

continue

n2 = int(all_keys[classmate][‘N’], 16)

ifis_waldo(n1, n2):

waldo = classmate

d = get_private_key(n1, n2, e)

break

print “your private key: “, hex(d).rstrip(“L”)

print “your waldo: “, waldo

if __name__ == “__main__”:

main()

task4

recover.py

 #!/usr/bin/python

importjson, sys, hashlib

def usage():

print “””Usage:

python recover.py student_id (i.e., qchenxiong3)”””

sys.exit(1)

#TODO

defrecover_msg(N1, N2, N3, C1, C2, C3):

m = 42

# your code starts here: to calculate the original message – m

# Function to calculate cubic root using binary search

deffind_cubic_root(x):

high = 1                        # Upper bound

while high ** 3 <= x: high = high*2

low = high/2                    # Lower bound

while low < high:

mid = (low + high) // 2     # Find midpoint

if low < mid and mid**3 < x:# Move lower bound

low = mid

elif high > mid and mid**3 > x:

high = mid              # Move upper bound

else:

return mid              # Solution found

return mid + 1                  # Nearest solution

m = find_cubic_root(C1)

# convert the int to message string

msg = hex(m).rstrip(‘L’)[2:].decode(‘hex’)

returnmsg

def main():

iflen(sys.argv) != 2:

usage()

all_keys = None

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:

printsys.argv[1], “not in keylist”

usage()

data = all_keys[name]

N1 = int(data[‘N0’], 16)

N2 = int(data[‘N1’], 16)

N3 = int(data[‘N2’], 16)

C1 = int(data[‘C0’], 16)

C2 = int(data[‘C1’], 16)

C3 = int(data[‘C2’], 16)

msg = recover_msg(N1, N2, N3, C1, C2, C3)

printmsg

if __name__ == “__main__”:

main()