直接来分析题目吧

from Crypto.Util.number import getStrongPrime
from gmpy import next_prime
from random import getrandbits
from libnum import s2n
#from flag import flag
flag = 'this_is_f1ag'
p=getStrongPrime(1024)
q=next_prime(p^((1<<900)-1)^getrandbits(300))
n=p*q
e=65537

m=int(flag.encode('hex'),16)
assert m<n
c=pow(m,e,n)

print(hex(n))
#0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3

print(hex(c))
#0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1

从p, q生成的过程来看,p和q的高124位是相同的,900~300位是相反的,所以可以直接开根号得到高124位,中间的600位可以通过爆破得到大致的一个数据大小,最后用coppersmith解

中间的爆破过程

刚开始的p,q是这样的:

$$p\quad\overbrace{\cdots\cdots}^{124}\overbrace{1\cdots1}^{600}\overbrace{0\cdots0}^{300}$$

$$q\quad\overbrace{\cdots\cdots}^{124}\overbrace{0\cdots0}^{600}\overbrace{1\cdots1}^{300}$$

这时$p * q<n$所以可以从高位开始,让p,q同位置的比特同时亦或1,若$p * q<n$则保留当前的p,q,一直循环600次,即遍历900~301比特(根据owp写的)

官方的exp已经出了 官方exp,但感觉写的糊里糊涂的有点(可能是我不太喜欢这种码风),所以就按着它小改了一下

from Crypto.Util.number import *
from libnum import n2s

n=0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
c=0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1
e = 65537

PR.<x> = PolynomialRing(Zmod(n))
pm=int(sqrt(n))>>900  # high 124 bits
p0 = (1<<900)-1  
q0 = 1<<300-1     # last 300 bits all '1'

p = p0 + (pm << 900)  # middle 600 bits all '1'
q = q0 + (pm << 900)  # middle 600 bits all '0'
assert p * q < n
#burte force
for i in range(898, 301, -1):
    cur = 1<<i
    if (p^^cur) * (q^^cur) < n:
        p ^^= cur
        q ^^= cur

PR.<x> = PolynomialRing(Zmod(n))
f = p + x
roots = f.small_roots(X = 2**425, beta = 0.5)
if roots:
    p = p + roots[0]
    q = n // int(p)
    phi = (p - 1)*(q - 1)
    d = inverse(e, phi)
    print(n2s(int(pow(c, d, n))))
else:
    print('no solution')

比赛时队里的队友想到的是构造这样的方程

$$ N=(a+b)(a+2^{900}-1-b+c)\\N=a^{2}+2^{900}a+b*2^{900}-b^2+ac+bc-a-b $$

a是高124位,b是剩下的位,c是最后300位亦或产生的差值

a=(floor(sqrt(n))>>900)<<900
   kbar=(((n-a**2-a*2**900))) 
   bbar1=(((2**900+floor(sqrt(2**1800-4*kbar)))//2)>>428)<<428
   P.<x,y> = PolynomialRing(ZZ)
   pol = (a+(x+bbar1))*(a+2^900-1-(x+bbar1)+y)-n
   X = 2^430
   Y = 2^300
   x0,y0=(coron(pol,X,Y,k=4,debug=True))[0]  #coron没有贴出来,根small_roots一样,也是用coppersmith method
   print(x0,y0)
   p=a+(x0+bbar1)
   q=a+(2**900-1)-(x0+bbar1)+y0
   phi=(p-1)*(q-1)
   e=65537
   d=inverse_mod(e,phi)
   m=pow(c,d,n)
   print(long_to_bytes(m))