DSO NUS CTF - Protect The Vaccine

Description

A nation-supported hacker group is using their cutting edge technology to attack a company that develops vaccine. They roll their own crypto with a hope that it will be more secure. Luckily, we have got some of their crypto system information and also have found some research that is likely to break their crypto system. I heard you are a cipher breaker, could you help us to decrypt their secret and protect the vaccine from their plan?

Files (Any of the links are fine):
ProtectTheVaccine.zip

Flag format conversion may have to be done for this challenge (Refer to notifications)

Solution

After downloading the file and unzipping it, we see the following contents.

$ ls -al 
total 552
drwxr-xr-x  2 kali kali   4096 Feb 27 22:18  .
drwxr-xr-x 37 kali kali   4096 Feb 28 02:36  ..
-rw-r--r--  1 kali kali 278139 Feb 26 10:50 'A New LSB Attack on Special-Structured RSA Primes.pdf'
-rw-r--r--  1 kali kali   1268 Feb 26 10:50  data.txt
-rw-r--r--  1 kali kali    261 Feb 26 10:50  encryptor.py

The data.txt file seems to contain the paramters used for the encryption as well as the ciphertext.

$ cat data.txt    
N: 3275733051034358984052873301763419226982953208866734590577442123100212241755791923555521543209801099055699081707325573295107810120279016450478569963727745375599027892100123044479660797401966572267597729137245240398252709789403914717981992805267568330238483858915840720285089128695716116366797390222336632152162599116524881401005018469215424916742801818134711336300828503706379381178900753467864554260446708842162773345348298157467411926079756092147544497068000233007477191578333572784654318537785544709699328915760518608291118807464400785836835778315009377442766842129158923286952014836265426233094717963075689446543
e: 65537
r_p: 5555
r_q: 2021
c: 1556192154031991594732510705883546583096229743096303430901374706824505750761088363281890335979653013911714293502545423757924361475736093242401222947901355869932133190452403616496603786871994754637823336368216836022953863014593342644392369877974990401809731572974216127814977558172171864993498081681595043521251475276813852699339208084848504200274031750249400405999547189108618939914820295837292164648879085448065561197691023430722069818332742153760012768834458654303088057879612122947985115227503445210002797443447539212535515235045439442675101339926607807561016634838677881127459579466831387538801957970278441177712

The encryptor.py script details how the encryption was performed and seemed to follow the method described in the given A New LSB Attack on Special-Structured RSA Primes.pdf document.

$ cat encryptor.py 
from config import a,b,m,r_p,r_q,secret
from Crypto.Util.number import bytes_to_long

p = a**m + r_p
q = b**m + r_q
N = p*q
e = 65537

M = bytes_to_long(secret)
c = pow(M, e, N)

print('N:', N)
print('e:', e)
print('r_p:', r_p)
print('r_q:', r_q)
print('c:', c)

The document also had a section describing a method on factoring the N parameter that will enable us to decrypt the provided ciphertext c.

This challenge was more or less following the instructions, however the problem appears when trying performing square root calculations.

Python 3.9.1 (default, Dec  8 2020, 07:51:42) 
[GCC 10.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> N = 3275733051034358984052873301763419226982953208866734590577442123100212241755791923555521543209801099055699081707325573295107810120279016450478569963727745375599027892100123044479660797401966572267597729137245240398252709789403914717981992805267568330238483858915840720285089128695716116366797390222336632152162599116524881401005018469215424916742801818134711336300828503706379381178900753467864554260446708842162773345348298157467411926079756092147544497068000233007477191578333572784654318537785544709699328915760518608291118807464400785836835778315009377442766842129158923286952014836265426233094717963075689446543
>>> N**0.5 
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: int too large to convert to float

As N is too big, I used gmpy2’s sqrt() function, which seems to work like a charm with amazing precision when configured properly.

Python 3.9.1 (default, Dec  8 2020, 07:51:42) 
[GCC 10.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import gmpy2
>>> gmpy2.get_context().precision=10000
>>> N = 3275733051034358984052873301763419226982953208866734590577442123100212241755791923555521543209801099055699081707325573295107810120279016450478569963727745375599027892100123044479660797401966572267597729137245240398252709789403914717981992805267568330238483858915840720285089128695716116366797390222336632152162599116524881401005018469215424916742801818134711336300828503706379381178900753467864554260446708842162773345348298157467411926079756092147544497068000233007477191578333572784654318537785544709699328915760518608291118807464400785836835778315009377442766842129158923286952014836265426233094717963075689446543
>>> int(gmpy2.sqrt(N))
57234020049568062680167149397320334138475055366692391619414576898418757640197516619972969585657005770922760034647027169113852192292388168770093382325177206332179127469187791105500801029820725502775079428327432025791102473091395337531487693106678627965501939161224320205026459078466305245593078568807696469431

Below is the script that was used to decrypt the ciphertext.

#!/usr/bin/python3
import math
import gmpy2
from Crypto.Util.number import long_to_bytes

gmpy2.get_context().precision=10000

# Extended Euclidean Algorithm to compute the greatest common divosr between 2 numbers
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)

# Compute the modular multiplicative inverse of a give number 
def modinv(a, m):
     gcd, x, y = egcd(a, m)
     if gcd != 1:
         return None  # modular inverse does not exist
     else:
         return x % m

# Given parameters
N = 3275733051034358984052873301763419226982953208866734590577442123100212241755791923555521543209801099055699081707325573295107810120279016450478569963727745375599027892100123044479660797401966572267597729137245240398252709789403914717981992805267568330238483858915840720285089128695716116366797390222336632152162599116524881401005018469215424916742801818134711336300828503706379381178900753467864554260446708842162773345348298157467411926079756092147544497068000233007477191578333572784654318537785544709699328915760518608291118807464400785836835778315009377442766842129158923286952014836265426233094717963075689446543
e = 65537
c = 1556192154031991594732510705883546583096229743096303430901374706824505750761088363281890335979653013911714293502545423757924361475736093242401222947901355869932133190452403616496603786871994754637823336368216836022953863014593342644392369877974990401809731572974216127814977558172171864993498081681595043521251475276813852699339208084848504200274031750249400405999547189108618939914820295837292164648879085448065561197691023430722069818332742153760012768834458654303088057879612122947985115227503445210002797443447539212535515235045439442675101339926607807561016634838677881127459579466831387538801957970278441177712
r_p = 5555
r_q = 2021

# Used to store the computed p and q
p = 0
q = 0

# Initial i 
start = int(math.ceil((r_p * r_q) ** 0.5))

# Need to keep incrementing i until we get the correct p and q
for i in range(start, start + 1000):

    # Equation (13)
    sigma = (int(gmpy2.sqrt(N)) - i)**2
    z = (N - r_p * r_q) % sigma

    # Using quadratic formula to solve Equation (14)
    A = 1
    B = -z
    C = sigma * r_p * r_q

    x2 = (-B + gmpy2.sqrt(B**2 - 4 * A * C))/(2 * A)
    x1 = (-B - gmpy2.sqrt(B**2 - 4 * A * C))/(2 * A)

    q = N/(x2 / r_q + r_p)
    p = N/(x1 / r_p + r_q)

    # p and q are required to be integers
    if p.is_integer() and q.is_integer():
        p = int(p)
        q = int(q)
        break

# Typical RSA decryption
phi = (p-1)*(q-1)
d = modinv(e,phi)
M = pow(c,d,N)

# Print decrypted contents
print(long_to_bytes(M))

If we run the script, we will get the following contents:

b"Let's meet at Yichun on 30 Feb. On that day, say 'DSO-NUS{851f6c328f2da456cbc410184c7ada365c6d1f69199f0f4fdcb9fd43101ce9ee}' to confirm your identity."

Libraries used

gmpy2

pycrypto