[GoogleCTF2023]LEAST COMMON GENOMINATOR?

Twilightl 发表于 2023-7-23 17:14

本帖最后由 Twilightl 于 2023-7-23 17:16 编辑

# Challenge Name: LEAST COMMON GENOMINATOR?

## Description:

> Someone used this program to send me an encrypted message
> but I can't read it! It uses something called an LCG, do you know what
> it is? I dumped the first six consecutive values generated from it but
> what do I do with it?!

## 题目附件：

- generate.py

- ```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#a
   lcg_c = config.c#b
   lcg_n = config.n#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
```
- public.pem

- ```
-----BEGIN PUBLIC KEY-----
MIICITANBgkqhkiG9w0BAQEFAAOCAg4AMIICCQKCAgACnR8r4GemZPmX2+zLsBgz
qHanMd0pbEGFRRldNezYX9A3HT99peociEbEMUnUaVWuDbzHJX7drG8s/exQW4XF
fE5lGy+D0gSkJfQS1komUxic6iWH/1bZnU6rWFJlpbIzy/3IMx4QIx5cbOA0SsLu
AomMEi4ZERGLxm2ta7ZZZuEYVYIa9/mrlXYkTgi1fxLguT35ykHNk5Rm8e8Q8KF/
V2pQ3CQIQYZra2WLGNsxOXW7FLttmMyzgi4WQjLE/SVMs7Th5lGkjmXoQpMcc0Zh
kL3H0vMHWtQeclqsE+QXgAUQFshiSb0auf69y/H+R+qJCO0jRgBz3OVudSx91oSB
GaF7DTfFu3LsgJvMDRAdhPgdlLLzlR0PldVq1jKwjs1dWce2R5r4B0dnXqPrxLuu
A/WNp3ni3jp6AL2y7MKn2AylPUEr+/fQ6+B33wuIHcZiXHdYYPvemehtCf1WCV4Q
/C10Q3E6PK6R+dncE7ZUg0U3qnA84rAZUwweGLUD2yXngHMxDLLRv44Uv28XFvl3
5kFrlJhIhxtx/Fon70EKNboDCT8UXJ5ZlMyt47WBmYGp7FZbafbH6coLAQr1LQCy
HCJYimu7lXr9eGYixE93xXHJ3KIJPaZGmhW3qbj3B8ZxrIvGjkZtHqiw+OCNj343
Q44DknQ8F3CwBmZUmBxZSQIDAQAB
-----END PUBLIC KEY-----
```

## 题目分析：

- 分析源代码，整体思路是读取预设参数，使用LCG生成RSA中的参数phi，读取预设e生成n，使用RSA加密flag
- 其中，解题的关键是通过LCA的output（dump.txt给出），反推LCA的生成参数：a、b、m。

- 关于LCG，线性同余发生器，可参考(https://blog.csdn.net/superprintf/article/details/108964563)
- 这里给出攻击代码：
- ```python
from functools import reduce
from math import gcd
from Crypto.Util.number import *
def egcd(a, b):
   if a == 0:
         return (b, 0, 1)
   else:
         g, y, x = egcd(b % a, a)
         return (g, x - (b // a) * y, y)
def modinv(a, m):
   g, x, y = egcd(a, m)
   if g != 1:
         raise Exception('modular inverse does not exist')
   else:
         return x % m
def crack_unknown_increment(states, modulus, multiplier):
   increment = (states - states*multiplier) % modulus
   return modulus, multiplier, increment
def crack_unknown_multiplier(states, modulus):
   multiplier = (states - states) * modinv(states - states, modulus) % modulus
   return crack_unknown_increment(states, modulus, multiplier)
def crack_unknown_modulus(states):
   diffs = )]
   zeroes = , diffs)]
   modulus = abs(reduce(gcd, zeroes))
   return crack_unknown_multiplier(states, modulus)
# N = (A*N+B) % M
# A,B,N均未知
sequence = []
modulus, multiplier, increment = crack_unknown_modulus(sequence)
print('A = '+str(multiplier))
print('B = '+str(increment))
print('N = '+str(modulus))
```
- 攻击后可得到LCG初始参数：
```
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, isPrime
class LCG:
lcg_m = 99470802153294399618017402366955844921383026244330401927153381788409087864090915476376417542092444282980114205684938728578475547514901286372129860608477#a
lcg_c = 3910539794193409979886870049869456815685040868312878537393070815966881265118275755165613835833103526090552456472867019296386475520134783987251699999776365#b
lcg_n = 8311271273016946265169120092240227882013893131681882078655426814178920681968884651437107918874328518499850252591810409558783335118823692585959490215446923#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__':
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
dump_file = open("dump.txt", "w")
primes_n = 1
while True:
   for i in range(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() != 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
for i in primes_arr:
   print(i)
phi = 1
for k in primes_arr:
   phi *= (k - 1)
print(phi)
```
- 之后就是基本RSA解密

- 特别的：RSA的公钥以public.pem文件形式给出，需要转换
- 这里使用网站解析：http://www.hiencode.com/pub_asys.html
- 当然也可以使用Python相关库导入
- 编写python脚本
- ```python
from Crypto.Util.number import *
from gmpy2 import *
e=65537
n=10663197782188755187683519128391607889384236984841159980368295444757556251666173181966270935627381363634363152017932100870866073743196496182631686860974529519304898483583880797787662017633083156395595834399833548697123723014690019039843286516441722069672629491734333533874814655021750465470744221908153042891598629847474248035637833322061522018106952433195747728295433960640630861246440503259390376775374597599893181929337896828585045200809527092809746018806372033463639511758548910283175609247004446838778595246305426570138737826179346237355482797652195577697810275921391495040635386160960077290295503041318571091585994232128977189250560450541724526298324540333633756525782039764692046496665886338829810667477580556894564708344208454824227841439832096019161139930247745872364451624685509376111571650368725564985474387879414080347347860850162991841345901292668284154455326375190710973306072342463052980587717861754724857153296737480485351289440257347649463959856275061657492903860650820592573032713540474706170687783458640870091611869081448943812812946839710972240290444677129959352614435646729998203754847928052523568784250017348717982594389028978174915940120215557880850880860400503991453968452316505964854586987874049061874850121
with open(r'D:\lenovo\VSCode\CTF\7.22\c\flag.txt','rb') as f:
   c=bytes_to_long(f.read()[::-1])
# print(c)
phi=10663197782188755187683519128391607889384236984841159980368295444757556251666173181966270935627381363634363152017932100870866073743196496182631686860974518215336308559118375893619890700566492246455484248865065942975919518821420696894418516412087824875580336264450895120608590786960103732463735259314746627602481490634183029017002524008299865576550974115842994899362462506740342026543406560282128252586317741411826809367436511777686104024771128452674932531192224723706907716833848808135180104501764984240012323401024049549978818892958211947253027021172432101248326724880191387361026527894934644325582519289043602145078962059823083375709403213297514989173849682349374277191142325479424357500368940265794006074137733272137342565970150847115890972043431768285064555903295753465581583657708894234169997201812684367717581685538245496933190164547560072929740493318805568286958724231450156740155971287257415601496588835565287706802963284818961466920678551895969101307349683566564580517648582979443095366832488807574064804819371853182596765904847800309068939076791323026159289764642558267730090790476527577604463134018573846651149743622527934870659053517579542096949282004235077015296802375481771769578980224915514371840316985391540016742400
d=gmpy2.invert(e,phi)
flag=gmpy2.powmod(c,d,n)
print(long_to_bytes(flag))
```
- 得到flag：

- CTF{C0nGr@tz_RiV35t_5h4MiR_nD_Ad13MaN_W0ulD_b_h@pPy}

NightGlow 发表于 2023-7-24 13:53

这份密码学的writeup写的太好了！向大佬学习！

页: [1]

吾爱破解 - 52pojie.cn's Archiver

[GoogleCTF2023]LEAST COMMON GENOMINATOR?