Part1
\because p1\equiv p^{-1} \mod q
q1\equiv q^{-1} \mod p
\therefore p\cdot p1 \equiv 1 \mod q
q\cdot q1 \equiv 1 \mod p
\therefore p\cdot p1 = 1+k1\cdot q
q\cdot q1 = 1+k2\cdot p
\therefore p\cdot p1-1 =k1\cdot q
q\cdot q1-1=k2\cdot p
ps1：这里首先已知0<p1<q,0<q1<p，因此有k1\cdot q<pq,k2\cdot p<pq，则有k1<p,k2<q
(1)证明k1=p-q1,k2=q-p1
两式相减，得到
p\cdot p1 -q\cdot q1 = k1\cdot q - k2\cdot p
化简得
(p1+k2)\cdot p = (q1+k1)\cdot q
分析，由于p,q肯定是互质的，若要满足该等式，必然有p整除q1+k1，q整除p1+k2
再由前面ps1的结论可知，0<q1+k1<2\cdot p,0<p1+k2<2\cdot q
\therefore q1+k1=p,p1+k2=q
即k1=p-q1,k2=q-p1
(2)证明p1q1-k1k2=1
pq\cdot p1q1-pp1-qq1+1=k1k2\cdot pq
变换得(p1\cdot q1 - k1\cdot k2)\cdot pq=pp1+qq1-1
\because p1<q,q1<p
\therefore 0<(p1q1-k1k2)\cdot pq <2\cdot pq
\therefore p1q1-k1k2=1
(3)构造二次方程求k
phi=(p-1)\cdot (q-1)
=(q1+k1-1)\cdot (p1+k2-1)
=(q1-1+k1)\cdot (p1-1+k2)
=(q1-1)\cdot (p1-1)+k1\cdot (p1-1)+k2\cdot (q1-1)+k1k2
=(q1-1)\cdot (p1-1)+k1\cdot (p1-1)+\frac{p1q1-1}{k1}\cdot (q1-1)+p1q1-1
移项得
(q1-1)\cdot (p1-1)+k1\cdot (p1-1)+\frac{p1q1-1}{k1}\cdot (q1-1)+p1q1-1-phi=0
变换成关于k1的一元二次方程
(p1-1)\cdot k1^2+[(q1-1)\cdot (p1-1)+p1q1-phi-1]\cdot k1+(p1q1-1)(q1-1)=0
之后解方程得到整数k1,k2，再代入便可以计算出p,q，之后便可以解出n,d，直接解密得到flag
Part2
\because hint\equiv (2023p+114514)^q \mod n
\therefore hint\equiv 114514^q \mod p
由费马小定理得a^p\equiv a \mod p
\therefore hint \equiv 114514^{pq}\mod p
\therefore hint-114514^n=kp
\therefore p=gcd(n,hint-114514^n)
exp
import gmpy2
from Crypto.Util.number import long_to_bytes, bytes_to_long
#part1
p1= 3020925936342826638134751865559091272992166887636010673949262570355319420768006254977586056820075450411872960532347149926398408063119965574618417289548987
q1= 4671408431692232396906683283409818749720996872112784059065890300436550189441120696235427299344866325968178729053396743472242000658751114391777274910146291
cipher= 25112054943247897935419483097872905208058812866572413543619256987820739973912338143408907736140292730221716259826494247791605665059462509978370784276523708331832947651238752021415405546380682507724076832547566130498713598421615793975775973104012856974241202142929158494480919115138145558312814378701754511483
phi= 57503658815924732796927268512359220093654065782651166474086873213897562591669139461637657743218269483127368502067086834142943722633173824328770582751298229218384634668803018140064093913557812104300156596305487698041934061627496715082394633864043543838906900101637618600513874001567624343801197495058260716932
e = 65537
d = gmpy2.invert(e, phi)
def solve(a,b,c):
delta = b*b - 4*a*c
if delta < 0:
return None
sqrt_delta = gmpy2.iroot(delta,2)[0]
k1 = (-b + sqrt_delta) // (2*a)
k2 = (-b - sqrt_delta) // (2*a)
return k1, k2
a = p1-1
b = (q1-1)*(p1-1)+p1*q1-phi-1
c = (p1*q1-1)*(q1-1)
k1,k2 = solve(a,b,c)
if (p1*q1-1) % k1 == 0:
k2 = (p1*q1-1) // k1
elif (p1*q1-1) % k2 == 0:
k1,k2= k2,(p1*q1-1) // k2
#print(k1,k2)
"""
#保留正数解
k_candidates = [k for k in (k1, k2) if k > 0 and (p1 * q1 - 1) % k == 0]
if not k_candidates:
print("No valid k found")
exit()
k1 = k_candidates[0]
k2 = (p1 * q1 - 1) // k1
print(k1,k2)
"""
p =q1+k1
q =p1+k2
n = p * q
m1 = pow(cipher, d, n)
ans1 = long_to_bytes(m1)
print(ans1)
#part2
n= 12775720506835890504634034278254395430943267336816473660983646973423280986156683988190224391394224069040565587173690009193979401332176772774003070053150665425296356891182224095151626957780349726980433545162004592720236315207871365869074491602494662741551613634958123374477023452496165047922053316939727488269523121920612595228860205356006298829652664878874947173274376497334009997867175453728857230796230189708744624237537460795795419731996104364946593492505600336294206922224497794285687308908233911851722675754289376914626682400586422368439122244417279745706732355332295177737063024381192630487607768783465981451061
cipher= 11915755246503584850391275332434803210208427722294114071001100308626307947436200730224125480063437044802693983505018296915205479746420176594816835977233647903359581826758195341201097246092133133080060014734506394659931221663322724002898147351352947871411658624516142945817233952310735792476179959957816923241946083918670905682025431311942375276709386415064702578261223172000098847340935816693603778431506315238612938066215726795441606532661443096921685386088202968978123769780506210313106183173960388498229061590976260661410212374609180449458118176113016257713595435899800372393071369403114116302366178240855961673903
hint= 3780943720055765163478806027243965253559007912583544143299490993337790800685861348603846579733509246734554644847248999634328337059584874553568080801619380770056010428956589779410205977076728450941189508972291059502282197067064652703679207594494311426932070873126291964667101759741689303119878339091991064473009603015444698156763131697516348762529243379294719509271792197450290763350043267150173332933064667716343268081089911389405010661267902446894363575630871542572200564687271311946580866369204751787686029541644463829030926902617740142434884740791338666415524172057644794094577876577760376741447161098006698524808
p = gmpy2.gcd(n, pow(114514,n,n)-hint )
q = n // p
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m2 = pow(cipher, d, n)
ans2 = long_to_bytes(m2)
print(ans2)
print(ans1 + ans2)