近期因?yàn)橐恍┍荣愐约捌渌颍偨Y(jié)了一些RSA方面的東西沟绪，于是在這里與大家分享怔檩，希望大家能有所收獲褪秀，如有不當(dāng)之處敬請(qǐng)批評(píng)指正。
0x01 前言
這里就不討論數(shù)論的基礎(chǔ)了薛训，進(jìn)行RSA的題目解答媒吗，至少要懂得基本的數(shù)論知識(shí)的，如果不了解數(shù)論的基本知識(shí)的話乙埃，網(wǎng)上相關(guān)內(nèi)容還是挺多的闸英。
RSA基于一個(gè)簡(jiǎn)單的數(shù)論事實(shí)，兩個(gè)大素?cái)?shù)相乘十分容易介袜，將其進(jìn)行因式分解確實(shí)困難的甫何。在量子計(jì)算機(jī)還沒有成熟的今天，RSA算法憑借其良好的抵抗各種攻擊的能力遇伞，在公鑰密碼體制中發(fā)揮著中流砥柱的作用辙喂。然而即便RSA算法目前來說是安全可靠的，但是錯(cuò)誤的應(yīng)用場(chǎng)景，錯(cuò)誤的環(huán)境配置巍耗，以及錯(cuò)誤的使用方法秋麸，都會(huì)導(dǎo)致RSA的算法體系出現(xiàn)問題，從而也派生出針對(duì)各種特定場(chǎng)景下的RSA攻擊方法炬太。
本文針對(duì)一些在CTF中常見的RSA攻擊方法灸蟆，從如何識(shí)別應(yīng)該應(yīng)用那種方法以及如何去解題來介紹CTF中的RSA題目的常見解法。
RSA算法描述
RSA算法涉及三個(gè)參數(shù)亲族，n次乓，e，d孽水，私鑰為n票腰，d，公鑰為n女气，e杏慰。
其中n是兩個(gè)大素?cái)?shù)p，q的乘積炼鞠。
d是e模 $varphi(n)$的逆元缘滥，$ varphi(n) $是n的歐拉函數(shù)。
$$sh(x)=\frac{e^x+e^{-x}}{2}$$
c為密文谒主，m為明文朝扼，則加密過程如下：
$ cequiv m^e mod n $
解密過程如下：
$ mequiv c^d$ $mod$ $n$
n，e是公開的情況下霎肯，想要知道d的值擎颖，必須要將n分解計(jì)算出n的歐拉函數(shù)值，而n是兩個(gè)大素?cái)?shù)p观游，q的乘積搂捧，將其分解是困難的。
RSA題目類型
在CTF競(jìng)賽中懂缕，RSA理所當(dāng)然處在CRYPTO中居多允跑。而且RSA作為典型的加密算法，其出鏡率可謂相當(dāng)高搪柑，基本上所有比賽都會(huì)有幾道RSA的題目出現(xiàn)聋丝。
數(shù)據(jù)處理
在進(jìn)行做題之前，我們要將數(shù)據(jù)處理成可以做題的模式工碾∪跄溃基本上來說，RSA的題目都是圍繞著c倚喂，m每篷，e，d端圈，n焦读，p，q這幾個(gè)參數(shù)展開的舱权，但是題目一般不會(huì)直接給這種樣子的參數(shù)矗晃，而是通過別的方式給出，這里就需要我們使用一些工具或者自己手工將這些參數(shù)提取出來宴倍。
pem文件：針對(duì)此類文件可以直接使用openssl提取张症，大概使用過的方式有：
openssl rsautl -encrypt -in FLAG -inkey public.pem -pubin -out flag.enc
openssl rsa -pubin -text -modulus -in warmup -in public.pem
pcap文件：針對(duì)此類文件可以使用wireshark follow一下。這種問題一般都是寫了一個(gè)交互的crypto系統(tǒng)鸵贬，所以可能產(chǎn)生多輪交互俗他。
PPC模式：這種模式是上述pcap文件的交互版，會(huì)給一個(gè)端口進(jìn)行一些crypto的交互阔逼，參數(shù)會(huì)在交互中給出兆衅。
第二個(gè)需要處理的就是明密文，這個(gè)方法多多嗜浮，不多贅述羡亩。
0x02 模數(shù)分解
說一說
解決RSA題目最簡(jiǎn)單，最暴力危融，最好使的方法就是分解模數(shù)n畏铆。如果能夠?qū)分解成功，成功得到p吉殃，q的取值辞居，那么可求n的歐拉函數(shù)的值。
$ varphi(n)=(p-1)(q-1) $
而通過e蛋勺，d與n的歐拉函數(shù)滿足如下關(guān)系：
$ed=1$ $mod$ $varphi(n) $
通過歐幾里得算法可以通過e與n的歐拉函數(shù)的值輕易求出d速侈，從而計(jì)算出解密密鑰。
即在知道e迫卢，p倚搬，q的情況下，可以解出d：
自己寫,或者gmpy2 invert
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
modinv函數(shù)即為求模擬的函數(shù)乾蛤，在知道e每界，p，q的情況下家卖，可以：
d=modinv(e,(p-1)*(q-1))
即可求出解密密鑰眨层。
寫到這里，要提出一個(gè)細(xì)節(jié)問題上荡，在利用python進(jìn)行rsa的題目求解過程中：
$ cequiv m^e mod n $
此類運(yùn)算需要使用pow函數(shù)來進(jìn)行求解趴樱，而不是直接m**e % n馒闷，這樣會(huì)慢死的。Python在處理此類運(yùn)算進(jìn)行了優(yōu)化叁征。比如剛才在已知p纳账，q的時(shí)候利用modinv函數(shù)求出了d，然后就可以利用pow函數(shù)求出明文：
m=pow(c,d,n)
例題：
https://www.jarvisoj.com (very easy RSA)
題目中直接給了p捺疼，q疏虫，e。
可以直接求出d：
import gmpy2
from gmpy2 import mpz
p = mpz(3487583947589437589237958723892346254777)
q = mpz(8767867843568934765983476584376578389)
e = mpz(65537)
d = gmpy2.invert(e, (q-1)*(p-1))
print d
直接分解n
介紹：
素?cái)?shù)分解問題是困難的啤呼，但是可以通過計(jì)算機(jī)進(jìn)行暴力分解卧秘。1999年，名為Cray的超級(jí)計(jì)算機(jī)用了5個(gè)月時(shí)間分解了512bit的n官扣。2009年翅敌，一群研究人員成功分解了768bit的n。2010年惕蹄，又提出了一些針對(duì)1024bit的n的分解的途徑哼御，但是沒有正面分解成功。通常意義上來說焊唬，一般認(rèn)為2048bit以上的n是安全的×抵纾現(xiàn)在一般的公鑰證書都是4096bit的證書。
如果n比較小赶促，那么可以通過工具進(jìn)行直接n分解液肌，從而得到私鑰。如果n的大小小于256bit鸥滨，那么我們通過本地工具即可爆破成功嗦哆。例如采用windows平臺(tái)的RSATool2v17，可以在幾分鐘內(nèi)完成256bit的n的分解婿滓。
如果n在768bit或者更高老速，可以嘗試使用一些在線的n分解網(wǎng)站，這些網(wǎng)站會(huì)存儲(chǔ)一些已經(jīng)分解成功的n凸主，比如：http://factordb.com
通過在此類網(wǎng)站上查詢n橘券，如果可以分解或者之前分解成功過，那么可以直接得到p和q卿吐。然后利用前述方法求解得到密文旁舰。
識(shí)別：
此類問題一般是分值較小的題目，提取出n之后可以發(fā)現(xiàn)n的長(zhǎng)度小于等于512bit嗡官，可以直接取分解n箭窜。如果大于512bit，建議在使用每個(gè)題目都用后面所說的方法去解題衍腥。
例題：
比如在某次競(jìng)賽中磺樱，發(fā)現(xiàn)：
n=87924348264132406875276140514499937145050893665602592992418171647042491658461
利用factordb分解：
利用公約數(shù)
介紹：
如果在兩次公鑰的加密過程中使用的$n_1$ 和$n_2$具有相同的素因子纳猫，那么可以利用歐幾里得算法直接將$n_1$和$n_2$分解。
通過歐幾里得算法可以直接求出$n_1$和$n_2$的最大公約數(shù)p：
$(n1,n2)=p$
可以得出：
$n_1=p$$q_1$
$n_2=p$$q_2$
直接分解成功竹捉。而歐幾里得算法的時(shí)間復(fù)雜度為：O(log n)芜辕。這個(gè)時(shí)間復(fù)雜度即便是4096 bit也是秒破級(jí)別。
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
識(shí)別此類題目活孩，通常會(huì)發(fā)現(xiàn)題目給了若干個(gè)n物遇，均不相同乖仇，并且都是2048bit憾儒，4096bit級(jí)別，無法正面硬杠乃沙，并且明文都沒什么聯(lián)系起趾，e也一般取65537。 識(shí)別：
例題：
在一個(gè)題目中警儒，你拿到了兩個(gè)n训裆，e都為65537，兩個(gè)n分別為：
n1=9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327
n2=13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743
通過直接分解蜀铲，上factordb都分解失敗边琉。通過嘗試發(fā)現(xiàn)：
print gcd(n1,n2)
打印出：
1564859779720039565508870182569324208117555667917997801104862601098933699462849007879184203051278194180664616470669559575370868384820368930104560074538872199213236203822337186927275879139590248731148622362880471439310489228147093224418374555428793546002109
則此致即為兩個(gè)n共有的素因子p，然后進(jìn)一步求出q记劝，求解完畢变姨。
Fermat方法與Pollard rho方法
介紹：
針對(duì)大整數(shù)的分解有很多種算法，性能上各有優(yōu)異厌丑，有Fermat方法定欧，Pollard rho方法，試除法怒竿，以及橢圓曲線法砍鸠，連分?jǐn)?shù)法，二次篩選法耕驰，數(shù)域分析法等等爷辱。其中一些方法應(yīng)用在RSA的攻擊上也有奇效。
在p朦肘，q的取值差異過大托嚣，或者p，q的取值過于相近的時(shí)候厚骗，F(xiàn)ormat方法與Pollard rho方法都可以很快將n分解成功示启。
此類分解方法有一個(gè)開源項(xiàng)目yafu將其自動(dòng)化實(shí)現(xiàn)了，不論n的大小领舰，只要p和q存在相差過大或者過近時(shí)夫嗓，都可以通過yafu很快地分解成功迟螺。
識(shí)別：
在直接分解n無望，不能利用公約數(shù)分解n之后舍咖，都應(yīng)該使用yafu去試一下矩父。
例題：
https://www.jarvisoj.com (Medium RSA)
此題首先從pem中提取N和e，然后上yafu排霉，直接分解成功窍株。
0x03 低加密指數(shù)攻擊
在RSA中e也稱為加密指數(shù)。由于e是可以隨意選取的攻柠，選取小一點(diǎn)的e可以縮短加密時(shí)間球订，但是選取不當(dāng)?shù)脑挘蜁?huì)造成安全問題瑰钮。
e=3時(shí)的小明文攻擊
介紹：
當(dāng)e=3時(shí)冒滩，如果明文過小，導(dǎo)致明文的三次方仍然小于n浪谴，那么通過直接對(duì)密文三次開方开睡，即可得到明文。
即：
$ cequiv m^e$ $mod$ $n$
如果e=3苟耻，且$ m^e<{n} $篇恒，那么：
$ c= m^e,$ $e=3$
$ m=sqrt[3]{c}$
如果明文的三次方比n大，但是不是足夠大凶杖，那么設(shè)k胁艰，有：
$ c= m^e+kn$
爆破k，如果$ c-kn $能開三次根式官卡，那么可以直接得到明文蝗茁。
識(shí)別：
推薦在e=3的時(shí)候首先嘗試這種方法。
例題：
https://www.jarvisoj.com (Extremely hard RSA)
關(guān)鍵代碼如下：此題通過不斷給明文+n開三次方即可求得：
i=0
while 1:
if(gmpy.root(c+i*N, 3)[1]==1):
print gmpy.root(c+i*N, 3)
break
i=i+1
低加密指數(shù)廣播攻擊
介紹：
如果選取的加密指數(shù)較低寻咒，并且使用了相同的加密指數(shù)給一個(gè)接受者的群發(fā)送相同的信息哮翘，那么可以進(jìn)行廣播攻擊得到明文。
即毛秘，選取了相同的加密指數(shù)e（這里取e=3）饭寺，對(duì)相同的明文m進(jìn)行了加密并進(jìn)行了消息的傳遞，那么有：
$ c_1equiv m^e$ $mod$ $n_1$
$ c_2equiv m^e$ $mod$ $n_2$
$ c_3equiv m^e$ $mod$ $n_3$
對(duì)上述等式運(yùn)用中國剩余定理叫挟，在e=3時(shí)艰匙，可以得到：
$ c_xequiv m^3$ $mod$ $n_1n_2n_3$
通過對(duì)$ c_x $進(jìn)行三次開方可以求得明文。
識(shí)別：
這個(gè)識(shí)別起來比較簡(jiǎn)單抹恳，一般來說都是給了三組加密的參數(shù)和明密文员凝，其中題目很明確地能告訴你這三組的明文都是一樣的，并且e都取了一個(gè)較小的數(shù)字奋献。
例題：
SCTF2016健霹，CODE300
題目第二輪中通過流量包的方式給了廣播攻擊的參數(shù)旺上。
這里我就不賣萌了，直接給國外類似一題的網(wǎng)址：http://codezen.fr/2014/01/16/hackyou-2014-crypto-400-cryptonet
Coppersmith定理攻擊
Coppersmith定理指出在一個(gè)e階的mod n多項(xiàng)式f(x)中糖埋，如果有一個(gè)根小于$ n^frac{1}{e} $宣吱，就可以運(yùn)用一個(gè)O(log n)的算法求出這些根。
這個(gè)定理可以應(yīng)用于RSA算法瞳别。如果e = 3并且在明文當(dāng)中只有三分之二的比特是已知的揖盘，這種算法可以求出明文中所有的比特味咳。
并未找到真題钝侠。
0x04 低解密指數(shù)攻擊
介紹：
與低加密指數(shù)相同佣蓉，低解密指數(shù)可以加快解密的過程，但是者也帶來了安全問題垒棋。Wiener表示如果滿足：
$ d<frac{1}{3}gn^frac{1}{4}$
那么一種基于連分?jǐn)?shù)(一個(gè)數(shù)論當(dāng)中的問題)的特殊攻擊類型就可以危害RSA的安全卒煞。此時(shí)需要滿足：
$q<$$p$$<2q$
如果滿足上述條件痪宰，通過Wiener Attack可以在多項(xiàng)式時(shí)間中分解n叼架。
rsa-wiener-attack的攻擊源碼開源在了github中，采取python編寫衣撬，可以很容易使用乖订。
識(shí)別：
非常簡(jiǎn)單，e看起來很大就行了具练。
例題：
直接github用工具就行乍构。https://github.com/pablocelayes/rsa-wiener-attack
這里注意一個(gè)細(xì)節(jié)問題，如果在運(yùn)行腳本的時(shí)候報(bào)錯(cuò)扛点，請(qǐng)?jiān)谀_本前加上：
import sys
sys.setrecursionlimit(10000000)
0x05 共模攻擊
介紹：
如果在RSA的使用中使用了相同的模n對(duì)相同的明文m進(jìn)行了加密哥遮，那么就可以在不分解n的情況下還原出明文m的值。
即：
$ c_1equiv m^{e_1}$ $mod$ $n$
$ c_2equiv m^{e_2}$ $mod$ $n$
此時(shí)不需要分解n陵究，不需要求解私鑰眠饮，如果兩個(gè)加密指數(shù)互素，就可以通過共模攻擊在兩個(gè)密文和公鑰被嗅探到的情況下還原出明文m的值铜邮。
過程如下仪召，首先兩個(gè)加密指數(shù)互質(zhì)，則：
$ (e_1,e_2)=1 $
即存在$ s_2 $松蒜，$ s_2 $使得：
$ s_1e_1+s_2e_2=1 $
又因?yàn)椋?/p>
$ c_1equiv m^{e_1}$ $mod$ $n$
$ c_2equiv m^{e_2}$ $mod$ $n$
通過代入化簡(jiǎn)可以得出：
$c_1{s_1}c_2{s_2}equiv m$ $mod$ $n$
明文解出扔茅。
識(shí)別：
非常簡(jiǎn)單，若干次加密秸苗，每次n都一樣召娜，明文根據(jù)題意也一樣即可。
例題：
https://www.jarvisoj.com (very hard RSA)
如果已知：n1惊楼，n2玖瘸，c1吐句，c2，e1店读，e2嗦枢，并且其中n1=n2的話：
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
print s
n=n1
if s1<0:
s1 = - s1
c1 = modinv(c1, n)
elif s2<0:
s2 = - s2
c2 = modinv(c2, n)
m=(pow(c1,s1,n)*pow(c2,s2,n)) % n
**0x06 總結(jié) **
這里總結(jié)方法也不是全部的方法，但是希望能夠?qū)Υ蠹襌SA方面解題過程中能提供一些幫助屯断。這里推薦汪神的OJ系統(tǒng)文虏，里面題目多多，關(guān)于RSA也有不少殖演，可以在此練習(xí)：https://www.jarvisoj.com
