[CTF]RSA入门题目题解若干

babyrsa 普通rsa解密

题目给了e、p、q，还给了c 

e = 65537
p = 104046835712664064779194734974271185635538927889880611929931939711001301561682270177931622974642789920918902563361293345434055764293612446888383912807143394009019803471816448923969637980671221111117965227402429634935481868701166522350570364727873283332371986860194245739423508566783663380619142431820861051179
q = 140171048074107988605773731671018901813928130582422889797732071529733091703843710859282267763783461738242958098610949120354497987945911021170842457552182880133642711307227072133812253341129830416158450499258216967879857581565380890788395068130033931180395926482431150295880926480086317733457392573931410220501
c = 4772758911204771028049020670778336799568778930072841084057809867608022732611295305096052430641881550781141776498904005589873830973301898523644744951545345404578466176725030290421649344936952480254902939417215148205735730754808467351639943474816280980230447097444682489223054499524197909719857300597157406075069204315022703894466226179507627070835428226086509767746759353822302809385047763292891543697277097068406512924796409393289982738071019047393972959228919115821862868057003145401072581115989680686073663259771587445250687060240991265143919857962047718344017741878925867800431556311785625469001771370852474292194


思路：根据两个质数p、q可以算出n和φ(n)，从而算出解密参数d（d为e在模φ(n)下的逆元），由密文c、解密参数d、还有素数乘积n可以算出明文m。

解密代码 

import libnum
from Crypto.Util.number import long_to_bytes

e = 65537
p = 104046835712664064779194734974271185635538927889880611929931939711001301561682270177931622974642789920918902563361293345434055764293612446888383912807143394009019803471816448923969637980671221111117965227402429634935481868701166522350570364727873283332371986860194245739423508566783663380619142431820861051179
q = 140171048074107988605773731671018901813928130582422889797732071529733091703843710859282267763783461738242958098610949120354497987945911021170842457552182880133642711307227072133812253341129830416158450499258216967879857581565380890788395068130033931180395926482431150295880926480086317733457392573931410220501
c = 4772758911204771028049020670778336799568778930072841084057809867608022732611295305096052430641881550781141776498904005589873830973301898523644744951545345404578466176725030290421649344936952480254902939417215148205735730754808467351639943474816280980230447097444682489223054499524197909719857300597157406075069204315022703894466226179507627070835428226086509767746759353822302809385047763292891543697277097068406512924796409393289982738071019047393972959228919115821862868057003145401072581115989680686073663259771587445250687060240991265143919857962047718344017741878925867800431556311785625469001771370852474292194

# 根据p、q可以算出n和φ(n)
n = p * q
phi_n = (p-1)*(q-1)

# 根据e和φ(n)可以算出d
d = libnum.invmod(e, phi_n)

# 根据c、d、n可以解密出明文m
m = pow(c, d, n)

# 数字转字节序列
print(long_to_bytes(m))



得到明文：flag{b4by_R5A}

easyrsa1 n太小可以直接分解

题目给了e、n，还有密文c 

e = 65537
n = 1455925529734358105461406532259911790807347616464991065301847
c = 69380371057914246192606760686152233225659503366319332065009
思路：我们缺少参数p、q，也就缺少φ(n)，但是我们发现n这个数比较小，很有可能在可接受时间内被现有计算机分解质因数出两个素数p、q

我们使用yafu工具分解质因数
yafu-x64.exe factor(1455925529734358105461406532259911790807347616464991065301847)
很快分解质因数成功得到2个质数


P31 = 1212112637077862917192191913841
P31 = 1201147059438530786835365194567
有了2个质数p、q就好办了，就可以算出φ(n)了
解密代码
import libnum
from Crypto.Util.number import long_to_bytes

e = 65537
n = 1455925529734358105461406532259911790807347616464991065301847
c = 69380371057914246192606760686152233225659503366319332065009

# p和q是我们发现n比较小于是果断用工具分解质因数得到的
p = 1212112637077862917192191913841
q = 1201147059438530786835365194567


n = p * q
phi_n = (p-1)*(q-1)
d = libnum.invmod(e, phi_n)

m = pow(c, d, n)
print(long_to_bytes(m))



得到明文：flag{fact0r_sma11_N}

easyrsa2 两个n有公因数

题目给了我们2组e、n、c，而且n是比较大的，如果不是特殊的n不太好分解~~，但是经观察发现这两组参数中的e参数是一样的（貌似没啥用）。~~
将大数n分解为2个素数是困难问题，如果不是特殊的n不太好办，但是求2个大数的最大公因子是简单问题，欧几里得算法就可以办到。
我们猜测给的这两个大数n1和n2是不是有不等于1的最大公因子呢？
由于n1=p1*q1、n2=p2*q2，如果n1和n2有一个公因子p，即p=p1=p2，那么我们就可以用欧几里得算法快速求出两个数n1、n2的最大公因子p，于是q1和q2也可以通过q1=n1/p、q2=n2/p得到了。
解密脚本 

import libnum
from Crypto.Util.number import long_to_bytes

e = 65537
n1 = 23686563925537577753047229040754282953352221724154495390687358877775380147605152455537988563490716943872517593212858326146811511103311865753018329109314623702207073882884251372553225986112006827111351501044972239272200616871716325265416115038890805114829315111950319183189591283821793237999044427887934536835813526748759612963103377803089900662509399569819785571492828112437312659229879806168758843603248823629821851053775458651933952183988482163950039248487270453888288427540305542824179951734412044985364866532124803746008139763081886781361488304666575456680411806505094963425401175510416864929601220556158569443747
c1 = 1627484142237897613944607828268981193911417408064824540711945192035649088104133038147400224070588410335190662682231189997580084680424209495303078061205122848904648319219646588720994019249279863462981015329483724747823991513714172478886306703290044871781158393304147301058706003793357846922086994952763485999282741595204008663847963539422096343391464527068599046946279309037212859931303335507455146001390326550668531665493245293839009832468668390820282664984066399051403227990068032226382222173478078505888238749583237980643698405005689247922901342204142833875409505180847943212126302482358445768662608278731750064815

# e = 65537
n2 = 22257605320525584078180889073523223973924192984353847137164605186956629675938929585386392327672065524338176402496414014083816446508860530887742583338880317478862512306633061601510404960095143941320847160562050524072860211772522478494742213643890027443992183362678970426046765630946644339093149139143388752794932806956589884503569175226850419271095336798456238899009883100793515744579945854481430194879360765346236418019384644095257242811629393164402498261066077339304875212250897918420427814000142751282805980632089867108525335488018940091698609890995252413007073725850396076272027183422297684667565712022199054289711
c2 = 2742600695441836559469553702831098375948641915409106976157840377978123912007398753623461112659796209918866985480471911393362797753624479537646802510420415039461832118018849030580675249817576926858363541683135777239322002741820145944286109172066259843766755795255913189902403644721138554935991439893850589677849639263080528599197595705927535430942463184891689410078059090474682694886420022230657661157993875931600932763824618773420077273617106297660195179922018875399174346863404710420166497017196424586116535915712965147141775026549870636328195690774259990189286665844641289108474834973710730426105047318959307995062

# 尝试获取n1和n2的不为1的最大公因子
p = libnum.gcd(n1, n2)
if p==1:
    exit("n1和n2没有不为1的最大公因子")

# 这里要用 // 使得q1、q2的类型为整数，不然浮点数的话后边的运算似乎会超慢
q1 = n1 // p
q2 = n2 // p

phi_n1 = (p-1)*(q1-1)
phi_n2 = (p-1)*(q2-1)
d1 = libnum.invmod(e, phi_n1)
d2 = libnum.invmod(e, phi_n2)

m1 = pow(c1, d1, n1)
m2 = pow(c2, d2, n2)

print(long_to_bytes(m1))
print(long_to_bytes(m2))
得到明文m1：flag{m0_bv_hv_sv}
得到明文m2：flag{m0_bv_hv_sv}
easyrsa3 相同的n，共模攻击


题目给了我们2组e、n，还有对应的c，经过观察发现这两组参数的n是一样的。如果将相同的明文分别用两组公钥(e1, n1)、(e2, n2)进行加密，那么攻击者只需要将这两组公钥都拿到手，并且发现e1、e2是互素的，那么就有办法解出原始明文而无需两组公钥中的任何一个私钥参数。明文计算公式如下

即先通过扩展欧几里得算法得到使贝祖等式成立的两个参数 s1和s2，s1和s2必然是一正一负，而在数论模运算中，要求一个数的负数次幂，与常规方法并不一样。比如此处要求c2的s2次幂，就要先计算c2的模反元素c2r，然后求c2r的-s2次幂，通过上述步骤即可恢复出明文m。

解密代码：
 

import libnum
from Crypto.Util.number import long_to_bytes

e1 = 797
n = 15944475431088053285580229796309956066521520107276817969079550919586650535459242543036143360865780730044733026945488511390818947440767542658956272380389388112372084760689777141392370253850735307578445988289714647332867935525010482197724228457592150184979819463711753058569520651205113690397003146105972408452854948512223702957303406577348717348753106868356995616116867724764276234391678899662774272419841876652126127684683752880568407605083606688884120054963974930757275913447908185712204577194274834368323239143008887554264746068337709465319106886618643849961551092377843184067217615903229068010117272834602469293571
c1 = 11157593264920825445770016357141996124368529899750745256684450189070288181107423044846165593218013465053839661401595417236657920874113839974471883493099846397002721270590059414981101686668721548330630468951353910564696445509556956955232059386625725883038103399028010566732074011325543650672982884236951904410141077728929261477083689095161596979213961494716637502980358298944316636829309169794324394742285175377601826473276006795072518510850734941703194417926566446980262512429590253643561098275852970461913026108090608491507300365391639081555316166526932233787566053827355349022396563769697278239577184503627244170930

e2 = 521
# n = 15944475431088053285580229796309956066521520107276817969079550919586650535459242543036143360865780730044733026945488511390818947440767542658956272380389388112372084760689777141392370253850735307578445988289714647332867935525010482197724228457592150184979819463711753058569520651205113690397003146105972408452854948512223702957303406577348717348753106868356995616116867724764276234391678899662774272419841876652126127684683752880568407605083606688884120054963974930757275913447908185712204577194274834368323239143008887554264746068337709465319106886618643849961551092377843184067217615903229068010117272834602469293571
c2 = 6699274351853330023117840396450375948797682409595670560999898826038378040157859939888021861338431350172193961054314487476965030228381372659733197551597730394275360811462401853988404006922710039053586471244376282019487691307865741621991977539073601368892834227191286663809236586729196876277005838495318639365575638989137572792843310915220039476722684554553337116930323671829220528562573169295901496437858327730504992799753724465760161805820723578087668737581704682158991028502143744445435775458296907671407184921683317371216729214056381292474141668027801600327187443375858394577015394108813273774641427184411887546849

# 扩展欧几里得算法
def ext_euclid(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = ext_euclid(b, a % b)
        x, y = y, (x - (a // b) * y)
        return x, y, q

# e1 和 e2 要互素
assert libnum.gcd(e1, e2)==1

s1, s2, q = ext_euclid(e1,e2)
assert s1*s2<0 and q==1

if s1<0:
    s1 = -s1
    c1 = libnum.invmod(c1, n)
elif s2<0:
    s2 = -s2
    c2 = libnum.invmod(c2, n)

# 这里的pow函数是否模n在数学上是一样的，但是模n可以极大的加速运算
m = (pow(c1,s1,n) * pow(c2,s2,n)) % n

print(long_to_bytes(m))
得到明文：flag{sh4r3_N}


easyrsa4 e很小，n和c比较大

题目给了我们e、n、c，发现e=3，是一个很小的值。
RSA的加密公式为

如果c和n比较大，而e比较小，就有可能导致可以通过穷举k的方式来获得m^e，再开e次方就能获得明文m

解密代码：

import gmpy2
from libnum import n2s
from Crypto.Util.number import long_to_bytes

e = 3
n = gmpy2.mpz(18970053728616609366458286067731288749022264959158403758357985915393383117963693827568809925770679353765624810804904382278845526498981422346319417938434861558291366738542079165169736232558687821709937346503480756281489775859439254614472425017554051177725143068122185961552670646275229009531528678548251873421076691650827507829859299300272683223959267661288601619845954466365134077547699819734465321345758416957265682175864227273506250707311775797983409090702086309946790711995796789417222274776215167450093735639202974148778183667502150202265175471213833685988445568819612085268917780718945472573765365588163945754761)
c = gmpy2.mpz(150409620528139732054476072280993764527079006992643377862720337847060335153837950368208902491767027770946661)


i = 0
while True:
    # 开方后的根取整，能否开出整数的根
    root, is_success = gmpy2.iroot(c+i*n, e)
    if is_success:
        m = root
        break
    i += 1
    
print(long_to_bytes(m))
得到明文：flag{Sm4ll_eee}
easyrsa5 e很大，n和c比较大

题目给了我们e、n、c，发现是一个很大的值。
由于e和d互为对于φ(n)模反元素，e很大会导致d比较小，即解密的指数比较小，此时使用维纳攻击可以获得解密参数d。

解密代码：

import gmpy2
from Crypto.Util.number import long_to_bytes

def transform(x, y):  # 使用辗转相处将分数 x/y 转为连分数的形式
    res = []
    while y:
        res.append(x//y)
        x, y = y, x % y
    return res

def continued_fraction(sub_res):
    numerator, denominator = 1, 0
    for i in sub_res[::-1]:  # 从sublist的后面往前循环
        denominator, numerator = numerator, i*numerator+denominator
    return denominator, numerator  # 得到渐进分数的分母和分子，并返回

# 求解每个渐进分数
def sub_fraction(x, y):
    res = transform(x, y)
    # 将连分数的结果逐一截取以求渐进分数
    res = list(map(continued_fraction, (res[0:i] for i in range(1, len(res)))))
    return res

def get_pq(a, b, c):  # 由p+q和pq的值通过维达定理来求解p和q
    par = gmpy2.isqrt(b*b-4*a*c)  # 由上述可得，开根号一定是整数，因为有解
    x1, x2 = (-b+par)//(2*a), (-b-par)//(2*a)
    return x1, x2

def wienerAttack(e, n):
    for (d, k) in sub_fraction(e, n):  # 用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数
        if k == 0:  # 可能会出现连分数的第一个为0的情况，排除
            continue
        if (e*d-1) % k != 0:  # ed=1 (mod φ(n)) 因此如果找到了d的话，(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
            continue
        phi = (e*d-1)//k  # 这个结果就是 φ(n)
        px, qy = get_pq(1, n-phi+1, n)
        if px*qy == n:
            p, q = abs(int(px)), abs(int(qy))  # 可能会得到两个负数，负负得正未尝不会出现
            # 求ed=1 (mod  φ(n))的结果，也就是e关于 φ(n)的乘法逆元d
            d = gmpy2.invert(e, (p-1)*(q-1))
            return d
    print("该方法不适用")


e = 284100478693161642327695712452505468891794410301906465434604643365855064101922252698327584524956955373553355814138784402605517536436009073372339264422522610010012877243630454889127160056358637599704871937659443985644871453345576728414422489075791739731547285138648307770775155312545928721094602949588237119345
n = 468459887279781789188886188573017406548524570309663876064881031936564733341508945283407498306248145591559137207097347130203582813352382018491852922849186827279111555223982032271701972642438224730082216672110316142528108239708171781850491578433309964093293907697072741538649347894863899103340030347858867705231
c = 350429162418561525458539070186062788413426454598897326594935655762503536409897624028778814302849485850451243934994919418665502401195173255808119461832488053305530748068788500746791135053620550583421369214031040191188956888321397450005528879987036183922578645840167009612661903399312419253694928377398939392827

d = wienerAttack(e, n)
m = pow(c, d, n)
print(long_to_bytes(m))

得到明文：flag{very_biiiiig_e}

easyrsa6 p和q很接近

题目给了我们e、n、c，并且通过代码告诉我们素数q是素数p紧接着的下一个素数。
p和q很接近会导致n容易被分解出来。
我们使用yafu工具分解质因数

yafu-x64.exe factor(26737417831000820542131903300607349805884383394154602685589253691058592906354935906805134188533804962897170211026684453428204518730064406526279112572388086653330354347467824800159214965211971007509161988095657918569122896402683130342348264873834798355125176339737540844380018932257326719850776549178097196650971801959829891897782953799819540258181186971887122329746532348310216818846497644520553218363336194855498009339838369114649453618101321999347367800581959933596734457081762378746706371599215668686459906553007018812297658015353803626409606707460210905216362646940355737679889912399014237502529373804288304270563)

很快分解质因数成功得到2个质数 

P309 = 163515803000813412334620775647541652549604895368507102613553057136855632963322853570924931001138446030409251690646645635800254129997200577719209532684847732809399187385176309169421205833279943214621695444496660249881675974141488357432373412184140130503562295159152949524373214358417567189638680209172147385801
P309 = 163515803000813412334620775647541652549604895368507102613553057136855632963322853570924931001138446030409251690646645635800254129997200577719209532684847732809399187385176309169421205833279943214621695444496660249881675974141488357432373412184140130503562295159152949524373214358417567189638680209172147385163
有了2个质数p、q就好办了，就可以算出φ(n)了

解密代码
import libnum
from Crypto.Util.number import long_to_bytes

e = 0x10001
n = 26737417831000820542131903300607349805884383394154602685589253691058592906354935906805134188533804962897170211026684453428204518730064406526279112572388086653330354347467824800159214965211971007509161988095657918569122896402683130342348264873834798355125176339737540844380018932257326719850776549178097196650971801959829891897782953799819540258181186971887122329746532348310216818846497644520553218363336194855498009339838369114649453618101321999347367800581959933596734457081762378746706371599215668686459906553007018812297658015353803626409606707460210905216362646940355737679889912399014237502529373804288304270563
c = 18343406988553647441155363755415469675162952205929092244387144604220598930987120971635625205531679665588524624774972379282080365368504475385813836796957675346369136362299791881988434459126442243685599469468046961707420163849755187402196540739689823324440860766040276525600017446640429559755587590377841083082073283783044180553080312093936655426279610008234238497453986740658015049273023492032325305925499263982266317509342604959809805578180715819784421086649380350482836529047761222588878122181300629226379468397199620669975860711741390226214613560571952382040172091951384219283820044879575505273602318856695503917257
p = 163515803000813412334620775647541652549604895368507102613553057136855632963322853570924931001138446030409251690646645635800254129997200577719209532684847732809399187385176309169421205833279943214621695444496660249881675974141488357432373412184140130503562295159152949524373214358417567189638680209172147385801
q = 163515803000813412334620775647541652549604895368507102613553057136855632963322853570924931001138446030409251690646645635800254129997200577719209532684847732809399187385176309169421205833279943214621695444496660249881675974141488357432373412184140130503562295159152949524373214358417567189638680209172147385163

phi_n = (q-1)*(p-1)

d = libnum.invmod(e, phi_n)

m = pow(c, d, n)

print(long_to_bytes(m))
得到明文：flag{p&q_4re_t00_c1o5ed}

easyrsa7 已知p的部分高位
题目给了我们e、n，还有c，并且还给了我们p的抹除掉低128位数据以后的值。
已知n，和p的部分高位，可以利用Coppersmith定理再可接受时间内恢复出完整的P。需要知道的p的位数大约为n位数的一半多，如n为1024位至少需要知道p的前576位。
sage是一个数学计算软件，其脚本语法和python类似，我们可以用如下sage脚本恢复出完整p。
当然，如果你不想安装庞大的sage运行软件，可以在这里在线运行sage脚本：https://sagecell.sagemath.org/
sage脚本：
n = 0x79e0bf9b916e59286163a1006f8cefd4c1b080387a6ddb98a3f3984569a4ebb48b22ac36dff7c98e4ebb90ffdd9c07f53a20946f57634fb01f4489fcfc8e402865e152820f3e2989d4f0b5ef1fb366f212e238881ea1da017f754d7840fc38236edba144674464b661d36cdaf52d1e5e7c3c21770c5461a7c1bc2db712a61d992ebc407738fc095cd8b6b64e7e532187b11bf78a8d3ddf52da6f6a67c7e88bef5563cac1e5ce115f3282d5ff9db02278859f63049d1b934d918f46353fea1651d96b2ddd874ec8f1e4b9d487d8849896d1c21fb64029f0d6f47e560555b009b96bfd558228929a6cdf3fb6d47a956829fb1e638fcc1bdfad4ec2c3590dea1ed3L
# 已知高位但低位未知所以用0代替的p
p_fake = 0xd1c520d9798f811e87f4ff406941958bab8fc24b19a32c3ad89b0b73258ed3541e9ca696fd98ce15255264c39ae8c6e8db5ee89993fa44459410d30a0a8af700ae3aee8a9a1d6094f8c757d3b79a8d1147e85be34fb260a970a52826c0a92b46cefb5dfaf2b5a31edf867f8d34d2222900000000000000000000000000000000L
# p的总位数(包括0)
pbits = 1024
# p的低位0的位数
kbits = 128
# 取出p_fake的高有效数据位 (pbits-kbits)
pbar = p_fake & (2^pbits-2^kbits)
print("upper %d bits (of %d bits) is given" % (pbits-kbits, pbits))

# 生成一个以x为符号的一元多项式环
PR.<x> = PolynomialRing(Zmod(n))
# 定义求解的函数
f = x + pbar
# 多项式小值根求解及因子分解，X表示求解根的上界
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.4
print("p =", x0 + pbar)
# sage output:
# upper 896 bits (of 1024 bits) is given
# p = 147305526294483975294006704928271118039370615054437206404408410848858740256154476278591035455064149531353089038270283281541411458250950936656537283482331598521457077465891874559349872035197398406708610440618635013091489698011474611145014167945729411970665381793142591665313979405475889978830728651549052207969
恢复出完整p以后就可以算出q，进而算出解密参数d，从而可以对密文进行解密了。

解密代码：
import libnum
from Crypto.Util.number import long_to_bytes

# 通过sage脚本得到完整的p
p = 147305526294483975294006704928271118039370615054437206404408410848858740256154476278591035455064149531353089038270283281541411458250950936656537283482331598521457077465891874559349872035197398406708610440618635013091489698011474611145014167945729411970665381793142591665313979405475889978830728651549052207969

e = 0x10001
n = 0x79e0bf9b916e59286163a1006f8cefd4c1b080387a6ddb98a3f3984569a4ebb48b22ac36dff7c98e4ebb90ffdd9c07f53a20946f57634fb01f4489fcfc8e402865e152820f3e2989d4f0b5ef1fb366f212e238881ea1da017f754d7840fc38236edba144674464b661d36cdaf52d1e5e7c3c21770c5461a7c1bc2db712a61d992ebc407738fc095cd8b6b64e7e532187b11bf78a8d3ddf52da6f6a67c7e88bef5563cac1e5ce115f3282d5ff9db02278859f63049d1b934d918f46353fea1651d96b2ddd874ec8f1e4b9d487d8849896d1c21fb64029f0d6f47e560555b009b96bfd558228929a6cdf3fb6d47a956829fb1e638fcc1bdfad4ec2c3590dea1ed3
c = 0x1b2b4f9afed5fb5f9876757e959c183c2381ca73514b1918d2f123e386bebe9832835350f17ac439ac570c9b2738f924ef49afea02922981fad702012d69ea3a3c7d1fc8efc80e541ca2622d7741090b9ccd590906ac273ffcc66a7b8c0d48b7d62d6cd6dd4cd75747c55aac28f8be3249eb255d8750482ebf492692121ab4b27b275a0f69b15baef20bf812f3cbf581786128b51694331be76f80d6fb1314d8b280eaa16c767821b9c2ba05dfde5451feef22ac3cb3dfbc88bc1501765506f0c05045184292a75c475486b680f726f44ef8ddfe3c48f75bb03c8d44198ac70e6b7c885f53000654db22c8cee8eb4f65eaeea2da13887aaf53d8c254d2945691

q = n//p

phi_n = (p-1)*(q-1)
d = libnum.invmod(e, phi_n)
m = pow(c,d,n)

print(long_to_bytes(m))
得到明文：flag{Kn0wn_Hi9h_Bit5}

easyrsa8 p很小导致n可被分解

题目给了我们两个文件，一个public.key公钥文件，一个flag.enc被加密的文件，我们可以从公钥文件中读取到参数e、n，看起来可以利用的数据就这俩参数，于是我们抱着试试看的心态用工具yafu分解n，一会就分解成功了，原来是p参数很小导致n很容易被分解开来。 

yafu-x64 factor(10306247299477991196335954707897189353577589618180446614762218980226685668311143526740800444344046158260556585833057716406703213966249956775927205061731821632025483608182881492214855240841820024816859031176291364212054293818204399157346955465232586109199762630150640804366966946066155685218609638749171632685073)
得到分解结果 

P2 = 97
P309 = 106249972159566919549855203174197828387397831115262336234662051342543151219702510584956705611794290291345944183845955839244363030579896461607496959399297130227066841321473005074379950936513608503266587950271044991876848389878395867601515004796212227929894460104645781488319246866661398816686697306692491058609
有了参数p、q，我们就可以得到φ(n)，然后得到私钥参数d了。

解密代码：
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import libnum

# 从文件中读取公钥参数(e,n)
publicKey = RSA.importKey(open('public.key').read())
e = publicKey.e
n = publicKey.n

p = 97
q = 106249972159566919549855203174197828387397831115262336234662051342543151219702510584956705611794290291345944183845955839244363030579896461607496959399297130227066841321473005074379950936513608503266587950271044991876848389878395867601515004796212227929894460104645781488319246866661398816686697306692491058609
assert p*q==n
phi_n = (p-1)*(q-1)
d = libnum.invmod(e, phi_n)

# 解密加密文件
privatekey = RSA.construct((n,e,d,p,q))
rsa = PKCS1_OAEP.new(privatekey)
plain_text = rsa.decrypt(open('flag.enc','rb').read())
print(plain_text)
得到明文：flag{p_1s_5mall_num6er}

标签: CTF 安全 夺旗比赛

发表评论

路人甲 表情
看不清楚？点图切换 Ctrl+Enter快速提交

网友评论（0）

sitemap