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:
- Import Libraries:
sympy
: A Python library for symbolic mathematics, including functions for factorization.Crypto.Util.number
: A module from theCrypto
library used for cryptographic operations.
- Define a Function to Factorize RSA:
factorize_rsa(n, e)
is a function that factors the modulusn
into its prime factors (p
andq
), calculates the Euler’s totient function (phi_n
), and computes the private exponent (d
) using the provided public exponent (e
).
- Given RSA Parameters:
n
: The RSA modulus.e
: The public exponent.c
: The ciphertext to be decrypted.
- Factorize RSA Modulus (Brute-Force Approach):
- Call the
factorize_rsa
function to obtain the prime factors (p
andq
) and the private exponent (d
) using a brute-force factorization approach.
- Call the
- 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:
- Import Libraries:
sympy
: A Python library for symbolic mathematics, including functions for factorization.Crypto.Util.number
: A module from theCrypto
library used for cryptographic operations.
- Define a Function to Factorize RSA:
factorize_rsa(n, e)
is a function that factors the modulusn
into its prime factors (p
andq
), calculates the Euler’s totient function (phi_n
), and computes the private exponent (d
) using the provided public exponent (e
).
- Given RSA Parameters:
n
: The RSA modulus.e
: The public exponent.c
: The ciphertext to be decrypted.
- Factorize RSA Modulus:
- Call the
factorize_rsa
function to obtain the prime factors (p
andq
) and the private exponent (d
) using the providedn
ande
.
- Call the
- 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:
-
Import Libraries:
gmpy2
: A Python library for arbitrary-precision arithmetic.Crypto.Util.number
: A module from theCrypto
library used for cryptographic operations.
-
Given RSA Parameters:
n
: The RSA modulus.e
: The low public exponent.c
: The ciphertext to be decrypted.
-
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})
-
-
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:
- Import Libraries:
sympy
: A Python library for symbolic mathematics, including functions for prime number generation and modular inverse.Crypto.Util.number
: A module from theCrypto
library used for cryptographic operations.
- Given RSA Parameters:
e
: The public exponent (common for all ciphertexts).ciphertexts
: A list of ciphertexts.n_values
: A list of modulus values.
- Calculate Greatest Common Divisor (GCD):
- Define a function
euclid_gcd
to calculate the greatest common divisor (GCD) between two numbers.
- Define a function
- Find Common Factors:
- Iterate through the
n_values
to find pairs with a common factor using theeuclid_gcd
function.
- Iterate through the
- 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 factorsp
andq
.
- Use the found common divisor between n values to determine the shared modulus
- Calculate Private Exponent d:
- Calculate the private exponent
d
using one of the modulusn
and its prime factorsp
andq
.
- Calculate the private exponent
- Decrypt Ciphertexts:
- Decrypt one of the ciphertexts using the calculated private exponent
d
and the corresponding modulusn
.
- Decrypt one of the ciphertexts using the calculated private exponent
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:
- Given RSA Parameters:
n
: The RSA modulus (common for all ciphertexts).e1
ande2
: The public exponents for different ciphertexts.c1
andc2
: The ciphertexts corresponding to the respective public exponents.
- Calculate Coefficients (x) and (y):
- The function
gcdExtended
calculates the coefficients (x) and (y) for the equation (e1 \times x + e2 \times y = 1).
- The function
- Invert (c2) modulo (n):
- Calculate the modular inverse of (c2) modulo (n) using
gmpy2
.
- Calculate the modular inverse of (c2) modulo (n) using
- Decrypt Ciphertexts:
- Decrypt each ciphertext using the respective private exponents (x) and (y).
- Obtain the Plaintext Message:
- Calculate the product of the decrypted ciphertexts modulo (n) to obtain the plaintext message.
- 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:
- Given RSA Parameters:
- n1, n2, n3: Modulus for the respective ciphertexts.
- c1, c2, c3: Corresponding ciphertexts.
- e: The public exponent.
- Chinese Remainder Theorem (CRT):
- The script implements the Chinese Remainder Theorem to efficiently combine the results from different moduli.
- Modular Inverse Calculation:
- The script also calculates the modular inverse necessary for the CRT computation.
- 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.