[HDCTF 2023]Normal_Rsa(revenge)

1.题目

from Crypto.Util.number import *
#from shin import flagm=bytes_to_long(b'HDCTF{******}')
e=65537
p=getPrime(256)
q=getPrime(512)
r=getPrime(512)
n=p*q*r
P=pow(p,2,n)
Q=pow(q,2,n)
c=pow(m,e,n)
print(f"P = {P}")
print(f"Q = {Q}")
print(f"n = {n}")
print(f"c = {c}")
'''
P = 8760210374362848654680470219309962250697808334943036049450523139299289451311563307524647192830909610600414977679146980314602124963105772780782771611415961
Q = 112922164039059900199889201785103245191294292153751065719557417134111270255457254419542226991791126571932603494783040069250074265447784962930254787907978286600866688977261723388531394128477338117384319760669476853506179783674957791710109694089037373611516089267817074863685247440204926676748540110584172821401
n = 12260605124589736699896772236316146708681543140877060257859757789407603137409427771651536724218984023652680193208019939451539427781667333168267801603484921516526297136507792965087544395912271944257535087877112172195116066600141520444466165090654943192437314974202605817650874838887065260835145310202223862370942385079960284761150198033810408432423049423155161537072427702512211122538749
c = 7072137651389218220368861685871400051412849006784353415843217734634414633151439071501997728907026771187082554241548140511778339825678295970901188560688120351732774013575439738988314665372544333857252548895896968938603508567509519521067106462947341820462381584577074292318137318996958312889307024181925808817792124688476198837079551204388055776209441429996815747449815546163371300963785
'''

2.思路

已知：
P=pow(p,2,n)
Q=pow(q,2,n)
n=p*q*r

P=p^2%n
Q=q^2%n
=>p^2=P%n  =>p^2-P=0%n
意思就是 p² - P是 n的倍数
p² - P = k * n

=>q^2=Q%n  =>q^2-Q=0%n
即 q² - Q也是 n的倍数
q² - Q = k * n

对于p² - P = k * n,
由p=getPrime(256)，p是256位，p^2是512位，n则更大，所以k只能取唯一值0
p^2=P
同理得出q^2=Q

这两个条件足够得出p和q了，那么r = n // (p * q)，求出他们的欧拉函数phi=（p-1）*（q-1）*（r-1）
后面就迎刃而解了

3.脚本

import libnum
e=65537
P = 8760210374362848654680470219309962250697808334943036049450523139299289451311563307524647192830909610600414977679146980314602124963105772780782771611415961
Q = 112922164039059900199889201785103245191294292153751065719557417134111270255457254419542226991791126571932603494783040069250074265447784962930254787907978286600866688977261723388531394128477338117384319760669476853506179783674957791710109694089037373611516089267817074863685247440204926676748540110584172821401
n = 12260605124589736699896772236316146708681543140877060257859757789407603137409427771651536724218984023652680193208019939451539427781667333168267801603484921516526297136507792965087544395912271944257535087877112172195116066600141520444466165090654943192437314974202605817650874838887065260835145310202223862370942385079960284761150198033810408432423049423155161537072427702512211122538749
c = 7072137651389218220368861685871400051412849006784353415843217734634414633151439071501997728907026771187082554241548140511778339825678295970901188560688120351732774013575439738988314665372544333857252548895896968938603508567509519521067106462947341820462381584577074292318137318996958312889307024181925808817792124688476198837079551204388055776209441429996815747449815546163371300963785
#计算p和q的整数平方根并验证一下
p=libnum.nroot(P, 2)
q=libnum.nroot(Q,2)
assert p * p == P and q * q == Q
#由n=pqr,求出r并验证
r=n//(p*q)
assert p * q * r == n
#求欧拉函数
phi=(p-1)*(q-1)*(r-1)
#求私钥d
d=libnum.invmod(e,phi)
m=pow(c,d,n)
flag=libnum.n2s(m)
print(flag)
#b'HDCTF{08c66aa2-f8ea-49a2-a84f-ab9c7999ebb2}'

（我建议这种推导类的最好验证一下防止出错）