[NSSCTF 2nd]Math

原题py：

from secret import flag
from Crypto.Util.number import *
import gmpy2
 
length = len(flag)
flag1 = flag[:length//2]
flag2 = flag[length//2:]
e = 65537
 
m1 = bytes_to_long(flag1)
p = getPrime(512)
q = getPrime(512)
n = p*q
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
 
p1 = gmpy2.invert(p,q)
q1 = gmpy2.invert(q,p)
c = pow(m1,e,n)
 
print("p1=",p1)
print("q1=",q1)
print("c=",c)
print("phi=",phi)
 
"""
p1= 3020925936342826638134751865559091272992166887636010673949262570355319420768006254977586056820075450411872960532347149926398408063119965574618417289548987
q1= 4671408431692232396906683283409818749720996872112784059065890300436550189441120696235427299344866325968178729053396743472242000658751114391777274910146291
c= 25112054943247897935419483097872905208058812866572413543619256987820739973912338143408907736140292730221716259826494247791605665059462509978370784276523708331832947651238752021415405546380682507724076832547566130498713598421615793975775973104012856974241202142929158494480919115138145558312814378701754511483
phi= 57503658815924732796927268512359220093654065782651166474086873213897562591669139461637657743218269483127368502067086834142943722633173824328770582751298229218384634668803018140064093913557812104300156596305487698041934061627496715082394633864043543838906900101637618600513874001567624343801197495058260716932
"""
 
m2 = bytes_to_long(flag2)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
c = pow(m2, e, n)
hint = pow(2023 * p + 114514, q, n)
print("n=",n)
print("c=",c)
print("hint=",hint)
 
"""
n= 12775720506835890504634034278254395430943267336816473660983646973423280986156683988190224391394224069040565587173690009193979401332176772774003070053150665425296356891182224095151626957780349726980433545162004592720236315207871365869074491602494662741551613634958123374477023452496165047922053316939727488269523121920612595228860205356006298829652664878874947173274376497334009997867175453728857230796230189708744624237537460795795419731996104364946593492505600336294206922224497794285687308908233911851722675754289376914626682400586422368439122244417279745706732355332295177737063024381192630487607768783465981451061
c= 11915755246503584850391275332434803210208427722294114071001100308626307947436200730224125480063437044802693983505018296915205479746420176594816835977233647903359581826758195341201097246092133133080060014734506394659931221663322724002898147351352947871411658624516142945817233952310735792476179959957816923241946083918670905682025431311942375276709386415064702578261223172000098847340935816693603778431506315238612938066215726795441606532661443096921685386088202968978123769780506210313106183173960388498229061590976260661410212374609180449458118176113016257713595435899800372393071369403114116302366178240855961673903
hint= 3780943720055765163478806027243965253559007912583544143299490993337790800685861348603846579733509246734554644847248999634328337059584874553568080801619380770056010428956589779410205977076728450941189508972291059502282197067064652703679207594494311426932070873126291964667101759741689303119878339091991064473009603015444698156763131697516348762529243379294719509271792197450290763350043267150173332933064667716343268081089911389405010661267902446894363575630871542572200564687271311946580866369204751787686029541644463829030926902617740142434884740791338666415524172057644794094577876577760376741447161098006698524808
"""

 审计代码：

此题分为两个部分，第一部分是一道告知我们p1 = gmpy2.invert(p,q)、q1 = gmpy2.invert(q,p)、c、phi四个条件，需要我们求出p和q的值，即可使用传统的rsa将未知的m分解的部分；

求解思路如下：

详细资料可参考：

https://github.com/pcw109550/write-up/tree/master/2019/HITCON/Lost_Modulus_Again

p1 = gmpy2.invert(p,q)

q1 = gmpy2.invert(q,p)

=>

p1*p = 1 + k1*q

q1*q = 1 + k2*p

=>相减

p*(p1 + k2) = q*(q1 + k1)

由于p和q都是素数，所以(p1 + k2) 必然整除q，(q1 + k1)必然整除p，将p、q用这两个值代替

phi(n) = (p-1)*(q-1) = p*q - (p+q) + 1

=>

phi(n) = (q1 + k1 - 1)*(p1 + k2 - 1)

=(q1 - 1) * (p1 - 1) + (q1 - 1) * k1 + (p1 - 1) * k2 + k1 * k2

=>

phi(n) = q1 * p1 - 1 + (p1 - 1) * (q1 * p1 - 1) / k1 + k1 * (q1 - 1) + (q1 - 1) * (p1 - 1)
# quadratic equation f(k1) = 0
(q1 - 1) * k1 ** 2 + (q1 * p1 - 1 - phi(n) + (q1 - 1) * (p1 - 1)) * k1 + (p1 - 1) * (q1 * p1 - 1) = 0

此时我们便可以建立一个以k1为系数的一元二次方程求解：

solve：

x = 3020925936342826638134751865559091272992166887636010673949262570355319420768006254977586056820075450411872960532347149926398408063119965574618417289548987
y = 4671408431692232396906683283409818749720996872112784059065890300436550189441120696235427299344866325968178729053396743472242000658751114391777274910146291
ct = 25112054943247897935419483097872905208058812866572413543619256987820739973912338143408907736140292730221716259826494247791605665059462509978370784276523708331832947651238752021415405546380682507724076832547566130498713598421615793975775973104012856974241202142929158494480919115138145558312814378701754511483
phi = 57503658815924732796927268512359220093654065782651166474086873213897562591669139461637657743218269483127368502067086834142943722633173824328770582751298229218384634668803018140064093913557812104300156596305487698041934061627496715082394633864043543838906900101637618600513874001567624343801197495058260716932
 
from Crypto.Util.number import *
import gmpy2
e = 65537
d = inverse(e,phi)
 
def solve(a, b, c):
    D = b ** 2 - 4 * a * c
    # assert gmpy2.is_square(D)
    x1 = (-b + gmpy2.isqrt(D)) // (2 * a)
    x2 = (-b - gmpy2.isqrt(D)) // (2 * a)
    return x1, x2
 
a = x - 1
b = x * y - 1 + (x - 1) * (y - 1) - phi
c = (y - 1) * (x * y - 1)
k1, k2 = solve(a, b, c)
if (x * y - 1) % k1 == 0:
    k2 = (x * y - 1) // k1
elif (x * y - 1) % k2 == 0:
    k1, k2 = k2, (x * y - 1) // k2
else:
    assert False
 
p, q = x + k2, y + k1
N = p * q
flag1 = long_to_bytes(pow(ct, d, N)).strip()
print(flag1)

第二部分则是相似推导：

原题py：

m2 = bytes_to_long(flag2)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
c = pow(m2, e, n)
hint = pow(2023 * p + 114514, q, n)
print("n=",n)
print("c=",c)
print("hint=",hint)
 
"""
n= 12775720506835890504634034278254395430943267336816473660983646973423280986156683988190224391394224069040565587173690009193979401332176772774003070053150665425296356891182224095151626957780349726980433545162004592720236315207871365869074491602494662741551613634958123374477023452496165047922053316939727488269523121920612595228860205356006298829652664878874947173274376497334009997867175453728857230796230189708744624237537460795795419731996104364946593492505600336294206922224497794285687308908233911851722675754289376914626682400586422368439122244417279745706732355332295177737063024381192630487607768783465981451061
c= 11915755246503584850391275332434803210208427722294114071001100308626307947436200730224125480063437044802693983505018296915205479746420176594816835977233647903359581826758195341201097246092133133080060014734506394659931221663322724002898147351352947871411658624516142945817233952310735792476179959957816923241946083918670905682025431311942375276709386415064702578261223172000098847340935816693603778431506315238612938066215726795441606532661443096921685386088202968978123769780506210313106183173960388498229061590976260661410212374609180449458118176113016257713595435899800372393071369403114116302366178240855961673903
hint= 3780943720055765163478806027243965253559007912583544143299490993337790800685861348603846579733509246734554644847248999634328337059584874553568080801619380770056010428956589779410205977076728450941189508972291059502282197067064652703679207594494311426932070873126291964667101759741689303119878339091991064473009603015444698156763131697516348762529243379294719509271792197450290763350043267150173332933064667716343268081089911389405010661267902446894363575630871542572200564687271311946580866369204751787686029541644463829030926902617740142434884740791338666415524172057644794094577876577760376741447161098006698524808
"""

hint = pow(2023 * p + 114514, q, n)

=>

hint = (2023 * p + 114514)^q mod p

hint = 114514^q + k1 * p

114514^q = hint - k1*p

(114514^q)^p = (hint - k1*p)^p

114514^n = p*(.....) + hint^p

=>

114514^n = hint^p mod p = hint

所以 114514^n - hint^p，必然是p的倍数，p和q便可以求出。

solve:

nn = 12775720506835890504634034278254395430943267336816473660983646973423280986156683988190224391394224069040565587173690009193979401332176772774003070053150665425296356891182224095151626957780349726980433545162004592720236315207871365869074491602494662741551613634958123374477023452496165047922053316939727488269523121920612595228860205356006298829652664878874947173274376497334009997867175453728857230796230189708744624237537460795795419731996104364946593492505600336294206922224497794285687308908233911851722675754289376914626682400586422368439122244417279745706732355332295177737063024381192630487607768783465981451061
cc = 11915755246503584850391275332434803210208427722294114071001100308626307947436200730224125480063437044802693983505018296915205479746420176594816835977233647903359581826758195341201097246092133133080060014734506394659931221663322724002898147351352947871411658624516142945817233952310735792476179959957816923241946083918670905682025431311942375276709386415064702578261223172000098847340935816693603778431506315238612938066215726795441606532661443096921685386088202968978123769780506210313106183173960388498229061590976260661410212374609180449458118176113016257713595435899800372393071369403114116302366178240855961673903
hint = 3780943720055765163478806027243965253559007912583544143299490993337790800685861348603846579733509246734554644847248999634328337059584874553568080801619380770056010428956589779410205977076728450941189508972291059502282197067064652703679207594494311426932070873126291964667101759741689303119878339091991064473009603015444698156763131697516348762529243379294719509271792197450290763350043267150173332933064667716343268081089911389405010661267902446894363575630871542572200564687271311946580866369204751787686029541644463829030926902617740142434884740791338666415524172057644794094577876577760376741447161098006698524808
 
p = GCD(pow(114514,nn,nn) - hint,nn)
q = nn//p
D = inverse(e,(p-1)*(q-1))
flag2 = long_to_bytes(pow(cc,D,nn))
print(flag2)

将两次求解得到的flag相加即可。