Jarvis OJ -- crypto题（中）

发表于 | 更新于 | 分类于
Jarvis OJ -- crypto题（中）

Jarvis’s encryption system

Let’s play with Jarvis’s new encryption box.

nc pwn.jarvisoj.com 9880

题目来源：基于BCTF2016 hyperRSA改编。

Hint1: 此题需要一定量的爆破。

题目给了一个py，一个png

crypto500.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#!/usr/bin/env python

from Crypto.PublicKey import RSA
import gmpy2

key = RSA.importKey(open('private.pem').read())

N = 808637320166213096433765975908829772554859069394497436792703828416763985949910999652518305818627321094257781267795371106923808192073932662313603219525599014635435542122940843344921727149256852355110338886574805360544004118210641173633231100848831019159519744863314748281129830905559513810272933968408858616937223539622595750248885831720830102914499513408356858587797522763592193335162884129664298938995394243273615798207065590802899685489088903478734288977143851327400816886878238915788561611104380001569848016035186213716602462262685777960742683591155978590371074585063550419528377002596163321548052257322263024813745933243795081592986850478573362522245788630785664119935566422559659277401321793012274415007906726880710258434953224297253000176721652344571059040066987969691706315602374506498087282531643212970147526356421919309049062439117990930204486012562031589114880474346559407445496718773030816258262150397230280669274725009415653773469037623986165899557423095323109994543129373149980880777219450714265152054529287453826506032747047856303879606356141420416161004589629524370677871918513405209191951229311529443558187652701599377904802383252318582028816524498306240682160249309341335405511246150908708558397938689907425750101507

p = key.p
q = key.q


def encrypt(m, e):
    return pow(m, e, N)


def main():
    print 'Welcome to Jarvis\'s encryption system.Let\'s init the cipher first:'
    print "e:",
    e = int(raw_input().strip())
    d = gmpy2.invert(e, (p - 1) * (q - 1))
    print "d: %d" % d

    cnt = 0
    while True:
        cnt += 1
        print "m%d:" % cnt,
        m = int(raw_input().strip())
        c = encrypt(m, e)
        print "c%d: %d" % (cnt, c)
        print ''


if __name__ == '__main__':
    main()

flag.png
flag

在线ocr提取一下图片中的数字：

1
2
3
4
5
Welcome to Jarvis's encryption system.Let's init the cipher first:
m1: 89372489723987498237894327984372
c1: 792279062886162218096642776664224514933347584486280723004734021586336212749049858600481963227286459323970478541843083793725468708921717787221937249530784012084036132167698694870670989692185525559265359595824727956010042190235432643115112280623082788133230708728369892499755238276075667536752879449115011933006031581738186877618805996280847737363426887886868682686959858371130406926178828888575004380515988821399247906070333132810952695798429265793849588130806947806841034544612000197604854503195512120025729616966658790540157838337703936086683817085220432748606686965902101050255048796382841321391071407100767404596588780879740560771450534303617347553555472893929700798373187625224545676303975128589469709553887522697982505366205159178754377849727155295773459020853899833570753142832536760229326028534739725856990225488803963836214548294423502322319111713836053680359093114158912017408230992904911531693795674356749450578360594750306010644345865018135713049088702085668117922755659876667178408188245170381487842104129405699987082399408416605832498886309106565903612880735897179022046135207448286905927468981921408174446350113407999312543013150441972687118445672308468055301677455644948365453703227341347327118261153884632046860369729
m2: flag here
c2: 738822002752800877524466308025949155169562722946933006009883884249589602039677687891359871510923927357766748131398443497541198900771818831638644263405425815579383553019562159083788644122365536627592737115316351290153544908592280731090451811311680698586032725090719266003369555867584457372823678746133588560994163232730766388456903527206840527304843529539480355012405496730615078972755415860013097394363116913629756292725693596880188792245847698225435105827398989245800248197290718407831242734331874121327502564673597694670795036098967372950089253263743880807024448724715652660602771818683520844873803372738417012436219777372987997036211306992938395670636075660990930360358970016244484405618827909229400111542660072678812089441010001235353317911131109787281238112284352067511452432985149442969693926797740772628154057474332702139775407456229918917403138849681496015981718513476254353617586634306067889050783266988506871489696817574207289110594169371818597141857443042841485880477066344316648550850088971005108756497748568090122624591451915965314486079436499049418137147522360690326710468200339550170216543240318289067712843687012174036874897324652429812609807952220427326987655148639613323665786093803557065570465270944069296977739085

只知道一个不能分解的N，一段知道明文的密文，一段不知道明文的密文。理论上爆破出e，然后去服务端输入e就能得到d，于是我这样爆破

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
N = 808637320166213096433765975908829772554859069394497436792703828416763985949910999652518305818627321094257781267795371106923808192073932662313603219525599014635435542122940843344921727149256852355110338886574805360544004118210641173633231100848831019159519744863314748281129830905559513810272933968408858616937223539622595750248885831720830102914499513408356858587797522763592193335162884129664298938995394243273615798207065590802899685489088903478734288977143851327400816886878238915788561611104380001569848016035186213716602462262685777960742683591155978590371074585063550419528377002596163321548052257322263024813745933243795081592986850478573362522245788630785664119935566422559659277401321793012274415007906726880710258434953224297253000176721652344571059040066987969691706315602374506498087282531643212970147526356421919309049062439117990930204486012562031589114880474346559407445496718773030816258262150397230280669274725009415653773469037623986165899557423095323109994543129373149980880777219450714265152054529287453826506032747047856303879606356141420416161004589629524370677871918513405209191951229311529443558187652701599377904802383252318582028816524498306240682160249309341335405511246150908708558397938689907425750101507
m1 = 89372489723987498237894327984372
c1 = 792279062886162218096642776664224514933347584486280723004734021586336212749049858600481963227286459323970478541843083793725468708921717787221937249530784012084036132167698694870670989692185525559265359595824727956010042190235432643115112280623082788133230708728369892499755238276075667536752879449115011933006031581738186877618805996280847737363426887886868682686959858371130406926178828888575004380515988821399247906070333132810952695798429265793849588130806947806841034544612000197604854503195512120025729616966658790540157838337703936086683817085220432748606686965902101050255048796382841321391071407100767404596588780879740560771450534303617347553555472893929700798373187625224545676303975128589469709553887522697982505366205159178754377849727155295773459020853899833570753142832536760229326028534739725856990225488803963836214548294423502322319111713836053680359093114158912017408230992904911531693795674356749450578360594750306010644345865018135713049088702085668117922755659876667178408188245170381487842104129405699987082399408416605832498886309106565903612880735897179022046135207448286905927468981921408174446350113407999312543013150441972687118445672308468055301677455644948365453703227341347327118261153884632046860369729


def encrypt(m, e):
    return pow(m, e, N)


for i in range(1000000):
    c = encrypt(m1, i)
    print i
    if c == c1:
        print 'e: %d' % i
        break

如上，我爆破了1000000，还是没有爆破出来，说明e有点大，这样爆破可能明年就能做出这题了。换个思路，这里看到提示

题目来源：基于BCTF2016 hyperRSA改编。

然后谷歌BCTF 2016 hyper RSA找到这个

https://grocid.net/2016/03/24/bctf-hyper-rsa-partial-write-up/

我理解的意思是先根据n，e，d解出p和q，然后再穷举攻击，所以还是得爆破，本来以为这样爆破的速度快一点，结果发现速度更慢了，excuse me，感觉这题改编的和原题一点都不像，不能按上面链接的那个思路，还是老老实实爆破e吧，这里记录一下得到p，q的过程，和本题无关

根据n，e，d解出p和q我们用rsatool来做

安装rsatool

1
2
3
git clone https://github.com/ius/rsatool.git
cd rsatool
python setup.py install

安装gmpy时可能会报错，不过在（上）中我们已经安装了gmpy2了，而且看到rsatool.py的开头，

1
2
3
4
5
6
7
try:
    import gmpy
except ImportError as e:
    try:
        import gmpy2 as gmpy
    except ImportError:
        raise e

所以不需要再去安gmpy了

先去自己搞个e，d，如

1
2
3
4
➜  ~ nc pwn.jarvisoj.com 9880
Welcome to Jarvis's encryption system.Let's init the cipher first:
e: 12345
d: 201356915527820093838590247869075959565300670661699888270617381008759213674364229480100548569174595791312144156922071347321489378893095909595141052800461026406587999715343876261019796618616084579960241534008177535707757688082584930558813479466124467630325127234494089608440105322291611620314216202421128504533416375925464506785344272718495887918928432905410205208496523691800923638095642431315354794529918339718355201594857806895756470894569403749990215011400583149488060843277740496325154993319956591723427525418563177072890722478371493029673795816866219375196491152246687240958301409961976998820470849656430663286940461573658530706920751204584928314511527848932364909480262481771973980401259537991290562234025866097602539853912980185823807829336228072050786680235009860665712273945365084597149021027979295475982762918274831787872437578386202106209918943005520433768199111496786661297419031437065511891561694954596320600362045032143402360451033935757012176534340874526429735666279970953464963828325846439119588268406895121820266798459368907873035613676994065206516383402542718175309215036737597352281817964369266908506553518026519971286354947917971368166585913520185398205139859199725823771675331562803357914714179340973647678752889

新建一个get_pq.py

1
2
3
4
5
6
7
from rsatool import factor_modulus

e = 12345
d = 201356915527820093838590247869075959565300670661699888270617381008759213674364229480100548569174595791312144156922071347321489378893095909595141052800461026406587999715343876261019796618616084579960241534008177535707757688082584930558813479466124467630325127234494089608440105322291611620314216202421128504533416375925464506785344272718495887918928432905410205208496523691800923638095642431315354794529918339718355201594857806895756470894569403749990215011400583149488060843277740496325154993319956591723427525418563177072890722478371493029673795816866219375196491152246687240958301409961976998820470849656430663286940461573658530706920751204584928314511527848932364909480262481771973980401259537991290562234025866097602539853912980185823807829336228072050786680235009860665712273945365084597149021027979295475982762918274831787872437578386202106209918943005520433768199111496786661297419031437065511891561694954596320600362045032143402360451033935757012176534340874526429735666279970953464963828325846439119588268406895121820266798459368907873035613676994065206516383402542718175309215036737597352281817964369266908506553518026519971286354947917971368166585913520185398205139859199725823771675331562803357914714179340973647678752889
n = 808637320166213096433765975908829772554859069394497436792703828416763985949910999652518305818627321094257781267795371106923808192073932662313603219525599014635435542122940843344921727149256852355110338886574805360544004118210641173633231100848831019159519744863314748281129830905559513810272933968408858616937223539622595750248885831720830102914499513408356858587797522763592193335162884129664298938995394243273615798207065590802899685489088903478734288977143851327400816886878238915788561611104380001569848016035186213716602462262685777960742683591155978590371074585063550419528377002596163321548052257322263024813745933243795081592986850478573362522245788630785664119935566422559659277401321793012274415007906726880710258434953224297253000176721652344571059040066987969691706315602374506498087282531643212970147526356421919309049062439117990930204486012562031589114880474346559407445496718773030816258262150397230280669274725009415653773469037623986165899557423095323109994543129373149980880777219450714265152054529287453826506032747047856303879606356141420416161004589629524370677871918513405209191951229311529443558187652701599377904802383252318582028816524498306240682160249309341335405511246150908708558397938689907425750101507

print factor_modulus(n, d, e)

执行得到p和q

1
2
➜  rsatool git:(master) ✗ python get_pq.py
(27200154960954227235541819668009472012084286261734091722170154481644756866164527250830540275835506132703525181946061278474016037684976554417523086836831359548636853015984589908613534046005317727141826672590441878984810812783493735937537688532183221554822925253529608362391669124208763896128072575179396699623562847543761634607862389921729915536387801522541553962435180388095592872002991464363762976666060101937325707664414266166368945403841659913817298126829937148569179681290426604950786796380764431701519236947537978114396818142372228177619800336261973442683963482889536869167264816021933025822891275282558513928279L, 29729143871680528751740142119100596543134632399647397265497654715939443094184918167923383261983609500477990736235614419561382430137607621816853595552473874320617275905995651998776069698909071999346881132724516330101583472405523543921649250704165298312036068472395012578017885338290580565995781070427078565789924061087799055006909151787170102655896030290882335570861323074011189512021087001712931962221353481078772508888453639684477267704904921538633637138014338076307696912393557877527097168734733786901104596613726641973212386174566867834116990132542399691508959274527499752566503084136140055299008389146766847687733L)

扯完废话，改进一下脚本然后放到服务器上跑，这次跑0到100000000，根据log的输出预算时间为21小时，先去看后面的题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import logging

logging.basicConfig(level=logging.DEBUG,
                    filename='rsa.log',
                    filemode='a',
                    format='%(asctime)s : %(message)s')
N = 808637320166213096433765975908829772554859069394497436792703828416763985949910999652518305818627321094257781267795371106923808192073932662313603219525599014635435542122940843344921727149256852355110338886574805360544004118210641173633231100848831019159519744863314748281129830905559513810272933968408858616937223539622595750248885831720830102914499513408356858587797522763592193335162884129664298938995394243273615798207065590802899685489088903478734288977143851327400816886878238915788561611104380001569848016035186213716602462262685777960742683591155978590371074585063550419528377002596163321548052257322263024813745933243795081592986850478573362522245788630785664119935566422559659277401321793012274415007906726880710258434953224297253000176721652344571059040066987969691706315602374506498087282531643212970147526356421919309049062439117990930204486012562031589114880474346559407445496718773030816258262150397230280669274725009415653773469037623986165899557423095323109994543129373149980880777219450714265152054529287453826506032747047856303879606356141420416161004589629524370677871918513405209191951229311529443558187652701599377904802383252318582028816524498306240682160249309341335405511246150908708558397938689907425750101507
m1 = 89372489723987498237894327984372
c1 = 792279062886162218096642776664224514933347584486280723004734021586336212749049858600481963227286459323970478541843083793725468708921717787221937249530784012084036132167698694870670989692185525559265359595824727956010042190235432643115112280623082788133230708728369892499755238276075667536752879449115011933006031581738186877618805996280847737363426887886868682686959858371130406926178828888575004380515988821399247906070333132810952695798429265793849588130806947806841034544612000197604854503195512120025729616966658790540157838337703936086683817085220432748606686965902101050255048796382841321391071407100767404596588780879740560771450534303617347553555472893929700798373187625224545676303975128589469709553887522697982505366205159178754377849727155295773459020853899833570753142832536760229326028534739725856990225488803963836214548294423502322319111713836053680359093114158912017408230992904911531693795674356749450578360594750306010644345865018135713049088702085668117922755659876667178408188245170381487842104129405699987082399408416605832498886309106565903612880735897179022046135207448286905927468981921408174446350113407999312543013150441972687118445672308468055301677455644948365453703227341347327118261153884632046860369729


def encrypt(m, e):
    return pow(m, e, N)


for i in xrange(100000000):
    if i % 10000 == 0:
        logging.debug('Brute Force e: %d' % i)
    c = encrypt(m1, i)
    if c == c1:
        logging.info('Find e: %d' % i)
        break

吃了个晚饭，看了集黑客军团，登陆服务器一看，爆破出来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
root:~# head rsa.log
2017-12-01 19:38:00,250 : Brute Force e: 0
2017-12-01 19:38:04,344 : Brute Force e: 10000
2017-12-01 19:38:09,663 : Brute Force e: 20000
2017-12-01 19:38:15,528 : Brute Force e: 30000
2017-12-01 19:38:21,614 : Brute Force e: 40000
2017-12-01 19:38:27,950 : Brute Force e: 50000
2017-12-01 19:38:34,411 : Brute Force e: 60000
2017-12-01 19:38:41,028 : Brute Force e: 70000
2017-12-01 19:38:47,804 : Brute Force e: 80000
2017-12-01 19:38:54,710 : Brute Force e: 90000
root:~# tail rsa.log
2017-12-01 21:47:08,037 : Brute Force e: 7760000
2017-12-01 21:47:18,886 : Brute Force e: 7770000
2017-12-01 21:47:29,725 : Brute Force e: 7780000
2017-12-01 21:47:40,583 : Brute Force e: 7790000
2017-12-01 21:47:51,453 : Brute Force e: 7800000
2017-12-01 21:48:02,286 : Brute Force e: 7810000
2017-12-01 21:48:13,143 : Brute Force e: 7820000
2017-12-01 21:48:24,017 : Brute Force e: 7830000
2017-12-01 21:48:34,867 : Brute Force e: 7840000
2017-12-01 21:48:41,113 : Find e: 7845741

可以看到，爆破用时2h 10min 41s，出题人一点都不友好

然后可以通过上面得到的p和q来得到e=7845741时的d

1
2
3
4
5
import libnum
p = 27200154960954227235541819668009472012084286261734091722170154481644756866164527250830540275835506132703525181946061278474016037684976554417523086836831359548636853015984589908613534046005317727141826672590441878984810812783493735937537688532183221554822925253529608362391669124208763896128072575179396699623562847543761634607862389921729915536387801522541553962435180388095592872002991464363762976666060101937325707664414266166368945403841659913817298126829937148569179681290426604950786796380764431701519236947537978114396818142372228177619800336261973442683963482889536869167264816021933025822891275282558513928279
q = 29729143871680528751740142119100596543134632399647397265497654715939443094184918167923383261983609500477990736235614419561382430137607621816853595552473874320617275905995651998776069698909071999346881132724516330101583472405523543921649250704165298312036068472395012578017885338290580565995781070427078565789924061087799055006909151787170102655896030290882335570861323074011189512021087001712931962221353481078772508888453639684477267704904921538633637138014338076307696912393557877527097168734733786901104596613726641973212386174566867834116990132542399691508959274527499752566503084136140055299008389146766847687733
d = libnum.invmod(7845741, (p - 1) * (q - 1))
# d = 624460328909915360701402168639641282028094468418961878947574807290638891758678991143435088653980701535371225162050430031333639072505365342535152293096454464491608234713910040741806054032872119204341656042243036836513731486079394171780995659012791615808025872985542653518800484827924355387767430294123689221121329057758535673622344148467540232245253256875196052350040448617224502051601181938246394036842235391465615724331125440683500889291172253639404968619326290436776700446299000007994603663440301337649478949521483497552296109838827309290662620012954396232530653067994746179325738761837228276717554780296018709380622306541045859622715377902354561164951333797443088787938481179135106105790091663516291819506679417163921126064227724274720567814644923715786512409941352289194976639518315198223889636540907899742620702027181209723760906029440110133038012652837512150214031930229627563605747245442722777826347211476418833664939434587222857079580932195626606642019627685477852118740507133047312988551945249158637120933025247874896831420739652406553559282198158772718455703088272187706565621125165787151495212884395636011063049499722644316616892917352706474956487897928799493388647214180485284836266930315584778253034297866155428036121429

我们可以去服务端验证一下

1
2
3
4
➜  ~ nc pwn.jarvisoj.com 9880
Welcome to Jarvis's encryption system.Let's init the cipher first:
e: 7845741
d: 624460328909915360701402168639641282028094468418961878947574807290638891758678991143435088653980701535371225162050430031333639072505365342535152293096454464491608234713910040741806054032872119204341656042243036836513731486079394171780995659012791615808025872985542653518800484827924355387767430294123689221121329057758535673622344148467540232245253256875196052350040448617224502051601181938246394036842235391465615724331125440683500889291172253639404968619326290436776700446299000007994603663440301337649478949521483497552296109838827309290662620012954396232530653067994746179325738761837228276717554780296018709380622306541045859622715377902354561164951333797443088787938481179135106105790091663516291819506679417163921126064227724274720567814644923715786512409941352289194976639518315198223889636540907899742620702027181209723760906029440110133038012652837512150214031930229627563605747245442722777826347211476418833664939434587222857079580932195626606642019627685477852118740507133047312988551945249158637120933025247874896831420739652406553559282198158772718455703088272187706565621125165787151495212884395636011063049499722644316616892917352706474956487897928799493388647214180485284836266930315584778253034297866155428036121429

最后一步，用d解密

1
2
3
4
c2 = 738822002752800877524466308025949155169562722946933006009883884249589602039677687891359871510923927357766748131398443497541198900771818831638644263405425815579383553019562159083788644122365536627592737115316351290153544908592280731090451811311680698586032725090719266003369555867584457372823678746133588560994163232730766388456903527206840527304843529539480355012405496730615078972755415860013097394363116913629756292725693596880188792245847698225435105827398989245800248197290718407831242734331874121327502564673597694670795036098967372950089253263743880807024448724715652660602771818683520844873803372738417012436219777372987997036211306992938395670636075660990930360358970016244484405618827909229400111542660072678812089441010001235353317911131109787281238112284352067511452432985149442969693926797740772628154057474332702139775407456229918917403138849681496015981718513476254353617586634306067889050783266988506871489696817574207289110594169371818597141857443042841485880477066344316648550850088971005108756497748568090122624591451915965314486079436499049418137147522360690326710468200339550170216543240318289067712843687012174036874897324652429812609807952220427326987655148639613323665786093803557065570465270944069296977739085
m2 = pow(c2, d, N)
print libnum.n2s(m2)
# WUSTCTF{U_r_real33y_m4st3r_0f_math}

影之密码

请分析下列密文进行解密 8842101220480224404014224202480122 得到flag，flag为8位大写字母

题目来源：CFF2016

1
2
3
4
5
6
7
8
9
import string
flag = ''
for i in '8842101220480224404014224202480122'.split('0'):
    n = 0
    for j in i:
        n += int(j)
    flag += string.uppercase[n - 1]
print flag
# WELLDONE

好多盐

某遗留系统采用固定格式+6-10位数字类型密码，今天他们发生了数据泄露事件，已知固定格式为{FLAG:}，做为一名黑客，你要开始干活了。字符串长度为10位

题目来源：CFF2016

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import hashlib
import logging

logging.basicConfig(level=logging.DEBUG,
                    format='%(asctime)s : %(message)s')
password = '''f09ebdb2bb9f5eb4fbd12aad96e1e929 p5Zg6LtD
6cea25448314ddb70d98708553fc0928 ZwbWnG0j
2629906b029983a7c524114c2dd9cc36 1JE25XOn
2e854eb55586dc58e6758cfed62dd865 ICKTxe5j
7b073411ee21fcaf177972c1a644f403 0wdRCo1W
6795d1be7c63f30935273d9eb32c73e3 EuMN5GaH
d10f5340214309e3cfc00bbc7a2fa718 aOrND9AB
8e0dc02301debcc965ee04c7f5b5188b uQg6JMcx
4fec71840818d02f0603440466a892c9 XY5QnHmU
ee8f46142f3b5d973a01079f7b47e81c zMVNlHOr
e4d9e1e85f3880aedb7264054acd1896 TqRhn1Yp
0fd046d8ecddefc66203f6539cac486b AR5lI2He
f6326f02adaa31a66ed06ceab2948d01 Aax2fIPl
720ba10d446a337d79f1da8926835a49 ZAOYDPR2
06af8bcc454229fe5ca09567a9071e62 hvcECKYs
79f58ca7a81ae2775c2c2b73beff8644 TgFacoR3
46aaa5a7fef5e250a2448a8d1257e9cf GLYu0NO4
2149ac87790dd0fe1b43f40d527e425a 5Xk2O1sG
d15a36d8be574ac8fe64689c728c268e aZikhUEy
ff7bced91bd9067834e3ad14cc1464cd E7UROqXn
8cc0437187caf10e5eda345cb6296252 XPin3mVB
5cfcdca4a9cb2985a0b688406617689e nsGqoafv
5a7dfa8bc7b5dfbb914c0a78ab2760c6 YC1qZUFR
8061d8f222167fcc66569f6261ddd3cc wNgQi615
3d8a02528c949df7405f0b48afe4a626 CO2NMusb
70651acbc8bd027529bbcccdbf3b0f14 CAXVjFMd
a9dbe70e83596f2d9210970236bdd535 TL6sjEuK
9ed6ef5780f705ade6845b9ef349eb8f tJ90ibsz
4b46fac0c41b0c6244523612a6c7ac4a VTjOSNmw
8141e6ecb4f803426d1db8fbeb5686ef lh75cdNC
df803949fd13f5f7d7dd8457a673104b V39sEvYX
19052cc5ef69f90094753c2b3bbcd41d YwoGExpg
cf8591bdccfaa0cdca652f1d31dbd70f pJCLui49
66e10e3d4a788c335282f42b92c760a1 NQCZoIhj
94c3ae5bcc04c38053106916f9b99bda vOktelLQ
e67e88646758e465697c15b1ef164a8d x0hwJGHj
84d3d828e1a0c14b5b095bedc23269fb 2HVWe9fM
264a9e831c3401c38021ba3844479c3f Cx4og6IW
ed0343dec184d9d2c30a9b9c1c308356 g2rqmPkT
ad5ba8dc801c37037350578630783d80 pFK2JDT5
3f588bedb704da9448e68fe81e42bca6 4ANDOiau
970c9cf3cad3dfa7926f53ccaae89421 R6ML7Qy8
e0a097b7cceaa7a8949fe039884e4a2d dul2ynqL
7df505218102c64b1fe4fa5981ddb6fa jPeoyS57
fd4f6043da1f7d5dca993c946ef6cd7c 6p9CwGaY
5fe6d99b9a2824949279187c246c9c30 OGQ2J57y
135b150ad513a961089bb1c05085a3d9 h0dw1Fro
ad6af4fb623b3c51181a371911667fed HbQT4dRz
c9fa4b0db317d88e2b10060225e92494 ebVnpMzS
d0deab17d115bd6fdce8592bb3667643 bL5zwgvX
006f0cb3a422716692f143f28eb0d187 NHXg1Fof
ddc125de34da1a6ec0cbe401f147bc8f GDai9Y0n
be5052053c5a806e8f56ed64e0d67821 40alyH3w
aaf18ac446b8c385c4112c10ae87e7dc ZJQzuIL0
a2db20a4b7386dc2d8c30bf9a05ceef7 QnpOlPWH
8a4fbc32a3251bb51072d51969ba5d33 rtcbipeq
5e35d2c9675ed811880cea01f268e00f i1Hbne6h
9da23007699e832f4e9344057c5e0bd3 EtbGpMSW
f09233683d05171420f963fc92764e84 fxHoinEe
4feabf309c5872f3cca7295b3577f2a8 KymkJXqA
9b94da2fa9402a3fdb4ff15b9f3ba4d2 G3Tdr1Pg
b3cd8d6b53702d733ba515dec1d770c5 Y71LJWZz
6a5b3b2526bb7e94209c487585034534 rIwb4oxt
e9728ef776144c25ba0155a0faab2526 e1sOXSb8
d41a5e7a98e28d76dbd183df7e3bcb49 36bedvia
81d5ebfea6aff129cf515d4e0e5f8360 dDG4qTjW'''

password = password.split('\n')
for i in password:
    pass_md5 = i.split(' ')[0]
    salt = i.split(' ')[1]
    logging.debug('start: ' + pass_md5 + ' ' + salt)
    for j in xrange(10000000000):
        if j % 100000000 == 0:
            logging.debug('exploit num: ' + str(j))
        md5 = hashlib.md5()
        md5.update('{FLAG:' + str(j).zfill(10) + '}' + salt)
        if md5.hexdigest() == pass_md5:
            logging.info('sucess find flag:' + j)
            break

flag:1234567890

superexpress

题目来源：TWCTF2016

下载解压，两个文件

encrypted

1
805eed80cbbccb94c36413275780ec94a857dfec8da8ca94a8c313a8ccf9

problem.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sys
key = '****CENSORED***************'
flag = 'TWCTF{*******CENSORED********}'

if len(key) % 2 == 1:
    print("Key Length Error")
    sys.exit(1)

n = len(key) / 2
encrypted = ''
for c in flag:
    c = ord(c)
    for a, b in zip(key[0:n], key[n:2*n]):
        c = (ord(a) * c + ord(b)) % 251
    encrypted += '%02x' % c

print encrypted

设key为'a1a2a3b1b2b3'，zip后得到一个列表包含三个元组[(a1,b1),(a2,b2),(a3,b3)]，按照脚本里的加密方式，可以推出

1
a3*(a2*(a1*c+b1)+b2)+b3 = a3*a2*a1*c+b1*a2*a3+b2*a3+b3

于是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import string
q = "805eed80cbbccb94c36413275780ec94a857dfec8da8ca94a8c313a8ccf9"
Q = []
for i in range(0, len(q), 2):
    Q += [int(q[i:i + 2], 16)]

for a in range(251):
    for b in range(251):
        if (ord("T") * a + b) % 251 == Q[0] and (ord("W") * a + b) % 251 == Q[1]:
            A = ""
            for q in Q:
                for i in string.printable:
                    if (ord(i) * a + b) % 251 == q:
                        A += chr(ord(i))
            print A
# TWCTF{Faster_Than_Shinkansen!}

vigenere

题目来源：TWCTF2016

解压，有三个文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
➜  Downloads cd vigenere_300
➜  vigenere_300 ls
README        cipher.py     encrypted.txt
➜  vigenere_300 cat README
$ file plain.txt
plain.txt: ASCII text
$ python cipher.py encrypt key plain.txt > encrypted.txt

➜  vigenere_300 cat encrypted.txt
a7TFeCShtf94+t5quSA5ZBn4+3tqLTl0EvoMsNxeeCm50Xoet+1fvy821r6Fe4fpeAw1ZB+as3Tphe8xZXQ/s3tbJy8BDzX4vN5svYqIZ96rt35dKuz0DfCPf4nfKe300fM9utiauTe5tgs5utLpLTh0FzYx0O1sJYKgJvul0OfiuTl00BCks+aaJZm8Kwb4u+LtLCqbZ96lv3bieCahtegx+7nzqyO6YCb4b9LovCELZ9Pe0L5rLSaBDzXaftxseAw1JzCF0MGjeCacKb69u9TlgCudZT6Os3ojhcWxD914vNHfeCuaJvH4s4aarBKlGdsT8G4UKZhfJB+y0LbjqCOnZT6baF1WiZeNtfsNtuoo+c==
➜  vigenere_300 cat cipher.py
# Python 3 Source Code
from base64 import b64encode, b64decode
import sys
import os
import random

chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+/'

def shift(char, key, rev = False):
    if not char in chars:
        return char
    if rev:
        return chars[(chars.index(char) - chars.index(key)) % len(chars)]
    else:
        return chars[(chars.index(char) + chars.index(key)) % len(chars)]

def encrypt(message, key):
    encrypted = b64encode(message.encode('ascii')).decode('ascii')
    return ''.join([shift(encrypted[i], key[i % len(key)]) for i in range(len(encrypted))])

def decrypt(encrypted, key):
    encrypted = ''.join([shift(encrypted[i], key[i % len(key)], True) for i in range(len(encrypted))])
    return b64decode(encrypted.encode('ascii')).decode('ascii')

def generate_random_key(length = 5):
    return ''.join(map(lambda a : chars[a % len(chars)], os.urandom(length)))

if len(sys.argv) == 4 and sys.argv[1] == 'encrypt':
    f = open(sys.argv[3])
    plain = f.read()
    f.close()

    key = generate_random_key(random.randint(5,14))

    print(encrypt(plain, key))

    f = open(sys.argv[2], 'w')
    f.write(key)
    f.close()

elif len(sys.argv) == 4 and sys.argv[1] == 'decrypt':
    f = open(sys.argv[3])
    encrypted = f.read()
    f.close()

    f = open(sys.argv[2])
    key = f.read()
    f.close()

    print(decrypt(encrypted, key), end = '')

else:
    print("Usage: python %s encrypt|decrypt (key-file) (input-file)" % sys.argv[0])

解密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
# Python 3 Source Code
from base64 import b64encode, b64decode
import os
from math import sqrt

candi_count = 0
chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+/'
encrypted = "a7TFeCShtf94+t5quSA5ZBn4+3tqLTl0EvoMsNxeeCm50Xoet+1fvy821r6Fe4fpeAw1ZB+as3Tphe8xZXQ/s3tbJy8BDzX4vN5svYqIZ96rt35dKuz0DfCPf4nfKe300fM9utiauTe5tgs5utLpLTh0FzYx0O1sJYKgJvul0OfiuTl00BCks+aaJZm8Kwb4u+LtLCqbZ96lv3bieCahtegx+7nzqyO6YCb4b9LovCELZ9Pe0L5rLSaBDzXaftxseAw1JzCF0MGjeCacKb69u9TlgCudZT6Os3ojhcWxD914vNHfeCuaJvH4s4aarBKlGdsT8G4UKZhfJB+y0LbjqCOnZT6baF1WiZeNtfsNtuoo+c=="


def shift(char, key, rev=False):
    if char not in chars:
        return char
    if rev:
        return chars[(chars.index(char) - chars.index(key)) % len(chars)]
    else:
        print((chars.index(char) + chars.index(key)) % len(chars))
        return chars[(chars.index(char) + chars.index(key)) % len(chars)]


def encrypt(message, key):
    encrypted = b64encode(message.encode('ascii')).decode('ascii')
    return ''.join([shift(encrypted[i], key[i % len(key)]) for i in range(len(encrypted))])


def original_decrypt(encrypted, key):
    encrypted = ''.join([shift(encrypted[i], key[i % len(key)], True)
                         for i in range(len(encrypted))])
    return b64decode(encrypted.encode('ascii')).decode('ascii')

# not using encode or decode ascii


def decrypt(encrypted, key):
    encrypted = ''.join([shift(encrypted[i], key[i % len(key)], True)
                         for i in range(len(encrypted))])
    return b64decode(encrypted)


def generate_random_key(length=5):
    return ''.join(map(lambda a: chars[a % len(chars)], os.urandom(length)))


def Kasiski_exam(encrypted):
    strlist = []
    count = 0
    indexlist = []
    for i in range(len(encrypted)):
        for j in range(i, len(encrypted)):
            if j - i < 3:
                continue
            start = i
            search_str = encrypted[i:j]
            while True:
                detect = encrypted[start:].find(search_str)
                if detect == -1:
                    break
                else:
                    count += 1
                    if count == 2:
                        strlist.append(search_str)
                        indexlist.append(detect + j - i)
                    start += detect + (j - i)
            if count == 0:
                break
            count = 0
    print(indexlist)
    print(strlist)
    anslist = my_factor(indexlist)
    return anslist


def my_factor(numlist):
    factor_list = []
    for x in range(2, int(sqrt(numlist[0])) + 1):
        if numlist[0] % x == 0 and x >= 5 and x <= 14:
            factor_list.append(x)
    for i in range(1, len(numlist)):
        anslist = list(factor_list)
        num = numlist[i]
        for x in factor_list:
            if num % x != 0:
                anslist.remove(x)
    return anslist


def is_ascii(string):
    if string:
        for char in string:
            if char > 126:
                return False
            if char < 32 and not char == 10:
                return False
    return True


def split_str_and_isascii(plain, num, block):
    start = 3 * block
    for i in range(start, len(plain), 9):
        if not is_ascii(plain[i:i + num]):
            return False
    return True

# if key_len == 12


def brute_key(encrypted, key_len):
    global candi_count
    candi_key_list = [[], [], []]
    for block in range(int(key_len / 4)):
        for a in chars:
            for b in chars:
                if not split_str_and_isascii(decrypt(encrypted, a + b + "aa"), 1, block):
                    continue
                for c in chars:
                    if not split_str_and_isascii(decrypt(encrypted, a + b + c + "a"), 2, block):
                        continue
                    for d in chars:
                        if split_str_and_isascii(decrypt(encrypted, a + b + c + d), 3, block):
                            candi_key_list[block].append(a + b + c + d)
                            candi_count += 1
    return candi_key_list

# if key_len == 6


def brute_key_6(encrypted, key_len):
    global candi_count
    candi_key_list = []
    for block in range(int(key_len / 4)):
        for a in chars:
            for b in chars:
                if not split_str_and_isascii(decrypt(encrypted, a + b + "aa"), 1, block):
                    continue
                for c in chars:
                    if not split_str_and_isascii(decrypt(encrypted, a + b + c + "a"), 2, block):
                        continue
                    for d in chars:
                        if split_str_and_isascii(decrypt(encrypted, a + b + c + d), 3, block):
                            candi_key_list.append(a + b + c + d)
                            candi_count += 1
    return candi_key_list


def main():
    # ==== kasiski examination ====
    factor_list = Kasiski_exam(encrypted)  # [6,12]
    key_len = factor_list[1]
    # ==== brute force attack to base64 ====
    print("Start brute force...")
    candi_key1, candi_key2, candi_key3 = brute_key(encrypted, key_len)
    print(candi_key1)
    print(candi_key2)
    print(candi_key3)

    # ==== key candidate ====
    keylist = []
    for key1 in candi_key1:
        for key2 in candi_key2:
            for key3 in candi_key3:
                keylist.append(key1 + key2 + key3)
    print(candi_count)
    print(keylist)

    # if "TWCTF{" in decrypted, It is highly possible that the key is correct.
    for key in keylist:
        dec = decrypt(encrypted, key)
        check = b"TWCTF{"
        if check in dec:
            print("--------- key candidate : decrypted ---------------")
            print(key, ":", dec)
            print()


if __name__ == '__main__':
    main()

具体操作过程参见：http://73spica.tech/blog/tw_mma_ctf_2016_vigenere-cipher/

运行结果

TWCTF{C14ss1caL CiPhEr iS v3ry fun}

DSA

DSA是基于整数有限域离散对数难题的，其安全性与RSA相比差不多。DSA的一个重要特点是两个素数公开，这样，当使用别人的p和q时，即使不知道私钥x，你也能确认它们是否是随机产生的，还是作了手脚。

可以使用openssl方便地进行dsa签名和验证。

签名与验证：

openssl dgst -sha1 -sign dsa_private.pem -out sign.bin message.txt

openssl sha1 -verify dsa_public.pem -signature sign.bin message.txt

本题的攻击方法曾被用于PS3的破解，答案格式：CTF{x}(x为私钥，请提交十进制格式)

目录结构为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
➜  dsa tree
.
├── dsa_public.pem
├── packet1
│   ├── message1
│   └── sign1.bin
├── packet2
│   ├── message2
│   └── sign2.bin
├── packet3
│   ├── message3
│   └── sign3.bin
└── packet4
    ├── message4
    └── sign4.bin

4 directories, 9 files

先用题目给的验证命令看一下

1
2
3
4
5
6
7
8
➜  dsa openssl sha1 -verify dsa_public.pem -signature packet1/sign1.bin packet1/message1
Verified OK
➜  dsa openssl sha1 -verify dsa_public.pem -signature packet2/sign2.bin packet2/message2
Verified OK
➜  dsa openssl sha1 -verify dsa_public.pem -signature packet3/sign3.bin packet3/message3
Verified OK
➜  dsa openssl sha1 -verify dsa_public.pem -signature packet4/sign4.bin packet4/message4
Verified OK

读一下公钥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
➜  dsa openssl dsa -in dsa_public.pem -text -noout  -pubin
read DSA key
pub:
    45:bb:18:f6:0e:b0:51:f9:d4:82:18:df:8c:d9:56:
    33:0a:4f:f3:0a:f5:34:4f:6c:95:40:06:1d:53:83:
    29:2d:95:c4:df:c8:ac:26:ca:45:2e:17:0d:c7:9b:
    e1:5c:c6:15:9e:03:7b:cc:f5:64:ef:36:1c:18:c9:
    9e:8a:eb:0b:c1:ac:f9:c0:c3:5d:62:0d:60:bb:73:
    11:f1:cf:08:cf:bc:34:cc:aa:79:ef:1d:ad:8a:7a:
    6f:ac:ce:86:65:90:06:d4:fa:f0:57:71:68:57:ec:
    7c:a6:04:ad:e2:c3:d7:31:d6:d0:2f:93:31:98:d3:
    90:c3:ef:c3:f3:ff:04:6f
P:
    00:c0:59:6c:3b:5e:93:3d:33:78:be:36:26:be:31:
    5e:e7:0c:a6:b5:b1:1a:51:9b:55:23:d4:0e:5b:a7:
    45:66:e2:2c:c8:8b:fe:c5:6a:ad:66:91:8b:9b:30:
    ad:28:13:88:f0:bb:c6:b8:02:6b:7c:80:26:e9:11:
    84:be:e0:c8:ad:10:cc:f2:96:be:cf:e5:05:05:38:
    3c:b4:a9:54:b3:7c:b5:88:67:2f:7c:09:57:b6:fd:
    f2:fa:05:38:fd:ad:83:93:4a:45:e4:f9:9d:38:de:
    57:c0:8a:24:d0:0d:1c:c5:d5:fb:db:73:29:1c:d1:
    0c:e7:57:68:90:b6:ba:08:9b
Q:
    00:86:8f:78:b8:c8:50:0b:eb:f6:7a:58:e3:3c:1f:
    53:9d:35:70:d1:bd
G:
    4c:d5:e6:b6:6a:6e:b7:e9:27:94:e3:61:1f:41:53:
    cb:11:af:5a:08:d9:d4:f8:a3:f2:50:03:72:91:ba:
    5f:ff:3c:29:a8:c3:7b:c4:ee:5f:98:ec:17:f4:18:
    bc:71:61:01:6c:94:c8:49:02:e4:00:3a:79:87:f0:
    d8:cf:6a:61:c1:3a:fd:56:73:ca:a5:fb:41:15:08:
    cd:b3:50:1b:df:f7:3e:74:79:25:f7:65:86:f4:07:
    9f:ea:12:09:8b:34:50:84:4a:2a:9e:5d:0a:99:bd:
    86:5e:05:70:d5:19:7d:f4:a1:c9:b8:01:8f:b9:9c:
    dc:e9:15:7b:98:50:01:79

读一下签名的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
➜  dsa openssl asn1parse -inform der -in packet1/sign1.bin
    0:d=0  hl=2 l=  45 cons: SEQUENCE
    2:d=1  hl=2 l=  21 prim: INTEGER           :8158B477C5AA033D650596E93653C730D26BA409
   25:d=1  hl=2 l=  20 prim: INTEGER           :165B9DD1C93230C31111E5A4E6EB5181F990F702
➜  dsa openssl asn1parse -inform der -in packet2/sign2.bin
    0:d=0  hl=2 l=  44 cons: SEQUENCE
    2:d=1  hl=2 l=  20 prim: INTEGER           :60B9F2A5BA689B802942D667ED5D1EED066C5A7F
   24:d=1  hl=2 l=  20 prim: INTEGER           :3DC8921BA26B514F4D991A85482750E0225A15B5
➜  dsa openssl asn1parse -inform der -in packet3/sign3.bin
    0:d=0  hl=2 l=  44 cons: SEQUENCE
    2:d=1  hl=2 l=  20 prim: INTEGER           :5090DA81FEDE048D706D80E0AC47701E5A9EF1CC
   24:d=1  hl=2 l=  20 prim: INTEGER           :30EB88E6A4BFB1B16728A974210AE4E41B42677D
➜  dsa openssl asn1parse -inform der -in packet4/sign4.bin
    0:d=0  hl=2 l=  44 cons: SEQUENCE
    2:d=1  hl=2 l=  20 prim: INTEGER           :5090DA81FEDE048D706D80E0AC47701E5A9EF1CC
   24:d=1  hl=2 l=  20 prim: INTEGER           :5E10DED084203CCBCEC3356A2CA02FF318FD4123

注意到3和4的2:d=1 hl=2 l= 20 prim: INTEGER :值一样，这里这个值代表签名结果中的r，下面一行为s。由于r一样，说明采用的随机数k一样，采用共享k攻击

这里读取dsa的公钥采用，需要从github上clone下来的，pip的这个函数阉割了，在虚拟机中读取

1
2
3
4
5
6
7
from Crypto.PublicKey import DSA
with open('dsa/dsa_public.pem') as f:
    key = DSA.importKey(f)
    y = key.y
    g = key.g
    p = key.p
    q = key.q

然后攻击脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from hashlib import sha1
import gmpy2
p = 135072277349986231918767318777496371552998523256306836680207886328250469140725070958493165166375742776776188095739453689162118072119637932393028705045785456135605269009498175908369054264845986650254461451778502410559449967848738173219539609196568432769555817217073171835795353828043869976253611672766967842971L
q = 768204286206312924745826772404361572053995803069L
y = 48966667837013414801031811810642280772647236378744040304912885467993823167141281755249027785686488654582548005766785141294865650644124270468685164456792976944411071341740863520743350743985636739430430553599637295250998469649774667076175577773243724165204009991562726052681112720456820018391695334506416243823L
g = 53955759259506195629370221955882028602129565196710167480649056988330906117971891319360466002581132965581793497788773734702624458318101767983345305577358509640139391448262692595149152168335401138516115001646783546740429454038931813085439969488499666706724464185937932560157850845046285161405028860099711467897L
f3 = open(r"dsa/packet3/message3", 'r')
f4 = open(r"dsa/packet4/message4", 'r')
data3 = f3.read()
data4 = f4.read()
sha = sha1()
sha.update(data3)
m3 = int(sha.hexdigest(), 16)
sha = sha1()
sha.update(data4)
m4 = int(sha.hexdigest(), 16)
s3 = 0x30EB88E6A4BFB1B16728A974210AE4E41B42677D
s4 = 0x5E10DED084203CCBCEC3356A2CA02FF318FD4123
r = 0x5090DA81FEDE048D706D80E0AC47701E5A9EF1CC
ds = s4 - s3
dm = m4 - m3
k = gmpy2.mul(dm, gmpy2.invert(ds, q))
k = gmpy2.f_mod(k, q)
tmp = gmpy2.mul(k, s3) - m3
x = tmp * gmpy2.invert(r, q)
x = gmpy2.f_mod(x, q)
print 'CTF{%d}' % int(x)

CTF{520793588153805320783422521615148687785086070744}

Complicated Crypto

五层密码，好复杂

来源：sunnyelf

第一层：crc32爆破

crc32_util.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
# -*- coding: utf-8 -*-

import itertools
import binascii
import string


class crc32_reverse_class(object):
    def __init__(self, crc32, length, tbl=string.printable,
                 poly=0xEDB88320, accum=0):
        self.char_set = set(map(ord, tbl))
        self.crc32 = crc32
        self.length = length
        self.poly = poly
        self.accum = accum
        self.table = []
        self.table_reverse = []

    def init_tables(self, poly, reverse=True):
        # build CRC32 table
        for i in range(256):
            for j in range(8):
                if i & 1:
                    i >>= 1
                    i ^= poly
                else:
                    i >>= 1
            self.table.append(i)
        assert len(self.table) == 256, "table is wrong size"
        # build reverse table
        if reverse:
            found_none = set()
            found_multiple = set()
            for i in range(256):
                found = []
                for j in range(256):
                    if self.table[j] >> 24 == i:
                        found.append(j)
                self.table_reverse.append(tuple(found))
                if not found:
                    found_none.add(i)
                elif len(found) > 1:
                    found_multiple.add(i)
            assert len(self.table_reverse) == 256, "reverse table is wrong size"

    def rangess(self, i):
        return ', '.join(map(lambda x: '[{0},{1}]'.format(*x), self.ranges(i)))

    def ranges(self, i):
        for kg in itertools.groupby(enumerate(i), lambda x: x[1] - x[0]):
            g = list(kg[1])
            yield g[0][1], g[-1][1]

    def calc(self, data, accum=0):
        accum = ~accum
        for b in data:
            accum = self.table[(accum ^ b) & 0xFF] ^ (
                (accum >> 8) & 0x00FFFFFF)
        accum = ~accum
        return accum & 0xFFFFFFFF

    def findReverse(self, desired, accum):
        solutions = set()
        accum = ~accum
        stack = [(~desired,)]
        while stack:
            node = stack.pop()
            for j in self.table_reverse[(node[0] >> 24) & 0xFF]:
                if len(node) == 4:
                    a = accum
                    data = []
                    node = node[1:] + (j,)
                    for i in range(3, -1, -1):
                        data.append((a ^ node[i]) & 0xFF)
                        a >>= 8
                        a ^= self.table[node[i]]
                    solutions.add(tuple(data))
                else:
                    stack.append(((node[0] ^ self.table[j]) << 8,) + node[1:] + (j,))
        return solutions

    def dfs(self, length, outlist=['']):
        tmp_list = []
        if length == 0:
            return outlist
        for list_item in outlist:
            tmp_list.extend([list_item + chr(x) for x in self.char_set])
        return self.dfs(length - 1, tmp_list)

    def run_reverse(self):
        self.init_tables(self.poly)
        desired = self.crc32
        accum = self.accum
        if self.length >= 4:
            patches = self.findReverse(desired, accum)
            for patch in patches:
                checksum = self.calc(patch, accum)
                print 'verification checksum: 0x{0:08x} ({1})'.format(
                    checksum, 'OK' if checksum == desired else 'ERROR')
            for item in self.dfs(self.length - 4):
                patch = map(ord, item)
                patches = self.findReverse(desired, self.calc(patch, accum))
                for last_4_bytes in patches:
                    if all(p in self.char_set for p in last_4_bytes):
                        patch.extend(last_4_bytes)
                        print '[find]: {1} ({0})'.format(
                            'OK' if self.calc(patch, accum) == desired else 'ERROR', ''.join(map(chr, patch)))
        else:
            for item in self.dfs(self.length):
                if crc32(item) == desired:
                    print '[find]: {0} (OK)'.format(item)


def crc32_reverse(crc32, length, char_set=string.printable,
                  poly=0xEDB88320, accum=0):
    obj = crc32_reverse_class(crc32, length, char_set, poly, accum)
    obj.run_reverse()


def crc32(s):
    return binascii.crc32(s) & 0xffffffff

爆破脚本，注意6位的crc32碰撞有很多结果，手动缩小一下字典，这里先试了string.letters + string.digits，发现没有特别像密码的，再加个_到字典里就得到了

1
2
3
4
5
6
7
8
9
10
from crc32_util import *

crc = [0x7C2DF918,
       0xA58A1926,
       0x4DAD5967]

for i in crc:
    crc32_reverse(i, 6, char_set=string.letters + string.digits + '_')

# _CRC32_i5_n0t_s4f3

解出一个CRC32 Collision.7z，没有密码，直接解压得到

1
2
3
4
5
6
7
8
➜  CRC32 Collision tree
.
├── Find password.7z
├── ciphertext.txt
├── keys.txt
└── tips.txt

0 directories, 4 files

第二层：维吉尼亚

看一下每个文件的内容

1
2
3
4
5
6
7
8
9
10
➜  CRC32 Collision cat ciphertext.txt
rla xymijgpf ppsoto wq u nncwel ff tfqlgnxwzz sgnlwduzmy vcyg ib bhfbe u tnaxua ff satzmpibf vszqen eyvlatq cnzhk dk hfy mnciuzj ou s yygusfp bl dq e okcvpa hmsz vi wdimyfqqjqubzc hmpmbgxifbgi qs lciyaktb jf clntkspy drywuz wucfm     
➜  CRC32 Collision cat tips.txt
你知道维吉尼亚密码吗？
我们给了keys.txt，唯一的密钥就在其中，那么解密ciphertext.txt里的密文吧！
解压密码就在明文里，祝你好运！

Do you know the Vigenére Ciphers?
We gave the keys.txt, Only have a key in it, So decrypts ciphertext.txt!
Unzip Password in plaintext, good luck to you!

还有几千行key

先在线解一下看看：https://guballa.de/vigenere-solver

结果不是太理想，看最后那里有个f开头某个单词，但是我们不知道是什么，不过可以看出个大概了，用关键字password爆破一下，最后密码换成小写加上空格

1
2
3
4
5
6
7
8
9
10
11
from pycipher import Vigenere

with open('CRC32 Collision/keys.txt', 'r') as file:
    for i in file.readlines():
        m = Vigenere(i.strip()).decipher(
            'rla xymijgpf ppsoto wq u nncwel ff tfqlgnxwzz sgnlwduzmy vcyg ib bhfbe u tnaxua ff satzmpibf vszqen eyvlatq cnzhk dk hfy mnciuzj ou s yygusfp bl dq e okcvpa hmsz vi wdimyfqqjqubzc hmpmbgxifbgi qs lciyaktb jf clntkspy drywuz wucfm')
        if 'PASSWORD' in m:
            print i, m
# YEWCQGEWCYBNHDHPXOYUBJJPQIRAPSOUIYEOMTSV
# THEVIGENERECIPHERISAMETHODOFENCRYPTINGALPHABETICTEXTBYUSINGASERIESOFDIFFERENTCAESARCIPHERSBASEDONTHELETTERSOFAKEYWORDITISASIMPLEFORMOFPOLYALPHABETICSUBSTITUTIONSOPASSWORDISVIGENERECIPHERFUNNY
# vigenere cipher funny

然后解压得到

1
2
3
4
5
6
➜  Find password tree
.
├── Easy SHA1.7z
└── U need unzip password.txt

0 directories, 2 files

第三层：sha1爆破

txt的内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
恭喜!

现在我们遇到一个问题,我们有一个zip文件,但我们不知道完整的解压密码。
幸好我们知道解压密码的一部分sha1值。
你能帮我们找到的密码吗?

不完整的密码："*7*5-*4*3?"  *代表可打印字符

不完整的sha1："619c20c*a4de755*9be9a8b*b7cbfa5*e8b4365*"  *代表可打印字符

人生苦短，我用Python。

Congratulations!
Now we run into a problem,We have a zip file, but we don't know the complete unzip password.
Fortunately, we know that part of the unzip password of sha1 value.
can you help us to find the password?

Incomplete password is "*7*5-*4*3?"   * in the range of ASCII printable characters

Incomplete sha1 is "619c20c*a4de755*9be9a8b*b7cbfa5*e8b4365*"    * in the range of ASCII printable characters

Life is short, you need Python.

直接爆破

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import hashlib
import string

sha1 = "619c20c*a4de755*9be9a8b*b7cbfa5*e8b4365*"
pw = "*7*5-*4*3?"
dic = string.printable
for i in dic:
    for j in dic:
        for k in dic:
            for l in dic:
                pw = '%s7%s5-%s4%s3?' % (i, j, k, l)
                sha11 = hashlib.sha1(pw).hexdigest()
                if sha11[0:7] == sha1[0:7] and sha11[8:15] == sha1[8:15] and sha11[16:23] == sha1[16:23]:
                    print pw, sha11
# I7~5-s4F3? 619c20c4a4de75519be9a8b7b7cbfa54e8b4365b

解压出来

1
2
3
4
5
6
➜  Easy SHA1 tree
.
├── MD5_is_really_safe? .txt
└── Vulnerable RSA.7z

0 directories, 2 files

第四层：md5碰撞

txt内容为

1
2
3
4
5
6
7
8
9
10
11
Hello World ;-)
MD5校验真的安全吗？
有没有两个不同的程序MD5却相同呢？
如果有的话另一个程序输出是什么呢？
解压密码为单行输出结果。

Hello World ;-)
MD5 check is really safe?
There are two different procedures MD5 is the same?
If so what is the output of another program?
The decompression password is a single-line output.

之前看过这个，就是有个输出Hello World ;-)的程序的md5碰撞，直接百度得到这篇文章

blog.csdn.net/xiaofei0859/article/details/54924123

换到win10环境下载下来，运行得到结果

Goodbye World :-(

第五层：RSA

历经艰辛，终于到最后一关了，这次终于没压缩包了

1
2
3
4
5
6
➜  Vulnerable RSA tree
.
├── flag.enc
└── rsa_public_key.pem

0 directories, 2 files

读取公钥

1
2
3
4
5
6
7
8
9
from Crypto.PublicKey import RSA
with open('Vulnerable RSA/rsa_public_key.pem', 'r') as f:
    key = RSA.importKey(f)
    n = key.n
    e = key.e
print n
#460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597
print e
#354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619

e特别大，那么一般d就特别小。在d比较小时，有两种攻击方法：

  • d < N^(1/4)/3时，可以使用wiener’s attack来获得RSA的私钥。
  • d ≤ N^0.292时， 我们可以利用Boneh and Durfee attack，在一定程度上该要攻击比wiener attack要强一些。

使用wiener’s attack：

安装

1
git clone https://github.com/pablocelayes/rsa-wiener-attack.git

新建一个py文件

1
2
3
4
5
6
from RSAwienerHacker import hack_RSA

n = 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597
e = 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619
print 'd = %d' % hack_RSA(e, n)
# d = 8264667972294275017293339772371783322168822149471976834221082393409363691895

使用Boneh and Durfee attack：

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

然后修改boneh_durfee.sage中的example()中的N和e，然后运行sage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
➜  RSA-and-LLL-attacks git:(master) ✗ sage boneh_durfee.sage
=== checking values ===
* delta: 0.180000000000000
* delta < 0.292 True
* size of e: 1024
* size of N: 1025
* m: 4 , t: 2
=== running algorithm ===
* removing unhelpful vector 0
6 / 18  vectors are not helpful
det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)
00 X 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ~
01 X X 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
02 0 0 X 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ~
03 0 0 X X 0 0 0 0 0 0 0 0 0 0 0 0 0 0
04 0 0 X X X 0 0 0 0 0 0 0 0 0 0 0 0 0
05 0 0 0 0 0 X 0 0 0 0 0 0 0 0 0 0 0 0 ~
06 0 0 0 0 0 X X 0 0 0 0 0 0 0 0 0 0 0 ~
07 0 0 0 0 0 X X X 0 0 0 0 0 0 0 0 0 0
08 0 0 0 0 0 X X X X 0 0 0 0 0 0 0 0 0
09 0 0 0 0 0 0 0 0 0 X 0 0 0 0 0 0 0 0 ~
10 0 0 0 0 0 0 0 0 0 X X 0 0 0 0 0 0 0 ~
11 0 0 0 0 0 0 0 0 0 X X X 0 0 0 0 0 0
12 0 0 0 0 0 0 0 0 0 X X X X 0 0 0 0 0
13 0 0 0 0 0 0 0 0 0 X X X X X 0 0 0 0
14 X X 0 X X 0 0 0 0 0 0 0 0 0 X 0 0 0
15 0 0 X X X 0 X X X 0 0 0 0 0 0 X 0 0
16 0 0 0 0 0 X X X X 0 X X X X 0 0 X 0
17 0 0 X X X 0 X X X 0 0 X X X 0 X X X
optimizing basis of the lattice via LLL, this can take a long time
LLL is done!
looking for independent vectors in the lattice
found them, using vectors 0 and 1
=== solution found ===
private key found: 8264667972294275017293339772371783322168822149471976834221082393409363691895
=== 1.08708715439 seconds ===

解密flag

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes

with open('Vulnerable RSA/rsa_public_key.pem', 'r') as f:
    key = RSA.importKey(f)
    n = key.n
    e = key.e
d = 8264667972294275017293339772371783322168822149471976834221082393409363691895
with open('Vulnerable RSA/flag.enc', 'r') as f:
    c = f.read().encode('hex')
    c = int(c, 16)
m = pow(c, d, n)
print long_to_bytes(m)
1
2
➜  crypto python Complicated_Crypto.py
���W8��S/cwr�ӵCf��w�h	��d�D}�7�!�;��w�Uf��%˖�B�<"QS��{�.���z@���h硏��%&���'J�!�'h8!Y�o(H�}flag{W0rld_Of_Crypt0gr@phy}