TL;DR

  • 線形合同法を用いて生成した素数をRSAに利用している
  • 最初に素数が出てから次に素数が出るまでの関係を線形合同法の式から導出して$N$を求めると最初に出たほうの素数に関する2次方程式が得られる
  • というわけでこれを解けば$N$の素因数分解が出来る

Prerequisite

  • 線形合同法

Writeup

次のスクリプトとその実行結果が与えられる。

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)

$x_{i+1} = Ax_i + B \mod M$という線形合同法を用いて素数が作られている。ここで、$x_i$とその後に現れた数$x_{i+k} \ (k \gt 0)$に対して次のような関係がある。

$$ x_{i+k} = A^kx_i + \left(\sum_{j=0}^{k-1}A^j\right)B \mod M $$

よって、$p = x_i, q = x_{i+k} \ (k \gt 0)$とすると$pq = N$より次のような2次方程式が得られ、これの解は$p$となる。

$$ A^kx_i^2 + \left(\sum_{j=0}^{k-1}A^j\right)B - N \equiv 0 \mod M $$

というわけで$k$を小さい方から順に試していき、この方程式を解いて解が$N$で割れるかを試す。これは数百程度の$k$で実現され、十分早く終わる。

Code

e = 65537
n = 198148795890507031730221728469492521085435050254010422245429012501864312776356522213014006175424179860455397661479243825590470750385249479224738397071326661046694312629376866307803789411244554424360122317688081850938387121934893846964467922503328604784935624075688440234885261073350247892064806120096887751
A = 1677936292368545917814039483235622978551357499172411081065325777729488793550136568309923513362117687939170753313352485633354858207097035878077942534451467
B = 5687468800624594128838903842767411040727750916115472185196475570099217560998907467291416768835644005325105434981167565207313702286530912332233402467314947
M = 1244793456976456877170839265783035368354692819005211513409129011314633866460250237897970818451591728769403864292158494516440464466254909969383897236264921
c = 48071438195829770851852911364054237976158406255022684617769223046035836237425012457131162001786019505606941050117178190535720928339364199078329207393922570246678871062386142183424414041935978305046280399687623437942986302690599232729065536417757505209285175593543234585659130582659013242346666628394528555

PR.<x> = PolynomialRing(GF(M))

k = 1
while True:
    if k % 10 == 0:
        print(k)
    _A = pow(A, k, M)
    _B = 0
    for j in range(k):
        _B += pow(A, j, M)
        _B %= M
    _B *= B
    _B %= M
    f = _A * x^2 + _B * x - n
    r = f.roots()
    if len(r) > 0:
        assert len(r) == 2
        (r1, _), (r2, _) = r
        r1 = int(r1)
        r2 = int(r2)
        if n % r1 == 0:
            p = r1
            q = n // r1
            break
        if n % r2 == 0:
            p = r2
            q = n // r2
            break
    k += 1

print(p)
print(q)

phi = (p-1)*(q-1)
d = inverse_mod(e, phi)
pt = pow(c, int(d), n)
from Crypto.Util.number import long_to_bytes

print(long_to_bytes(pt))

Flag

hitcon{so_weak_randomnessssss}