来自starctf2022的
ezRSA
源码：
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))
#0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
print(hex(c))
#0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1
通过分析知道应该是从这一行入手：
q=next_prime(p^((1<<900)-1)^getrandbits(300))
p与后面的部分异或产生的效果就是，q的高124位部分与p相同，q的中间600位部分与p相反，q的低300位部分是p的低300位部分与随机的300位的数异或。
由此可见，p、q低900位不同，可以说p、q是相近的，因为都是大整数。
接下来从高位到低位的顺序求p、q。
1、高124位
因为p、q相近且都是大整数，故直接对n开方，其结果的高124位部分大概率与p相同（同样也与q相同）。一开始我想着检验一下：
p = getPrime(1024)
q = next_prime(p ^ ((1<<900)-1) ^ random.getrandbits(300))
n = p*q
x = iroot(n,2)[0]
def get_num(s1, s2):
num = 0
len_s1 = len(s1)
list_s1 = []
for i in range(len_s1):
two_s1 = s1[0:i+1]
list_s1.append(two_s1)
for i in list_s1:
if s2.startswith(i) and len(i) > num:
num = len(i)
return num
x1 = str(bin(p))[2:]
x2 = str(bin(x))[2:]
x = get_num(x1,x2)
print(x)
#124 or 125
相同的位数果然就是124位，也有125位的情况。
2、中间600位
令p的低900位最大，即全为1，q的低900位最小，即全为0，保证了中间600位部分相反，接着对p、q中间600位部分逐位与1异或，并计算相乘的值与n的大小，比n小就更新p、q的值，让p增大，q减小。
c = 0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
ph = int(bin(iroot(n,2)[0])[2:126],2)
p_high = (ph<<900)^((1<<900)-1)^((1<<300)-1)
#中间600位为1，低300位为0
q_high = ph<<900
for i in range(899, 300, -1):
cur = 1<<i
if (p_high ^ cur) * (q_high ^ cur) < n:
p_high ^= cur
q_high ^= cur
print(p_high)
print(q_high)
3、低300位
知道p的高位，采用copperSmith攻击得到完整p即可：
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
e = 65537
p4 = 170966211863977623201944075700366958395158791305775637137148430402719914596268969449870561801896130406088025694634815584789789278534177858182071449441084789053688828370314062664371344767976558822028720769455584351917211545467432347213218207146202261834961563977909337587431826932558897962855935319930935705600
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^450, beta=0.4)
p = p4+int(roots[0])
print(n)
print(p)
print(n//p)
最后就是常规思路解rsa了。
中间600位的方法还不太理解，有待加深学习，放下参考过的大佬们的博客：
starctf2022 - gla2xy’s blog (gal2xy.github.io)
starCTF2022 Writeup by or4nge (or4ngesec.github.io)
官方wp：
starctf2022/exp.sage at main · sixstars/starctf2022 (github.com)
鹤城杯2021–babyrsa
源码：
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 724
hint2 = q % (2 ** 265)
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)
#1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
#40812438243894343296354573724131194431453023461572200856406939246297219541329623
#21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
#19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
有这两行：hint1 = p >> 724、hint2 = q % ($2^{256}$)
知道了p的高300位和q的低265位，之前提到了对于1024位的p或q，未知的位数不能超过454位，这里显然超过了，所以需要想办法通过已知的q的低位来推出p的低位来，推导如下：
$n = p \times q = p \times (q_{high}+q_{low}) = p \times (k \times 2^{265}+q \space mod \space 2^{265})$
$等式两侧同模2^{265},得到：$
$n_{low} \equiv p \times q_{low}(mod \space 2^{256})$
$p \space mod \space 2^{265} \equiv n_{low} \times q_{low}^{-1}(mod \space 2^{265})$
$p_{low} \equiv n_{low} \times q_{low}^{-1}(\space mod \space 2^{265})$
这样一来，未知的位数减小到459位，剩下的5位爆破即可，代码如下：
p_high = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q_low = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
e = 65537
c = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
mod = pow(2,265)
p0 = n * inverse_mod(q_low,mod) % mod
pbar = (p_high << 724) + p0
PR.<x> = PolynomialRing(Zmod(n))
for i in range(32):
f = pbar + x * 32 * mod
f = f.monic()
roots = f.small_roots(2^454,0.4)
if roots:
print(i)
break
pbar += mod
p = pbar + roots[0] * 32 * mod
print(p)
#19
#133637329398256221348922087205912367118213472434713498908220867690672019569057789598459580146410501473689139466275052698529257254973211963162087316149628000798221014338373126500646873612341158676084318494058522014519669302359038980726479317742766438142835169562422371156257894374341629012755597863752154328407
有几处不是很理解：
$f = pbar + x \times 32 \times mod pbar += mod、p = pbar + roots[0] \times 32 \times mod。$
另一种方法，也是参考的大佬的，但解出来的p是错的？：
p_high = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q_low = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
enc = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
e = 65537
mod = pow(2,265)
p0 = n * inverse_mod(q_low,mod) % mod
PR.<x> = PolynomialRing(Zmod(n))
for i in range(2**5):
f = p_high * (2^724) + p0 + (x * 32 + i) * mod
f = f.monic()
out_p = f.small_roots(2^454,0.4)
if len(out_p) != 0:
print(out_p[0])
break
p = out_p[0] * 32 + i * mod + p_high * (2^724) + p0
print(p)
与上一种方法不同之处在：$f = p_high \times (2^724) + p0 + (x \times 32 + i) \times modp = out_p[0] \times 32 + i \times mod + p_high \times (2^724) + p0$，本质应该都是一样的，就是不知道为什么求出的p不对，折磨了我好久😓。
p出了就是常规rsa求解了。
不理解的地方暂时放着。
参考：
鹤城杯 Writeup-安全客 - 安全资讯平台 (anquanke.com)
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com