CTF中RSA的一些攻击思路

收集了一些RSA的攻击脚本,并将其中一部分用python3重构

参考文章:

https://www.tr0y.wang/2017/11/06/CTFRSA/index.html

http://inaz2.hatenablog.com/entry/2016/01/20/022936

关于RSA算法

RSA加密算法是一种非对称加密算法，1977年由Ron Rivest、Adi Shamir和Leonard Adleman一起提出的，算法安全性依赖于极大整数做因数分解的难度

RSA算法加解密实现

1.随意选择两个大素数p和q，且p不等于q，计算N=p***q

2.计算n的欧拉函数φ(n) = (p-1)(q-1)（常用phi(n)表示φ(n)）

3.选择一个整数e，满足1< e < φ(n)，且e与φ(n) 互质（e通常取65537）

4.计算模反元素d，ed ≡ 1 (mod φ(n)) 即求解ex + φ(n)y = 1方程组（利用扩展欧几里得算法可以求出d）

1	d = gmpy2.invert(e, (p-1)*(q-1))

5.得到公钥（N，e）私钥（N，d）

6.加密 > c 为密文，m 为明文，则加密过程如下：

c = pow(m,e,N)
$$
c\equiv m^e,mod,n
$$
7.解密 > m = pow(c,d,N)
$$
m\equiv m^d,mod,n
$$

N的分解

介绍

素数分解问题是困难的，但是可以通过计算机进行暴力分解。通常意义上来说，一般认为 2048bit 以上的 n 是安全的。现在一般的公钥证书都是 4096bit 的证书

如果 n 比较小，那么可以通过工具进行直接 n 分解，从而得到私钥。如果 n 的大小小于 256bit，那么我们通过本地工具即可爆破成功。例如采用 windows 平台的 RSATool 2v17，可以在几分钟内完成 256bit 的 n 的分解。

如果 n 在 768bit 或者更高，可以尝试使用一些在线的 n 分解网站，这些网站会存储一些已经分解成功的 n:

factordb

通过在此类网站上查询 n，如果可以分解或者之前分解成功过，那么可以直接得到 p 和 q。然后利用前述方法求解得到密文。

利用公约数分解N

如果在两次公钥的加密过程中使用的 n1 和 n2 具有相同的素因子，那么可以利用欧几里得算法直接将 n1 和 n2 分解。通过欧几里得算法可以直接求出 n1 和 n2 的最大公约数 p:

(n1,n2)=p

可以得出：

n1=pq1
n2=pq2
而欧几里得算法的时间复杂度为：O(log n)。即便是 4096 bit 也是 1s

例题

n1 = 9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327
n2 = 13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743
分解以上 2 个 n

import gmpy2
n1 = 9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327
n2 = 13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743
p = gmpy2.gcd(n1, n2)
print 'gcd(n1, n2):\n', p
q1 = n1 / p
q2 = n2 / p
print 'q1 is:\n', q1
print 'q2 is:\n', q2

大数分解算法

针对大整数的分解有很多种算法，性能上各有优异，有 Fermat 方法，Pollard rho 方法，Pollard rho p-1 方法，试除法，以及椭圆曲线法，连分数法，二次筛选法，数域分析法等等
(有很多种方法，不同的方法适应的情况不一样。比如 Fermat 适用于 p q 相差不大的时候，Pollard rho 适用相差较大的时候)

在 p，q 的取值差异过大，或者 p，q 的取值过于相近的时候，Format 方法与 Pollard rho 方法都可以很快将 n 分解成功。

此类分解方法有一个开源项目 yafu 将其自动化实现了，不论 n 的大小，只要 p 和 q 存在相差过大或者过近时，都可以通过 yafu 很快地分解成功

mark

例题

n = 0x4333AF6B43F36028D8D9650EC3EED3238541EE5C15E626C58C9EC33674A6D08D5B1F2580A1A0B07E9D853536CD994E197889D122701A62BB2A9E79559F3D5281014535F6C54F83CA8D9700EEB67D99AF318D20A5150AD46D622A6A12DE0A758EE7DF75F5D10F2FE2585F2348537787063321FFDAC91BB3C3D1D88CBD04A824ED

使用 yafu 或者自己实现一下也不难(Pollard rho)

from random import randint
from gmpy2 import *
n = 0x4333AF6B43F36028D8D9650EC3EED3238541EE5C15E626C58C9EC33674A6D08D5B1F2580A1A0B07E9D853536CD994E197889D122701A62BB2A9E79559F3D5281014535F6C54F83CA8D9700EEB67D99AF318D20A5150AD46D622A6A12DE0A758EE7DF75F5D10F2FE2585F2348537787063321FFDAC91BB3C3D1D88CBD04A824ED
x2 = 1
c = 7
while 1:
    x1 = randint(1, n)
    x2 = pow(x2,2,n)+c%n
    fac = gcd(abs(x1-x2),n)
    if fac>1 and is_prime(fac):
        print fac
        break
print n/fac

[+]Factorizing...
    [-] 61
    [-] 773619275532336166780131034131537047698382905406699459738433912728814690826971077672213458922591659515422213659384429825869636190931438071752760069044720849251021757447451724245843949904731556928399535652826184559462738196560605850834849524266612351125462326539046145850265061707227031895088845938578346609
[!]Timer
   [-] 9.53054374318e-05 s
[!]All Done!

Pollard rho p-1

from gmpy2 import *
def PollardRho_p_1(Q,N):
    a = i = 2
    while 1:
        a = pow(a, i, N)
        d = gcd(a - 1, N)
        if d != 1:
            return d
        i += 1

Fermat

from gmpy2 import *
def Fermat(Q,n):
    a = isqrt_rem(n)[0]+1
    b = a ** 2 - n
    while 1:
        q = isqrt_rem(b)
        if q[1] == 0:
            return a - q[0]
        a += 1
        b = a ** 2 - n

RSA在CTF中的攻击方法

gmpy2 安装

先安装mpfr和mpc

sudo apt install libmpc-dev

pip/pip3 install gmpy2

sage安装

https://mirrors.tuna.tsinghua.edu.cn/sagemath/linux/64bit/index.html

明文解密

模互素

$d = gmpy2.invert(e,(p-1) * (q-1))$

$m = gmpy2.powmod(c,d,n)$

模不互素

第一种情况

给出$p,q,c,e$且$gcd(e, (p-1)*(q-1))$非常小(可能为3)

example:

p,q= 3881, 885445853681787330351086884500131209939

c = 1926041757553905692219721422025224638913707

e = 33

第二种情况

给出n1,n2,e1,e2,c1,c2求满足以下式子

assert p = gcd(n1,n2)

assert pow(flag,e1,n1)==c1

assert pow(flag,e2,n2)==c2

assert gcd(e1,(p1-1) * (q1-1))==gcd(e2,(p2-1) * (q2-1))

低加密指数攻击

在 RSA 中 e 也称为加密指数。由于 e 是可以随意选取的，选取小一点的 e 可以缩短加密时间（比如 3），但是选取不当的话，就会造成安全问题

介绍

当 e=3 时，如果明文过小，导致明文的三次方仍然小于 n，那么通过直接对密文三次开方，即可得到明文，即
$$
c\equiv m^e,mod,n
$$
如果 $e=3, m^e<n$，

那么 $c=m^e, m=\sqrt[3]{c}$

还有一种情况是：

如果明文的 3 次方比$n$大，但不足够大，那么设$k$，有：

$c=m^e+kn$

爆破$k$，如果$c − kn$能开三次根式，那么可以直接得到明文

例题

e = 3 且明文很小

n= 22885480907469109159947272333565375109310485067211461543881386718201442106967914852474989176175269612229966461160065872310916096148216253429849921988412342732706875998100337754561586600637594798877898552625378551427864501926224989873772743227733285336042475675299391051376624685754547818835551263597996620383338263448888107691240136257201191331617560711786674975909597833383395574686942099700631002290836152972352041024137872983284691831292216787307841877839674258086005814225532597955826353796634417780156185485054141684249037538570742860026295194559710972266059844824388916869414355952432189722465103299013237588737

c= 15685364647213619014219110070569189770745535885901269792039052046431067708991036961644224230125219358149236447900927116989931929305133870392430610563331490276096858863490412102016758082433435355613099047001069687409209484751075897343335693872741

e = 3

求 m

# -*- coding: cp936 -*-
import gmpy2
e = 3
# 读入 n, 密文
n= 22885480907469109159947272333565375109310485067211461543881386718201442106967914852474989176175269612229966461160065872310916096148216253429849921988412342732706875998100337754561586600637594798877898552625378551427864501926224989873772743227733285336042475675299391051376624685754547818835551263597996620383338263448888107691240136257201191331617560711786674975909597833383395574686942099700631002290836152972352041024137872983284691831292216787307841877839674258086005814225532597955826353796634417780156185485054141684249037538570742860026295194559710972266059844824388916869414355952432189722465103299013237588737
c= 15685364647213619014219110070569189770745535885901269792039052046431067708991036961644224230125219358149236447900927116989931929305133870392430610563331490276096858863490412102016758082433435355613099047001069687409209484751075897343335693872741
print 'n=', n
print 'c=', c
print '[+]Detecting m...'
result = gmpy2.iroot(c, 3)
print '  [-]The c has cubic root?', result[1]
if result[1]: print '  [-]The m is:', '{:x}'.format(result[0]).decode('hex')
print '[!]All Done!'

结果

n= 22885480907469109159947272333565375109310485067211461543881386718201442106967914852474989176175269612229966461160065872310916096148216253429849921988412342732706875998100337754561586600637594798877898552625378551427864501926224989873772743227733285336042475675299391051376624685754547818835551263597996620383338263448888107691240136257201191331617560711786674975909597833383395574686942099700631002290836152972352041024137872983284691831292216787307841877839674258086005814225532597955826353796634417780156185485054141684249037538570742860026295194559710972266059844824388916869414355952432189722465103299013237588737
c= 15685364647213619014219110070569189770745535885901269792039052046431067708991036961644224230125219358149236447900927116989931929305133870392430610563331490276096858863490412102016758082433435355613099047001069687409209484751075897343335693872741
[+]Detecting m...
  [-]The c has cubic root? True
  [-]The m is: Tr0y{e=3_And_Sma11_M_1s_danger0us}
[!]All Done!

例题2

e = 3 且明文的三次方比 n 大，但是不是足够大

n= 114976915747243387792157708464120735018971336213935438953074748276198282761939060395482051056351068439137722626185590043024556656813730840050547350912425438364703854627760482842307943026011880815011654341047422453012558617703411700393668892701036222135444420377515575624398723436532681305293727164639582093389

c= 5828813410620741112500628876643872258919868379601617907887884191584237969605489971465692568848339200057188383649365078832766143513766368216471491824042974016773526107276856706832404477882581400769791378958901067683158857990261489285951805740071223765359992165262854641069674603160977034446644199945940251030

e = 3

还原 m

# -*- coding: cp936 -*-
import gmpy2, time
e = 3
# 读入 n, 密文
n = 114976915747243387792157708464120735018971336213935438953074748276198282761939060395482051056351068439137722626185590043024556656813730840050547350912425438364703854627760482842307943026011880815011654341047422453012558617703411700393668892701036222135444420377515575624398723436532681305293727164639582093389
c = 5828813410620741112500628876643872258919868379601617907887884191584237969605489971465692568848339200057188383649365078832766143513766368216471491824042974016773526107276856706832404477882581400769791378958901067683158857990261489285951805740071223765359992165262854641069674603160977034446644199945940251030
i = 239000000 # i 应该是未知的。这里缩短一下距离, 防止跑得太久
print 'n=', n
print 'c=', c
print '[!]Done!\n'
print '[+]Detecting m...'
s = time.clock()
while 1:
    m, b = gmpy2.iroot(c + i * n, 3)
    if b:
        print '  [-]m is: ' + '{:x}'.format(int(m)).decode('hex')
        break
    #print '  [-]i = %d\r' % i,
    i += 1
print '[!]Timer:', round(time.clock() - s, 2), 's'

结果：

n= 114976915747243387792157708464120735018971336213935438953074748276198282761939060395482051056351068439137722626185590043024556656813730840050547350912425438364703854627760482842307943026011880815011654341047422453012558617703411700393668892701036222135444420377515575624398723436532681305293727164639582093389
c= 5828813410620741112500628876643872258919868379601617907887884191584237969605489971465692568848339200057188383649365078832766143513766368216471491824042974016773526107276856706832404477882581400769791378958901067683158857990261489285951805740071223765359992165262854641069674603160977034446644199945940251030
[!]Done!
[+]Detecting m...
  [-]m is: Tr0y{e=3_1s_danger0us!}                     
[!]Timer: 9.07 s

低加密指数广播攻击

介绍

如果选取的加密指数较低，并且使用了相同的加密指数给一个接受者的群发送相同的信息，那么可以进行广播攻击得到明文。选取了相同的加密指数 e（这里取 e=3），对相同的明文 m 进行了加密并进行了消息的传递，那么有：

$c_1 ≡ m^e,mod ,n_1$

$c_2 ≡ m^e,mod,n_2$

$c_3\equiv m^e ,mod ,n_3$

对上述等式运用中国剩余定理，在 e=3 时，可以得到：

$c_x\equiv m^3,mod,n_1n_2n_3$

通过对$c_x$进行三次开方就可以求得明文

例题

e = 9

n = [142782424368849674771976671955176187834932417027468006479038058385550042422280158726561712259205616626939123504489410624745195777853423961104590708231562726165590769610040722589287393102301338152085670464005026301781192671834390892019478189768725018303217559795377795540494239283891894830166363576205812991157L, 153610425077816156109768509904751446801233412970601397035720458311275245730833227428213917577405780162151444202393431444812010569489900435979730559895340377469612234558042643742219128033827948585534761030527275423811282367831985007507137144308704413007806012914286105842311420933479771294576841956749281552971L, 152540067782701001222493009941492423063369171831039847414320547494725020441901272486665728360741395415762864872737675660423920609681185809510355937534756399208661762715484879562585724584849261266873624875852300611683382543315580370484972470694466195837255994159609193239840228218925381488410059939975556977947L, 125842716702134814646356078531900645012495638692517778270527426844383063904041812273637776798591687732598509470005151551320457132061693618473039437320011446697406190781306264437609046721508738109650829547010385875425097336266103994639126319889016342284747700714199556143378526590058467791687837422897022829661L, 116144389285266462769913139639175922392318396923181100785008570884082681963637784423143843845816350379438789947802939701820129805341796427821894273985551331666719808355412080909245720551238149511778060242720419584504473490216670437024863860559347959698828131475160058721701582089480924088773887932997353631767L, 127833907448946785858374094953899556339175475846831397383049660262333005992005484987913355932559627279178940862787593749842796469355336182379062826441222705075178971785791223706944120681105575965622931327112817747065200324610697178273898956820957640413744954233327851461318200323486469677469950386824833536523L, 130561613227079478921314550968562766645507834694262831586725464124109153306162445639759476845681271537955934718244296904503168256991962908095007040044300188572466395275317838178325500238288302672390013747102961340256309124310478931896245221622317302428447389760864327859640573452084295225059466376349115703119L, 115953389401040751013569404909249958538962411171147823610874077094621794755967854844224923689925397631692572916641171075740839099217316101334941033937183815345038898177087515909675028366437302462022970987947264115373697445950951595479758872029099661065186221250394358255523574834723958546450323357472451930993L, 143437107845384843564651522639125300763388830136500260725097766445883003928355325003575359566631064630487365774344508496878731109174874449170057678821440711511966073934025028100604234445470976333825866939923998344367645612128590820812489407412175198698290167077116185959180877334222693344630253253476594907313L]

c = [85033868418784308573673709960700777350314426427677627319697346811123742342359072170220428874952996988431950989321281905284522596263957356289624365171732095210045916218066135140320107686084053271623461104022705353814233772164502775939590711842361956121603943483040254727995655776263673058788416722141673409688L, 66065963470666895005407449599703926269325406456711861190876894466341571726360462706664546294453572319565476664348345756905411939632955966517708138047546806602828064213238537646393524578984547577761559965654539771172357089802682793169968961304179886652390277814477825753096636750388350662980872556701402397564L, 116011740820520887443111656288411611070614127688662643257265381793048354928820176624229624692124188995846076431510548507016903260774215950803926107831505634778278712070141663189086436127990584944132764896694777031370995058271038329228336417590284517922855284619653301817355115583540545182119702335431334401666L, 97640420284096094887471273365295984332267897927392169402918423863919914002451127544715668846623138003564829254309568918651163254043205129883843425179687841236818720463784828905460885026290909768599562386370732119591181513319548915478512030197629196018254041500662654260834562708620760373487652389789200792120L, 8112507653841374573057048967617108909055624101437903775740427861003476480616929517639719198652146909660899632120639789106782550275648578142883715280547602249589837441805676364041484345030575130408744621981440093280624046635769338568542048839419939250444929802135605724150484414516536378791500915047844188300L, 36792148360808115566234645242678223867680969786675055638670907933041180936164293809961667801099516457636164692292891528415720085345494773373966277807505798679784807614784581861287048096977968620964436947452527540958289441390882589051225367658014709290392321808926567572528170531844664734909469690750971883323L, 53043093283305492238903255767698153246673671181809989362223466090875767705978690531154079519999671834688647277179370374802495005937892824566602423646978168777735383632928274082669949750078161820002768640908750005814934158829006019656592134357897586040866207754535586785064545866404380204728594863102313407789L, 88499407133762624445946519155722583633934260410706930537441122463087556094734626189377091740335667052378955691250910459790202385799502439716173363179773811920751410726795431402796346647688144853156900427797933862087074385441977254140336390678022955770879265490567987868532251217565094093318626424653599450992L, 138337520305048557335599940473834485492131424901034295018189264168040969172072024612859307499682986987325414798210700710891033749119834960687318156171051379643844580970963540418974136891389303624057726575516576726845229494107327508855516437230240365759885913142671816868762838801720492804671259709458388192984L]

求 m

# -*- coding: cp936 -*-
import gmpy2
import time
def CRT(items):
    N = reduce(lambda x, y: x * y, (i[1] for i in items))
    result = 0
    for a, n in items:
        m = N / n
        d, r, s = gmpy2.gcdext(n, m)
        if d != 1: raise Exception("Input not pairwise co-prime")
        result += a * s * m
    return result % N, N
# 读入 e, n, c
e = 9
n = [142782424368849674771976671955176187834932417027468006479038058385550042422280158726561712259205616626939123504489410624745195777853423961104590708231562726165590769610040722589287393102301338152085670464005026301781192671834390892019478189768725018303217559795377795540494239283891894830166363576205812991157L, 153610425077816156109768509904751446801233412970601397035720458311275245730833227428213917577405780162151444202393431444812010569489900435979730559895340377469612234558042643742219128033827948585534761030527275423811282367831985007507137144308704413007806012914286105842311420933479771294576841956749281552971L, 152540067782701001222493009941492423063369171831039847414320547494725020441901272486665728360741395415762864872737675660423920609681185809510355937534756399208661762715484879562585724584849261266873624875852300611683382543315580370484972470694466195837255994159609193239840228218925381488410059939975556977947L, 125842716702134814646356078531900645012495638692517778270527426844383063904041812273637776798591687732598509470005151551320457132061693618473039437320011446697406190781306264437609046721508738109650829547010385875425097336266103994639126319889016342284747700714199556143378526590058467791687837422897022829661L, 116144389285266462769913139639175922392318396923181100785008570884082681963637784423143843845816350379438789947802939701820129805341796427821894273985551331666719808355412080909245720551238149511778060242720419584504473490216670437024863860559347959698828131475160058721701582089480924088773887932997353631767L, 127833907448946785858374094953899556339175475846831397383049660262333005992005484987913355932559627279178940862787593749842796469355336182379062826441222705075178971785791223706944120681105575965622931327112817747065200324610697178273898956820957640413744954233327851461318200323486469677469950386824833536523L, 130561613227079478921314550968562766645507834694262831586725464124109153306162445639759476845681271537955934718244296904503168256991962908095007040044300188572466395275317838178325500238288302672390013747102961340256309124310478931896245221622317302428447389760864327859640573452084295225059466376349115703119L, 115953389401040751013569404909249958538962411171147823610874077094621794755967854844224923689925397631692572916641171075740839099217316101334941033937183815345038898177087515909675028366437302462022970987947264115373697445950951595479758872029099661065186221250394358255523574834723958546450323357472451930993L, 143437107845384843564651522639125300763388830136500260725097766445883003928355325003575359566631064630487365774344508496878731109174874449170057678821440711511966073934025028100604234445470976333825866939923998344367645612128590820812489407412175198698290167077116185959180877334222693344630253253476594907313L]
c = [85033868418784308573673709960700777350314426427677627319697346811123742342359072170220428874952996988431950989321281905284522596263957356289624365171732095210045916218066135140320107686084053271623461104022705353814233772164502775939590711842361956121603943483040254727995655776263673058788416722141673409688L, 66065963470666895005407449599703926269325406456711861190876894466341571726360462706664546294453572319565476664348345756905411939632955966517708138047546806602828064213238537646393524578984547577761559965654539771172357089802682793169968961304179886652390277814477825753096636750388350662980872556701402397564L, 116011740820520887443111656288411611070614127688662643257265381793048354928820176624229624692124188995846076431510548507016903260774215950803926107831505634778278712070141663189086436127990584944132764896694777031370995058271038329228336417590284517922855284619653301817355115583540545182119702335431334401666L, 97640420284096094887471273365295984332267897927392169402918423863919914002451127544715668846623138003564829254309568918651163254043205129883843425179687841236818720463784828905460885026290909768599562386370732119591181513319548915478512030197629196018254041500662654260834562708620760373487652389789200792120L, 8112507653841374573057048967617108909055624101437903775740427861003476480616929517639719198652146909660899632120639789106782550275648578142883715280547602249589837441805676364041484345030575130408744621981440093280624046635769338568542048839419939250444929802135605724150484414516536378791500915047844188300L, 36792148360808115566234645242678223867680969786675055638670907933041180936164293809961667801099516457636164692292891528415720085345494773373966277807505798679784807614784581861287048096977968620964436947452527540958289441390882589051225367658014709290392321808926567572528170531844664734909469690750971883323L, 53043093283305492238903255767698153246673671181809989362223466090875767705978690531154079519999671834688647277179370374802495005937892824566602423646978168777735383632928274082669949750078161820002768640908750005814934158829006019656592134357897586040866207754535586785064545866404380204728594863102313407789L, 88499407133762624445946519155722583633934260410706930537441122463087556094734626189377091740335667052378955691250910459790202385799502439716173363179773811920751410726795431402796346647688144853156900427797933862087074385441977254140336390678022955770879265490567987868532251217565094093318626424653599450992L, 138337520305048557335599940473834485492131424901034295018189264168040969172072024612859307499682986987325414798210700710891033749119834960687318156171051379643844580970963540418974136891389303624057726575516576726845229494107327508855516437230240365759885913142671816868762838801720492804671259709458388192984L]
print '[+]Detecting m...'
data = zip(c, n)
x, n = CRT(data)
realnum = gmpy2.iroot(gmpy2.mpz(x), e)[0].digits()
print '  [-]m is: ' + '{:x}'.format(int(realnum)).decode('hex')
print '[!]All Done!'

结果：

1
2
3

[+]Detecting m...
  [-]m is: Tr0y{e=3_1s_danger0us!}                     
[!]All Done!

低解密指数攻击

与低加密指数攻击相反，需要满足e非常大，接近于N

介绍

与低加密指数相同，低解密指数可以加快解密的过程，但是者也带来了安全问题。Wiener 表示如果满足：$d<\frac{1}{3}n^\frac{1}{4}$

那么一种基于连分数(一个数论当中的问题)的特殊攻击类型就可以危害 RSA 的安全。此时需要满足：$q<p<2q$

如果满足上述条件，通过 Wiener Attack 可以在多项式时间中分解 n，思路如下：

回想一下 RSA：
$$
N = pq \
\varphi(n) = (p-1)(q-1)=pq - (p + q) + 1=N - (p + q) + 1\
\because p,q非常大,\therefore,pq\gg p+q ,,\therefore\varphi(n)\approx N\
\because ed\equiv1,mod,\varphi(n),,\therefore ed-1=k\varphi(n),,这个式子两边同除 dφ(n) 可得：\
\frac{e}{\varphi(n)}-\frac{k}{d}=\frac{1}{d\varphi(n)}\
\because \varphi(n)\approx N,,\therefore \frac{e}{N}-\frac{k}{d}=\frac{1}{d\varphi(n)},,同样 dφ(n) 是一个很大的数，所以 \frac{e}{N} 略大于\frac{k}{d}
$$
为啥要这么写呢，因为 e 和 N 是我们是知道的，公钥中给我们的，所以我们计算出 $\frac{e}{N}$后，比它略小的$\frac{k}{d}$怎么出来呢，计算 $\frac{e}{N}$的连分数展开，依次算出这个分数每一个渐进分数，由于$\frac{e}{N}$略大于 $\frac{k}{d}$，wiener 证明了，该攻击能精确的覆盖 kdkd（论文刚不动，只知道结论）

我们来举个例子，现在有一个 rsa, e = 42667, N = 64741,我们来求。第一步，我们把分数 e/N 连分数展开，以此求出每一个渐进分数：0，1, 1/2, 2/3 ….用 1/2 举例子:

假设 1/2 成立，则把 k=1, d=2 代入上面的 $ed−1=kφ(n)$中，显然 e,d,k 都有了，$φ(n)$就有了，知道 $φ(n)$有啥用呢？我们知道 $φ(n)= pq - (p + q) + 1 = N - (p + q) + 1，N = pq $作为公钥我们是知道的，所以知道了$ φ(n) $我们只要算出$ N- φ(n)+1 $就是$(p + q)$的值，好回到初三，现在知道了 pq,和 p+q 的值，我们如何求出 p 和 q 的值呢？很简单，利用韦达定理，我们可以轻松构造出方程 $x^2−(p+q)∗x+pq=0$, 这个方程的两个根就是我们要求的 p,q, 至此 rsa 中所有的参数都被我们求了出来

例题

n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827

e = 11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517

c = 9472193174575536616954091686751964873836697237500198884451530469300324470671555310791335185133679697207007374620225900775502162690848135615431624557389304657410880981454777737587420426091879654002644281066474715074536611611252677882396384453641127487515845176069574754606670518031472235144795376526854484442135299818868525539923568705203042265537204111153151119105287648912908771710419648445826883069030285651763726003413418764301988228077415599665616637501056116290476861280240577145515875430665394216054222788697052979429015400411487342877096677666406389711074591330476335174211990429870900468249946600544116793793

# -*- coding: cp936 -*-
import gmpy2
import time
# 展开为连分数
def continuedFra(x, y):
    cF = []
    while y:
        cF += [x / y]
        x, y = y, x % y
    return cF
def Simplify(ctnf):
    numerator = 0
    denominator = 1
    for x in ctnf[::-1]:
        numerator, denominator = denominator, x * denominator + numerator
    return (numerator, denominator)
# 连分数化简
def calculateFrac(x, y):
    cF = continuedFra(x, y)
    cF = map(Simplify, (cF[0:i] for i in xrange(1, len(cF))))
    return cF
# 解韦达定理
def solve_pq(a, b, c):
    par = gmpy2.isqrt(b * b - 4 * a * c)
    return (-b + par) / (2 * a), (-b - par) / (2 * a)
def wienerAttack(e, n):
    for (d, k) in calculateFrac(e, n):
        if k == 0: continue
        if (e * d - 1) % k != 0: continue
        phi = (e * d - 1) / k
        p, q = solve_pq(1, n - phi + 1, n)
        if p * q == n:
            return abs(int(p)), abs(int(q))
    print 'not find!'
time.clock()
n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827
e = 11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517
c = 9472193174575536616954091686751964873836697237500198884451530469300324470671555310791335185133679697207007374620225900775502162690848135615431624557389304657410880981454777737587420426091879654002644281066474715074536611611252677882396384453641127487515845176069574754606670518031472235144795376526854484442135299818868525539923568705203042265537204111153151119105287648912908771710419648445826883069030285651763726003413418764301988228077415599665616637501056116290476861280240577145515875430665394216054222788697052979429015400411487342877096677666406389711074591330476335174211990429870900468249946600544116793793
p, q = wienerAttack(e, n)
print '[+]Found!'
print '  [-]p =',p
print '  [-]q =',q
print '  [-]n =',p*q
d = gmpy2.invert(e,(p-1)*(q-1))
print '  [-]d =', d
print '  [-]m is:' + '{:x}'.format(pow(c,d,n)).decode('hex')
print '\n[!]Timer:', round(time.clock(),2), 's'
print '[!]All Done!'

结果：

[+]Found!
  [-]p = 110628229052318704152246095359270943887813104444949254398128993373602031238362003253725157377156430190674485981957445623074380516333901046053625898418396428434438992000260593732179397554401650954591549716160461307807121354462523624398848957270672460052953336283536148203105186509336678669629895378279072978393
  [-]q = 110628229052318704152246095359270943887813104444949254398128993373602031238362003253725157377156430190674485981957445623074380516333901046053625898418396428434438992000260593732179397554401650954591549716160461307807121354462523624398848957270672460052953336283536148203105186509336678669629895378279072978539
  [-]n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827
  [-]d = 392321823339749506721829211885
  [-]m is:Tr0y{W1eNer_AttaCk_1s_p0werfu1!}
[!]Timer: 0.09 s
[!]All Done!

共模攻击

$c_1\equiv m^{e_1},mod,n$

$c_2\equiv m^{e_2},mod,n$

如以上使用了相同的模数N对相同的明文进行加密, 那么就可以在不分解 n 的情况下还原出明文 m 的值。此时不需要分解 n，不需要求解私钥，如果两个加密指数互素，就可以通过共模攻击在两个密文和公钥被嗅探到的情况下还原出明文 m 的值。过程如下，首先两个加密指数互质，则：

$(e_1,e_2)=1$，即存在 $s2$，使得：

$s_1e_1+s_2e_2=1$

$\because c_1\equiv m^{e_1},mod,n, c_2\equiv m^{e_2},mod,n$

代入化简可以得出：

$c_1^{s_1}c_2^{s_2}\equiv m,mod,n$

例题

n = 158052722013789461456896900244510199169216575693048895162538548356466884311543740968048825149608833390255268602486435690724338965409521812963337715301197225841194835534751041470231293288252951274190599189716955573428884560130364021535005115652592074445852835422027406556727605302404510264249211145063332337043

e = [665213, 368273]

c = [16698617641888248664694980135332125531792692516788088682722832061393117609508765284473236240256421599515450690670639565968165473479697383505401285976148490839526672808730165847471005704945978274496508928460578173068717106075169723401049489389383596761956301440156581021583368058047939083755488885694261340425L, 59192887933967939708054321952273893559113509451228797382728687616356609407020086787061368452871936378934964292805289941535766263083244529814852043063188312786173717046316177403357053871483983775362121186037776932260378728059531236711960979620603784044468207000654149190295060179235411429700710154759043236436L]

求 m

# -*- coding: cp936 -*-
import time
import gmpy2
n = 158052722013789461456896900244510199169216575693048895162538548356466884311543740968048825149608833390255268602486435690724338965409521812963337715301197225841194835534751041470231293288252951274190599189716955573428884560130364021535005115652592074445852835422027406556727605302404510264249211145063332337043
e = [665213, 368273]
c = [16698617641888248664694980135332125531792692516788088682722832061393117609508765284473236240256421599515450690670639565968165473479697383505401285976148490839526672808730165847471005704945978274496508928460578173068717106075169723401049489389383596761956301440156581021583368058047939083755488885694261340425L, 59192887933967939708054321952273893559113509451228797382728687616356609407020086787061368452871936378934964292805289941535766263083244529814852043063188312786173717046316177403357053871483983775362121186037776932260378728059531236711960979620603784044468207000654149190295060179235411429700710154759043236436L]
print '[+]Detecting m...'
time.clock()
c1 = c[0]
c2 = c[1]
e1 = e[0]
e2 = e[1]
s = gmpy2.gcdext(e1, e2)
s1 = s[1]
s2 = s[2]
# 求模反元素
if s1 < 0:
    s1 = -s1
    c1 = gmpy2.invert(c1, n)
elif s2 < 0:
    s2 = -s2
    c2 = gmpy2.invert(c2, n)
m = pow(c1, s1, n) * pow(c2, s2, n) % n
print '  [-]m is:' + '{:x}'.format(int(m)).decode('hex')
print '\n[!]Timer:', round(time.clock(),2), 's'
print '[!]All Done!'

结果：

[+]Detecting m...
  [-]m is:Tr0y{D0_n0t_use_N_m0re_thAn_0nce!}
[!]Timer: 0.0 s
[!]All Done!

Boneh and Durfee attack

e 非常大接近于N，跟低解密指数攻击类似，比低解密指数攻击更强，可以解决d<N的0.292次方的问题

点击下载exp

Coppersmith 定理攻击

介绍

oppersmith 定理指出在一个 e 阶的 mod n 多项式 f(x)中，如果有一个根小于 n1en1e，就可以运用一个 O(log n)的算法求出这些根。

这个定理可以应用于 RSA 算法。如果 e = 3 并且在明文当中只有三分之二的比特是已知的，这种算法可以求出明文中所有的比特。

听上去很简单，但是会涉及到格这个东西，还有个 LLL 算法。经过查找，发现 sage 里有相关的库。。等闲下来用 python 实现一遍

sage 是基于 Python 的一个科学运算，很强大，这里可以在线运行

Coppersmith攻击:已知p的高位攻击

知道p的高位为p的位数的约1/2时即可

点击下载exp

Coppersmith攻击:已知明文高位攻击

点击下载exp

Coppersmith攻击:已知d的低位攻击

如果知道d的低位，低位约为n的位数的1/4就可以恢复d

点击下载exp

其他思路

给出两组数据

n1,c1,e1,n2,c2,e2且无以上特征可尝试gcd(n1,n2)得到公因子（存在的话）

给出一组数据

n1,c1,e1

尝试yafu或http://www.factordb.com分解n(p,q相差过大或过小yafu可分解成功)

给出如下数据

p,q,nextprime(p),nextprime(q)

n1 = p * q

n2 = nextprime(p) * nextprime(q)

n = n1 * n2

用yafu分解n可得到

n3 = p * nextprime(q)

n4 = q * nextprime(p)

CTF中RSA的一些攻击思路

关于RSA算法

RSA算法加解密实现

N的分解

介绍

利用公约数分解N

例题

大数分解算法

例题

RSA在CTF中的攻击方法

明文解密

模互素

模不互素

低加密指数攻击

介绍

例题

例题2

低加密指数广播攻击

介绍

例题

低解密指数攻击

介绍

例题

共模攻击

例题

Boneh and Durfee attack

Coppersmith 定理攻击

介绍

Coppersmith攻击:已知p的高位攻击

Coppersmith攻击:已知明文高位攻击

Coppersmith攻击:已知d的低位攻击

Coppersmith攻击:明文高位相同

已知dp或dq（dp = d mod p-1，dq = d mod q-1）

Least Significant Bit Oracle Attack

其他思路