2018-noxCTF-Crypto-RSA

前言

2018-noxCTF的密码题中有许多RSA的题目，正好最近在看RSA，于是就做了一下，难度并不是很大

 

Chop Suey

题目如下

Today 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

推导完成后，写脚本即可

from 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)

得到结果

noxCTF{W31c0m3_70_Ch1n470wn}

 

Decryptor

题目如下

I 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过去后，得到提示

Please insert your ciphertext to decrypt in hex form:

所以看来服务器是会解密我们input的密文
那么这里就是一个典型的选择密文攻击，我们现在有
我们可以构造一个x，使得
然后我们把k发送过去，得到

Payload

所以这里就很简单了，我们构造x=2即可
即
所以我们Input k

hex((pow(2,e,N)*c)%N)[2:-1]

得到解密结果：

dcdef086a88cf660ea6ee6da68e46e66c8fa

我们解密即可得到flag

tmp = 0xdcdef086a88cf660ea6ee6da68e46e66c8fa
print libnum.n2s((tmp*gmpy2.invert(2,N))%N)

得到noxCTF{0u7sm4r73d}

 

WTF

题目如下

Um uhhhhhhhhh WTF IS THIS?! I give up. Now you try to solve this.

N = lObAbAbSBlZOOEBllOEbblTlOAbOlTSBATZBbOSAEZTZEAlSOggTggbTlEgBOgSllEEOEZZOSSAOlBlAgBBBBbbOOSSTOTEOllbZgElgbZSZbbSTTOEBZZSBBEEBTgESEgAAAlAOAEbTZBZZlOZSOgBAOBgOAZEZbOBZbETEOSBZSSElSSZlbBSgbTBOTBSBBSOZOAEBEBZEZASbOgZBblbblTSbBTObAElTSTOlSTlATESEEbSTBOlBlZOlAOETAZAgTBTSAEbETZOlElBEESObbTOOlgAZbbOTBOBEgAOBAbZBObBTg

e = lBlbSbTASTTSZTEASTTEBOOAEbEbOOOSBAgABTbZgSBAZAbBlBBEAZlBlEbSSSETAlSOlAgAOTbETAOTSZAZBSbOlOOZlZTETAOSSSlTZOElOOABSZBbZTSAZSlASTZlBBEbEbOEbSTAZAZgAgTlOTSEBEAlObEbbgZBlgOEBTBbbSZAZBBSSZBOTlTEAgBBSZETAbBgEBTATgOZBTllOOSSTlSSTOSSZSZAgSZATgbSOEOTgTTOAABSZEZBEAZBOOTTBSgSZTZbOTgZTTElSOATOAlbBZTBlOTgOSlETgTBOglgETbT

c = SOSBOEbgOZTZBEgZAOSTTSObbbbTOObETTbBAlOSBbABggTOBSObZBbbggggZZlbBblgEABlATBESZgASBbOZbASbAAOZSSgbAOZlEgTAlgblBTbBSTAEBgEOEbgSZgSlgBlBSZOObSlgAOSbbOOgEbllAAZgBATgEAZbBEBOAAbZTggbOEZSSBOOBZZbAAlTBgBOglTSSESOTbbSlTAZATEOZbgbgOBZBBBBTBTOSBgEZlOBTBSbgbTlZBbbOBbTSbBASBTlglSEAEgTOSOblAbEgBAbOlbOETAEZblSlEllgTTbbgb

题目分析

拿到题目，乍一看非常奇怪，因为(n,e,c)都是编码过的，我们没有办法直接破解，尝试了一些常见编码方式，都无法破解，于是统计了一下

for i in (N,e,c):
    print list(collections.Counter(i))

得到结果

['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
即

dict = {
'O' : '0',
'l' : '1',
'Z' : '2',
'E' : '3',
'A' : '4',
'S' : '5',
'b' : '6',
'T' : '7',
'B' : '8',
'g' : '9'
}

然后写脚本替换

for 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极大

18165674577527345773800436360005849487629584246818834218136555374150149407637407524285601002127374055517203100485286275425145721883636036574242949710753834106366928190387866524288552807173498852374689387479028711005571557055252495247965030797704485232834280077859527260792773150470416827810790513797809193767

于是想到winner攻击

payload

使用github的winner attack的脚本

https://github.com/pablocelayes/rsa-wiener-attack

运行

➜  rsa-wiener-attack-master python RSAwienerHacker.py
Hacked!
noxCTF{RSA_1337_10rd}

 

Trinity

题目如下

Neo, 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，但是都没有结果
发现一直报错

ZeroDivisionError: invert() no inverse exists

想到题目给的数字可能有问题，仔细观察，发现只有0-4
于是想到5进制
转一波以后就正常了

Payload

import gmpy2
import gmpy
import libnum
def boradcast_fuzz(question,e):
    N=1
    for i in range(len(question)):
        N *= question[i]['n']
    N_list = []
    for i in range(len(question)):
        N_list.append(N / question[i]['n'])
    t_list = []
    for i in range(len(question)):
        t_list.append(int(gmpy2.invert(N_list[i], question[i]['n'])))
    sum = 0
    for i in range(len(question)):
        sum = (sum + question[i]['c'] * t_list[i] * N_list[i]) % N
    sum = gmpy.root(sum, e)[0]
    return libnum.n2s(sum)
n1 = int(str(n1),5)
n2 = int(str(n2),5)
n3 = int(str(n3),5)
c1 = int(str(c1),5)
c2 = int(str(c2),5)
c3 = int(str(c3),5)

question=[
{'n':n1,'c':c1},
{'n': n2, 'c': c2},
{'n':n3,'c':c3},
]


for i in range(2,20):
    res = boradcast_fuzz(question,i)
    if 'noxCTF' in res:
        print res
        print 'e=%d'%(i)
        break

得到结果

noxCTF{D4mn_y0u_h4s74d_wh47_4_b100dy_b4s74rd!}
e=3

 

拓展-Boneh and Durfee attack

由于题目中有一道Wiener’s Attack，于是我联想到了最近看的

Boneh and Durfee attack

我们知道，如果要使用Wiener’s Attack，有一个特征，即e很大，那么到底有多大？
这里有一个评判标准，即
那么如果e很大，但d比这里的限定值大怎么办？
那么可以尝试Boneh and Durfee attack
其使用标准为
比如这次题目里

d=33859466522204630502415021058361047681307615225229354334148022345758288750359
n=106464658120038110366171046017584728605432723415099799671398095113303220554018149888866005570730116293196252665770382258833879353944414043672822102509840890423260826373058255315521685967807858850204383823245609286166175687064317570157147353365780181201403742497875436372013183350667001942660780839408462806879

我们简单比较下

N1 = 1.0/3*pow(n,1.0/4)
N2 = pow(n,0.292)
print int(N1)-d
print int(N2)-d

得到结果

941571295587957309748289456353490745482373040518812393691369

878909169550944842698019812370775334246473513796204883182700468007058108344282016448403689

明显Boneh and Durfee attack给的空间更大，所以如果我们在不能使用Wiener’s Attack的时候，可以尝试Boneh and Durfee attack
利用脚本

https://github.com/mimoo/RSA-and-LLL-attacks