RSA 大礼包

CTF 中 RSA 的常见攻击方法

简单介绍

RSA 基于一个简单的数论事实，两个大素数相乘十分容易，将其进行因式分解却是困难的

然而即便 RSA 算法目前来说是安全可靠的，但是错误的应用场景，错误的环境配置，以及错误的使用方法都会导致 RSA 的算法体系出现问题，从而也派生出针对各种特定场景下的 RSA 攻击方法

RSA

RSA 算法涉及三个参数，n，e，d，私钥为 d，公钥对为 n，e

其中 \(N=pq\ \)(\(p\), \(q\) \(\ \)均为大素数)

\(ed\equiv1\ mod\ \varphi(n)\)

\(\varphi(n)\) 是 n 的欧拉函数

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

\(c\equiv m^e\ mod\ n\)

解密过程如下：

\(m\equiv c^d\ mod\ n\)

n，e 是公开的情况下，想要知道 d 的值，必须要将 n 分解计算出 n 的欧拉函数值，而 n 是两个大素数 p，q 的积, 将其分解是困难的。但是对于特定的情况可以使用特殊方法进行分解

数论知识

看课本

gmpy2

pip install gmpy2

py 的一个数论库，很方便。自己写也行，有点麻烦

RSA 题目类型

不能再简单了！

介绍

解决 RSA 题目最简单，最暴力，最吼的方法就是直接分解模数 n。如果能够将 n 分解成功，成功得到 p，q 的取值，那么可求 n 的欧拉函数的值

\(\varphi(n)=(p-1)(q-1)\)

而通过 e，d 与 n 的欧拉函数满足如下关系：

\(ed=1\ mod\ \varphi(n)\)

通过欧几里得算法可以通过 e 与 n 的欧拉函数的值轻易求出 d，从而计算出解密密钥。

在知道 e，p，q 的情况下，可以解出 d（这种情况实际上啥都告诉你了）

例题

p = 3487583947589437589237958723892346254777
q = 8767867843568934765983476584376578389
e = 65537
求 d

代码如下

import gmpy2

p = 3487583947589437589237958723892346254777
q = 8767867843568934765983476584376578389
e = 65537
print gmpy2.invert(e, (p-1)*(q-1))

#结果 mpz(19178568796155560423675975774142829153827883709027717723363077606260717434369L)

直接分解 n

介绍

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

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

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

factordb

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

例题

1	`n = 87924348264132406875276140514499937145050893665602592992418171647042491658461`

利用 factordb 分解：

利用公约数分解 n

介绍

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

(\(n_1\), \(n_2\))=p

可以得出：

\(n_1\)=\(pq_1\)

\(n_2\)=\(pq_2\)

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

例题

1
2
3

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 很快地分解成功

yafu
(千万不要迷信工具，yafu 到后面默认 ecm 模式分解的，有些时候效果反而没有自己写脚本效果好。或者说针对性不强)

例题

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

介绍

当 e=3 时，如果明文过小，导致明文的三次方仍然小于 n，那么通过直接对密文三次开方，即可得到明文。

即

\(c\equiv m^e\ mod\ n\)

如果 e=3, \(m^e<n\)，那么：

\(c=m^e\), e=3

\(m=\sqrt[3]{c}\)

还有一种情况是：

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

\(c=m^e+kn\)

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

例题 1

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\equiv m^e\ mod\ n_1\)

\(c_2\equiv 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!

Coppersmith 定理攻击

介绍

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

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

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

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

有空详细说吧，先放着

低解密指数攻击

介绍

与低加密指数相同，低解密指数可以加快解密的过程，但是者也带来了安全问题。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\varphi(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\varphi(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 证明了，该攻击能精确的覆盖 \(\frac{k}{d}\)（论文刚不动，只知道结论）

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

假设 1/2 成立，则把 k=1, d=2 代入上面的 \(ed-1=k\varphi(n)\) 中，显然 e,d,k 都有了，\(\varphi(n)\) 就有了，知道 \(\varphi(n)\) 有啥用呢？我们知道 \(\varphi(n)\) = pq - (p + q) + 1 = N - (p + q) + 1，N = pq 作为公钥我们是知道的，所以知道了 \(\varphi(n)\) 我们只要算出 N- \(\varphi(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!

共模攻击

介绍

如果在 RSA 的使用中使用了相同的模 n 对相同的明文 m 进行了加密，那么就可以在不分解 n 的情况下还原出明文 m 的值。即：

\(c_1\equiv m^{e_1}\ mod\ n\)

\(c_2\equiv m^{e_2}\ mod\ n\)

此时不需要分解 n，不需要求解私钥，如果两个加密指数互素，就可以通过共模攻击在两个密文和公钥被嗅探到的情况下还原出明文 m 的值。

过程如下，首先两个加密指数互质，则：

\((e_1,e_2)=1\)，即存在 \(s_2\)，使得：

\(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!

总结

就像《图解密码学》里提到的，完美的密码技术因为有不完美的人类参与而无法实现完美的安全性。还是要多多提高自己的姿势水平呀

参考资料

我的这篇博客来源于这篇文章，它讲的挺详细了。我补充了一点东西

参考资料 1

以及 wiener 的详解：

参考资料 2

来呀快活呀

经验总结

#工具 #CTF #Python #密码学 #CTF-Crypto

RSA 大礼包

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

作者

Tr0y

发布于

2017年11月6日

更新于

2024年6月3日

许可协议

SM4 的 py 实现上一篇

《图解密码学》下一篇