starctf2022

ezRSA

附件： ezRSA.zip

from Crypto.Util.number import getStrongPrime
from gmpy import next_prime
from random import getrandbits
from flag import flag

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))

print(hex(c))

一道相似的题目，虽有所改动，但可以参考一下：

Writeup: zer0pts CTF 2022 - nevi.dev

分析一下题目，有用的关键信息是q=next_prime(p^((1<<900)-1)^getrandbits(300))。

从中我们可以知道解题的方向是从bit出发并且目的是分解$n$。通过上式将$p,q$分为三部分，高124bits相同，中间600bits相反，低300bits是无法预测的。

所以我们将求解$p,q$的步骤分为3步：

1. 求$p,q$的高124bits。

   由$p$生成$q$的步骤只是改变了低900bits，由于$p,q$是大数，而且开平方根的误差大概率会出现在低位，因此我们可以对$n$开平方根取其高124bits即可。

   ph = int(bin(gmpy2.iroot(n,2)[0])[2:126],2)

2. 求$p,q$的中间600bits。

   我们令$p$的低900bits最大化，即每个bit位全为1，令$q$的低900bits最小化，即每个bit位全为0。这样也的话中间600bits正好是相反的。

   之后我们对$p,q$的中间600bits的从高到低同时与1进行异或，这样可以保证中间600bits仍是相反的。期间对得到的$p,q$之积与$n$进行比较，小的话就更新$p,q$的值，最终得到中间600bits。

   那为什么这样做呢？

   我们知道两个数在和不变的情况下，只有当这两个数相等时乘积才能最大化。

   

   现在$p$是最大的，$q$是最小的，$p+q$是固定的，$p*q<n$说明$p$太大了，$q$太小了，于是更改$p,q$的对应bit位（做到了$p$增加了相应的量，$q$减少了相应的量）。大于的情况就不说明了。（感觉有点废话了，说的有点过于详细以至于有点……）

   ph = int(bin(gmpy2.iroot(n,2)[0])[2:126],2)
   p = (ph<<900)^((1<<900)-1)^((1<<300)-1)
   q = ph<<900
   for i in range(899, 300, -1):
       cur = 1<<i
       if (p ^ cur) * (q ^ cur) < n:
           p ^= cur
           q ^= cur
   
   print(f'highp = {p}')
   print(f'highq = {q}')

3. 求$p$或$q$的低300bits。

   知道了$p$或$q$高位，求其低位，于是可以用small_roots()求解了。

   highp = 170966211863977623201944075700366958395158791305775637137148430402719914596268969449870561801896130406088025694634815584789789278534177858182071449441084789053688828370314062664371344767976558822028720769455584351917211545467432347213218207146202261834961563977909337587431826932558897962855935319930935705600
   n = 29229445599118483001701466306458274418313207587536209963238059476868917454504410032112597117546615733598387274665904107870896556998881063494600049216084775281584147609749667294182462818941181246561319625259137178286553974862986352158857172427903588054746932151579636584132759169528954347728678147797597780996214188968831836400285920685337294608990778009074569367505456248478822993714411937836237079928768898433354626698856023139709607246825672149802133458391862603953992754636020632951723690379324712160511376119409228990756977864084382454893999090811914709514495628598844102290648843131526073812299407141152746828211
   c = 0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1
   e = 65537
   
   R.<x> = PolynomialRing(Zmod(n))
   f = highp+x
   x0 = f.small_roots(X=2**450,beta = 0.4)[0]#适当提高点x的范围
   p = f(x0)
   q = n//int(p)
   print(p)
   print(q)
   d = inverse_mod(e,(p-1)*(q-1))
   m = pow(c,d,n)
   print(m)

   （哦，对了！因为我写成small_roots(x = 2**450)导致报错了，但给出的报错信息是list index out of range，还以为是没有解呢。）

分析完毕，整体代码如下：

#python
import gmpy2
from Crypto.Util.number import *

e = 
n = 
c = 

ph = int(bin(gmpy2.iroot(n,2)[0])[2:126],2)#高124bits相同
p = (ph<<900)^((1<<900)-1)^((1<<300)-1)
q = ph<<900
for i in range(899, 300, -1):
    cur = 1<<i
    if (p ^ cur) * (q ^ cur) < n:
        p ^= cur
        q ^= cur

print(f'highp = {p}')
print(f'highq = {q}')
#sage
highp = 
n = 
e = 

R.<x> = PolynomialRing(Zmod(n))
f = highp+x
x0 = f.small_roots(X=2**450,beta = 0.4)[0]#适当提高点x的范围
p = f(x0)
q = n//int(p)
print(p)
print(q)
d = inverse_mod(e,(p-1)*(q-1))
m = pow(c,d,n)
print(m)
#python
print(long_to_bytes(m))
#*CTF{St.Diana_pls_take_me_with_you!}

---

参考：

https://github.com/sixstars/starctf2022