THS Challenges Writeups - Crypto

Writeups of the challenges of THS - Crypto

 

Crypto

RSA with Weak Key Generation

RSA with public key (n, e), where n is the modulus and e is the public exponent, has been used to encrypt a message (c). Break the encryption and retrieve the flag!

Solution

import sympy
from Crypto.Util.number import long_to_bytes

def factorize_rsa(n, e):
    # Factorize n
    p, q = sympy.factorint(n)
    phi_n = (p - 1) * (q - 1)
    d = sympy.mod_inverse(e, phi_n)
    return p, q, d

n=61886745084257631376488227331867711713709402213271607752836119943649359023667208312483665009582971079823046811338833406961794657413393778092534084222138475089147141696179355977692335422731845770908312945444299254259133792282993335641429805931242152085766033674121178257768597630195914815454715609367808317869
e=65537
c=29184854329273146705082304498278279007891632368627171242276651126149934346884387033845388118635683203163310791789528451430981802738727935419627068963524759975113719613080593449715622314139734404660709392180503270726011733745509304350413748188026452571306638146400806346222379626392181072620190074397326311078

# Brute force approach to factorize n
p, q, d = factorize_rsa(n, e)

plaintext = long_to_bytes(pow(c, d, n))
print(f"Decrypted plaintext: {plaintext}")

Explanation

The provided code is an implementation of RSA factorization to decrypt a given ciphertext (c) using the modulus (n) and the public exponent (e). Here’s a step-by-step explanation of the code:

  1. Import Libraries:
    • sympy: A Python library for symbolic mathematics, including functions for factorization.
    • Crypto.Util.number: A module from the Crypto library used for cryptographic operations.
  2. Define a Function to Factorize RSA:
    • factorize_rsa(n, e) is a function that factors the modulus n into its prime factors (p and q), calculates the Euler’s totient function (phi_n), and computes the private exponent (d) using the provided public exponent (e).
  3. Given RSA Parameters:
    • n: The RSA modulus.
    • e: The public exponent.
    • c: The ciphertext to be decrypted.
  4. Factorize RSA Modulus (Brute-Force Approach):
    • Call the factorize_rsa function to obtain the prime factors (p and q) and the private exponent (d) using a brute-force factorization approach.
  5. Decrypt the Ciphertext:
    • Use the RSA decryption formula: plaintext = ciphertext^d mod n to obtain the decrypted plaintext.

Problem to Exploit

The vulnerability in this challenge lies in the weak generation of the RSA key pairs. The key generation did not follow best practices, allowing p and q to be factorized using a brute-force approach. A strong RSA key pair generation process would ensure that p and q are large, random, and distinct primes, making brute-force attacks infeasible.

By exploiting this weakness, an attacker can easily factorize n and obtain the private exponent d, enabling the decryption of the ciphertext c.

 

 

RSA with Close Primes

RSA with public key (n, e), where n is the modulus and e is the public exponent, has been used to encrypt a message (c). Break the encryption and retrieve the flag!

Solution

import sympy
from Crypto.Util.number import long_to_bytes

# Function to factorize RSA
def factorize_rsa(n, e):
    # Factorize n
    p, q = sympy.factorint(n)  
    phi_n = (p - 1) * (q - 1)
    d = sympy.mod_inverse(e, phi_n)
    return p, q, d

n=48706743526456110909428995124449408863187502680671706144671247865632703597785484902782407848707211100406427544099273968655959926749210447499225035943265124025648199091660367526030690917367663667107925476791028825151493494621282112817554558981244752772243791642631132895597905737204721830373839441463773763961
e=65537
c=17494215219452418410735376548777416672918857860269874380125017320239219944217737827971553197914209737210660246817471880119097142967110758156891959698116796855064386986723057380756325429190521798810246080683688121106799846172205318734520267225783976882420050682350087876912575488787283094615360025293044048739

# Factorize RSA modulus
p, q, d = factorize_rsa(n, e)

# Decrypt the ciphertext
plaintext = long_to_bytes(pow(c, d, n))
print(f"Decrypted plaintext: {plaintext}")

Explanation

The provided code is an implementation of RSA factorization to decrypt a given ciphertext (c) using the modulus (n) and the public exponent (e). Here’s a step-by-step explanation of the code:

  1. Import Libraries:
    • sympy: A Python library for symbolic mathematics, including functions for factorization.
    • Crypto.Util.number: A module from the Crypto library used for cryptographic operations.
  2. Define a Function to Factorize RSA:
    • factorize_rsa(n, e) is a function that factors the modulus n into its prime factors (p and q), calculates the Euler’s totient function (phi_n), and computes the private exponent (d) using the provided public exponent (e).
  3. Given RSA Parameters:
    • n: The RSA modulus.
    • e: The public exponent.
    • c: The ciphertext to be decrypted.
  4. Factorize RSA Modulus:
    • Call the factorize_rsa function to obtain the prime factors (p and q) and the private exponent (d) using the provided n and e.
  5. Decrypt the Ciphertext:
    • Use the RSA decryption formula: plaintext = ciphertext^d mod n to obtain the decrypted plaintext.

Problem to Exploit

Given the small difference between p and q in this challenge, traditional factorization algorithms can be employed to efficiently factorize n into p and q. This undermines the security of the RSA encryption and allows an attacker to obtain the private exponent d, subsequently leading to the decryption of the ciphertext c.

 

 

RSA with Low Public Exponent

RSA with public key (n, e), where n is the modulus and e is the public exponent, has been used to encrypt a message (c). Break the encryption and retrieve the flag!

Solution

from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes

# Given RSA parameters
n=157403096125982580243517971785240979426378156189291161074203023308369585977650302735904992519425671267015982772445200003227356999669208283493063856013366034601719281545339053459985262254286856036985424437020056829886845534373553739163622586736178743458885820804631465446973115761187478772456859249378193759871
e=3
c=73642555357189624726271241819566304380058839628677760958794990200642872060081404255864431749783264544323825228853106361018373004664113167960293820852713779572805351991923351604771227715639094802857818671608378375877219115547654818778969234293720241524489737123617125

# Use low public exponent attack to obtain the plaintext
plaintext = long_to_bytes(iroot(c, e)[0])

print(f"Decrypted plaintext: {plaintext}")

Explanation

The provided code demonstrates an RSA encryption with a low public exponent e and a corresponding ciphertext c that is much smaller than the modulus n. Here’s a step-by-step explanation of the code:

  1. Import Libraries:

    • gmpy2: A Python library for arbitrary-precision arithmetic.
    • Crypto.Util.number: A module from the Crypto library used for cryptographic operations.
  2. Given RSA Parameters:

    • n: The RSA modulus.
    • e: The low public exponent.
    • c: The ciphertext to be decrypted.
  3. Low Public Exponent Attack:

    • The code uses a low public exponent attack exploiting the fact that (c^{1/e}) is approximately equal to the plaintext. The function iroot(c, e)[0] calculates this value.

      (c^{1/e})

  4. Decrypt the Ciphertext:

    • Use the low public exponent attack to obtain an approximation of the plaintext.

Problem to Exploit

The vulnerability in this challenge is the use of a low public exponent e (in this case, (e=3)) and a ciphertext c that is much smaller than the modulus n. This makes the RSA encryption susceptible to a low public exponent attack. Using this weakness, an attacker can efficiently approximate the plaintext using (c^{1/e}), undermining the security of the encryption.

 

 

RSA with GCD between n

RSA was used to encrypt many messages, but apparently the randomness was a bit flawed.

Solution

import sympy
from Crypto.Util.number import *

# Given RSA Parameters
n_values = [ ... ]
ciphertexts = [ ... ]
e = 65537
result_gcd = []

# Function to calculate GCD using Euclidean algorithm
def euclid_gcd(x, y):
    if x < y:
        return euclid_gcd(y, x)
    while y != 0:
        (x, y) = (y, x % y)
    return x

# Iterate through n_values to find common factors
for a in n_values:
    for i in n_values:
        if i != a:
            result = euclid_gcd(a, i)
            if result != 1:
                result_gcd.extend([a, result])
        break

# Obtain the shared modulus n and its prime factors p, q
print(result_gcd)
n = result_gcd[0]
p = result_gcd[1]
q = n // p
print(q)

phi_n = (p - 1) * (q - 1)
d = sympy.mod_inverse(e, phi_n)

# Decrypt ciphertexts and check for the flag
for i in range(len(ciphertexts)):
    plaintext = long_to_bytes(pow(ciphertexts[i], d, n))
    if b'THS' in plaintext:
        print(f"Decrypted plaintext: {plaintext}")

Explanation

The provided code demonstrates an RSA encryption scenario where multiple ciphertexts share a common modulus n. Here’s a step-by-step explanation of the code:

  1. Import Libraries:
    • sympy: A Python library for symbolic mathematics, including functions for prime number generation and modular inverse.
    • Crypto.Util.number: A module from the Crypto library used for cryptographic operations.
  2. Given RSA Parameters:
    • e: The public exponent (common for all ciphertexts).
    • ciphertexts: A list of ciphertexts.
    • n_values: A list of modulus values.
  3. Calculate Greatest Common Divisor (GCD):
    • Define a function euclid_gcd to calculate the greatest common divisor (GCD) between two numbers.
  4. Find Common Factors:
    • Iterate through the n_values to find pairs with a common factor using the euclid_gcd function.
  5. Obtain the Shared Modulus n and its Prime Factors p, q:
    • Use the found common divisor between n values to determine the shared modulus n and calculate its prime factors p and q.
  6. Calculate Private Exponent d:
    • Calculate the private exponent d using one of the modulus n and its prime factors p and q.
  7. Decrypt Ciphertexts:
    • Decrypt one of the ciphertexts using the calculated private exponent d and the corresponding modulus n.

Problem to Exploit

The vulnerability in this challenge is the possibility of finding a common divisor between two distinct modulus values n. By exploiting this vulnerability, one can calculate the private key and decrypt the ciphertext associated with one of the moduli.

The common modulus n is a weakness in this scenario. When the modulus n is shared across multiple RSA instances, it allows for the possibility of calculating the greatest common divisor (GCD) between these moduli. If a non-trivial GCD is found, it indicates that the two moduli share a common prime factor. This can be used to factorize the moduli and obtain the private key, ultimately leading to decryption of ciphertexts.

 

 

RSA with Common Modulus

In a company, all the employees are associated with a RSA public key. The cybersecurity guy who is in charge is too lazy to generate a completely new public key for each new employee. So he decided to recycle the same modulus n for everyone, changing only the public exponent. At some point, a message m is broadcasted in encrypted form to all the employee of the company. The information you have is the common public modulus n and the data associated to two employees, i.e. their public keys e1, e2 and the ciphertexts c1, c2 corresponding to m. Are you able to find out the original message m?

Solution

import gmpy2
from Crypto.Util.number import long_to_bytes

# Given values
n = 54091136062731189097684838662133730287805248616280945524818499074174178792921107970338405562623800475671952250241219301481555035985163774303923971007210358200895011198122865359958581567527848886246719199618581799287912557968141059152021173457855601404027408448802610510064740223784290948744501305515730596997
e1 = 1865575455884331305675554729885762114935344119504545880670853799431652817950448203252572257
e2 = 1312243660361784808275488430749762831225040489432564480368052176946960407384352742950812177
c1 = 17388944013212914709111843302373363154177810314909226069833458440142999382506980558537758425521552507465344517971486052354978300372605259672815020783196035462386299618047720964517867551193923325437684543772519253451584390962031497382020739845600737725890176948987014875085558953291018803210239123619775482932
c2 = 33250791921906562143753311787247221381260546987912195950044761388182931039632232256265471306279253936021807284695159322620020776657098775913521016551805253075107986592397891820718524215746314165431201429215309566146400402509358680223349076052610642879947434103437190444964383660138126171417916846643510769415

# Calculate the coefficients (x, y) for e1*x + e2*y = 1
def gcdExtended(a, b):
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = gcdExtended(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

# Calculate the coefficients for e1*x + e2*y = 1
g, x, y = gcdExtended(e1, e2)

# Calculate the inverse of c2 modulo n
i = gmpy2.invert(c2, n)

# Decrypt the ciphertexts using the private exponents
decrypted_with_e1 = pow(c1, x, n)
decrypted_with_e2 = pow(i, int(-y), n)

# Obtain the plaintext message
m = decrypted_with_e1 * decrypted_with_e2 % n

# Convert the plaintext to bytes
plaintext = long_to_bytes(m)

print("Decrypted plaintext:", plaintext)

Explanation

The provided code demonstrates an RSA encryption scenario where multiple ciphertexts share a common modulus n but have different public exponents e1 and e2. Here’s a step-by-step explanation of the code:

  1. Given RSA Parameters:
    • n: The RSA modulus (common for all ciphertexts).
    • e1 and e2: The public exponents for different ciphertexts.
    • c1 and c2: The ciphertexts corresponding to the respective public exponents.
  2. Calculate Coefficients (x) and (y):
    • The function gcdExtended calculates the coefficients (x) and (y) for the equation (e1 \times x + e2 \times y = 1).
  3. Invert (c2) modulo (n):
    • Calculate the modular inverse of (c2) modulo (n) using gmpy2.
  4. Decrypt Ciphertexts:
    • Decrypt each ciphertext using the respective private exponents (x) and (y).
  5. Obtain the Plaintext Message:
    • Calculate the product of the decrypted ciphertexts modulo (n) to obtain the plaintext message.
  6. Convert to Bytes:
    • Convert the obtained plaintext to bytes.

Problem to Exploit

The vulnerability in this challenge is the usage of a common modulus (n) with different public exponents (e1) and (e2). By exploiting the coefficients (x) and (y) such that (e1 \times x + e2 \times y = 1), we can efficiently calculate the plaintext message from the given ciphertexts.

The shared modulus (n) is a vulnerability because when two public keys share the same modulus, the greatest common divisor (GCD) of their public exponents is not 1. This allows us to calculate (x) and (y) such that (e1 \times x + e2 \times y = 1). Using this property, we can efficiently calculate the original message (m) from the given ciphertexts (c1) and (c2).

 

 

RSA with Chinese Reminder Theorem

Three RSA public keys have been used to encrypt the same message m. The three public keys have the same exponent e=3 but different moduli, i.e. (n1, 3), (n2, 3), (n3, 3). Given c1, c2, c3 encryption of m under each key, are you able to find out the original message m? The flag format is THS{m_in_base_10}

Solution

import sympy
from gmpy2 import iroot

# Given values
n1 = 85667815574861619903823020734533014758497517129884920616214802541098363447680440172184486722087145209053447848996237848934244008599360860637027022690716373111251917149818843329284837276342823124988862132327437056204754198531063993808031061018616042619216387796979644142647922795828529235261286375252354390063
n2 = 146825997036352110245960059001360194347948188573286974674641344811517602727223717209837808109729490159701434527698628570575321775660553998994589424821168562205858458354384116767308355332092559541524922140124107506966027111051071572911755705349514694449804245783590573764095514071122982302155622677270073579393
n3 = 126544077525498025320598712777907896955205564795328624870301965015430682262467340470541178431837985468584094637225798274404278743227923491443245955862615159873284856215560581071498437573890782583365748146854546320263620393749915310571726480907686382214711241661860512785774497778808223771838053406539416576479
c1 = 45512244749960737068762928598042488637828624542043307040990197747313444784018535834815887416147740125294323994588261583522452852456068856863379250538376048332923364458763172479458691661588110286726710567698648374134511145284452830756712535784097058446561842278071719514607192557768101864770873294674384094465
c2 = 123588398908311767727101679376457828849663963115288179775711742629380839446592473764338993671478334873446178318004409923292465225389810454413006911399858642047006099581825255346445514571891529369799000388707048554582114937936722673420025235592403007724208657309233083747811960480630198049806825599634022878798
c3 = 112175491066960361570409951547003985463067829151083921740671033347833502662682014450106279649923202079324172182162545693708582829214404116395393681198229804355301311901211214418659038661959928829326341589776070076629631491939911273164128605630101357046542494238831195406755324135589154844551960532164332662226
e = 3

from functools import reduce
def chinese_remainder(n, a):
    sum=0
    prod=reduce(lambda a, b: a*b, n)
    for n_i, a_i in zip(n,a):
        p=prod//n_i
        sum += a_i* mul_inv(p, n_i)*p
    return sum % prod
def mul_inv(a, b):
    b0= b
    x0, x1= 0,1
    if b== 1: return 1
    while a>1 :
        q=a// b
        a, b= b, a%b
        x0, x1=x1 -q *x0, x0
    if x1<0 : x1+= b0
    return x1

n=[n1,n2,n3]
a=[c1,c2,c3]
print(iroot(chinese_remainder(n,a), 3))

Explanation

The provided Python script reveals a vulnerability in RSA encryption due to the narrow gap between the prime factors p and q of the modulus n. Here’s a step-by-step breakdown:

  1. Given RSA Parameters:
    • n1, n2, n3: Modulus for the respective ciphertexts.
    • c1, c2, c3: Corresponding ciphertexts.
    • e: The public exponent.
  2. Chinese Remainder Theorem (CRT):
    • The script implements the Chinese Remainder Theorem to efficiently combine the results from different moduli.
  3. Modular Inverse Calculation:
    • The script also calculates the modular inverse necessary for the CRT computation.
  4. Combining Results:
    • Utilizing the Chinese Remainder Theorem and modular inverse, the script combines the decrypted results to recover the original message.

Problem to Exploit

The vulnerability in this challenge lies in the small difference between the prime factors p and q of n. This small difference makes the factorization of n into p and q feasible using traditional factorization algorithms. Once p and q are obtained, an attacker can deduce the private exponent d, enabling the decryption of the ciphertext c.