记一次比赛的题解（三）

前言：本篇题解涉及Crypto方向和一小部分的Web方向的题解。

一、Crypto-baby_e

1.代码如下

from Crypto.Util.number import getPrime,bytes_to_long

p,q = getPrime(2048),getPrime(2048)
e = 7
n = p*q
m = bytes_to_long(open('flag.txt','rb').read().strip())
c = pow(m,e,n)
print("c = ",c)
print("n = ",n)

# c =  147693154873835354725007152781732424355869776162377337823960431913672366269917723916891506269449726723757821517328874729037838600793748824028829185409932536014732765063216715033843955453706710187792772702199448156372644163429786386035008302836467605094954587157232829525150652611067567669525072625329634860065850520051628272535479197120008981979404760445193750864902244921407742155742716289495581989134730376783828846663464819337418977287363028738701414486788851136608957124505485242331701209645216580641917007780811842757125048746184068597664780265422321550909392419865169775282217442331295071069272774722564587602419768461231775480847018941840911357926330143045826277813722919121117172763493242590521245640828462665947672485094793188432098216701511715232654611338293295459889814699850788048985878279440740712956248569068077253790198036918598519191892836075254345518967666166925163908185663991353344555402397055977817370082929420443034626201745027965444069777059760865359310439815816749939498993014457995041394803598825093836045546578310632172636478575946653375857640993393714607308326474003446154152048840071034349831168612740218034679021240949747357214453636633636662650940968576792518622437627529244515229173
# n =  553409369582823237678532685244026647155180191225879439432235077135813123637186465008813830373646133388592395760175777499266561095087891764348044063111935877931069321764391883899483374576303169645488542398590564148654412004383012178107972880058460460806768779452529433458826925606225797078653905380530651390617109384086518728626571028089036812787671647095695947167204428442727185744172445701874820612799168887428075695751162763647868386879374037826876671079326544820609721731078985096813307183878793033824330869698508952853770794414757655681370862323768018291030331209143189638496644361618184164228294031490537429556439588954274708598530042700988138862000054458742762198052079867259365645914383561162796796952346445529346145323567650621600171442575319262718389389870407629339714751583360252884338116164466349449862781112019462555743429653595045695696967783338371470032332852204294900011651434678829104876529439166176589508898757122660322523937330848536715937381297551894198974459004139082562228022412335520195652419375915216074658463954339332593244483927157329404652516225481116614815221154229491846087288087715884363786672244655901308480290011237244562251084095684531716327141154558809471185132979704992609461470501119328696999713829

2.题目中给出了e，c，n。我们都知道rsa算法最重要的是需要知道p，q，e，其他的变量都可以根据这三个变量得到。

RSA算法的几个重要公式
n=p*q
dp=(p-1)*(q-1)
c=pow(m,e,n)
m=pow(c,d,n)

题目中的p和q是随机生成的，长度都为2048，但是有n，所以第一想法是去暴力分解n。这里介绍两个常用的分解大素数n的工具。一个是在线网站（http://www.factordb.com/） ，一个是yahu。我尝试了这两个工具，但是因为n实在太大，无法分解。

3.既然分解不出来p和q，就换一种思路。我们可以观察到e很小，但是n很大，加密的c=(m^e)mod n，当m^en时，则有m^e=k*n+c，对k进行爆破。编写脚本：

import gmpy2

e = 7
c = 147693154873835354725007152781732424355869776162377337823960431913672366269917723916891506269449726723757821517328874729037838600793748824028829185409932536014732765063216715033843955453706710187792772702199448156372644163429786386035008302836467605094954587157232829525150652611067567669525072625329634860065850520051628272535479197120008981979404760445193750864902244921407742155742716289495581989134730376783828846663464819337418977287363028738701414486788851136608957124505485242331701209645216580641917007780811842757125048746184068597664780265422321550909392419865169775282217442331295071069272774722564587602419768461231775480847018941840911357926330143045826277813722919121117172763493242590521245640828462665947672485094793188432098216701511715232654611338293295459889814699850788048985878279440740712956248569068077253790198036918598519191892836075254345518967666166925163908185663991353344555402397055977817370082929420443034626201745027965444069777059760865359310439815816749939498993014457995041394803598825093836045546578310632172636478575946653375857640993393714607308326474003446154152048840071034349831168612740218034679021240949747357214453636633636662650940968576792518622437627529244515229173
n = 553409369582823237678532685244026647155180191225879439432235077135813123637186465008813830373646133388592395760175777499266561095087891764348044063111935877931069321764391883899483374576303169645488542398590564148654412004383012178107972880058460460806768779452529433458826925606225797078653905380530651390617109384086518728626571028089036812787671647095695947167204428442727185744172445701874820612799168887428075695751162763647868386879374037826876671079326544820609721731078985096813307183878793033824330869698508952853770794414757655681370862323768018291030331209143189638496644361618184164228294031490537429556439588954274708598530042700988138862000054458742762198052079867259365645914383561162796796952346445529346145323567650621600171442575319262718389389870407629339714751583360252884338116164466349449862781112019462555743429653595045695696967783338371470032332852204294900011651434678829104876529439166176589508898757122660322523937330848536715937381297551894198974459004139082562228022412335520195652419375915216074658463954339332593244483927157329404652516225481116614815221154229491846087288087715884363786672244655901308480290011237244562251084095684531716327141154558809471185132979704992609461470501119328696999713829
k = 0
while 1:
    res = gmpy2.iroot(k * n + c, e)
    if res[1]:
        print(bytes.fromhex(hex(res[0])[2:]))        # b'moectf{SMaLL_3xPon3nt_Mak3_rSa_w3ak!_!lP0iYlJf!M3rux9G9Vf!JoxiMl903lllA}'
        break
    k += 1

二、Crypto-bad_E

1.源代码如下。

from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
e = 65537

print(p) # 6853495238262155391975011057929314523706159020478084061020122347902601182448091015650787022962180599741651597328364289413042032923330906135304995252477571
print(q) # 11727544912613560398705401423145382428897876620077115390278679983274961030035884083100580422155496261311510530671232666801444557695190734596546855494472819

with open("flag.txt","r") as fs:
    flag = fs.read().strip()

m = bytes_to_long(flag.encode())
c = pow(m,e,p*q)
print(c) # 63388263723813143290256836284084914544524440253054612802424934400854921660916379284754467427040180660945667733359330988361620691457570947823206385692232584893511398038141442606303536260023122774682805630913037113541880875125504376791939861734613177272270414287306054553288162010873808058776206524782351475805

2.因为我们知道了p和q，第一反应就是求出d，那这题不就解决了吗。可以问题就出现在求d上了。我们都知道d是当e和(p-1)*(q-1)互素的情况下求出来的逆元，可是这题e和(p-1)*(q-1)不互素，所以用常规的方法就不行了。求gcd(e,(p-1))和gcd(e,(q-1))，发现e与q-1互素，而我们都知道有以下公式：

m = c^d mod n
==>
m=c^d mod p
m=c^d mod q
(注：此推论满足的前提是------在c不是p或q的倍数，以及d是正整数的情况下，m = c ^ d modp 和m = c ^ d modq 总是成立的，有兴趣的同志们可以自行查找推导过程，这里就不过多说了)

故这题可以使用以下代码求解：

d = invert(e,q-1)
m = pow(c,d,q)