Table of Contents
Hello all! I played Google CTF 2023 which was happened from 24 June to 26 June.
Crypto - LEAST COMMON GENOMINATOR?
Attached File : [generate.py,dump.txt,flag.txt,public.pem]
generate.py
from secret import config
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, isPrime
class LCG:
lcg_m = config.m
lcg_c = config.c
lcg_n = config.n
def __init__(self, lcg_s):
self.state = lcg_s
def next(self):
self.state = (self.state * self.lcg_m + self.lcg_c) % self.lcg_n
return self.state
if __name__ == '__main__':
assert 4096 % config.it == 0
assert config.it == 8
assert 4096 % config.bits == 0
assert config.bits == 512
# Find prime value of specified bits a specified amount of times
seed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635
lcg = LCG(seed)
primes_arr = []
dump = True
items = 0
dump_file = open("dump.txt", "w")
primes_n = 1
while True:
for i in range(config.it):
while True:
prime_candidate = lcg.next()
if dump:
dump_file.write(str(prime_candidate) + '\n')
items += 1
if items == 6:
dump = False
dump_file.close()
if not isPrime(prime_candidate):
continue
elif prime_candidate.bit_length() != config.bits:
continue
else:
primes_n *= prime_candidate
primes_arr.append(prime_candidate)
break
# Check bit length
if primes_n.bit_length() > 4096:
print("bit length", primes_n.bit_length())
primes_arr.clear()
primes_n = 1
continue
else:
break
# Create public key 'n'
n = 1
for j in primes_arr:
n *= j
print("[+] Public Key: ", n)
print("[+] size: ", n.bit_length(), "bits")
# Calculate totient 'Phi(n)'
phi = 1
for k in primes_arr:
phi *= (k - 1)
# Calculate private key 'd'
d = pow(config.e, -1, phi)
# Generate Flag
assert config.flag.startswith(b"CTF{")
assert config.flag.endswith(b"}")
enc_flag = bytes_to_long(config.flag)
assert enc_flag < n
# Encrypt Flag
_enc = pow(enc_flag, config.e, n)
with open ("flag.txt", "wb") as flag_file:
flag_file.write(_enc.to_bytes(n.bit_length(), "little"))
# Export RSA Key
rsa = RSA.construct((n, config.e))
with open ("public.pem", "w") as pub_file:
pub_file.write(rsa.exportKey().decode())
dump.txt
2166771675595184069339107365908377157701164485820981409993925279512199123418374034275465590004848135946671454084220731645099286746251308323653144363063385
6729272950467625456298454678219613090467254824679318993052294587570153424935267364971827277137521929202783621553421958533761123653824135472378133765236115
2230396903302352921484704122705539403201050490164649102182798059926343096511158288867301614648471516723052092761312105117735046752506523136197227936190287
4578847787736143756850823407168519112175260092601476810539830792656568747136604250146858111418705054138266193348169239751046779010474924367072989895377792
7578332979479086546637469036948482551151240099803812235949997147892871097982293017256475189504447955147399405791875395450814297264039908361472603256921612
2550420443270381003007873520763042837493244197616666667768397146110589301602119884836605418664463550865399026934848289084292975494312467018767881691302197
And the flag.txt is an encrypted flag.
Observations:
1. The actual flag was encrypted with the RSA
2. The primes are generated using a Linear Congruential Generator
3. The seed is known
4. First 6 generated random values of LCG are known
The LCG works on equation :
$$ X_{n+1} = (a \times X_{n}+c) mod p $$
Where,
- $$X(n)$$ is a sequence of pseudo random values.
- $$p$$ is modulo defined as $$0 < p$$
- $$a$$ is the multiplier defined as $$0 < a < p$$
- $$c$$ is the increment $$0 <= c < p$$ ( if $$c = 0$$ the LCG is called Multiplicative Congruential Generator)
We can see the generate.py implementation.
lcg_m = a lcg_c = c lcg_n = p
We have total generated values of lcg including seed.
We can find the n(modulus) by making the 4 $$2 \times 2$$ matrices from $$ X_1,X_2,X_3,X_4,X_5,X_6,X_7$$ and finding the GCD of the determinant values of these 7 values.
The 4 $$2 \times 2$$ matrices, $$ \begin{bmatrix} X_1 - X_0 & X_2 - X_1\ X_2 - X_0 & X_3 - X_1 \end{bmatrix} \begin{bmatrix} X_2 - X_0 & X_3 - X_1\ X_3 - X_0 & X_4 - X_1 \end{bmatrix}$$
$$ \begin{bmatrix} X_3 - X_0 & X_4 - X_1\ X_4 - X_0 & X_5 - X_1 \end{bmatrix}, \begin{bmatrix} X_4 - X_0 & X_5 - X_1\ X_5 - X_0 & X_6 - X_1 \end{bmatrix} $$
Finding determinant of these all and then finding the GCD of them will give us the modulus(n) used in lcg.
With $$n$$ we can find $$a$$ by solving these equations.
$$ X_1 = (a \times X_0+c) mod p\ X_2 = (a \times X_1+c) mod p\ $$
$$ X_2 - X_1 = (a \times X_1+c - (X_0 \times a+c)) mod p\ X_2 - X_1 = (a \times X_1 - (X_0 \times a)) mod p\ X_2 - X_1 = (X_1 - X_0) \times a mod p\ \frac{X_2 - X_1}{X_1 - X_0} = a mod p \ a = \frac{X_2 - X_1}{X_1 - X_0} mod p\ a = ((X_2 - X_1)) \times InverseMod(X_1 - X_0,p) mod p\ $$
Lets solve for $$c$$,
$$ X_1 = (a \times X_0+c) mod p\ X_1 - c = (a \times X_0) mod p\ -c = (a \times X_0 - X_1) mod p\ c = (X_1 - a \times X_0) mod p $$
So, with n,c,m we can generate entire series which is used to generate primes in the encryption.
The python implementation to find n,c,m
import math
def calc_det(i, j, X):
a1 = X[i] - X[0]
b1 = X[i + 1] - X[1]
a2 = X[j] - X[0]
b2 = X[j + 1] - X[1]
det = a1 * b2 - a2 * b1
return abs(det)
def GCD(a, b):
a = abs(a)
b = abs(b)
while a:
a, b = b % a, a
return b
def modInverse(a, m):
if GCD(a, m) != 1:
return None #if not releatively prime no modinv
u1, u2, u3 = 1, 0, a
v1, v2, v3 = 0, 1, m
while v3 != 0:
q = u3 // v3
v1, v2, v3, u1, u2, u3 = (
u1 - q * v1,
u2 - q * v2,
u3 - q * v3,
v1,
v2,
v3,
)
return u1 % m
def main():
while True:
try:
X = [
211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635,
2166771675595184069339107365908377157701164485820981409993925279512199123418374034275465590004848135946671454084220731645099286746251308323653144363063385,
6729272950467625456298454678219613090467254824679318993052294587570153424935267364971827277137521929202783621553421958533761123653824135472378133765236115,
2230396903302352921484704122705539403201050490164649102182798059926343096511158288867301614648471516723052092761312105117735046752506523136197227936190287,
4578847787736143756850823407168519112175260092601476810539830792656568747136604250146858111418705054138266193348169239751046779010474924367072989895377792,
7578332979479086546637469036948482551151240099803812235949997147892871097982293017256475189504447955147399405791875395450814297264039908361472603256921612,
2550420443270381003007873520763042837493244197616666667768397146110589301602119884836605418664463550865399026934848289084292975494312467018767881691302197,
]
Det_X = []
Det_X.append(calc_det(1, 2, X))
Det_X.append(calc_det(2, 3, X))
Det_X.append(calc_det(3, 4, X))
Det_X.append(calc_det(4, 5, X))
found_p = math.gcd(math.gcd(Det_X[0], Det_X[1]), math.gcd(Det_X[2], Det_X[3]))
# To find 'a' and 'c' we need to solve the
mod_inv_a = modInverse((X[2] - X[3]), found_p)
found_a = ((X[3] - X[4]) * mod_inv_a) % found_p
found_c = (X[4] - found_a * X[3]) % found_p
print("n = %d\nm = %d\nc = %d\n" % (found_p, found_a, found_c))
break
except TypeError:
pass
if __name__ == "__main__":
main()
#Output
# n = 8311271273016946265169120092240227882013893131681882078655426814178920681968884651437107918874328518499850252591810409558783335118823692585959490215446923
# m = 99470802153294399618017402366955844921383026244330401927153381788409087864090915476376417542092444282980114205684938728578475547514901286372129860608477
# c = 3910539794193409979886870049869456815685040868312878537393070815966881265118275755165613835833103526090552456472867019296386475520134783987251699999776365
With these values as input we can find the modulus used in the encryption, n, phi and followed by d.
Or we can just import the public.pem to find e,n used in the encryption.
Here is the final solution script to get the flag.
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, isPrime,long_to_bytes
class LCG:
lcg_m = 99470802153294399618017402366955844921383026244330401927153381788409087864090915476376417542092444282980114205684938728578475547514901286372129860608477
lcg_c = 3910539794193409979886870049869456815685040868312878537393070815966881265118275755165613835833103526090552456472867019296386475520134783987251699999776365
lcg_n = 8311271273016946265169120092240227882013893131681882078655426814178920681968884651437107918874328518499850252591810409558783335118823692585959490215446923
def __init__(self, lcg_s):
self.state = lcg_s
def next(self):
self.state = (self.state * self.lcg_m + self.lcg_c) % self.lcg_n
return self.state
if __name__ == '__main__':
it = 8
bits = 512
# Find prime value of specified bits a specified amount of times
seed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635
lcg = LCG(seed)
primes_arr = []
dump = True
items = 0
primes_n = 1
while True:
for i in range(it):
while True:
prime_candidate = lcg.next()
if not isPrime(prime_candidate):
continue
elif prime_candidate.bit_length() != bits:
continue
else:
primes_n *= prime_candidate
primes_arr.append(prime_candidate)
break
# Check bit length
if primes_n.bit_length() > 4096:
print("bit length", primes_n.bit_length())
primes_arr.clear()
primes_n = 1
continue
else:
break
# Create public key 'n'
n = 1
for j in primes_arr:
n *= j
# Calculate totient 'Phi(n)'
phi = 1
for k in primes_arr:
phi *= (k - 1)
# Read the public key from the "public.pem" file
with open("public.pem", "rb") as pub_file:
rsa_key = RSA.import_key(pub_file.read())
# Extract the values of e and n from the RSA key
e = rsa_key.e
n = rsa_key.n
# Calculate private key 'd'
d = pow(e, -1, phi)
with open("flag.txt", "rb") as flag_file:
flag_data = flag_file.read()
_enc = int.from_bytes(flag_data, "little")
# decrypt flag
flag = pow(_enc,d,n)
print(long_to_bytes(flag))
# b'CTF{C0nGr@tz_RiV35t_5h4MiR_nD_Ad13MaN_W0ulD_b_h@pPy}'
Flag : CTF{C0nGr@tz_RiV35t_5h4MiR_nD_Ad13MaN_W0ulD_b_h@pPy}
Reference : https://teamrocketist.github.io/2019/03/31/Crypto-VolgaCtf2019-LG/