1、RSA
已知p,q,e求d
1 2 3 4 5 6 7 import gmpy2 p=473398607161 q=4511491 e=17 phi_n = (p-1 )*(q-1 ) d = gmpy2.invert(e,phi_n)print (d)
2、rsarsa
已知p,q,e,c求m
先通过p,q,e求d
1 2 3 4 5 6 7 import gmpy2 p=9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483 q=11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407 e=65537 phi_n = (p-1 )*(q-1 ) d = gmpy2.invert(e,phi_n)print (d)
1 d =56632047571190660567520341028861194862411428416862507034762587229995138605649836960220619903456392752115943299335385163216233744624623848874235303309636393446736347238627793022725260986466957974753004129210680401432377444984195145009801967391196615524488853620232925992387563270746297909112117451398527453977
然后是已知c,d,n求m
1 2 3 4 5 6 7 d = 56632047571190660567520341028861194862411428416862507034762587229995138605649836960220619903456392752115943299335385163216233744624623848874235303309636393446736347238627793022725260986466957974753004129210680401432377444984195145009801967391196615524488853620232925992387563270746297909112117451398527453977 p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483 q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407 n = p*q c=83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034 m=pow (c,d,n)print (m)
1 m =5577446633554466577768879988
3、RSA1
这题是dp,dq泄漏,很明显了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 import gmpy2import binasciidef 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 (binascii.unhexlify(hex (m)[2 :])) p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852 decrypt(dp,dq,p,q,c)
4、RSA2
这是一个dp泄漏
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import gmpy2import libnumimport binasciidef getd (n,e,dp ): for i in range (1 ,e): if (dp*e-1 )%i == 0 : if n%(((dp*e-1 )/i)+1 )==0 : p=((dp*e-1 )/i)+1 q=n/(((dp*e-1 )/i)+1 ) phi = (p-1 )*(q-1 ) d = gmpy2.invert(e,phi)%phi return d e = 65537 n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113 dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657 c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751 d=getd(n,e,dp) m=pow (c,d,n)print (binascii.unhexlify(hex (m)[2 :]))print (libnum.n2s(m))
这个脚本用python2跑
5、RSA3
这题已知c1,c2,e1,e2,那么就是共模攻击了
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 import libnumfrom gmpy2 import invertdef 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 main (): n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801 c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361 c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397 e1 = 11187289 e2 = 9647291 s = egcd(e1, e2) s1 = s[1 ] s2 = s[2 ] if s1<0 : s1 = - s1 c1 = invert(c1, n) elif s2<0 : s2 = - s2 c2 = invert(c2, n) m = pow (c1,s1,n)*pow (c2,s2,n) % n print (libnum.n2s(m))if __name__ == '__main__' : main()
这题也用python2跑
6、RSA
已知公钥和c求m
先把公钥文件里面的信息提取出来
1 openssl rsa -pubin -text -modulus -in warmup -in pub.key
1 2 e =65537 N =C0332 C5 C64 AE47182 F6 C1 C876 D42336910545 A58 F7 EEFEFC0 BCAAF5 AF341 CCDD
N需要转成十进制
1 2 N = "C0332C5C64AE47182F6C1C876D42336910545A58F7EEFEFC0BCAAF5AF341CCDD" print (int (N,16 ))
得到N=86934482296048119190666062003494800588905656017203025617216654058378322103517
分解p和q
1 2 p =285960468890451637935629440372639283459 q =304008741604601924494328155975272418463
现在需要通过这些已知来求私钥文件,通过rsatool来求
https://github.com/ius/rsatool
1 python rsatool.py -o private.pem -e 65537 -p 285960468890451637935629440372639283459 -q 304008741604601924494328155975272418463
现在私钥文件就生成了
现在有私钥文件了,我们就可以解密了
1 openssl rsautl -decrypt -in flag.enc -inkey private.pem
其实,当得到了p和q之后,还有一种方法通过代码直接出flag
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import gmpy2import rsa e = 65537 n = 86934482296048119190666062003494800588905656017203025617216654058378322103517 p = 285960468890451637935629440372639283459 q = 304008741604601924494328155975272418463 phin = (q-1 )*(p-1 ) d = gmpy2.invert(e, phin) key = rsa.PrivateKey(n, e, int (d), p, q)with open ("flag.enc" , "rb+" ) as f: f = f.read() print (rsa.decrypt(f, key))
这个rsa的库必须是python3才能装
需要把flag.enc放到代码所在目录,不需要求出私钥文件,直接这个代码跑一下就得到结果了
7、RSAROLL
这题给了这样一个文件,第一个括号里第一个应该是N,第二个是e
下面是c,每行代表一个c
先把N分解成p和q,然后直接求了
1 2 3 4 5 6 7 8 9 10 11 12 13 import gmpy2 n=920139713 e=19 c=[704796792 ,752211152 ,274704164 ,18414022 ,368270835 ,483295235 ,263072905 ,459788476 ,483295235 ,459788476 ,663551792 ,475206804 ,459788476 ,428313374 ,475206804 ,459788476 ,425392137 ,704796792 ,458265677 ,341524652 ,483295235 ,534149509 ,425392137 ,428313374 ,425392137 ,341524652 ,458265677 ,263072905 ,483295235 ,828509797 ,341524652 ,425392137 ,475206804 ,428313374 ,483295235 ,475206804 ,459788476 ,306220148 ] p=18443 q=49891 phin=(p-1 )*(q-1 ) d=gmpy2.invert(e,phin) flag="" for i in c: flag=flag+chr (pow (i,d,n))print (flag)
8、Dangerous RSA(低加密指数攻击)
已经有了n,e,c
这题我们发现一个问题,N太大了,不可能分解出来。但是这里有个特点即e很小,只有3
这就需要用到低加密指数攻击。
我们重新看RSA的原理图
我们看加密过程,现在N,e,c都有了,但是m是需要求的,分解N的方法是不可行的,但是有另一种方法
这里分两张情况,当M^e < N的时候,M^e就等于c,比如2^3 mod 100=2^3,那么m就只需要把c开e次方就得到了。
另一种情况就是当M^e > N的时候,可以用爆破的方法,我们列方程,假设M^e / n 的商为 k 余数为C,那么M^e = kn + C,这个时候就可以对k进行爆破, 只要k满足 k*n + C能够开e次方就可以得明文
我们再看这两种情况,可以发现前提都是e必须小,越小越好,因为两张情况都需要开e次方,这就是这类题目的特点。
现在就可以写脚本解题了
写脚本的时候发现可以简化,刚刚两种情况其实可以看作一种情况,即第二种情况中的k=0时,就是第一种情况。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 from gmpy2 import irootimport libnum e = 0x3 n = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793 c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365 k = 0 while 1 : res = iroot(c+k*n,e) if (res[1 ] == True ): print (libnum.n2s(int (res[0 ]))) break k=k+1
9、[HDCTF2019]basic rsa
这题可以看到p和q都已知了,密文c是已知的,flag是m是需要求的,就是已知c,d,p,q求m
先把d求出来
1 2 3 4 5 6 7 import gmpy2 p = 262248800182277040650192055439906580479 q = 262854994239322828547925595487519915551 e = 65533 fn = (p-1 )*(q-1 ) d = gmpy2.invert(e,fn)print (d)
1 d =51938044911383735496696766945348482589325573182146510406365903911685548598997
有了d就可以求出m了
因为是flag所以肯定不是数字,所以m需要转一下
1 2 3 4 5 6 7 8 from binascii import a2b_hex d = 51938044911383735496696766945348482589325573182146510406365903911685548598997 p = 262248800182277040650192055439906580479 q = 262854994239322828547925595487519915551 n = p*q c=27565231154623519221597938803435789010285480123476977081867877272451638645710 flag = a2b_hex(hex (pow (c,d,n))[2 :]) print (flag)
10、[GUET-CTF2019]BabyRSA
给了p+q同时也给了(p+1)(q+1)这个就是φ(N)了,私钥d也给了,但是N没给,先要把N算出来
(p+1)(q+1)=p*q+(p+q)+1
那么p*q就可以算出来了
注:代码中a:(p+1)*(q+1),b:p+q
1 2 3 4 5 6 7 8 9 from binascii import a2b_hex a=0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740 b=0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea N=a-b-1 c=0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a d=0x2dde7fbaed477f6d62838d55b0d0964868cf6efb2c282a5f13e6008ce7317a24cb57aec49ef0d738919f47cdcd9677cd52ac2293ec5938aa198f962678b5cd0da344453f521a69b2ac03647cdd8339f4e38cec452d54e60698833d67f9315c02ddaa4c79ebaa902c605d7bda32ce970541b2d9a17d62b52df813b2fb0c5ab1a5 m=pow (c,d,N) flag = a2b_hex(hex (m)[2 :])print (flag)
11、rsa2(低解密指数攻击)
题目说明:听说这题是rsa的续集
这题给了N和e,需要我们求d,一般情况下我们是分解N,但是N太大了,我们还可以低加密指数攻击,但是e也太大了。
所以这里要用到低解密指数攻击,前提就是e很大,d很小,因为d是解密指数,所以低解密指数就是d很小,d和e是相对的,d越小e越大
解这种题目需要一个工具:https://github.com/pablocelayes/rsa-wiener-attack
需要把整个工具都下载下来,然后在这个文件夹里面新建我们的脚本文件——低解密指数攻击main.py
1 2 3 4 5 6 7 8 import hashlibimport RSAwienerHacker N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471 e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085 d = RSAwienerHacker.hack_RSA(e,N)print (d) flag = "flag{" + hashlib.md5(hex (d)).hexdigest() + "}" print (flag)
用python2跑
12、RSA5(低加密指数广播攻击)
这题有很多的n和c
是低加密指数广播攻击
就是说e比较小,并且都是用同一个加密指数e来加密,但是N不一样,这时就可以根据广播攻击得到明文
介绍一下什么是广播,假如我们需要将一份明文进行多份加密,但是每份使用不同的密钥,密钥中的模数n不同但指数e相同且很小,我们只要拿到多份密文和对应的n就可以利用中国剩余定理进行解密。
这篇专门讲了中国剩余定理的原理 ,下面摘录下来了,防止原文挂了
问题:今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?
简单点说就是,存在一个数x,除以3余2,除以5余三,除以7余二,然后求这个数。上面给出了解法。再明白这个解法的原理之前,需要先知道一下两个定理。
定理1:两个数相加,如果存在一个加数,不能被整数a整除,那么它们的和,就不能被整数a整除。
定理2:两数不能整除,若除数扩大(或缩小)了几倍,而被除数不变,则其商和余数也同时扩大(或缩小)相同的倍数(余数必小于除数)。
以上两个定理随便个例子即可证明!
现给出求解该问题的具体步骤:
1、求出最小公倍数
lcm=3*5*7=105
2、求各个数所对应的基础数
(1)105÷3=35
35÷3=11......2 //基础数35
(2)105÷5=21
21÷5=4……1
定理2把1扩大3倍得到3,那么被除数也扩大3倍,得到21*3=63//基础数63
(3)105÷7=15
15÷7=2……1
定理2把1扩大2倍得到2,那么被除数也扩大2倍,得到15*2=30//基础数30
把得到的基础数加和(注意:基础数不一定就是正数)
35+63+30=128
4、减去最小公倍数lcm(在比最小公倍数大的情况下)
x=128-105=23
那么满足题意得最小的数就是23了。一共有四个步骤。下面详细解释每一步的原因。
(1)最小公倍数就不解释了,跳过(记住,这里讨论的都是两两互质的情况)
(2)观察求每个数对应的基础数时候的步骤,比如第一个。105÷3=35。显然这个35是除了当前这个数不能整除以外都能够被其他数整除,就是其他数的最小公倍数。相当于找到了最小的起始值,用它去除以3发现正好余2。那么这个基础数就是35。记住35的特征,可以整除其他数但是不能被3整除,并且余数是2。体现的还不够明显,再看下5对应的基础数。21是其他数的最小公倍数,但是不能被5整除,用21除以5得到的余数是1,而要求的数除以5应该是余1的。所以余数被扩大,就得到了相应的基础数63。记住这个数的特征,可以被其他数整除但是被5除应该余三。同理,我们得到了第三个基础数23,那么他的特征就是:可以被其他数整除,但是不能被7整除,并且余数为2。
(3)第三步基础数加和,为什么要这样做呢?利用就是上面提到的定理1。
**35+63+30=128。对于3来说,可以把63+30的和看作一个整体,应该他们都可以被3整除。看着上面写出的三个数的特征,运用定理1来说,就是在35的基础上加上一个可以被3整除的倍数,那么得到的结果依然还是满足原先的性质的,就是128除以同样还是余2的。同理,对于5还说,这个数被除之后会剩余3;对于7来说,被除之后剩余2。所以说,我们当前得到的这个数是满足题目要求的一个数。但是这个数是不是最小的,那就不一定了。 **
(4)应该不能确定是不是最小的数,这个时候就要用到他们的最小公倍数了。最小公倍数顾名思义,一定是一个同时被几个数整除的最小的一个数,所以减去它剩余下来的余数还是符合题意要求的。当然也同样可以运用定理1来解释,只不过是加法变成了减法,道理还是一样的。当然具体要不要剪还是要看和lcm的大小关系的。
稍微的总结一下:就是已知m1,m2,m3是两两互质的正整数,求最小的正整数x,使它被m1,m2,m3除所得的余数分别是c1,c2,c3。孙子定理的思想便是线分别求出被其中数mi整除余1而被另外两个数整除的数Mi(i=1,2,3),则所求数之一的便是c1M1+c2M2+c3M3。由此我们可以得到n个两两互质数的情况。证明上面已经一步一步给出。
那么,到此为止基本的中国剩余定理的内容我们以及了解了,包括解答方法。那么如何编码呢?按照上面这个思路去编码,其实并不难。一共分为四大步。但是,大多数人的困惑在于如何求取基础数。这里呢,提供两种方法:
(1)第一种就是一直递增,直到找到。例如:3的基础数,35是其他数的最小公倍数。那么就从35开始,一直自增,直到余数为2,便停止(利用while循环)。
(2)第二种方法呢就是辗转相除法上得来的。这里的例子体现的不够明显,应当看看去求取乘法逆元的过程,下面讲的内容和乘法逆元有很大的关系,所以还是看看的好。简单举个例子:
假设现在三个数分别是14,3,5,它们两两互质,且要求的数除以5余3。求5对应的基础数。有:
42÷5=8……2
5÷2=2……1
所以1=5-2*2=5-2*(42-8*5)=-2*42+17*5
那么-2*42=-84 17*5=85 -84+85=1
把1扩大3倍变成3,则有-84*3=-252也就是5对应的基础数。
第一点: 基础数可以是负数,这个之前点到过。//并且下面的解法就是有这样的。
第二点: 当得到余数为1的时候后面的算式相当于是一个回溯的过程,最后解到-2*42。 但是还只不过是余数是1的情况对应的数,再运用定理2我们就得到了-252这个基础数。实际上要是看过乘法逆元,这里实际就是乘法逆元的求解过程,而-2也就是42关于15取模的乘法逆元。
用中国剩余定理解这道题的代码是这样的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import gmpy2import timedef CRT (items ): N = reduce(lambda x, y: x * y, (i[1 ] for i in items)) result = 0 for a, n in items: m = N / n d, r, s = gmpy2.gcdext(n, m) if d != 1 : raise Exception("Input not pairwise co-prime" ) result += a * s * m return result % N, N e = n = [...L,...L] c = [...L,...L] data = zip (c, n) x, n = CRT(data) m = gmpy2.iroot(gmpy2.mpz(x), e)[0 ]print m
但是本题e较大,不建议使用中国剩余定理求解,这题的方法是:
因为不同的模数n中可能存在相同的p或者相同的q,那么我们就求出不同n之间的最大公约数 gcd(),即可得到p或者是q,再求得d,最后得到明文
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 import gmpy2from binascii import a2b_hex e = 65537 n1 = 20474918894051778533305262345601880928088284471121823754049725354072477155873778848055073843345820697886641086842612486541250183965966001591342031562953561793332341641334302847996108417466360688139866505179689516589305636902137210185624650854906780037204412206309949199080005576922775773722438863762117750429327585792093447423980002401200613302943834212820909269713876683465817369158585822294675056978970612202885426436071950214538262921077409076160417436699836138801162621314845608796870206834704116707763169847387223307828908570944984416973019427529790029089766264949078038669523465243837675263858062854739083634207 c1 = 974463908243330865728978769213595400782053398596897741316275722596415018912929508637393850919224969271766388710025195039896961956062895570062146947736340342927974992616678893372744261954172873490878805483241196345881721164078651156067119957816422768524442025688079462656755605982104174001635345874022133045402344010045961111720151990412034477755851802769069309069018738541854130183692204758761427121279982002993939745343695671900015296790637464880337375511536424796890996526681200633086841036320395847725935744757993013352804650575068136129295591306569213300156333650910795946800820067494143364885842896291126137320 n2 = 20918819960648891349438263046954902210959146407860980742165930253781318759285692492511475263234242002509419079545644051755251311392635763412553499744506421566074721268822337321637265942226790343839856182100575539845358877493718334237585821263388181126545189723429262149630651289446553402190531135520836104217160268349688525168375213462570213612845898989694324269410202496871688649978370284661017399056903931840656757330859626183773396574056413017367606446540199973155630466239453637232936904063706551160650295031273385619470740593510267285957905801566362502262757750629162937373721291789527659531499435235261620309759 c2 = 15819636201971185538694880505120469332582151856714070824521803121848292387556864177196229718923770810072104155432038682511434979353089791861087415144087855679134383396897817458726543883093567600325204596156649305930352575274039425470836355002691145864435755333821133969266951545158052745938252574301327696822347115053614052423028835532509220641378760800693351542633860702225772638930501021571415907348128269681224178300248272689705308911282208685459668200507057183420662959113956077584781737983254788703048275698921427029884282557468334399677849962342196140864403989162117738206246183665814938783122909930082802031855 n3 = 25033254625906757272369609119214202033162128625171246436639570615263949157363273213121556825878737923265290579551873824374870957467163989542063489416636713654642486717219231225074115269684119428086352535471683359486248203644461465935500517901513233739152882943010177276545128308412934555830087776128355125932914846459470221102007666912211992310538890654396487111705385730502843589727289829692152177134753098649781412247065660637826282055169991824099110916576856188876975621376606634258927784025787142263367152947108720757222446686415627479703666031871635656314282727051189190889008763055811680040315277078928068816491 c3 = 4185308529416874005831230781014092407198451385955677399668501833902623478395669279404883990725184332709152443372583701076198786635291739356770857286702107156730020004358955622511061410661058982622055199736820808203841446796305284394651714430918690389486920560834672316158146453183789412140939029029324756035358081754426645160033262924330248675216108270980157049705488620263485129480952814764002865280019185127662449318324279383277766416258142275143923532168798413011028271543085249029048997452212503111742302302065401051458066585395360468447460658672952851643547193822775218387853623453638025492389122204507555908862 n4 = 21206968097314131007183427944486801953583151151443627943113736996776787181111063957960698092696800555044199156765677935373149598221184792286812213294617749834607696302116136745662816658117055427803315230042700695125718401646810484873064775005221089174056824724922160855810527236751389605017579545235876864998419873065217294820244730785120525126565815560229001887622837549118168081685183371092395128598125004730268910276024806808565802081366898904032509920453785997056150497645234925528883879419642189109649009132381586673390027614766605038951015853086721168018787523459264932165046816881682774229243688581614306480751 c4 = 4521038011044758441891128468467233088493885750850588985708519911154778090597136126150289041893454126674468141393472662337350361712212694867311622970440707727941113263832357173141775855227973742571088974593476302084111770625764222838366277559560887042948859892138551472680654517814916609279748365580610712259856677740518477086531592233107175470068291903607505799432931989663707477017904611426213770238397005743730386080031955694158466558475599751940245039167629126576784024482348452868313417471542956778285567779435940267140679906686531862467627238401003459101637191297209422470388121802536569761414457618258343550613 n5 = 22822039733049388110936778173014765663663303811791283234361230649775805923902173438553927805407463106104699773994158375704033093471761387799852168337898526980521753614307899669015931387819927421875316304591521901592823814417756447695701045846773508629371397013053684553042185725059996791532391626429712416994990889693732805181947970071429309599614973772736556299404246424791660679253884940021728846906344198854779191951739719342908761330661910477119933428550774242910420952496929605686154799487839923424336353747442153571678064520763149793294360787821751703543288696726923909670396821551053048035619499706391118145067 c5 = 15406498580761780108625891878008526815145372096234083936681442225155097299264808624358826686906535594853622687379268969468433072388149786607395396424104318820879443743112358706546753935215756078345959375299650718555759698887852318017597503074317356745122514481807843745626429797861463012940172797612589031686718185390345389295851075279278516147076602270178540690147808314172798987497259330037810328523464851895621851859027823681655934104713689539848047163088666896473665500158179046196538210778897730209572708430067658411755959866033531700460551556380993982706171848970460224304996455600503982223448904878212849412357 n6 = 21574139855341432908474064784318462018475296809327285532337706940126942575349507668289214078026102682252713757703081553093108823214063791518482289846780197329821139507974763780260290309600884920811959842925540583967085670848765317877441480914852329276375776405689784571404635852204097622600656222714808541872252335877037561388406257181715278766652824786376262249274960467193961956690974853679795249158751078422296580367506219719738762159965958877806187461070689071290948181949561254144310776943334859775121650186245846031720507944987838489723127897223416802436021278671237227993686791944711422345000479751187704426369 c6 = 20366856150710305124583065375297661819795242238376485264951185336996083744604593418983336285185491197426018595031444652123288461491879021096028203694136683203441692987069563513026001861435722117985559909692670907347563594578265880806540396777223906955491026286843168637367593400342814725694366078337030937104035993569672959361347287894143027186846856772983058328919716702982222142848848117768499996617588305301483085428547267337070998767412540225911508196842253134355901263861121500650240296746702967594224401650220168780537141654489215019142122284308116284129004257364769474080721001708734051264841350424152506027932 n7 = 25360227412666612490102161131174584819240931803196448481224305250583841439581008528535930814167338381983764991296575637231916547647970573758269411168219302370541684789125112505021148506809643081950237623703181025696585998044695691322012183660424636496897073045557400768745943787342548267386564625462143150176113656264450210023925571945961405709276631990731602198104287528528055650050486159837612279600415259486306154947514005408907590083747758953115486124865486720633820559135063440942528031402951958557630833503775112010715604278114325528993771081233535247118481765852273252404963430792898948219539473312462979849137 c7 = 19892772524651452341027595619482734356243435671592398172680379981502759695784087900669089919987705675899945658648623800090272599154590123082189645021800958076861518397325439521139995652026377132368232502108620033400051346127757698623886142621793423225749240286511666556091787851683978017506983310073524398287279737680091787333547538239920607761080988243639547570818363788673249582783015475682109984715293163137324439862838574460108793714172603672477766831356411304446881998674779501188163600664488032943639694828698984739492200699684462748922883550002652913518229322945040819064133350314536378694523704793396169065179 n8 = 22726855244632356029159691753451822163331519237547639938779517751496498713174588935566576167329576494790219360727877166074136496129927296296996970048082870488804456564986667129388136556137013346228118981936899510687589585286517151323048293150257036847475424044378109168179412287889340596394755257704938006162677656581509375471102546261355748251869048003600520034656264521931808651038524134185732929570384705918563982065684145766427962502261522481994191989820110575981906998431553107525542001187655703534683231777988419268338249547641335718393312295800044734534761692799403469497954062897856299031257454735945867491191 c8 = 6040119795175856407541082360023532204614723858688636724822712717572759793960246341800308149739809871234313049629732934797569781053000686185666374833978403290525072598774001731350244744590772795701065129561898116576499984185920661271123665356132719193665474235596884239108030605882777868856122378222681140570519180321286976947154042272622411303981011302586225630859892731724640574658125478287115198406253847367979883768000812605395482952698689604477719478947595442185921480652637868335673233200662100621025061500895729605305665864693122952557361871523165300206070325660353095592778037767395360329231331322823610060006 n9 = 23297333791443053297363000786835336095252290818461950054542658327484507406594632785712767459958917943095522594228205423428207345128899745800927319147257669773812669542782839237744305180098276578841929496345963997512244219376701787616046235397139381894837435562662591060768476997333538748065294033141610502252325292801816812268934171361934399951548627267791401089703937389012586581080223313060159456238857080740699528666411303029934807011214953984169785844714159627792016926490955282697877141614638806397689306795328344778478692084754216753425842557818899467945102646776342655167655384224860504086083147841252232760941 c9 = 5418120301208378713115889465579964257871814114515046096090960159737859076829258516920361577853903925954198406843757303687557848302302200229295916902430205737843601806700738234756698575708612424928480440868739120075888681672062206529156566421276611107802917418993625029690627196813830326369874249777619239603300605876865967515719079797115910578653562787899019310139945904958024882417833736304894765433489476234575356755275147256577387022873348906900149634940747104513850154118106991137072643308620284663108283052245750945228995387803432128842152251549292698947407663643895853432650029352092018372834457054271102816934 n10 = 28873667904715682722987234293493200306976947898711255064125115933666968678742598858722431426218914462903521596341771131695619382266194233561677824357379805303885993804266436810606263022097900266975250431575654686915049693091467864820512767070713267708993899899011156106766178906700336111712803362113039613548672937053397875663144794018087017731949087794894903737682383916173267421403408140967713071026001874733487295007501068871044649170615709891451856792232315526696220161842742664778581287321318748202431466508948902745314372299799561625186955234673012098210919745879882268512656931714326782335211089576897310591491 c10 = 9919880463786836684987957979091527477471444996392375244075527841865509160181666543016317634963512437510324198702416322841377489417029572388474450075801462996825244657530286107428186354172836716502817609070590929769261932324275353289939302536440310628698349244872064005700644520223727670950787924296004296883032978941200883362653993351638545860207179022472492671256630427228461852668118035317021428675954874947015197745916918197725121122236369382741533983023462255913924692806249387449016629865823316402366017657844166919846683497851842388058283856219900535567427103603869955066193425501385255322097901531402103883869 n11 = 22324685947539653722499932469409607533065419157347813961958075689047690465266404384199483683908594787312445528159635527833904475801890381455653807265501217328757871352731293000303438205315816792663917579066674842307743845261771032363928568844669895768092515658328756229245837025261744260614860746997931503548788509983868038349720225305730985576293675269073709022350700836510054067641753713212999954307022524495885583361707378513742162566339010134354907863733205921845038918224463903789841881400814074587261720283879760122070901466517118265422863420376921536734845502100251460872499122236686832189549698020737176683019 c11 = 1491527050203294989882829248560395184804977277747126143103957219164624187528441047837351263580440686474767380464005540264627910126483129930668344095814547592115061057843470131498075060420395111008619027199037019925701236660166563068245683975787762804359520164701691690916482591026138582705558246869496162759780878437137960823000043988227303003876410503121370163303711603359430764539337597866862508451528158285103251810058741879687875218384160282506172706613359477657215420734816049393339593755489218588796607060261897905233453268671411610631047340459487937479511933450369462213795738933019001471803157607791738538467 n12 = 27646746423759020111007828653264027999257847645666129907789026054594393648800236117046769112762641778865620892443423100189619327585811384883515424918752749559627553637785037359639801125213256163008431942593727931931898199727552768626775618479833029101249692573716030706695702510982283555740851047022672485743432464647772882314215176114732257497240284164016914018689044557218920300262234652840632406067273375269301008409860193180822366735877288205783314326102263756503786736122321348320031950012144905869556204017430593656052867939493633163499580242224763404338807022510136217187779084917996171602737036564991036724299 c12 = 21991524128957260536043771284854920393105808126700128222125856775506885721971193109361315961129190814674647136464887087893990660894961612838205086401018885457667488911898654270235561980111174603323721280911197488286585269356849579263043456316319476495888696219344219866516861187654180509247881251251278919346267129904739277386289240394384575124331135655943513831009934023397457082184699737734388823763306805326430395849935770213817533387235486307008892410920611669932693018165569417445885810825749609388627231235840912644654685819620931663346297596334834498661789016450371769203650109994771872404185770230172934013971 n13 = 20545487405816928731738988374475012686827933709789784391855706835136270270933401203019329136937650878386117187776530639342572123237188053978622697282521473917978282830432161153221216194169879669541998840691383025487220850872075436064308499924958517979727954402965612196081404341651517326364041519250125036424822634354268773895465698920883439222996581226358595873993976604699830613932320720554130011671297944433515047180565484495191003887599891289037982010216357831078328159028953222056918189365840711588671093333013117454034313622855082795813122338562446223041211192277089225078324682108033843023903550172891959673551 c13 = 14227439188191029461250476692790539654619199888487319429114414557975376308688908028140817157205579804059783807641305577385724758530138514972962209062230576107406142402603484375626077345190883094097636019771377866339531511965136650567412363889183159616188449263752475328663245311059988337996047359263288837436305588848044572937759424466586870280512424336807064729894515840552404756879590698797046333336445465120445087587621743906624279621779634772378802959109714400516183718323267273824736540168545946444437586299214110424738159957388350785999348535171553569373088251552712391288365295267665691357719616011613628772175 n14 = 27359727711584277234897157724055852794019216845229798938655814269460046384353568138598567755392559653460949444557879120040796798142218939251844762461270251672399546774067275348291003962551964648742053215424620256999345448398805278592777049668281558312871773979931343097806878701114056030041506690476954254006592555275342579529625231194321357904668512121539514880704046969974898412095675082585315458267591016734924646294357666924293908418345508902112711075232047998775303603175363964055048589769318562104883659754974955561725694779754279606726358588862479198815999276839234952142017210593887371950645418417355912567987 c14 = 3788529784248255027081674540877016372807848222776887920453488878247137930578296797437647922494510483767651150492933356093288965943741570268943861987024276610712717409139946409513963043114463933146088430004237747163422802959250296602570649363016151581364006795894226599584708072582696996740518887606785460775851029814280359385763091078902301957226484620428513604630585131511167015763190591225884202772840456563643159507805711004113901417503751181050823638207803533111429510911616160851391754754434764819568054850823810901159821297849790005646102129354035735350124476838786661542089045509656910348676742844957008857457 n15 = 27545937603751737248785220891735796468973329738076209144079921449967292572349424539010502287564030116831261268197384650511043068738911429169730640135947800885987171539267214611907687570587001933829208655100828045651391618089603288456570334500533178695238407684702251252671579371018651675054368606282524673369983034682330578308769886456335818733827237294570476853673552685361689144261552895758266522393004116017849397346259119221063821663280935820440671825601452417487330105280889520007917979115568067161590058277418371493228631232457972494285014767469893647892888681433965857496916110704944758070268626897045014782837 c15 = 14069112970608895732417039977542732665796601893762401500878786871680645798754783315693511261740059725171342404186571066972546332813667711135661176659424619936101038903439144294886379322591635766682645179888058617577572409307484708171144488708410543462972008179994594087473935638026612679389759756811490524127195628741262871304427908481214992471182859308828778119005750928935764927967212343526503410515793717201360360437981322576798056276657140363332700714732224848346808963992302409037706094588964170239521193589470070839790404597252990818583717869140229811712295005710540476356743378906642267045723633874011649259842 n16 = 25746162075697911560263181791216433062574178572424600336856278176112733054431463253903433128232709054141607100891177804285813783247735063753406524678030561284491481221681954564804141454666928657549670266775659862814924386584148785453647316864935942772919140563506305666207816897601862713092809234429096584753263707828899780979223118181009293655563146526792388913462557306433664296966331469906428665127438829399703002867800269947855869262036714256550075520193125987011945192273531732276641728008406855871598678936585324782438668746810516660152018244253008092470066555687277138937298747951929576231036251316270602513451 c16 = 17344284860275489477491525819922855326792275128719709401292545608122859829827462088390044612234967551682879954301458425842831995513832410355328065562098763660326163262033200347338773439095709944202252494552172589503915965931524326523663289777583152664722241920800537867331030623906674081852296232306336271542832728410803631170229642717524942332390842467035143631504401140727083270732464237443915263865880580308776111219718961746378842924644142127243573824972533819479079381023103585862099063382129757560124074676150622288706094110075567706403442920696472627797607697962873026112240527498308535903232663939028587036724 n17 = 23288486934117120315036919418588136227028485494137930196323715336208849327833965693894670567217971727921243839129969128783853015760155446770590696037582684845937132790047363216362087277861336964760890214059732779383020349204803205725870225429985939570141508220041286857810048164696707018663758416807708910671477407366098883430811861933014973409390179948577712579749352299440310543689035651465399867908428885541237776143404376333442949397063249223702355051571790555151203866821867908531733788784978667478707672984539512431549558672467752712004519300318999208102076732501412589104904734983789895358753664077486894529499 c17 = 10738254418114076548071448844964046468141621740603214384986354189105236977071001429271560636428075970459890958274941762528116445171161040040833357876134689749846940052619392750394683504816081193432350669452446113285638982551762586656329109007214019944975816434827768882704630460001209452239162896576191876324662333153835533956600295255158377025198426950944040643235430211011063586032467724329735785947372051759042138171054165854842472990583800899984893232549092766400510300083585513014171220423103452292891496141806956300396540682381668367564569427813092064053993103537635994311143010708814851867239706492577203899024 n18 = 19591441383958529435598729113936346657001352578357909347657257239777540424811749817783061233235817916560689138344041497732749011519736303038986277394036718790971374656832741054547056417771501234494768509780369075443550907847298246275717420562375114406055733620258777905222169702036494045086017381084272496162770259955811174440490126514747876661317750649488774992348005044389081101686016446219264069971370646319546429782904810063020324704138495608761532563310699753322444871060383693044481932265801505819646998535192083036872551683405766123968487907648980900712118052346174533513978009131757167547595857552370586353973 c18 = 3834917098887202931981968704659119341624432294759361919553937551053499607440333234018189141970246302299385742548278589896033282894981200353270637127213483172182529890495903425649116755901631101665876301799865612717750360089085179142750664603454193642053016384714515855868368723508922271767190285521137785688075622832924829248362774476456232826885801046969384519549385428259591566716890844604696258783639390854153039329480726205147199247183621535172450825979047132495439603840806501254997167051142427157381799890725323765558803808030109468048682252028720241357478614704610089120810367192414352034177484688502364022887 n19 = 19254242571588430171308191757871261075358521158624745702744057556054652332495961196795369630484782930292003238730267396462491733557715379956969694238267908985251699834707734400775311452868924330866502429576951934279223234676654749272932769107390976321208605516299532560054081301829440688796904635446986081691156842271268059970762004259219036753174909942343204432795076377432107630203621754552804124408792358220071862369443201584155711893388877350138023238624566616551246804054720492816226651467017802504094070614892556444425915920269485861799532473383304622064493223627552558344088839860178294589481899206318863310603 c19 = 6790553533991297205804561991225493105312398825187682250780197510784765226429663284220400480563039341938599783346724051076211265663468643826430109013245014035811178295081939958687087477312867720289964506097819762095244479129359998867671811819738196687884696680463458661374310994610760009474264115750204920875527434486437536623589684519411519100170291423367424938566820315486507444202022408003879118465761273916755290898112991525546114191064022991329724370064632569903856189236177894007766690782630247443895358893983735822824243487181851098787271270256780891094405121947631088729917398317652320497765101790132679171889 n20 = 26809700251171279102974962949184411136459372267620535198421449833298448092580497485301953796619185339316064387798092220298630428207556482805739803420279056191194360049651767412572609187680508073074653291350998253938793269214230457117194434853888765303403385824786231859450351212449404870776320297419712486574804794325602760347306432927281716160368830187944940128907971027838510079519466846176106565164730963988892400240063089397720414921398936399927948235195085202171264728816184532651138221862240969655185596628285814057082448321749567943946273776184657698104465062749244327092588237927996419620170254423837876806659 c20 = 386213556608434013769864727123879412041991271528990528548507451210692618986652870424632219424601677524265011043146748309774067894985069288067952546139416819404039688454756044862784630882833496090822568580572859029800646671301748901528132153712913301179254879877441322285914544974519727307311002330350534857867516466612474769753577858660075830592891403551867246057397839688329172530177187042229028685862036140779065771061933528137423019407311473581832405899089709251747002788032002094495379614686544672969073249309703482556386024622814731015767810042969813752548617464974915714425595351940266077021672409858645427346 n=[n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,n12,n13,n14,n15,n16,n17,n18,n19,n20] c=[c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19,c20]for i in range (len (n)): for j in range (len (n)): if (i!=j): if (gmpy2.gcd(n[i],n[j])!=1 ): print (i,j) p = gmpy2.gcd(n[i],n[j]) q = n[i] d = gmpy2.invert(e , (p-1 )*(q-1 )) m = pow (c[i],d,n[i]) print (m) flag = a2b_hex(hex (m)[2 :])print (flag)
13、[NCTF2019]childRSA
这题看上去就比较复杂了,我们分析一下
已知N,e和c
这里有一种方法直接用yafu分解N,应该算是一种非预期解法,但是确实可以解出来,yafu下载地址
(当 p、q 的取值差异过大或过于相近的时候,使用 yafu 可以快速的把 n 值分解出 p、q 值,但是如果 n 较大,且经过几轮分解都没有得出结果,那么此方法就不行了)
Windows下载到桌面shift+右键打开powershell
先测试一下是否可用
1 .\yafu-x64.exe "factor(8)"
分解因数8可以看到得到结果,证明程序运行没问题
如果因数过长,将 因数 用文本文件存放在 yafu 目录下,例如:data.txt 。
1 .\yafu-x64.exe "factor(@)" -batchfile data.txt
但是这里需要注意一下,txt文件最后要加一个空行,否则会报错,如下
回车换行即可
1 2 p =178449493212694205742332078583256205058672290603652616240227340638730811945224947826121772642204629335108873832781921390308501763661154638696935732709724016546955977529088135995838497476350749621442719690722226913635772410880516639651363626821442456779009699333452616953193799328647446968707045304702547915799734431818800374360377292309248361548868909066895474518333089446581763425755389837072166970684877011663234978631869703859541876049132713490090720408351108387971577438951727337962368478059295446047962510687695047494480605473377173021467764495541590394732685140829152761532035790187269724703444386838656193674253139 q =184084121540115307597161367011014142898823526027674354555037785878481711602257307508985022577801782788769786800015984410443717799994642236194840684557538917849420967360121509675348296203886340264385224150964642958965438801864306187503790100281099130863977710204660546799128755418521327290719635075221585824217487386227004673527292281536221958961760681032293340099395863194031788435142296085219594866635192464353365034089592414809332183882423461536123972873871477755949082223830049594561329457349537703926325152949582123419049073013144325689632055433283354999265193117288252918515308767016885678802217366700376654365502867
1 2 3 4 5 6 7 8 9 10 11 import gmpy2from binascii import a2b_hex p=178449493212694205742332078583256205058672290603652616240227340638730811945224947826121772642204629335108873832781921390308501763661154638696935732709724016546955977529088135995838497476350749621442719690722226913635772410880516639651363626821442456779009699333452616953193799328647446968707045304702547915799734431818800374360377292309248361548868909066895474518333089446581763425755389837072166970684877011663234978631869703859541876049132713490090720408351108387971577438951727337962368478059295446047962510687695047494480605473377173021467764495541590394732685140829152761532035790187269724703444386838656193674253139 q=184084121540115307597161367011014142898823526027674354555037785878481711602257307508985022577801782788769786800015984410443717799994642236194840684557538917849420967360121509675348296203886340264385224150964642958965438801864306187503790100281099130863977710204660546799128755418521327290719635075221585824217487386227004673527292281536221958961760681032293340099395863194031788435142296085219594866635192464353365034089592414809332183882423461536123972873871477755949082223830049594561329457349537703926325152949582123419049073013144325689632055433283354999265193117288252918515308767016885678802217366700376654365502867 e=0x10001 c=26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108 n=p*q phi_n = (p-1 )*(q-1 ) d = gmpy2.invert(e,phi_n) flag = a2b_hex(hex (pow (c,d,n))[2 :])print (flag)
刚刚这个分解N是非预期解法,现在看一下预期解法,先重新看回题目
这里的getPrime()函数是为了生成p和q。
其中primes是Crypto.Util.number
模块中定义的前10000个质数,按照官方wp的说法,在VScode中按F12即可跳转到定义处
可以看到在primes中显示其最大的质数是104729
再看getPrime()函数,它用choice()函数从primes中随机取出一个质数,然后累乘进n中。然后判断n+1是不是质数,如果是就返回n+1,这样getPrime()函数的功能就完成了,成功获取到质数。
还要补充一下这个累乘的条件,就是while中,如果n的二进制位数大于等于2048就不乘了(这个二进制位数比如1的二进制是1,那么二进制位数就是1,比如3的二进制是11,那么二进制位数就是2)
已经分析完了,现在重新对getPrime()函数做一个注释
1 2 3 4 5 6 7 def getPrime (bits ): while True : n = 2 while n.bit_length() < bits: n *= choice(primes) if isPrime(n + 1 ): return n + 1
然后再看这行引用getPrime()函数的代码
1 p, q = [getPrime(2048 ) for _ in range (2 )]
其他代码都很好理解,那么现在题目给的代码已经完全可以读懂了,我们需要反过来得到m
这里具体的方法还没搞懂,涉及到费马小定理,先贴上官方的wp供参考http://yulige.top/?p=752#childRSA213pt_38solvers
14、[BJDCTF2020]RSA 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 from Crypto.Util.number import getPrime,bytes_to_long flag=open ("flag" ,"rb" ).read() p=getPrime(1024 ) q=getPrime(1024 )assert (e<100000 ) n=p*q m=bytes_to_long(flag) c=pow (m,e,n)print c,nprint pow (294 ,e,n) p=getPrime(1024 ) n=p*q m=bytes_to_long("BJD" *32 ) c=pow (m,e,n)print c,n''' output: 12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120 13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037 381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018 979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721 12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047 '''
这里有c1,n1,c2,n2
通过q=gcd(n1,n2)这个公式我们可以求出q来
题目打印了pow(294,e,n)的结果,n我们知道n1或者n2都行,但是e不知道,题目说e<100000那么我们就枚举e
1 2 3 4 5 6 7 for i in range (100000 ): res=pow (294 ,i,n1) if (res==output): e=i break
得到e=52361
那么都可以解了,下面是完整代码(python2)
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 from gmpy2 import *from Crypto.Util.number import * c1=12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120 n1=13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037 c2=979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721 n2=12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047 q=gcd(n1,n2) output=381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018 for i in range (100000 ): res=pow (294 ,i,n1) if (res==output): e=i break e=52361 p=n1//q phi=(p-1 )*(q-1 ) d=invert(e,phi) m=pow (c1,d,n1) flag=long_to_bytes(m)print (flag)
15、[HDCTF2019]bbbbbbrsa
给了两个文件,这里的enc文件里面有个c但是是加密的,这两个等于号像是base64,但是base64的等于号是在最后的,所以怀疑需要把字符倒置
在线倒置一下
http://tool.huixiang360.com/str/reverse.php
c出来了
刚把c弄出来就发现encode.py文件最后一句就是输出c
那么就差e了,只需要把e算出来就解出来了
我们看代码
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 from base64 import b64encode as b32encodefrom gmpy2 import invert,gcd,irootfrom Crypto.Util.number import *from binascii import a2b_hex,b2a_heximport random flag = "******************************" nbit = 128 p = getPrime(nbit) q = getPrime(nbit) n = p*qprint pprint n phi = (p-1 )*(q-1 ) e = random.randint(50000 ,70000 )while True : if gcd(e,phi) == 1 : break ; else : e -= 1 ; c = pow (int (b2a_hex(flag),16 ),e,n)print b32encode(str (c))[::-1 ]
这里的e是通过最原始的方法求的,就是这个e的定义,1<e<phi并且还要与phi互质,因为这个e有范围50000到70000所以是好求的,那么我们也通过这个方法算e。这个gcd(e,phi) == 1其中gcd是求e和phi的最大公约数,如果为1就说明是互质
下面是解密脚本
这里的e是有很多情况的,所以我们要一个个试一下,因为我们已知flag是包含flag或者CTF并且一定包含{}所以我们就一个个试一下(python2跑)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 from base64 import b64encode as b32encodefrom base64 import b64decodefrom gmpy2 import invert, gcd, irootfrom Crypto.Util.number import * p = 177077389675257695042507998165006460849 n = 37421829509887796274897162249367329400988647145613325367337968063341372726061 c64 = '==gMzYDNzIjMxUTNyIzNzIjMyYTM4MDM0gTMwEjNzgTM2UTN4cjNwIjN2QzM5ADMwIDNyMTO4UzM2cTM5kDN2MTOyUTO5YDM0czM3MjM' c = int (b64decode(str (c64)[::-1 ]))print (c) q = n // p phi = (p - 1 ) * (q - 1 )for e in range (50000 , 70000 ): if gcd(e, phi) == 1 : d = invert(e, phi) m = pow (c, d, n) flag = str (long_to_bytes(m)) if 'flag' in flag or 'CTF' in flag or ("{" in flag and '}' in flag): print (flag)