1 | 文章首发于安全客 https://www.anquanke.com/post/id/159304 |
前言
2018-noxCTF的密码题中有许多RSA的题目,正好最近在看RSA,于是就做了一下,难度并不是很大
Chop Suey
题目如下1
2
3
4
5
6
7Today I ate in a Chinese restaurant and got myself a fortune cookie. These things usually contain a note with a nice sentence or phrase, but mine had numbers in it instead! Can you help me find the meaning of the numbers?
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
题目分析
还是先摆出已知条件
我们的目标很简单,如何从这些式子得到答案
首先根据
因为
利用中国剩余定理,我们可以得到
由式1可以得到
我们把这个带入式2
可以得到
等式两边同时减去m1,可以得到
这里因为
所以可以求p的逆元,得到
所以这里得到如下两个式子
我们上下两个式子合并,得到
最后可以有
那么问题来了
这里的m1和m2怎么求?
这时候我们有
那么分别带入,有
所以我们有
Payload
推导完成后,写脚本即可1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17from Crypto.Util import number
import gmpy2
import libnum
def decrypt(dp,dq,p,q,c):
InvQ = gmpy2.invert(q, p)
mp = pow(c, dp, p)
mq = pow(c, dq, q)
m = (((mp-mq)*InvQ) % p)*q+mq
print libnum.n2s(m)
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
decrypt(dp,dq,p,q,c)
得到结果1
noxCTF{W31c0m3_70_Ch1n470wn}
Decryptor
题目如下1
2
3
4
5
6
7
8I created this nice decryptor for RSA ciphertexts, you should try it out!
nc chal.noxale.com 4242
Oh, and someone told me to give this to you:
N = 140165355674296399459239442258630641339281917770736077969396713192714338090714726890918178888723629353043167144351074222216025145349467583141291274172356560132771690830020353668100494447956043734613525952945037667879068512918232837185005693504551982611886445611514773529698595162274883360353962852882911457919
c = 86445915530920147553767348020686132564453377048106098831426077547738998373682256014690928256854752252580894971618956714013602556152722531577337080534714463052378206442086672725486411296963581166836329721403101091377505869510101752378162287172126836920825099014089297075416142603776647872962582390687281063434
e = 65537
题目分析
我们nc过去后,得到提示1
Please insert your ciphertext to decrypt in hex form:
所以看来服务器是会解密我们input的密文
那么这里就是一个典型的选择密文攻击,我们现在有
我们可以构造一个x,使得
然后我们把k发送过去,得到
Payload
所以这里就很简单了,我们构造x=2
即可
即
所以我们Input k
1 | hex((pow(2,e,N)*c)%N)[2:-1] |
得到解密结果:1
dcdef086a88cf660ea6ee6da68e46e66c8fa
我们解密即可得到flag1
2tmp = 0xdcdef086a88cf660ea6ee6da68e46e66c8fa
print libnum.n2s((tmp*gmpy2.invert(2,N))%N)
得到noxCTF{0u7sm4r73d}
WTF
题目如下1
2
3
4
5
6
7Um uhhhhhhhhh WTF IS THIS?! I give up. Now you try to solve this.
N = lObAbAbSBlZOOEBllOEbblTlOAbOlTSBATZBbOSAEZTZEAlSOggTggbTlEgBOgSllEEOEZZOSSAOlBlAgBBBBbbOOSSTOTEOllbZgElgbZSZbbSTTOEBZZSBBEEBTgESEgAAAlAOAEbTZBZZlOZSOgBAOBgOAZEZbOBZbETEOSBZSSElSSZlbBSgbTBOTBSBBSOZOAEBEBZEZASbOgZBblbblTSbBTObAElTSTOlSTlATESEEbSTBOlBlZOlAOETAZAgTBTSAEbETZOlElBEESObbTOOlgAZbbOTBOBEgAOBAbZBObBTg
e = lBlbSbTASTTSZTEASTTEBOOAEbEbOOOSBAgABTbZgSBAZAbBlBBEAZlBlEbSSSETAlSOlAgAOTbETAOTSZAZBSbOlOOZlZTETAOSSSlTZOElOOABSZBbZTSAZSlASTZlBBEbEbOEbSTAZAZgAgTlOTSEBEAlObEbbgZBlgOEBTBbbSZAZBBSSZBOTlTEAgBBSZETAbBgEBTATgOZBTllOOSSTlSSTOSSZSZAgSZATgbSOEOTgTTOAABSZEZBEAZBOOTTBSgSZTZbOTgZTTElSOATOAlbBZTBlOTgOSlETgTBOglgETbT
c = SOSBOEbgOZTZBEgZAOSTTSObbbbTOObETTbBAlOSBbABggTOBSObZBbbggggZZlbBblgEABlATBESZgASBbOZbASbAAOZSSgbAOZlEgTAlgblBTbBSTAEBgEOEbgSZgSlgBlBSZOObSlgAOSbbOOgEbllAAZgBATgEAZbBEBOAAbZTggbOEZSSBOOBZZbAAlTBgBOglTSSESOTbbSlTAZATEOZbgbgOBZBBBBTBTOSBgEZlOBTBSbgbTlZBbbOBbTSbBASBTlglSEAEgTOSOblAbEgBAbOlbOETAEZblSlEllgTTbbgb
题目分析
拿到题目,乍一看非常奇怪,因为(n,e,c)
都是编码过的,我们没有办法直接破解,尝试了一些常见编码方式,都无法破解,于是统计了一下1
2for i in (N,e,c):
print list(collections.Counter(i))
得到结果1
2
3['A', 'B', 'E', 'g', 'l', 'O', 'S', 'b', 'T', 'Z']
['A', 'B', 'E', 'g', 'l', 'O', 'S', 'b', 'T', 'Z']
['A', 'B', 'E', 'g', 'l', 'O', 'S', 'b', 'T', 'Z']
发现都一样,并且长度为10,这里就需要开个脑洞了
将字母象形为0-9
即1
2
3
4
5
6
7
8
9
10
11
12dict = {
'O' : '0',
'l' : '1',
'Z' : '2',
'E' : '3',
'A' : '4',
'S' : '5',
'b' : '6',
'T' : '7',
'B' : '8',
'g' : '9'
}
然后写脚本替换1
2
3
4
5
6
7for key,value in dict.items():
N = N.replace(key,value)
c = c.replace(key,value)
e = e.replace(key,value)
n = int(N)
c = int(c)
e = int(e)
发现e极大1
18165674577527345773800436360005849487629584246818834218136555374150149407637407524285601002127374055517203100485286275425145721883636036574242949710753834106366928190387866524288552807173498852374689387479028711005571557055252495247965030797704485232834280077859527260792773150470416827810790513797809193767
于是想到winner攻击
payload
使用github的winner attack的脚本1
https://github.com/pablocelayes/rsa-wiener-attack
运行1
2
3➜ rsa-wiener-attack-master python RSAwienerHacker.py
Hacked!
noxCTF{RSA_1337_10rd}
Trinity
题目如下1
2
3
4
5
6
7
8
9
10Neo, you are the chosen one. The only person who can make sense of these numbers. Do it.
N = 331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004
c = 310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243
N = 302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114
c = 112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344
N = 332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323
c = 10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242
题目分析
看到3组(n,c),第一反应想到的就是低指数广播攻击,即我们有
根据中国剩余定理,可以有通解
其中
但是由于这里没有给e,又因为低指数,于是我选择爆破了一下e,但是都没有结果
发现一直报错1
ZeroDivisionError: invert() no inverse exists
想到题目给的数字可能有问题,仔细观察,发现只有0-4
于是想到5进制
转一波以后就正常了
Payload
1 | import gmpy2 |
得到结果1
2noxCTF{D4mn_y0u_h4s74d_wh47_4_b100dy_b4s74rd!}
e=3
拓展-Boneh and Durfee attack
由于题目中有一道Wiener’s Attack,于是我联想到了最近看的1
Boneh and Durfee attack
我们知道,如果要使用Wiener’s Attack,有一个特征,即e很大,那么到底有多大?
这里有一个评判标准,即
那么如果e很大,但d比这里的限定值大怎么办?
那么可以尝试Boneh and Durfee attack
其使用标准为
比如这次题目里1
2d=33859466522204630502415021058361047681307615225229354334148022345758288750359
n=106464658120038110366171046017584728605432723415099799671398095113303220554018149888866005570730116293196252665770382258833879353944414043672822102509840890423260826373058255315521685967807858850204383823245609286166175687064317570157147353365780181201403742497875436372013183350667001942660780839408462806879
我们简单比较下1
2
3
4N1 = 1.0/3*pow(n,1.0/4)
N2 = pow(n,0.292)
print int(N1)-d
print int(N2)-d
得到结果1
2
3941571295587957309748289456353490745482373040518812393691369
878909169550944842698019812370775334246473513796204883182700468007058108344282016448403689
明显Boneh and Durfee attack给的空间更大,所以如果我们在不能使用Wiener’s Attack的时候,可以尝试Boneh and Durfee attack
利用脚本1
https://github.com/mimoo/RSA-and-LLL-attacks