跳转至

[羊城杯 2021]Bigrsa

  1. 共享素数 $n_1 n_2$有一素数公因数$p$ $n_1=pq_1 n_2=pq_2$ $d_1e\equiv 1\space mod\space\varphi(n_1)$ $d_2e\equiv 1\space mod\space\varphi(n_2)$ $\therefore 只需要逆元求出\frac{1}{e}\space mod\space \varphi(n_1)和\frac{1}{e}\space mod\space \varphi(n_2)就可以得到d_1和d_2$
  2. exp
from gmpy2 import *
from Crypto.Util.number import *

n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264
p = gmpy2.gcd(n1, n2)
q1, q2 = n1//p, n2//p
phi_n1, phi_n2 = (p-1)*(q1-1), (p-1)*(q2-1)
d1, d2 = inverse(e, phi_n1), inverse(e, phi_n2)

m = pow(pow(c, d2, n2), d1, n1)
print(long_to_bytes(m).decode())

评论