RSA-详解dp泄漏

2020年10月23日 127点热度 2人点赞 2条评论

原理:

0.基本数学公式

a = kb + p

a mod b =p

1.RSA的基本公式

c \equiv m^emodn
m\equiv c^dmodn
\phi(n)=(p-1)\times(q-1)
d\times e \equiv1mod\phi (n)

2.dp是什么

dp\equiv d mod(p-1)

3.推导过程
4.求p

遍历X(65537种可能),求出(p-1),得到p且能被n整除;接下来就是常规RSA的解法

for i in range(1,65538):
    if (dp*e-1)%i == 0:
        if n%(((dp*e-1)/i)+1)==0:
            p=((dp*e-1)/i)+1
            q=n/(((dp*e-1)/i)+1)
            phi = (p-1)*(q-1)
            d = gmpy2.invert(e,phi)%phi

例题:

[WUSTCTF2020]dp_leaking_1s_very_d@angerous
题目:
e = 65537
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825
解密脚本:
import gmpy2 

e = 65537
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825

for x in range(1, e):
    if(e*dp%x==1):
        p=(e*dp-1)//x+1
        if(n%p!=0):
            continue
        q=n//p
        phin=(p-1)*(q-1)
        d=invert(e, phin)
        m=powmod(c, d, n)
        if(len(hex(m)[2:])%2==1):
            continue

        print("m:",m)
        #print(hex(m)[2:])
        print("flag:",bytes.fromhex(hex(m)[2:]))

luoluo

我爱吃螺蛳粉

文章评论

  • 🏀🤴✌😀👊

    luoluo师傅太强了,想舔

    2020年10月28日
    • 洛洛
      洛洛

      @🏀🤴✌😀👊 哇啊哦~~~~~~~

      2020年10月28日