HITCON CTF 2021 簡易Writeup

#1. はじめに
　2021/12/4(土) 11:00 JST ～ 2021/12/5(日) 23:00:00 JST で「HITCON CTF 2021」に参加し、302 点（得点を得た 288 チーム中 69 位）を獲得しました。
　一番易しい Crypto の Warmup 問しか解いていないので、Writeupを起こそうか迷いましたが、後で振り返るときに有用なので残すことにします。

#2. 簡易Writeup（so easy rsa）
###☆設問

So common so fragile.

prob.py

from gmpy2 import next_prime, is_prime
from random import randint
from Crypto.Util.number import bytes_to_long

class Rand:
    def __init__(self):
        self.seed = randint(2, 2**512)
        self.A = next_prime(randint(2, 2**512))
        self.B = next_prime(randint(2, 2**512))
        self.M = next_prime(randint(2, 2**512))
        for _ in range(10000):
            self.next()
    
    def next(self):
        self.seed = self.seed * self.A + self.B
        self.seed = self.seed % self.M
        return self.seed

    def __str__(self):
        return f"{self.A}, {self.B}, {self.M}"
        

def gen_prime(r):
    while True:
        v = r.next()
        if is_prime(v):
            return v

r = Rand()
p,q = gen_prime(r), gen_prime(r)
n = p*q
e = 65537
flag = bytes_to_long(open('flag','rb').read())
val = pow(flag, e, n)

print(n)
print(r)
print(val)

data

198148795890507031730221728469492521085435050254010422245429012501864312776356522213014006175424179860455397661479243825590470750385249479224738397071326661046694312629376866307803789411244554424360122317688081850938387121934893846964467922503328604784935624075688440234885261073350247892064806120096887751
1677936292368545917814039483235622978551357499172411081065325777729488793550136568309923513362117687939170753313352485633354858207097035878077942534451467, 5687468800624594128838903842767411040727750916115472185196475570099217560998907467291416768835644005325105434981167565207313702286530912332233402467314947, 1244793456976456877170839265783035368354692819005211513409129011314633866460250237897970818451591728769403864292158494516440464466254909969383897236264921
48071438195829770851852911364054237976158406255022684617769223046035836237425012457131162001786019505606941050117178190535720928339364199078329207393922570246678871062386142183424414041935978305046280399687623437942986302690599232729065536417757505209285175593543234585659130582659013242346666628394528555

###☆方針・解法
A、B、M がリークされているので、p と q を根にもつ 多項式 g を考えることができます。ただし、p を生成した後、gen_primeで q を生成する際、何回 r.next() されているか分からないので、ループさせて試行します。

solve.sage

from Crypto.Util.number import *

n = 198148795890507031730221728469492521085435050254010422245429012501864312776356522213014006175424179860455397661479243825590470750385249479224738397071326661046694312629376866307803789411244554424360122317688081850938387121934893846964467922503328604784935624075688440234885261073350247892064806120096887751

A = 1677936292368545917814039483235622978551357499172411081065325777729488793550136568309923513362117687939170753313352485633354858207097035878077942534451467
B = 5687468800624594128838903842767411040727750916115472185196475570099217560998907467291416768835644005325105434981167565207313702286530912332233402467314947
M = 1244793456976456877170839265783035368354692819005211513409129011314633866460250237897970818451591728769403864292158494516440464466254909969383897236264921
ct = 48071438195829770851852911364054237976158406255022684617769223046035836237425012457131162001786019505606941050117178190535720928339364199078329207393922570246678871062386142183424414041935978305046280399687623437942986302690599232729065536417757505209285175593543234585659130582659013242346666628394528555

R.<x> = PolynomialRing(GF(M))
f = x

while(True):
  f = A * f + B
  g = f * x - n
  if len(g.factor()) == 2:
    p = int(-g.factor()[0][0].coefficients()[0])
    q = int(-g.factor()[1][0].coefficients()[0]) 
    if n % p == 0:
      q = n // p
      break
    elif n % q == 0:
      p = n // q
      break

assert p * q == n
e = 65537
d = inverse(e, (p-1)*(q-1))
print(long_to_bytes(pow(int(ct), int(d), int(n))))

###☆フラグ
hitcon{so_weak_randomnessssss}

#3 おわりに
　1 問解けたからヨシ！からは早く卒業しないと。。。