# XJUSEC2019新生赛 **Repository Path**: L3SLIE/xjusec_2019 ## Basic Information - **Project Name**: XJUSEC2019新生赛 - **Description**: 关于XJUSEC2019新生赛的一些源码与WP - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2020-02-02 - **Last Updated**: 2020-12-19 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # XJUSEC2019新生赛 ### 介绍 关于XJUSEC2019新生赛的一些源码与WP ### 源码&WP 源码我会放在我的仓库里，WP的话会给出本次crypto方向上的做题思路 #### 0x01 truelove 1. 本题为一道娱乐题目，希望大家在做题的同时对密码学产生兴趣，并没有涉及加密原理，只是借用了火狐Mozilla的一个网页信息加密小游戏[Codemoji](http://https://codemoji.org/) 2. 接下来是题解，没有文件，点开是一段base64，很常见的加密，在线解base![输入图片说明](https://images.gitee.com/uploads/images/2020/0202/154857_844d277c_5231620.jpeg "批注 2020-01-13 171143.jpg") 3. 很明显的一个网站，后面是信息提示，也就是有关解密所需KEY的提示信息，真爱的颜色，因为是一道娱乐题，~~玩梗也是情有可原~~（误，所以是 :green_heart: ，解出flag![输入图片说明](https://images.gitee.com/uploads/images/2020/0202/155023_da88db64_5231620.jpeg "批注 2020-01-13 171209.jpg") #### 0x02 Singer 1. 本题是nctf的一道题，但做了一些改变，但思路完全一致。 2. 打开是个lrc文件，直接记事本打开就行，打开后是一段歌词，仔细观察会发现中间的逻辑 3. >***Leonard Adleman says star*** Problem Makers is Problem Makers >***Problem Makers says XJUSEC{*** God takes World A boy says flag The boy is Bob Evil takes your mind A girl says no flag The girl is Alice Truths were ctf hoster violently FUCK >***Bob says ar*** >***Adi Shamir says rock*** Love takes Alice and Bob Mallory was a eavesdroppers Mallory's in hell Everything is literatures, potentially flag, Earth, description, soul >***Alice says U*** Reality takes God and Evil God was in heaven Evil is in the world >***Ron Rivest says nice*** You Want To takes Alice and Love and Anything You's Loser. Without Alice, Love or Anything Listen to your heart You were Loser Listen to your mind Nothing was psb unfulfilled If Truths of Nothing is Everything Put Ron Rivest with Adi Shamir with Leonard Adleman into RSA If Everything over Nothing is Truths Put Problem Makers with Alice into Problem Makers with Bob Say Problem Makers The flag is in your heart The confusion is in your mind Shout RSA >***Mysterious One says }*** Whisper Mysterious One This is live This is the truth This is reality This is art This is CTF This is NOT program //flag XJUSEC{Uarnicerockstar} #### 0x03 RSA 1. 求解rsa问题，首先要了解什么是RSA加密，这里我给出两个介绍RSA的文章 > https://my.oschina.net/grittan/blog/3022794 https://www.freebuf.com/articles/others-articles/166049.html 2. 相信在看过这两篇关于RSA加密介绍的文章之后，大家对RSA加密有基本的认识。 ##### babyrsa ``` Math is cool! Use the RSA algorithm to decode the secret message, c, p, q, and e are parameters for the RSA algorithm. p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483 q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407 e = 65537 c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034 Use RSA to find the secret message ``` 题中已经给出了求解所需要的参数，p，q，c 根据rsa的加解密原理可以知道密文m = c^d mod(n) 所需求的就是公式中的n和d了 `n = p*q` `d = e-1 mod (p-1)(q-1)` 那么这道题就十分简单了 ``` import gmpy2 p= 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483 q= 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407 c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034 e = 65537 d = gmpy2.invert(e,(p-1)*(q-1)) m = gmpy2.powmod(c,d,p*q) print (m) #m = 5577446633554466577768879988 ``` ##### white give ``` n = 87924348264132406875276140514499937145050893665602592992418171647042491658461 e = 65537 c = 1323932973882505127567997561415668792873249397183695004797826407988557497789 ``` 只给出了n，没有p和q，我们知道，p和q是大整数n的两个质因数，所以如果我们能将p和q从n中分解出来，问题就简单了 分解n的途径常见的有两种，一种是借助网站 > http://factordb.com/ 另一种就是yafu，关于yafu的使用方法在这里就不做介绍，直接给出一篇文章 > https://blog.csdn.net/qq_38063791/article/details/82947840 分解n之后的做法与babyrsa类似，不过最后的结果是hex形式的需要对hex进行decode 脚本如下 ``` #p= 275127860351348928173285174381581152299 #q= 319576316814478949870590164193048041239 import gmpy2 p= 275127860351348928173285174381581152299 q= 319576316814478949870590164193048041239 n = 87924348264132406875276140514499937145050893665602592992418171647042491658461 c = 1323932973882505127567997561415668792873249397183695004797826407988557497789 e = 65537 d = gmpy2.invert(e,(p-1)*(q-1)) #print (d) m = gmpy2.powmod(c,d,p*q) #print (m) print hex(m)[2:].decode('hex') #flag{RSA_256_b1ts_1s_Writ3_Give} ``` ##### BADRSA 本题来源于nctf的childrsa 但由于yafu的存在使得题目出现非预期解，此题目考察的知识点要比它看起来难上很多，原题解我会放在文末，感兴趣的话可以去看看 在这里只简单做一些说明，让大家熟悉一下yafu的用法。 ``` from random import choice from Crypto.Util.number import isPrime, sieve_base as primes #from flag import flag def getPrime(bits): while True: n = 2 while n.bit_length() < bits: n *= choice(primes) if isPrime(n + 1): return n + 1 e = 0x10001 m = int.from_bytes(flag.encode(), 'big') p, q = [getPrime(2048) for _ in range(2)] n = p * q c = pow(m, e, n) # n = 18593156797240319857595213690397989325525271133791312568446889915944033064100371104581731532631091503535602596625206968072471704526126177851342525418065352417467770985181453703824446545624814020088229913551168590763366199919588136847850071664562617688476529621190774851840120407058647436312506530464806016595285635383696003993673806454695717060413467152754154513144019417535456912183908101178134376622811495589460230913620523468670014115494868998771020562765366580132207086571823654068805207267678182079407136151318954715956103702385746650410960251572017154913836121903910187180085726045619388926375551835371417950821682623000024801284942564252934622066982513069808153844627952587991020946738555222228604869905329180319500884904741344175251793148508216408423855810711975532367846363239787711715995658479820222265598667056600898798739613127011506726838268704794969053178356832056364415313634801521364848664926851455419983263590758318976832638538287441294652248048314135970474560326109966170454503135840319680085501388165869698699363869575935282973343755355221069596875056759101914737700734490057013244475426116029481857089224607822710888886260861212709912726937315772190048179791994180881028699201242836562990229871501718176782600488923257 # c = 12246991997075567299333091955286124558535771125749195173423462591589599148246950536973344094697381881646070498243284004511591709851494408238456430239563188718093790844278626764266152620960525723761516246723774655578541950353158264089529439510300643359496505293058256120248042719110261394400954207742621538178576397458332260872735455432116210127719059895327941419210227101610006232743470035370738902036204650099986796091293645836805715672742051379367426351214949720255263211757929775725767927428797634547731624209359659686810461433527870721288904156665416877886649780271067791070375868453920824069906301303084454877074971598874137542612767466215920704437582555100813862848596671066251385739102728744436701245255625274142088557050389981052011799213563131697180817380536760149832811383980148304471005533360303420649405365693059920261620172024940587939854149115212644375635137458440636666665470923622968214575033240820798902963695752881087927627235477085071263835758642220223269465762162655595604457355238859189544225277027198204392960013276202883658722658835947872141708889509483326851423286849130773940575088824121527885826595551585297165117396508871896716429882836101754262475018400076172172911058852073789264898626669187248096900091196951 ``` 脚本如下 ``` import gmpy2 p = 51308963365231078823980180783163312701364591578640124732853413081668009242653641543273422167594190724551718241651039656136929815558187076682148520261848343729842506911538008029402244904426466106213994045206195486044829099911620742565757303458978079220168495663537396903552624428295943111343650722070313014422853261589496459009700711849502318089286514813530187122343076451459596577825755454359910114123985984695641426908135897672868607775230576670448429924575369916140419672246447908984584723390063778693512496129356842385118604653880078286163722831392041845536949670226969006178880514817427702855672616031799953223152447 q = 362376387628204469145269430423216951565086054878398997974719157827795227813834042397417442897515483739980090458015295807686866863247745967036097901875624568571129136298940635713503036982890741317454711334663187708069580630684509676106211476007364927949071074211673294366197423368258060221980985314778738162518411941462023209061208761828332305788032402715816093840791342483832403146518480255631024173513753665497835941124682843780600571227815518557647215798438420785146083437102412572052068194339488122442066100126626096403365800233782528237586328611544796031937811136181188887363358486926539722942031307755626350364231 N = 18593156797240319857595213690397989325525271133791312568446889915944033064100371104581731532631091503535602596625206968072471704526126177851342525418065352417467770985181453703824446545624814020088229913551168590763366199919588136847850071664562617688476529621190774851840120407058647436312506530464806016595285635383696003993673806454695717060413467152754154513144019417535456912183908101178134376622811495589460230913620523468670014115494868998771020562765366580132207086571823654068805207267678182079407136151318954715956103702385746650410960251572017154913836121903910187180085726045619388926375551835371417950821682623000024801284942564252934622066982513069808153844627952587991020946738555222228604869905329180319500884904741344175251793148508216408423855810711975532367846363239787711715995658479820222265598667056600898798739613127011506726838268704794969053178356832056364415313634801521364848664926851455419983263590758318976832638538287441294652248048314135970474560326109966170454503135840319680085501388165869698699363869575935282973343755355221069596875056759101914737700734490057013244475426116029481857089224607822710888886260861212709912726937315772190048179791994180881028699201242836562990229871501718176782600488923257 c = 12246991997075567299333091955286124558535771125749195173423462591589599148246950536973344094697381881646070498243284004511591709851494408238456430239563188718093790844278626764266152620960525723761516246723774655578541950353158264089529439510300643359496505293058256120248042719110261394400954207742621538178576397458332260872735455432116210127719059895327941419210227101610006232743470035370738902036204650099986796091293645836805715672742051379367426351214949720255263211757929775725767927428797634547731624209359659686810461433527870721288904156665416877886649780271067791070375868453920824069906301303084454877074971598874137542612767466215920704437582555100813862848596671066251385739102728744436701245255625274142088557050389981052011799213563131697180817380536760149832811383980148304471005533360303420649405365693059920261620172024940587939854149115212644375635137458440636666665470923622968214575033240820798902963695752881087927627235477085071263835758642220223269465762162655595604457355238859189544225277027198204392960013276202883658722658835947872141708889509483326851423286849130773940575088824121527885826595551585297165117396508871896716429882836101754262475018400076172172911058852073789264898626669187248096900091196951 e = 0x10001 d = gmpy2.invert(e,(p-1)*(q-1)) m = gmpy2.powmod(c,d,p*q) print (m) print hex(m)[2:].decode('hex') ``` * * * 下面是期望的题解 > 最近在看一些整数分解的算法，其中有一个就是`Pollard's p-1 method。` > 这里输入引用文本前几天又正好在先知社区上看到了一篇Pollard's rho algorithm的文章： > https://xz.aliyun.com/t/6703 ，联想到一个Pollard's p-1 method。 > An Introduction to Mathematical Cryptography书中说到： > NCTF 2019 Official Writeup-小绿草信息安全实验室 > 有的时候（极少情况），RSA模数的位数越高并不意味着安全性越高。 > 存在一些比较特殊的模数，很容易被分解。 > 这个分解算法就叫做`Pollard's p-1 method。` 于是，就根据这个算法出了这一道题。 ***Analysis*** 这一题的关键是如何将分解n成两个5120位的大质数p, q。 首先，p,q由getPrime函数生成： NCTF 2019 Official Writeup-小绿草信息安全实验室 其中，primes是Crypto.Util.number模块中定义的前10000个质数。在VScode中按F12即可跳转到定义处。 NCTF 2019 Official Writeup-小绿草信息安全实验室 可以看到，最大的质数是104729。 一般来说，我们寻找大质数都是随机生成一个大数，然后将其经过素性测试，能够通过的就返回。 但是这一题里面，并不是这样生成的。 我们可以看到，getPrime生成的质数，都是由前10000个质数累乘起来然后再加1生成的。 这就使得生成的质数p，将其减一后，其结果（也就是这个质数的欧拉函数p-1）能够被分解为许多个相对来说很小的质数。这在数学上有一个专门的术语，叫做B-smooth。很显然，p是104729-smooth的。 关于smooth number的定义，请参考wiki： https://en.wikipedia.org/wiki/Smooth_number smooth有什么坏处呢？ 我们先来看一个叫做费马小定理的东西： $$ a^{p-1} \equiv 1 \quad (\text{mod}\ p) $$ 也就是说，指数那边每增加 $p-1$，其结果仍然不变。指数以 $p-1$ 为一个循环。 我们将其变形一下， $$ a^{p-1} - 1 \equiv 0 \quad (\text{mod}\ p) $$ 模p同余0，也就是说 $a^{p-1} - 1$ 是 $p$ 的倍数。 将同余式改写为等式， $$ a^{t \times (p-1)} - 1 = k\times p $$ 其中 $t, k$ 是两个整数。 如果指数$exp$是 $p-1$ 的倍数，那么$a^{exp} - 1 $就会是 $p$ 的倍数。 上面的$p$均指某一个质数，而非N = pq中的p 这里很关键。 如果我们能够找到一个指数$L$，使得对于某一个底数$a$，$a^{L} - 1$ 是p的倍数，但不是q的倍数。 这时，我们只要去计算 $$ gcd(a^{L}-1, N) $$ 得到的结果，必定是p。也就是说，我们成功地分解了N。 那么，怎么去找到这个$L$呢？ Pollard的厉害之处就在于此，他发现，如果p-1正好是一些很小的质数的乘积，那么p-1就能整除$n!$，其中$n$是一个不太大的数。 为什么呢？说下我自己的理解。 假设p-1是p1, p2, ..., pk这些质数的乘积，其中最大的质数是pk。那么，很显然pk!=1·2·...·pk肯定包括了p1, p2, ..., pk这些质数的乘积，pk!肯定是p-1的倍数。 也就是说，$n > pk$ 的时候，$n!$很大概率上就能被p-1整除。（考虑到p1, p2, ..., pk中可能有重复的情况） 这导致了Pollard' p-1 method： 对于每一个$n = 2, 3, 4, ...$，我们任意选择一个底数$a$（事实上，我们可以简单地选择为2），并计算 $$ gcd(a^{n!-1}, N) $$ 如果结果落在1和$N$中间，那么我们就成功了。 NCTF 2019 Official Writeup-小绿草信息安全实验室 实际操作中，这个算法有很多可以优化的地方。 例如，我们并不需要算出$a^{n!-1}$的确切值，当$n>100$时，$n!$本身就已经很大了，整体结果肯定巨大无比。我们每一次只需要算出$a^{n!-1}\ \text{mod}\ N$的值即可，可以将运算结果限制在模$N$的范围内。 这一题，实际上我们已经知道了最大的质数为104729，我们大概只需要算到$n = 104729$就可以了（不考虑p-1的构成中有几个重复的比较大的质数）。 并不需要每一个$n$都去算一遍$gcd(a^{n!-1}, N)$，每隔一个恰当的间隔去算就可以了。 Exploit 先自己照着算法流程实现一下Pollard's p-1 method： ``` from Crypto.Util.number import * def Pollard_p_1(N): a = 2 while True: f = a # precompute for n in range(1, 80000): f = pow(f, n, N) for n in range(80000, 104729+1): f = pow(f, n, N) if n % 15 == 0: d = GCD(f-1, N) if 1 < d < N: return d print(a) a += 1COPY ``` 然后就直接去分解这个10000+位的N。 `n = 1592519204764870135...` `print( Pollard_p_1(n) )` 大概*跑个十几分钟*（由于这个N太大了，十万次左右的快速幂还是需要点时间的），能分解出来： NCTF 2019 Official Writeup-小绿草信息安全实验室 后面就是正常的RSA解密了。 ``` from Crypto.Util.number import * n = 1592519204764870135... c = 5744608257563538066... p = 5075332621067110585... q = n // p assert(p*q == n) d = inverse(0x10001, (p-1)*(q-1)) m = pow(c, d, n) print(long_to_bytes(m)) # b'NCTF{Th3r3_ar3_1ns3cure_RSA_m0duli_7hat_at_f1rst_gl4nce_appe4r_t0_be_s3cur3}' ``` ***Summary*** 出这一道题的目的，还是希望能让大家去深入了解某些算法背后的原理。 > 不过看大家好像都是用yafu直接分解的。。。。而且还挺快的。