BUU刷题日记20221020

RSA1

给定dp、dq类型

dp ≡ d mod (p-1)

dq ≡ d mod (q-1)

m ≡ c^d mod n

m = c^d + k * n

m = c^d +k * p * q

对上式两端同时对p、q分别取余，得：（中国剩余定理）

m1 ≡ c^d mod p

m2 ≡ c^d mod q

同理，可得到 c^d = m1 +k * p

代入到 m2 ≡ c^d mod q 中：

m2 ≡ (m1 + k * p)mod q ，两端减去m1得

m2 - m1 ≡ k * p mod q ，两端乘p的逆元得

(m2 - m1)p^-1 ≡ k mod q

将k代入到 c^d = m1 +k * p 中得：

c^d = m1 + ((m2 - m1)p^-1 mod q) * p

m=c^d mod n

得到

m ≡ (((m2 - m1) * p^-1 mod q) * p + m1) mod n

接下来就是求解m1，m2

m1 ≡ c^dp+k(p-1) mod p

m2 ≡ c^dq+k(q-1) mod q

根据费马小定理

若p是素数，则a^(p-1) ≡ 1 mod p

因此 m1 ≡ c^dp mod p，m2 ≡ c^dq mod q

最终可求得m

exp

import gmpy2
from Crypto.Util.number import long_to_bytes
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
m1=pow(c,dp,p)
m2=pow(c,dq,q)
n=p*q
p0=gmpy2.invert(p,q)
m=(((m2-m1)*p0 % q)* p +m1)%n
print(long_to_bytes(m))
#noxCTF{W31c0m3_70_Ch1n470wn}

RSAROLL

RSA roll！roll！roll！
Only number and a-z
（don't use editor
which MS provide）

给了一个data.txt文件，打开盲猜一下第一行是n，e，后面是c

import gmpy2
from Crypto.Util.number import long_to_bytes
n = 920139713
e = 19
p=18443
q=49891
phi =(p-1)*(q-1)
d=gmpy2.invert(e,phi)
c=[704796792,752211152,274704164,18414022,368270835,483295235,263072905,459788476,483295235,459788476,663551792,475206804,459788476,428313374,475206804,459788476,425392137,704796792,458265677,341524652,483295235,534149509,425392137,428313374,425392137,341524652,458265677,263072905,483295235,828509797,341524652,425392137,475206804,428313374,483295235,475206804,459788476,306220148,
]
m=[]
flag=b''
for i in range (len(c)):
    m.append(pow(c[i],d,n))
    flag+=long_to_bytes(m[i])
print(flag)
#flag{13212je2ue28fy71w8u87y31r78eu1e2}