电脑疯子技术论坛|电脑极客社区

微信扫一扫 分享朋友圈

已有 527 人浏览分享

Forming密码学笔记----rsa中dp泄露及共模攻击

[复制链接]
527 0
【0】扩展欧几里得算法分析

(1)举例说明:

QQ截图20220517150409.png

(2)推导:

QQ截图20220517150443.png

【1】dp泄露

(1)概述:遍历1到e的值除e*dp-1能整除的数进行排除最后得到符合结果的p最终求解m。

(2)原理分析:

30.png

(3)代码举例(buu中rsa2):
  1. def buu_rsa2():
  2. p = 0
  3. e = 65537
  4. dp = 90507449805234690464302513287951833069192517457305400462187725331868267505
  5. 5421970943552016695528560364834446303196939207056642927148093290374440210503657
  6. c = 140423670976252696807533673586209400575664282100684119784203527124521188996
  7. 403826597436883766041879067494280957410201958935737360380801845453829293997433
  8. 414188838725751796261702622028587211560353362847191060306578510511380965162133
  9. 472698713063592621028959167072781482562673683090590521214218071160287665180751
  10. n = 482540078515262411777215266989018029858327661762216096122588773716205800604
  11. 331015383280303052199186976436198142009306796121098855338013353484450237516704
  12. 784370730555447242806847332980515991676603036451831461614974853586336814921296
  13. 68802402065797789905550489547645118787266601929429724133167768465309665906113
  14. # 2482540078515262411777215266989018029858327661762216096122588773716205800604
  15. 33101538328030305219918697643619814200930679612109885533801335348445023751670
  16. 4784370730555447242806847332980515991676603036451831461614974853586336814921
  17. 29668802402065797789905550489547645118787266601929429724133167768465309665906113
  18. temp=dp*e - 1
  19. for i in range(2,e) :
  20. if temp%i==0:
  21. p=temp//i+1
  22. q=n//p
  23. d=gmpy2.invert(e,(p-1)*(q-1))
  24. m=pow(c,d,n)
  25. print(m)
  26. # p = 9131277787351507734046081087074153364207684872918955079496908750249619987239
  27. 21084218161740762247806472238721460807860416768595691382327159766463278002713
  28. # 之后复制m的值调用binascii.a2b_hex()方法进行十六进制编码
  29. # m = 19868425343295459619334578479373466514930233617506599264000238874830707180236956147
  30. 9775356746782694904065947170519261584314403457835655705269315447475440706251964502468599
  31. 6391009016592657813240599900232631542378107041310868534490735688460313428297403655877887
  32. 03247933638196834034686786623463634700146737869245
  33. # 这个函数或许因为vscode上插件的原因对n赋正确的值之后会报错,所以要放到cmd中去跑,上面就是m的值
复制代码

【2】共模攻击

(1)概述:用扩展欧几里得算法求得m^(gcd(e1,e2))最后解密。

(2)原理分析:

26.png

22.png

共模问题的通式就是最后推到的形式,e1,e2互质可以看作是通式的一种特殊情况。

(3)代码举例(buu上rsa3):
  1. def buu_rsa3():
  2. s1 = 1
  3. s2 = 1
  4. c1 = 5
  5. # c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956
  6. 2628696408224864701211494244855713610074212936755163388221952803137949911360481409
  7. 1884247121984026353633888625049268273943641001343665116172072585548486669008478872
  8. 1349555662019879081501113222996123305533009325964377798892703161521852805956811219
  9. 5638833128963301562986216746843539195475581279209257068428089147621990110549558165
  10. 3497767526739500957534782038707348392842506653636148277489237096952074030428745655
  11. 5508933372782327506569010772537497541764311429052216291198932092617792645253901478
  12. 910801592878203564861118912045464959832566051361
  13. n = 2
  14. # n = 2270807881588501146246204906433918589871243927722683107345788840312937854735029
  15. 242026701655181905243077900475584664904400102414148528328648313070261605727469847361
  16. 114950879886970634750193158311763271070078722801648012767739364992953041659868602735
  17. 421642256593445901516192761360790283154285797785961259628235367932777330372700440726
  18. 219723158632459918198357262240459035408454178806226216451014060586812241038809017442
  19. 014775240855412978976090230089804627390900785281847403077069964764736301510211895673
  20. 767394135421769269604496969530850643657314256557348758350703735694484803986438233921
  21. 6266670673567488871508925311154801
  22. e1 = 11187289
  23. c2 = 1
  24. # c2 = 1870201004518701555654869164239498283566926214723021273130993867522645855521042
  25. 597242941844927341053538798593103671185426562390506680566575180326910688074676900347
  26. 890079109959023951392544974881407590401747158557284847355649056545006266470644912841
  27. 583478796194726625978978596292223870113407972041422841406619307149530461234105298745
  28. 561593002353682380149926977335718608745274750084064041936501155442118303750565346128
  29. 673274098370274082267114804561949766718458612365728560406187565390956782232891406533
  30. 779773344464035151877548764981997826236361726579798284317963088872940723849665098772
  31. 0428708217115257989007867331698397
  32. e2 = 9647291
  33. temp1 = gmpy2.powmod(c1,s1,0)
  34. temp2 = gmpy2.powmod(c2,s2,0)
  35. m = gmpy2.powmod(temp1*temp2,1,n)
  36. m = gmpy2.iroot(m,gcd(e1,e2))
  37. print(m)
  38. # 直接将m复制下来十进制换十六进制放到binascii.a2b_hex()方法中对其十六进制解码
  39. # 与rsa2一样因为vscode插件的原因要放到cmd命令行中执行才行,代码要合理转换
复制代码

您需要登录后才可以回帖 登录 | 注册

本版积分规则

1

关注

0

粉丝

9021

主题
精彩推荐
热门资讯
网友晒图
图文推荐

Powered by Pcgho! X3.4

© 2008-2022 Pcgho Inc.