Tags: lcg mj0ln1r crypto invaders0x1
Rating:
# Crypto - LEAST COMMON GENOMINATOR?
Attached File : [generate.py,dump.txt,flag.txt,public.pem]
```python
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`
```text
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`
```python
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.
```python
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}`
***
# [Original Writeup](https://themj0ln1r.github.io/posts/googlectf23)
