Tags: lcg mj0ln1r crypto invaders0x1
Rating:
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 :
Xn+1=(a×Xn+c)modp
Where,
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×2
The 4 2×2
[X3−X0X4−X1 X4−X0X5−X1],[X4−X0X5−X1 X5−X0X6−X1]
Finding determinant of these all and then finding the GCD of them will give us the modulus(n) used in lcg.
With n
X1=(a×X0+c)modp X2=(a×X1+c)modp
X2−X1=(a×X1+c−(X0×a+c))modp X2−X1=(a×X1−(X0×a))modp X2−X1=(X1−X0)×amodp X2−X1X1−X0=amodp a=X2−X1X1−X0modp a=((X2−X1))×InverseMod(X1−X0,p)modp
Lets solve for c
X1=(a×X0+c)modp X1−c=(a×X0)modp −c=(a×X0−X1)modp c=(X1−a×X0)modp
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}