爆破是你的"真言"?

Problem: [tangcuxiaojkuai]easy_copper3

[[toc]]

思路

因为我们只有一条数学表达式：
u*q=1 (mod p)

可以对其变形得到：
u*q=1+kp
u*q^2=q+kn
u*q^2-q=0 (mod n)
另外一种变形是没用的，un=p+k*p^2
虽然具有因子p，但是gcd的值一定还是n。

但是本题相对于原题缺失了 dp，也就是少了q的低位信息，好像只能强行爆破了。

然后去看了 ZMJ4396 大佬的WP，确实是我想的强行爆破了。
就贴一下大佬的WP吧。我稍微改进了一下，因为 ql 的低位一定是奇数，所以可以缩小搜索范围到 2^10。差不多769出。

EXP

# sage
from Crypto.Util.number import *
from tqdm import trange

n = 57054300236523364297068573084561858708294662390960413501481702646411973922601148943850295724745015979460852792874663924727251780057665081615966986614006891899776582114850433561286026344516509555159123543852355598205747122411634510298915483597709877911019093953862935760391037639842229970271659629400825516949
e = 3914808559
c = 34367961236912765697312756121175172638962230270006286310938236988443532571967649877497844350082733634910858022991620956125616557464236977620127700161939950208821044710180411053388650174106798369640918760166665311872344484980029847646184112357339382437302111172508120844002507660831969088208714656235021379114
u = 3971337705608798216937148389824777665706019231614517125236102421717365951782208458636759087630906187451681891734064328433966129922001851802738564150946911

NBITS = 11
print(f'NBITS = {NBITS}')
epsilon = (NBITS - 1) / 510.

for ql in range(301, 2^NBITS, 2):
    with open('q.txt', 'w') as f:
        f.write(f'ql={ql}')
    P.<x> = PolynomialRing(Zmod(n))
    q = 2^511 + 2^510 + x * 2^NBITS + ql
    f = u * q^2 - q
    f = f.monic()
    sol = f.small_roots(X=2^(510-NBITS), beta=1, epsilon=epsilon) 
    if (len(sol) > 0):
        x = sol[0]
        q = gcd(ZZ(q(x)), n)
        if (q.nbits() == 512):
            print(f'q={q}')
            with open('q.txt', 'w') as f:
                f.write(str(q))
            p=n//q
            phi=(p-1)*(q-1)
            d=inverse(e, phi)
            m=pow(c,d,n)
            print(long_to_bytes(int(m)))
            break

总结

Coppersmith