摸鱼Writeup-2

Ant x D3CTF

BabyLattice

考虑r很小，有\(b m + r= c + k n\)，故构造格

\[\begin{bmatrix} n & 0 & 0 \\ b & 1 & 0 \\ c & 0 & X\end{bmatrix}\]

X为放缩因子，目标向量为\((k, m, 1)\)时，通过格映射为向量\((r, m, X)\)，调整X大小为\(2^{300}\)，可成功规约出目标向量，exp如下：

from hashlib import sha256

n = 69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
b = 65473938578022920848984901484624361251869406821863616908777213906525858437236185832214198627510663632409869363143982594947164139220013904654196960829350642413348771918422220404777505345053202159200378935309593802916875681436442734667249049535670986673774487031873808527230023029662915806344014429627710399196
c = 64666354938466194052720591810783769030566504653409465121173331362654665231573809234913985758725048071311571549777481776826624728742086174609897160897118750243192791021577348181130302572185911750797457793921069473730039225991755755340927506766395262125949939309337338656431876690470938261261164556850871338570

X = 2**300
M = Matrix(ZZ, [[n, 0, 0], [b, 1, 0], [c, 0, X]])

ML = M.LLL()

r = int(ML[0][0])
m = int(abs(ML[0][1]))
assert (b * m + r) % n == c

print('d3ctf{%s}' % sha256(int(m).to_bytes(50, 'big')).hexdigest())

SimpleGroup

需要用到第一题中有关n，b的关系式，

\(b * a11 - a12 \equiv 0 \mod p\)

\(b * a21 - a22 \equiv 0 \mod q\)

考虑到a11，a12，a21，a22都很小，可以使用格基规约，但p，q未知（这里我一开始想直接二元Copper，但发现好像bound不太够，懒得想复杂的多项式构造了），考虑将两个式子相乘，展开得到

\[a11 * a21 * b^2 -(a11*a22 + a21*a12) *b + a12 * a22 = k * n\]

构造格如下：

\[\begin{bmatrix} n & 0 & 0 \\ b & 1 & 0 \\ b^2 & 0 & 1\end{bmatrix}\]

这里由于a11，a12，a21，a22都非常小，不需要平衡因子，目标向量\((k, a11*a22 + a21*a12, -a11 * a21)\)，通过格映射，得到向量\((a12 * a22, a11*a22 + a21*a12, -a12 * a22)\)，之后联立方程，即可解除a11，a12，a21，a22，然后即可分解n。

又考虑到$e = e_1 * e_2, e_1 = 36493 ,e_2= 52859 $

对于\(m_i\)， 有\(c_i \equiv y^{m_i} r_i^{e} \mod n,\quad m \equiv m_1 \mod e_1, \quad m \equiv m_2 \mod e_2\)

\(\Rightarrow c_1 \equiv y^{m_1} (y^{k_1} r^{e_2})^{e_1} \mod n, \quad c_2 \equiv y^{m_1} (y^{k_2} r^{e_1})^{e_2} \mod n\)

可以看到由于y已知，\(e_1, e_2\) 位数均很小，可以通过分别爆破\(m_1, m_2\)（利用\(c_1 y^{-m_1}, c_2 y^{-m_2}\) 在\(GF(n)\) 上是否是\(e_1, e_2\) 次数剩余来判断），之后CRT即可恢复\(m_i\)，完整exp如下：

from Crypto.Util.number import *
from tqdm import tqdm


def check(s, t, _phi):
    if _phi % t != 0:
        return False
    return pow(s, _phi//t, n) == 1


n = 69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
b = 65473938578022920848984901484624361251869406821863616908777213906525858437236185832214198627510663632409869363143982594947164139220013904654196960829350642413348771918422220404777505345053202159200378935309593802916875681436442734667249049535670986673774487031873808527230023029662915806344014429627710399196
y = 12064801545723347322936991186738560311049061235541031580807549422258814170771738262264930441670708308259694588963224372530498305648578520552038029773849342206125074212912788823834152785756697757209804475031974445963691941515756901268376267360542656449669715367587909233618109269372332127072063171947435639328
e = 1928983487
C = [63173987757788284988620600191109581820396865828379773315280703314093571300861961873159324234626635582246705378908610341772657840682572386153960342976445563045427986000105931341168525422286612417662391801508953619857648844420751306271090777865836201978470895906780036112804110135446130976275516908136806153488, 9763526786754236516067080717710975805995955013877681492195771779269768465872108434027813610978940562101906769209984501196515248675767910499405415921162131390513502065270491854965819776080041506584540996447044249409209699608342257964093713589580983775580171905489797513718769578177025063630080394722500351718, 37602000735227732258462226884765737048138920479521815995321941033382094711120810035265327876995207117707635304728511052367297062940325564085193593024741832905771507189762521426736369667607865137900432117426385504101413622851293642219573920971637080154905579082646915297543490131171875075081464735374022745371, 1072671768043618032698040622345664216689606325179075270470875647188092538287671951027561894188700732117175202207361845034630743422559130952899064461493359903596018309221581071025635286144053941851624510600383725195476917014535032481197737938329722082022363122585603600777143850326268988298415885565240343957, 27796821408982345007197248748277202310092789604135169328103109167649193262824176309353412519763498156841477483757818317945381469765077400076181689745139555466187324921460327576193198145058918081061285618767976454153221256648341316332169223400180283361166887912012807743326710962143011946929516083281306203120, 27578857139265869760149251280906035333246393024444009493717159606257881466594628022512140403127178174789296810502616834123420723261733024810610501421455454191654733275226507268803879479462533730695515454997186867769363797096196096976825300792616487723840475500246639213793315097434400920355043141319680299224, 29771574667682104634602808909981269404867338382394257360936831559517858873826664867201410081659799334286847985842898792091629138292008512383903137248343194156307703071975381090326280520578349920827357328925184297610245746674712939135025013001878893129144027068837197196517160934998930493581708256039240833145, 33576194603243117173665354646070700520263517823066685882273435337247665798346350495639466826097821472152582124503891668755684596123245873216775681469053052037610568862670212856073776960384038120245095140019195900547005026888186973915360493993404372991791346105083429461661784366706770467146420310246467262823, 5843375768465467361166168452576092245582688894123491517095586796557653258335684018047406320846455642101431751502161722135934408574660609773328141061123577914919960794180555848119813522996120885320995386856042271846703291295871836092712205058173403525430851695443361660808933971009396237274706384697230238104, 61258574367240969784057122450219123953816453759807167817741267194076389100252707986788076240792732730306129067314036402554937862139293741371969020708475839483175856346263848768229357814022084723576192520349994310793246498385086373753553311071932502861084141758640546428958475211765697766922596613007928849964, 13558124437758868592198924133563305430225927636261069774349770018130041045454468021737709434182703704611453555980636131119350668691330635012675418568518296882257236341035371057355328669188453984172750580977924222375208440790994249194313841200024395796760938258751149376135149958855550611392962977597279393428]

e1 = 36493
e2 = e//e1

X = 1
M = Matrix(ZZ, [[n, 0, 0], [b, X, 0], [b ^ 2, 0, X]])
ML = M.LLL()

# a = a11 * a21, b = a11*a22 + a21*a12, c = a12 * a22
'''
a = 211380743487233628797755584958526337321408979158793229985661
b = 1382843159437215516163973075066558157591473749635266665605630
c = 1173142580751247504024100371706709782500216511824162516724129

a11, a21, a12, a22 = var('a11, a21, a12, a22')
solve([a == a11 * a21, b == a11*a22 + a21*a12, c == a12 * a22], a11, a21, a12, a22)
'''


a11 = 1018979931854255696816714991181
a12 = 1017199123798810531137951821909

p = gcd(b * a11 - a12, n)
q = n//p
assert n == p * q

M = []
phi = (p-1)*(q-1)
for i in tqdm(range(len(C))):
    for m in range(1, e1+1):
        tmp = (C[i] * inverse(int(pow(y, m, n)), n)) % n
        if check(tmp, e1, phi):
            m1 = m
            break
    for m in range(1, e2+1):
        tmp = (C[i] * inverse(int(pow(y, m, n)), n)) % n
        if check(tmp, e2, phi):
            m2 = m
            break
    tmp_m = CRT([m1, m2], [e1, e2])
    M.append(tmp_m)

print('M:', M)
flag = 0
for i in range(len(M)):
    flag += M[i] * (e**i)

print(long_to_bytes(flag))

EasyCurve

这一题有个很大的非预期，就是由于x，y坐标给的较小，可以完全通过hackergame2020中OT的方法来获得完整的一对\(x, y\)，由于p-1非常光滑，可以直接在其曲线上使用Pohlig Hellman算法来得到e，从而得到flag。

这里谈下预期解法，是通过一个映射来讲曲线的点映射到GF上，然后构造OT，再在GF上使用Pohlig Hellman求解的，具体得到这个映射的方法很多，我这里讲一种比较简单的求通项得到的方法。

稍作分析可以发现题给曲线其实是一个\(GF(p)\) 上的pell方程，即\(x^2 \equiv Dy^2 + u^2\)，而pell方程的解可以通过以下方法得到（这里的\(x_n\) 即对应\((nG)x\)，即n倍点的坐标）

对矩阵\(\begin{bmatrix} x_1 & Dy_1 \\ y_1 & x_1\end{bmatrix}\)，进行对角化，可以得到其特征值为$ D y + x, -D y + x$，之后求得 \[ x_n = \frac{(y_1\sqrt D + x_1)^n + (-y_1\sqrt D + x_1)^n}{2 u^{n-1}} \]

\[ y_n = \frac{(y_1\sqrt D + x_1)^n - (-y_1\sqrt D + x_1)^n}{2 \sqrt Du^{n-1}} \]

容易得到 \[ \frac{x_n - \sqrt D y_n}{ u} = (\frac{x1 - \sqrt D y1}{u}) ^ n \]

\[ \frac{x_n + \sqrt D y_n}{ u} = (\frac{x1 + \sqrt D y1}{u}) ^ n \]

即找到了两个将曲线上点映射到GF的映射 \[ f: f(x, y) = \frac{x - \sqrt D y}{ u} \]

\[ g: g(x, y) = \frac{x + \sqrt D y}{ u} \]

此时，利用hackergame2020的OT中的技巧，且D已知，对于每一个点，可以得到\(x - \sqrt D y\)，得到两组数据后相除，即可得到 \[ \frac{x_{1n} + \sqrt D y_{1n}}{ x_{2n} + \sqrt D y_{2n}} = (\frac{x1 + \sqrt D y1}{x_1 + \sqrt D y_2}) ^ n \] 对这两个数通过Pohlig Hellman算法求DLP，即可得到e，从而得到flag，完整exp如下：

from winpwn import *
from Crypto.Util.number import *
from math import sqrt, ceil
from factordb.factordb import FactorDB
from gmpy2 import jacobi
from sympy import nthroot_mod
from hashlib import sha256
from string import digits, ascii_letters
import os

charset = digits + ascii_letters
p = 9688074905643914060390149833064012354277254244638141162997888145741631958242340092013958501673928921327767591959476890238698855704376126231923819603296257


def get_factor_list(n):
    factor = FactorDB(n)
    factor.connect()
    return list(factor.get_factor_list())


def get_factor_list_with_exponent(n, factor_list=None):
    if not factor_list:
        factor = FactorDB(n)
        factor.connect()
        factor_list = list(factor.get_factor_list())
    factor_list_with_exponent = {}
    for factor in factor_list:
        if factor not in factor_list_with_exponent.keys():
            factor_list_with_exponent[factor] = 1
        else:
            factor_list_with_exponent[factor] += 1
    return factor_list_with_exponent


def bsgs(g, y, p, upper_bound=None):
    res = []
    if not upper_bound:
        upper_bound = p - 1
    m = int(ceil(sqrt(upper_bound)))
    S = {pow(g, j, p): j for j in range(m+1)}
    gs = pow(g, (-m) % (p-1), p)
    for i in range(m+1):
        if y in S:
            return i * m + S[y]
        y = (y * gs) % p
    return None


def GCRT(mi, ai):
    assert (isinstance(mi, list) and isinstance(ai, list))
    curm, cura = mi[0], ai[0]
    for (m, a) in zip(mi[1:], ai[1:]):
        d = int(GCD(curm, m))
        c = a - cura
        assert (c % d == 0)
        K = c // d * inverse(curm // d, m // d)
        cura += curm * K
        curm = curm * m // d
        cura %= curm
    return cura % curm, curm


def get_n_order(g, p, phi=None, factor_list=None):
    if not phi:
        phi = p-1
    if not factor_list:
        factor_list = get_factor_list(phi)
    ord = phi
    new_factor_list = factor_list
    for factor in factor_list:
        if pow(g, ord//factor, p) == 1:
            ord //= factor
            new_factor_list.remove(factor)
    return ord, get_factor_list_with_exponent(p, new_factor_list)


def pohlig_hellman(g, y, p, ord=None, factor_list=None):
    if not ord:
        ord, factor_list = get_n_order(g, p, factor_list=factor_list)
    else:
        factor_list = get_factor_list_with_exponent(ord)
    prime_order_mod = [0] * len(factor_list)
    for i, factor in enumerate(factor_list.keys()):
        tmp_g = pow(g, ord//factor, p)
        for j in range(factor_list[factor]):
            tmp_y = (y * inverse(pow(g, prime_order_mod[i], p), p)) % p
            tmp_y = pow(tmp_y, ord//(factor**(j+1)), p)
            pmod = bsgs(tmp_g, tmp_y, p, factor**(j+1))
            prime_order_mod[i] += pmod * (factor**j)
    return GCRT([factor**factor_list[factor] for factor in factor_list.keys()], prime_order_mod)[0]


def proof_of_work(end, judge):
    for a in tqdm(charset):
        for b in charset:
            for c in charset:
                for d in charset:
                    tmp = a + b + c + d
                    if sha256((tmp + end).encode()).hexdigest() == judge:
                        return tmp


def get_x_y(s):
    io.recvuntil('n = ')
    n = int(io.recvuntil('\n').strip())
    io.recvuntil('e = ')
    e = int(io.recvuntil('\n').strip())
    io.recvuntil('x0 = ')
    x0 = int(io.recvuntil('\n').strip())
    io.recvuntil('x1 = ')
    x1 = int(io.recvuntil('\n').strip())
    io.recvuntil('v = ')

    v = pow(-s, e, n) * x1 - x0
    v = (v * inverse(pow(-s, e, n) - 1, n)) % n
    io.sendline(str(v))

    io.recvuntil('m0_ = ')
    m0 = int(io.recvuntil('\n').strip())
    io.recvuntil('m1_ = ')
    m1 = int(io.recvuntil('\n').strip())

    return (m0 + m1 * s) % n


while True:
    # io = remote('47.100.50.252', 10000)
    io = remote('127.0.0.1', 10015)
    '''io.recvuntil('sha256(XXXX+')
    have = io.recv(16)
    io.recvuntil('== ')
    ans = io.recv(64)
    io.recvuntil('Give me XXXX:')
    io.sendline(proof_of_work(have, ans))'''

    io.recvuntil('D = ')
    D = int(io.recvuntil('\n').strip())
    if jacobi(D, p) == 1:
        break
    io.close()
a = nthroot_mod(D, 2, p)

Gx = []
kGx = []
for i in range(2):
    Gx.append(get_x_y(a))
    kGx.append(get_x_y(a))
    io.recvuntil('do you know my e?')
    io.sendline(str(0))
    print(io.recvuntil('\n'))

get_x_y(0)
get_x_y(0)
io.recvuntil('do you know my e?')

g = (Gx[0] * inverse(Gx[1], p)) % p
y = (kGx[0] * inverse(kGx[1], p)) % p
print('g =', g)
print('y =', y)

guess = pohlig_hellman(g, y, p)
assert pow(g, guess, p) == y

print('guess =', guess)
io.sendline(str(guess))
print(io.recvuntil('\n'))
io.interactive()

ByteCTF2021 Final

acyclic group

另外几道题没什么说的，这道题比赛的时候折磨了我很久。。。最后几分钟差一点想出来但还是没出。

代码如下：

#!/usr/bin/env python3
from hashlib import sha256
from random import choices, getrandbits, randint
import signal
import string

from flag import FLAG


def proof_of_work() -> bool:
    alphabet = string.ascii_letters + string.digits
    nonce = "".join(choices(alphabet, k=8))
    print(f'SHA256("{nonce}" + ?) starts with "000000"')
    message = (nonce + input().strip()).encode()
    return sha256(message).digest().hex().startswith("000000")


def gen_modulus():
    primes = [
        2, 3, 5, 7, 11, 13, 17, 19,
        23, 29, 31, 37, 41, 43, 47, 53,
        59, 61, 67, 71, 73, 79, 83, 89,
        97, 101, 103, 107, 109, 113, 127, 131,
    ]
    n = 1
    t = []
    for p in primes:
        tmp_t = randint(1, 16)
        n *= p ** tmp_t
        t.append(tmp_t)
    return n, t


def test() -> bool:
    n, _ = gen_modulus()
    e = randint(1, n)
    for i in range(3):
        try:
            num = input().strip()
        except EOFError:
            return False
        if not str.isnumeric(num):
            return False
        num = int(num)
        if num == n:
            return True
        res = pow(num, e, n)
        print(res)
    return False


def main():
    signal.alarm(60)
    if not proof_of_work():
        return
    print("Listen...I have some acyclic groups for you..."
          "No noise this time...God bless you get them...")
    passed = 0
    T = 256
    signal.alarm(T)
    for i in range(T):
        print("Round", i)
        if test():
            passed += 1
            print("GOOD SHOT, MY FRIEND")
        else:
            print("CALM DOWN, MY FRIEND")
    if passed > T * 0.8:
        print("CONGRATULATIONS", FLAG)


main()

可以看到是一个类似oracle的猜数题，可以传两次消息\(m_0, m_1\)，然后得到\(m_0^e\mod n, m_1^e \mod n\)。而 \(n\) 是由一个指定素数集构成的，指数随机生成，于是我最早考虑计算primes所有素数的积\(N\)，那么必然有\(N | n, n | N^{16}\)，这样传入\(k_1N^{k_0}, k_2N^{k_0}\)，得到\(c_0, c_1\)，\(k_2*c_0 - k_1*c_1\) 必然是n的倍数，再通过一些简单的过滤则有可能得到\(n\)，但这样的理论概率极限也就是\(0.5\)，而题目需要大于\(0.8\)，实验中最多也就到\(0.55\)左右。

于是考虑别的想法，找到\(N^{16}\) 上的\(k_1\) 次根\(x_1\) 和 \(k_2\)次根 \(x_2\)，然后传入\(x_1, x_2\)，得到\(c_0, c_1\)， 有\(c_0^{k_1} - 1 \equiv 0 \mod n, c_1^{k_2} - 1 \equiv 0 \mod n\)， 则可以计算\(GCD(c_0^{k_1} - 1, c_1^{k_2} - 1 )\) 来得到n的倍数。当\(k_1, k_2\) 取到较大的两个素数时（测试中53，41为最佳），\(GCD(c_0^{k_1} - 1, c_1^{k_2} - 1 )\) 中的多余小因子很少，这样结合一些过滤可以稳定到 $ 0.6$ 左右的概率，实验中最高得到182/256次，距离要求仍然相差甚远。

赛后和Hermes聊这题，他用了先验奇数的思想，即先传一个\(x_0, x_0 \equiv 2 \mod 3\)，如果返回的\(c_0 \equiv 2 \mod 3\) ，那么e为奇数，反之为偶数，如果是奇数，第二个直接传\(-x_0 \mod N^{16}\) 即可，这样天然是\(0.5+\) 的概率，只需要考虑e为偶数的情况即可。

于是我将这个先验思想与之前的想法结合，由于只有2次根模3上为2，故考虑第一个数传2次根与一个53次根的积，然后根据返回的\(c_0\)判断e的奇偶性，如果为奇数则直接得到n，反之使用之前的方法，传入41次根，计算GCD并过滤，这里使用的过滤也很简单，用了一个简单的check函数：

def ez_check(x, tmp_n, tmp_c, index):
    for j in range(1, index):
        if pow(x, j, tmp_n) == tmp_c:
            return True
    return False

判断现有的n和c是否匹配，虽然不能完全判别正确性，但可以过滤掉一部分n，不加过滤的话，是无法到达0.8的要求的。

于是得到完整的exp（本地测试，非远程）如下：

from Crypto.Util.number import *
from tqdm import tqdm
from random import randint


primes = [2, 3, 5, 7, 11, 13, 17, 19,
          23, 29, 31, 37, 41, 43, 47, 53,
          59, 61, 67, 71, 73, 79, 83, 89,
          97, 101, 103, 107, 109, 113, 127, 131]
N = 525896479052627740771371797072411912900610967452630


def ez_check(x, tmp_n, tmp_c, index):
    for j in range(1, index):
        if pow(x, j, tmp_n) == tmp_c:
            return True
    return False


def gen_modulus():
    n = 1
    t = []
    for p in primes:
        tmp_t = randint(1, 16)
        n *= p ** tmp_t
        t.append(tmp_t)
    return n, t


X53 = 16146763596179907622493109012827107483432127255282437968769511754257220353461373199051318700354563705501798111116975423559551919422360373620077135733152834339753566421633318551588422901547881579218520776006792486613397971515271604855586579740039260074131940980987975405945266243817124527776349845008796650597901430324561617712539448004335786983097258035189240029672607297470279777590671871429356611345024068708210664204032378937951457734824660588211295536984531224843323388692707230473974167062051827530633678063778393771712605759122050047549153324446713490868711015327552083786926047655742819801159119820050854801807132456468704631166477801370570144842420484203774449336692121369166894459616914719270555761434836110634387526761779763136974433072352065708061222706777945829022683408311193928882620000000000000001
X41 = 14433742236573688560360048613517053763200707683208778120848086283299329941013908083365456158136248365405808895787635075734246983533602171353983415139484130546490622760668175853268336625517248976893430593633591158403560983700284581913439756565424800771408850504240484768112546298539809747045454017191685052792871835571611728801542959691013910881345442147407305419751546631888734401332725798315194326822778940702909396121047842327694640911259501609831936278582897452598156308636522732156722313669233126732015453396069197186228360843076869905501365431573710803270781244583676572897758932558706108800668583084492823482604125931433024709087840253930862552870791179735998515105708049484833368876195836038931796305023286562526358223498002848846916276239224031232879423197037204854042451328998802974875960000000000000001
X2 = 15845692616563450127497208839410301344402316795683874456673644728074297254230460786999608268999620577402794405164458414337023127673742026008021414589602557158573546834697406978953669032292544682264032538283813482564370439284759728142958678735148370476425664417360562433032379231110074243013706826953064966499154160963062921354644984286660194677706265414862607876360639364289269590679134724946975491236100718964941807053660511056670515549359602825507165267329870326738546498444951189947310784787069656189398361340810771090331973605773043378424416612980873234071900022982273879970686574341215845470279225478293269284360469028535434817147966175875953360972917337632136468352618104434531745056493725241600130859431706675615178872943525346567519727470007647885832252355970578673569499720213721708193542519836425781249
length = 90
M = N**16
test_length = 2049
times = 0
not_times = 0
pass_times = 0
t0 = 53 * 2
t1 = 41
x0 = (X2 * X53) % M
x1 = X41
for i in tqdm(range(256)):
    n, t = gen_modulus()
    e = randint(1, n-1)
    c0 = pow(x0, e, n)
    if c0 % 3 == 2:
        c1 = pow(-x0 % M, e, n)
        my_n = c1+c0
        assert my_n == n
        times += 1
        continue

    c1 = pow(x1, e, n)
    tmp0 = pow(c0, t0, M) - 1
    tmp1 = pow(c1, t1, M) - 1
    if tmp0 == 0:
        tmp0 = x0 - 1
    if tmp1 == 0:
        tmp1 = x1 - 1

    sn = GCD(tmp0, tmp1)
    my_n = 1
    for prime in primes:
        i = 1
        while sn % prime ** i == 0 and i <= 16:
            i += 1
        my_n *= prime ** (i - 1)

    if not (ez_check(x0, my_n, c0, t0) and ez_check(x1, my_n, c1, t1)):
        for l in range(2, test_length):
            if my_n % l != 0:
                continue
            tmp = my_n // l
            if ez_check(x0, tmp, c0, t0) and ez_check(x1, tmp, c1, t1):
                my_n = tmp
                break

    if my_n == n:
        times += 1
    if ez_check(x0, my_n, c0, t0) and ez_check(x1, my_n, c1, t1) and my_n != n:
        pass_times += 1
    if tmp0 < n or tmp1 < n:
        not_times += 1
print('times: %d' % times)

运行后发现通过率可以满足题目要求：

总体来说这题还是比较有意思的，但是对于为什么两个较大素数根做GCD的小因子很小尚未探究，也期待官方WP有比较好的解释。