2023 贵州大数据安全精英赛 --- Crypto childrsa wp

文章目录

- - 题目
  - 解题过程
  - 解题代码

题目

childrsa.py

from Crypto.Util.number import *flag = b'xxx'
p = getPrime(512)
q = getPrime(512)
n = p * q
P = getPrime(1024)
Q = getPrime(1024)
N = P * Q
e = 65537
gift = (P+Q) >> 400hint = (p & ((1 << 350) - 1)) >> 5
enc_hint = pow(hint,e,N)
c = pow(bytes_to_long(flag),e,n)
f = open(f'out{i+1}.txt','w')
f.write(f'N = {N}\n')
f.write(f'n = {n}\n'
f.write(f'gift = {gift}\n')
f.write(f'enc_hint = {enc_hint}\n')
f.write(f'c = {c}')

out.txt

N = 19913283586978731272870374837854045562790864804312115658302463830117436116219931849180682454814957654994095500743161455669517742683196683945049694888375426558735311269294662060482717191409995553476857418604462748567614908456839975140435522714312533340013676955820372105156740228641356206825881138276471973278761948406726062399175269553184359236859175084438349221553915085882218661560890322526503741457647907788204833926214096369428913779871365689037671018942683561649187089844083798834324075157252488088496084629641115161544547506935703532950490109236586524242732310854674446718076810611730874295399180178401471353663
n = 98394377912970161077976095071716071520245470884522650898371541866651139965831581427336428521179335097560338145643418890363050369233502530295868251106114979969844387393758147627569985743852463470545138002189902685566590889175140517151122304528973863485700142820829052897139853465497289644064298161242772703289
gift = 112012823249741273956420414320152024086394551241563686416444057368708038459572554871491781707278127933195689073127882065060125127295041489653572915729848455155059117821290550157606860744547
enc_hint = 13605762329549698957586626266580933128225639142810971158632386694900212152297364700673906983331081843360581227221052403163762155206266035280442283924005142717129467351643173282810669982201476798388553001056498736307588260706475327062302787323877507524036357644241120006072323797778327893834792299939570334886948188364597473931268889437417695532862093912649528155151390080600081199337965649892379699786628095487656690228838497716512853509768997296826487263776776447496125752546322173589223915740715451543895861668143819159937998988611022766833424669076863898157258297885102980961819003128529680884480390557024888414518
c = 73440769815335471983607426365687905918721184275652299429416892828899873930224614597826204961136670712832234285387297735959592122505613951335959593105045789810808172640134939607018894726831927984520480432707238536268054572649912957275921796939059679116900910403261478040783178268712136617053467195749630152736

解题过程

根据题目代码可知， $g i f t = (P + Q) >> 400$ ，也就是说此时我们知道P+Q的高位。
那么我们可以联立 $N = P * Q$ 构建一个方程去求解 $P_1$ ，此时解出来的 $P_1$ 高位是和P一样的，只是低400位不一样。

RF = RealField(2048)
X = polygen(RF)
f =X*((gift<<400)-X) - N
P = int(f.roots()[1][0])

然后我们在利用coppersmith定理去恢复P
PS：其实这里左移430再右移430是可以不用写的，这么写是因为我P高位解法的习惯使然，coppersmith本来就是去求差，所以直接讲解出来的 $P_1$ 带入到多项式环中求解即可。

P_high = (P<<430)>>430
PR.<x> = PolynomialRing(Zmod(N))
f1 = x + P_high
x0 =f1.small_roots(X=2^430, beta=0.4)[0]
P1 = P_high+x0

求出P之后，后面就简单了。
先简单RSA解密解出hint，之后由于hint = (p & ((1 << 350) - 1)) >> 5，可知其为p的低350位再右移了5位，也就是说解出来的hint是p的低345位并且损失了低5位
这个时候思路就非常明了哩：
直接爆破低5bit，然后利用已知p的低位泄露coppersmith还原p，最后解密即可得到flag

解题代码

#sage
import gmpy2
from Crypto.Util.number import *gift = 112012823249741273956420414320152024086394551241563686416444057368708038459572554871491781707278127933195689073127882065060125127295041489653572915729848455155059117821290550157606860744547
N = 19913283586978731272870374837854045562790864804312115658302463830117436116219931849180682454814957654994095500743161455669517742683196683945049694888375426558735311269294662060482717191409995553476857418604462748567614908456839975140435522714312533340013676955820372105156740228641356206825881138276471973278761948406726062399175269553184359236859175084438349221553915085882218661560890322526503741457647907788204833926214096369428913779871365689037671018942683561649187089844083798834324075157252488088496084629641115161544547506935703532950490109236586524242732310854674446718076810611730874295399180178401471353663
enc_hint = 13605762329549698957586626266580933128225639142810971158632386694900212152297364700673906983331081843360581227221052403163762155206266035280442283924005142717129467351643173282810669982201476798388553001056498736307588260706475327062302787323877507524036357644241120006072323797778327893834792299939570334886948188364597473931268889437417695532862093912649528155151390080600081199337965649892379699786628095487656690228838497716512853509768997296826487263776776447496125752546322173589223915740715451543895861668143819159937998988611022766833424669076863898157258297885102980961819003128529680884480390557024888414518
n = 98394377912970161077976095071716071520245470884522650898371541866651139965831581427336428521179335097560338145643418890363050369233502530295868251106114979969844387393758147627569985743852463470545138002189902685566590889175140517151122304528973863485700142820829052897139853465497289644064298161242772703289
c = 73440769815335471983607426365687905918721184275652299429416892828899873930224614597826204961136670712832234285387297735959592122505613951335959593105045789810808172640134939607018894726831927984520480432707238536268054572649912957275921796939059679116900910403261478040783178268712136617053467195749630152736
e = 65537
RF = RealField(2048)
X = polygen(RF)
f =X*((gift<<400)-X) - N
P = int(f.roots()[1][0])
P_high = (P<<430)>>430
PR.<x> = PolynomialRing(Zmod(N))
f1 = x + P_high
x0 =f1.small_roots(X=2^430, beta=0.4)[0]
P1 = P_high+x0
print(f"P = {P1}")
Q =N//int(P1)
print(f"Q = {Q}")
phi = (P1-1)*(Q-1)
d = gmpy2.invert(e,gmpy2.mpz(phi))
hint = pow(enc_hint,d,N)
print(f"hint = {hint}")
hint = hint<<5
for i in range(2**5):try:p_low = hint+iPR.<x> = PolynomialRing(Zmod(n))f = x*2^350+p_lowroots = f.monic().small_roots(X=2^162, beta=0.4)if roots:print(roots[0])p =  int(f(roots[0]))breakexcept:pass
print(f"p = {p}")
q = n//p
print(f"q = {q}")
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(int(m))
print(flag)