NSSCTF Round#6 Team

2022-10-16

binary(V1)

虽然在后面异或了3，对p和q的比特影响非常之小，所以p、q仍然大致满足$p+q=2^{512}$，所以类似zer0pts CTF那题，解方程即可。

from Crypto.Util.number import long_to_bytes

n = 28439705991045663908857355142942262888109378224567220640321971170147687906191867226507772290105722468453003997560405961037860301720566204163583071580117631863630591384712172525673589612679984312909885721474004407318513252973235607119935090030342220110613332646827222206888937013221686874130002976891337482347
c = 19147147229180935592900776234339673387299394177535713949270580797239517644947690854918878134729963297207021578792506584675663899080028514789587402852322201811049767759204792874820803675496704837543205833779286293353943614755261264004375211872686806028504902564331881943276490126603876805247247189761895772971

P.<x> = ZZ[]

t = 1 << 512
while True:
    f = x ^ 2 - t * x + n
    rs = f.roots()
    if len(rs) > 0:
        p = rs[0][0]
        q = n // p
        assert p * q == n
        break
    t += 1
d = inverse_mod(65537, (p - 1) * (q - 1))
m = power_mod(c, d, n)
print(long_to_bytes(m).decode())

binary(V2)

这里异或的数较大，不能用V1的方法，考虑先利用$p+q=2^{512}$这一大致关系建立方程解出p或q的高位，再copper已知p高位恢复即可。

import gmpy2 
from Crypto.Util.number import *

n = 30922990347456222917444539556680823943887227159919972225540984336960832339775501069487618715102061181838518715208122786885229224735713077740655704542042089733020521332143961366919882134247596845707777520653357831207540764924471585714534980480437755533066407887622784022020839396643521892154136823395518763847
c = 14404101377910063215556811836598054698395805241539170278590413082852350322381754181749356420746244575121938620896549335174534133100850321380464588512818088008879625862657133634998081654516156005613557049123826706652115924967600775632920027926373724318084460740820944304520569864767315879749100114552218784151
e=0x10001
s=2^512
q_=int((s+gmpy2.iroot(s**2-4*n,2)[0])//2)
PR.<x>=PolynomialRing(Zmod(n))
f=q_+x
q=q_+int(f.small_roots(X=2^50,beta=0.4,epsilon=0.05)[0])
p=n//q
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=int(pow(c,d,n))
print(long_to_bytes(m))