Writeup: UUT 2019 - Break The RSA

(Updated: )
writeups
, , , ,

Information

  • category : crypto
  • points : 50

Description

Flag is the decryption of the following:
PublicKey= (114869651319530967114595389434126892905129957446815070167640244711056341561089,113)
CipherText=102692755691755898230412269602025019920938225158332080093559205660414585058354

Writeup

We have :

  • n: 114869651319530967114595389434126892905129957446815070167640244711056341561089
  • e: 113
  • ct: 102692755691755898230412269602025019920938225158332080093559205660414585058354

We can see on factordb if n can be factorized. We get that n is the product of 338924256021210389725168429375903627261 * 338924256021210389725168429375903627349

So now he have :

  • p: 338924256021210389725168429375903627261
  • q: 338924256021210389725168429375903627349
  • phi: 114869651319530967114595389434126892904452108934772649388189907852304534306480

Now we can use The extended euclidian algorithm to calculate d :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import math
import codecs

def egcd(a, b):
     if a == 0:
         return (b, 0, 1)
     else:
         g, y, x = egcd(b % a, a)
         return (g, x - (b // a) * y, y)
 
def modinv(a, m):
     gcd, x, y = egcd(a, m)
     if gcd != 1:
         return None  # modular inverse does not exist
     else:
         return x % m

e = 113
p = 338924256021210389725168429375903627261
q = 338924256021210389725168429375903627349
n = p*q
phi = (p-1)*(q-1)   # calc phi 
ct = 102692755691755898230412269602025019920938225158332080093559205660414585058354

d = modinv(e,phi)   #calc d using extended euclidean algorithm
print("d :" + str(d))

d : 43711460236635677751571696864313773406118944107922335607895274669461017479457

Now to calculate the clear text t we need to compute : ct ^ d mod n. In python we can use pow with three arguments to do the job. In the last lines we need to convert the clear text which is an int in string, we can use for that thecodecs library.

Last lines 

1
2
3
4
t = pow(ct,d,n)     # computer clear text ct ^ d mod n 
hext = format(t,'x')    # remove x from hex number
print("t :"+str(t))
print("text : " +codecs.decode(hext,"hex").decode('ascii'))

Complete exploit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import math
import codecs

def egcd(a, b):
     if a == 0:
         return (b, 0, 1)
     else:
         g, y, x = egcd(b % a, a)
         return (g, x - (b // a) * y, y)
 
def modinv(a, m):
     gcd, x, y = egcd(a, m)
     if gcd != 1:
         return None  # modular inverse does not exist
     else:
         return x % m

e = 113
p = 338924256021210389725168429375903627261
q = 338924256021210389725168429375903627349
n = p*q
phi = (p-1)*(q-1)   # calc phi 
ct = 102692755691755898230412269602025019920938225158332080093559205660414585058354

d = modinv(e,phi)   #calc d using extended euclidean algorithm
print("d :" + str(d))

t = pow(ct,d,n)     # computer clear text ct ^ d mod n 
hext = format(t,'x')    # remove x from hex number
print("t :"+str(t))
print("text : " +codecs.decode(hext,"hex").decode('ascii'))
# alternative method
# print("flag : " +(bytes.fromhex(str(hex(t)[2:]))).decode('utf-8'))

Output

1
2
3
d :43711460236635677751571696864313773406118944107922335607895274669461017479457
t :535645912235879621902477379288244888293287927881054157873533
text : UUTCTF{easy sH0Rt RSA!!!}

Flag

UUTCTF{easy sH0Rt RSA!!!}