[鹤城杯 2021]BabyRSA

题目：

from Crypto.Util.number import getPrime, bytes_to_long
from secret import flagp = 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)hint1= 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
hint2= 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n= 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
ct= 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188

解题分析：
因此根据题目中给出的p高300位和q低265位，n=pq  =>  n=p0q0(mod 2265)可得p低265位 p0=nq0-1(mod 2265)
题目中q0= q%(2265)=hint2  =>  q0-1= inverse_mod(q0,2265)
则p低265位p0=n*inverse_mod(q0,2265)(mod 2265)
则p的高300位和低265位之和为:
pbar=ph+pl=(p1<<724) + n*inverse_mod(q0,2265)(mod 2265)
p中间的459位通过copperSmith求解
由于构造f=pbar+x*2265无解，尝试对2265抬高2^6(即抬高64)进行爆破
则 f需要加上i*2265,其中i in range(64)
所以在copperSmith构造中，f表达式中间项为x*64*2265,对应small_roots参数X=2453

sage:

#sage
p1 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q0 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
p0=n*invert(q0,2^265)%(2^265)
pbar=(p1<<724)+p0PR.<x> = PolynomialRing(Zmod(n))
for i in range(64):f=pbar+x*(2^265)*64 + i*(2^265)f=f.monic()pp=f.small_roots(X=2^453,beta=0.4)if(pp):print("pp[0]=",pp[0])print("i=",i)breakp=pbar+pp[0]*64*(2^265)+ i*(2^265)
print("p=",p)

python:

#python
from Cryptodome.Util.number import *
import libnum
from gmpy2 import gmpy2hint1 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
hint2 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
ct = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
e = 65537
p=133637329398256221348922087205912367118213472434713498908220867690672019569057789598459580146410501473689139466275052698529257254973211963162087316149628000798221014338373126500646873612341158676084318494058522014519669302359038980726479317742766438142835169562422371156257894374341629012755597863752154328407
q=n//p
phi_n=(p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
m = pow(ct,d,n)
print(long_to_bytes(m))