Contents

buuctf-rsa1

题目:

1
2
3
4
5
6
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

已知 dq,dp,q,p,c,求 m ,一个中国剩余定理扩展的题,原理咱也不太懂,用就完事了

证明过程:

已知: d = dp mod (p-1) d = dq mod (q-1) 令: m1 = cd mod p m2 = cd mod q 有:cd = kp + m1 故:m2 = ( kp + m1 )mod q –> m2 - m1 = k*p mod q

取 p 逆模 : ( m2 - m1 ) * p-1 = k mod q

k = ( m2 - m1 ) * p-1 mod q —-> k = ( k1 * q + [ ( m2 - m1 ) * p-1 mod q ] ) cd = k*p + m1 cd = ( k1 * q + [ ( m2 - m1 ) * p-1 mod q ] ) * p + m1 cd = k1 * q *p + [ ( m2 - m1 ) * p-1 mod q ] * p + m1

m = cd mod n = { k1 * q p + [ ( m2 - m1 ) * p-1 mod q ] * p + m1 } mod n (n = pq)

故:m = { [ ( m2 - m1 ) * p-1 mod q ] * p + m1 } mod n —— ①

d = k*( p-1 ) + dp

故:cd = ck*( p-1 ) + dp

m1 = cd mod p = ck*( p-1 ) + dp mod p

由于 费马小定理 :

m1 = c dp mod p

同理 :m2 = c dq mod q

exp:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
import libnum 
import Crypto.Util.number
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

invq=libnum.invmod(p,q)
mp=pow(c,dp,p)
mq=pow(c,dq,q)
m=((mp-mq)*invq%p)*q+mq
print(libnum.n2s(m))
#noxCTF{W31c0m3_70_Ch1n470wn}

证明过程用了模运算的一些特性,掌握模运算性质的话还是比较简单的。。。。