RSA题目常见分析

最近驹宝给我塞了很多RSA的题，自己也做了很多，学下点 RSA 算法的精髓，写一篇总结，后续持续在这里更新。

RSA的介绍

RSA的介绍见我这篇博客

RSA常用做法分析

低指数攻击

我们知道，RSA的安全在于取模运算的不可逆特性，如果说我的信息本来就是 2，你的加密指数为 2，那么平方下来也就是个 4，取模之后就是取了个寂寞，根据所给公钥和密文，我们直接开个方就得到了明文。

模不互素

如果两个公钥模不互素，含有公约数的话，我们用辗转相除法可以很快分解出 p 和 q，而辗转相除法的时间复杂度不会超过 O(log2N)，这优秀的复杂度也让我们能很快地分解得到两个质数。

例题

n1=28170992834270720831179261369471274598997702487696049830156332106869494605756009553416359364123120058506393684721611134396175255085248520813138288550002318384024725495758952465143175548462425605668727426820108069752293438648949444194603512285742873214792072294105948293367708158997811248728037063455817833123285203002351350137897355454137123787850275750591595704048821577823564124943498574623818380616182913536791603277118981723293551366839681774271977694827633752127448663006058876017157727926930195199823324400467529841773190345386219832514302786638128439120112894598351249563655852372309078552091992786038041766277
n2=30426052411541162629650340351029618556957464479756072258366284852617100608440692462790708527260160603801880998062586095228968453145338155923161883183976907495994708490254171467816217449157828401468749415010271748760024562712415222883445840692381712769800218961961965983057269763458953887162943884366520363358693455535663411308843107559177367470269889790117080885165058052596106490369729956697643818346630535515535267060826393590576457246653806670129899406037697985668889417354391424342725773231355312621066562784839302709229489550567684239158552675013440867386238425395428315796266930676815788000373750994287793821091
c1=2582291333174688473482837371310695558013344522219801451176882867544382844570171875599043056723912248821021128705894777239584884707037606324176075924881206372661647696306877429822668287235786023020814823874667156587819928274230054865962630859689154098113218782923808109545553391020429182265395418495962822105988502721180599540017512038621869581406476916453238250489026172610106413861344378397008077526294299119321017408325053654182442842084345081920983250459754887618685974033809325906564138957727999316089837005460571267003092757134432108859653429713579692972626913060573924381433177244348871427046105683280661716738
c2=9479980959348294048040415043005053472430206540648250182203975873154652511903511233814860462809419869817942169405620776050389695639672610182559325440498062679122369415235835023694654421107733717733775846408272826799042552945154258022884833151833319678933958340634903581390433575987867437793326943284375631246178387198398978881023408777618571874239336944658161598413171690119933787696662425323587221393547627048996325679636765500603814636055989176181848082280852597546562839789752131657822041737796527736673507903567282808259265596977598085942774362863079389090752606097401982926590840320148439167865891839785863650767
e=65537

这里我们 GCD 大可不必自己写，直接用 Crypto 库的 GCD 函数即可，安装方法也在上一篇博客。

解题脚本

from Crypto.Util.number import *
def solve(c,p,q,e):
    n=p*q
    phi=(p-1)*(q-1)
    d=inverse(e,phi)
    m=pow(c,d,n)
    return long_to_bytes(m).decode()
n1=28170992834270720831179261369471274598997702487696049830156332106869494605756009553416359364123120058506393684721611134396175255085248520813138288550002318384024725495758952465143175548462425605668727426820108069752293438648949444194603512285742873214792072294105948293367708158997811248728037063455817833123285203002351350137897355454137123787850275750591595704048821577823564124943498574623818380616182913536791603277118981723293551366839681774271977694827633752127448663006058876017157727926930195199823324400467529841773190345386219832514302786638128439120112894598351249563655852372309078552091992786038041766277
n2=30426052411541162629650340351029618556957464479756072258366284852617100608440692462790708527260160603801880998062586095228968453145338155923161883183976907495994708490254171467816217449157828401468749415010271748760024562712415222883445840692381712769800218961961965983057269763458953887162943884366520363358693455535663411308843107559177367470269889790117080885165058052596106490369729956697643818346630535515535267060826393590576457246653806670129899406037697985668889417354391424342725773231355312621066562784839302709229489550567684239158552675013440867386238425395428315796266930676815788000373750994287793821091
c1=2582291333174688473482837371310695558013344522219801451176882867544382844570171875599043056723912248821021128705894777239584884707037606324176075924881206372661647696306877429822668287235786023020814823874667156587819928274230054865962630859689154098113218782923808109545553391020429182265395418495962822105988502721180599540017512038621869581406476916453238250489026172610106413861344378397008077526294299119321017408325053654182442842084345081920983250459754887618685974033809325906564138957727999316089837005460571267003092757134432108859653429713579692972626913060573924381433177244348871427046105683280661716738
c2=9479980959348294048040415043005053472430206540648250182203975873154652511903511233814860462809419869817942169405620776050389695639672610182559325440498062679122369415235835023694654421107733717733775846408272826799042552945154258022884833151833319678933958340634903581390433575987867437793326943284375631246178387198398978881023408777618571874239336944658161598413171690119933787696662425323587221393547627048996325679636765500603814636055989176181848082280852597546562839789752131657822041737796527736673507903567282808259265596977598085942774362863079389090752606097401982926590840320148439167865891839785863650767
e=65537
p=GCD(n1,n2)
q1=int(n1//p)
q2=int(n2//p)
print(solve(c1,p,q1,e)+solve(c2,p,q2,e))
#flag{79a0ad16-d357-49af-81e9-d33dc3e541a2}

共模攻击

当一个明文信息在两个不同的指数对同一模数进行了加密之后，我们可以在不求出私钥的情况下计算得到明文信息。

假设有两个密钥

$key_1=<e_1,n>$

$key_2=<e_2,n>$

明文为 m，我们用这两个公钥分别加密出两串密文。

$c_1=m^{e_1}%n$

$c_2=m^{e_2}%n$

这里需要用到点高数知识。对于整数 $k_1,k_2$，使得方程 $k_1x+k_2y=b$ 存在整数解的前提是 b 能整除 $k_1$ 和 $k_2$ 的最小公约数，也就是 $\gcd(k_1,k_2)$。

特殊地，对于 b=1，存在整数解的充要条件则是 $k_1$ 与 $k_2$ 互质。

一般情况下，RSA 的加密指数我们会取质数，所以很容易有 $e_1x+e_2y=1$ 存在一对整数解 (x,y)。

那么

$c_1^{x}\times c_2^{y}%n=(m^{xe_1}\times m^{ye_2})%n=m^{xe_1+ye_2}%n$

最后化简即得到明文 m。

我们的目标就是找到一对整数解，对于这个问题，我们可以使用扩展欧几里得算法去计算，或者是使用 Z3 去求解。

但是我们也很容易能看出，这个整数解应该会是一正一负的，对于负数我们需要做点特殊处理。

其实比较简单，负数指数我们并不好处理，因为在乘法模的群当中，数集为整数，负指数表示了分数，显然不满足群的封闭性，其实这里处理的方法与我们之前逆元的处理方法一样。

举个栗子：假设 x>0,y<0，则 $x^y$ 它的逆元为多少，假设不在模乘法代数而是在普通乘法代数，数集被扩展到了实数集，那我们脱口而出肯定是 $x^{-y}$。那么其实，在模乘法体系中，$x^y$ 的逆元一样是 $x^{-y}$，但是它不好被辨别，于是我们再去找到它逆元的逆元，一个数的逆元的逆元一定是自身。

我们直接找到 $x$ 在模乘法意义下的逆元 $x^{-1}$ 之后再保持指数不变即是它的逆元，我们可以证明一下：

$x^{y}\times (x^{-1})^y%n=(x\times x^{-1})^y%n=1$

因此对于负指数，我们直接符号变正，底数变为逆元即可。

例题

c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291

解题脚本

from Crypto.Util.number import *
def 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)
c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291
s=egcd(e1, e2)
x=s[1]
y=s[2]
if x<0:
    x=-x
    c1=inverse(c1,n)
else:
    y=-y
    c2=inverse(c2,n)
m=(pow(c1,x,n)*pow(c2,y,n))%n
print(long_to_bytes(m).decode())
#flag{49d91077a1abcb14f1a9d546c80be9ef}

数学推导

这是一类比较泛的题目，题目除了给出密文和公钥以外，还会额外给出一些表达式信息，帮助破解 RSA 的密文，只要理解了 RSA，熟悉 RSA 的推导过程就不会有太大问题。

例题1

n=14113714305072797946493506481186688069348068525719522300918296843166886149586712593527278499546480608243022456418279126062291885234984378509284469719982424691272187376834036952743111743737743509787289516031073996690244502575328189110938473272385195987277353305316883743349963569552297946004952533211450648686747906145487061115730661553947322806175740991677666279314224690585522184085274523080051179955809948156424572176333474623245604759865579902860320192130044881910837668330885305900309636233281430338678478325361905450208233862057975227437570700376032367636653508625619621365742913511560163593564542385538976273511
e=65537
c=8618327949649600151577805769536868884186050491362368463626647780332443491577028760576306554954308943953267510827791879308004801627303605775129313660121772370222619585966214292305860970821159935577290407908606708688407395127864609535430976332421315463289482130097266383749917829831497635736596409478627650432841064479081322546224912505920515470753069832953929215867402615727986720952496172221103420158414576649301068869241456517428304569955008818909581293445988877086661570321362965360400214418049394686624646829322189252357911547541529314699149144426085781464325489219068048330497460674000186446200265603018557000483
dp=22254124501058125233734227965547943196721474032074981803310625346887468776340246924403662046504410526020245040082211662134244900364674425023930821673400316961211254098599523105818306877684796612309587274228054352459332784217520606687007798656236622150535124212386499498298989015161102829904127676310132589861
dp=d % (p -1)

这个题目中，它给了我们 d % (p-1) 的值 dp。

首先我们联立一下方程组

$e\times d%(p-1)(q-1)=1$

$d%(p-1)=dp$

根据①式我们可以推出

$e\times d=k(p-1)(q-1)+1$

我们在②式左右同乘一个 e。

$e\times d%(p-1)=dp\times e%(p-1)$

从左边不难看出，结果应当=1，于是得到等式

$dp\times e%(p-1)=1$

首先不难得到 $dp<p$ 则 $dp\times e<p\times e$。

$dp\times e=k(p-1)+1$

图中只有 k 与 p 未知，但是我们应当明白 k 不会超过 e。

于是我们可以将 $dp\times e -1$ 对 $k(k\le e)$ 进行取模判断，若取模结果为零则有可能是这个结果。

那么我们跑个脚本循环 $[2,65537]$ 即可。

解题脚本

from Crypto.Util.number import *
n=14113714305072797946493506481186688069348068525719522300918296843166886149586712593527278499546480608243022456418279126062291885234984378509284469719982424691272187376834036952743111743737743509787289516031073996690244502575328189110938473272385195987277353305316883743349963569552297946004952533211450648686747906145487061115730661553947322806175740991677666279314224690585522184085274523080051179955809948156424572176333474623245604759865579902860320192130044881910837668330885305900309636233281430338678478325361905450208233862057975227437570700376032367636653508625619621365742913511560163593564542385538976273511
e=65537
c=8618327949649600151577805769536868884186050491362368463626647780332443491577028760576306554954308943953267510827791879308004801627303605775129313660121772370222619585966214292305860970821159935577290407908606708688407395127864609535430976332421315463289482130097266383749917829831497635736596409478627650432841064479081322546224912505920515470753069832953929215867402615727986720952496172221103420158414576649301068869241456517428304569955008818909581293445988877086661570321362965360400214418049394686624646829322189252357911547541529314699149144426085781464325489219068048330497460674000186446200265603018557000483
dp=22254124501058125233734227965547943196721474032074981803310625346887468776340246924403662046504410526020245040082211662134244900364674425023930821673400316961211254098599523105818306877684796612309587274228054352459332784217520606687007798656236622150535124212386499498298989015161102829904127676310132589861
#dp=d % (p -1)
for i in range(2,65537):
    if (dp*e-1)%i==0:
        if isPrime((dp*e-1)//i+1):
            p=(dp*e-1)//i+1
            q=n//p
            phi=(p-1)*(q-1)
            d=inverse(e,phi)
            m=pow(c,d,n)
            print(long_to_bytes(m).decode())
#flag{0cd82bfc-5544-43c5-b48c-ce11136bea49}

e phi不互素

我们知道 RSA 的加密指数一般为质数，若不是质数会发生什么？

我们前面推导过 RSA 的计算过程，若 e 不是质数会导致可能求不出 phi 的逆元，或者说找不到一个这样的数 d，使得 $e\times d %\phi=1$，如果 $\gcd(e,\phi)=k$ 则 $e\times d%\phi$ 的结果至少为 k 的整倍数。

我们按照 RSA 的解密方法最后推导出来的结果也就是

$m^{k}%n$

因此我们就回到了怎么解这个指数的问题，若指数 k 小可以直接开方，或者是动用一下低指数攻击。

例题1

p=136959726431205865477775151957746058501964084915586200859223998224419328617512480807779057493884259671732817083158742688893426777301273633213099180123980988559064240005229990903986655711210993445188959348127903344696563428112042019089659624505185444899365837872965591393711833751140798071913532034918073969303
q=100775514992570031279080353204884456896540523509595089891057558352540088307146118253575941345444101592071454319892938692060454946607143974473707141313645549356430599711832162076318618985329980795933151213484006411944383963148067340413103907427302327136609462283013833061184517264215353793537565873817217882871
e=618
c=11474180598339059739824064616811901863008672847264841633401805944654527375502760803872877763162433116575938389089158136355223441822920717752520632181250987580240513955742874287005589873425759901749449152080440281411772036003528325772394140583924413056042024007990830484221229380940124523505145729796879325683192331242784866357454098755097887413530621128405967607900565276243646588213591552811550038972567938749944372033373196416854332876524071485674100971839799288548733601138685897794138343613068716766810753454049042387074495749784721897884348181557610094355833915443696680454373648737843918284068627924128987496538

题目中给出了 $p,q$，我们就照例求一下私钥，但是注意到 $e$ 并非一个质数，所以我们先看看有没有公约数，可以发现有公约数 6。但是这里需要注意，在 Crypto.Util.number 中的 inverse 函数，如果有公约数，则会自动帮你除公约数之后的逆元，而 gmpy2 的 invert 函数则会直接报错。

解题脚本

from Crypto.Util.number import *
from math import sqrt
import gmpy2
p=136959726431205865477775151957746058501964084915586200859223998224419328617512480807779057493884259671732817083158742688893426777301273633213099180123980988559064240005229990903986655711210993445188959348127903344696563428112042019089659624505185444899365837872965591393711833751140798071913532034918073969303
q=100775514992570031279080353204884456896540523509595089891057558352540088307146118253575941345444101592071454319892938692060454946607143974473707141313645549356430599711832162076318618985329980795933151213484006411944383963148067340413103907427302327136609462283013833061184517264215353793537565873817217882871
e=618
c=11474180598339059739824064616811901863008672847264841633401805944654527375502760803872877763162433116575938389089158136355223441822920717752520632181250987580240513955742874287005589873425759901749449152080440281411772036003528325772394140583924413056042024007990830484221229380940124523505145729796879325683192331242784866357454098755097887413530621128405967607900565276243646588213591552811550038972567938749944372033373196416854332876524071485674100971839799288548733601138685897794138343613068716766810753454049042387074495749784721897884348181557610094355833915443696680454373648737843918284068627924128987496538
n=p*q
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,p*q)
s=gmpy2.iroot(m,6)
print(long_to_bytes(int(s[0])).decode())
#flag{d8600272-fa37-4f2d-92e4-2b74bf3adf71}

在这里需要使用 gmpy2 的 iroot 函数，直接进行开 6 次方的操作。

例题2

e1=14606334023791426
p1=121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q1=130968576816900149996914427770826228884925960001279609559095138835900329492765336419489982304805369724685145941218640504262821549441728192761733409684831633194346504685627189375724517070780334885673563409259345291959439026700006694655545512308390416859315892447092639503318475587220630455745460309886030186593
c1=11402389955595766056824801105373550411371729054679429421548608725777586555536302409478824585455648944737304660137306241012321255955693234304201530700362069004620531537922710568821152217381257446478619320278993539785699090234418603086426252498046106436360959622415398647198014716351359752734123844386459925553497427680448633869522591650121047156082228109421246662020164222925272078687550896012363926358633323439494967417041681357707006545728719651494384317497942177993032739778398001952201667284323691607312819796036779374423837576479275454953999865750584684592993292347483309178232523897058253412878901324740104919248
n1=p1 * q1
e2=13813369129257838
p2=121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q2=94582257784130735233174402362819395926641026753071039760251190444144495369829487705195913337502962816079184062352678128843179586054535283861793827497892600954650126991213176547276006780610945133603745974181504975165082485845571788686928859549252522952174376071500707863379238688200493621993937563296490615649
c2=7984888899827615209197324489527982755561403577403539988687419233579203660429542197972867526015619223510964699107198708420785278262082902359114040327940253582108364104049849773108799812000586446829979564395322118616382603675257162995702363051699403525169767736410365076696890117813211614468971386159587698853722658492385717150691206731593509168262529568464496911821756352254486299361607604338523750318977620039669792468240086472218586697386948479265417452517073901655900118259488507311321060895347770921790483894095085039802955700146474474606794444308825840221205073230671387989412399673375520605000270180367035526919
n2=p2 * q2

这题略微有点难，因为需要用到新的数学知识了。

首先可以看到有 $c_1,c_2$，并且两个公钥由公因数 p。我们任意使用其中一个加密体系都发现 e 与 $\phi$ 不互素，并且有公约数 14，这题就不能像之前那么故技重施了，因为 14 这个指数虽然小但是也不小，直接开是开不了的，但是我们可以转换密钥体系。

根据之前的一些理论我们可以得出以下式子

$res_1=m^{14}%n_1=c_1^{d_1}%n_1$

$res_2=m^{14}%n_2=c_2^{d_2}%n_2$

我们在其中分解 p 和 q 可以得到三个式子。

$res_1%p=m^{14}%p$

$res_1%q_1=m^{14}%q_1$

$res_2%q_2=m^{14}%q_2$

对于这三个等式，我们可以使用中国剩余定理求出满足这三个方程的数 。

中国剩余定理

定义

中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中 $n_1, n_2, \cdots, n_k$ 两两互质）：

$$
\begin{cases}
x &\equiv a_1 \pmod {n_1} \
x &\equiv a_2 \pmod {n_2} \
&\vdots \
x &\equiv a_k \pmod {n_k} \
\end{cases}
$$

上面的「物不知数」问题就是一元线性同余方程组的一个实例。

过程

1. 计算所有模数的积 $n$；
2. 对于第 $i$ 个方程：
   1. 计算 $m_i=\frac{n}{n_i}$；
   2. 计算 $m_i$ 在模 $n_i$ 意义下的 逆元 $m_i^{-1}$；
   3. 计算 $c_i=m_im_i^{-1}$（不要对 $n_i$ 取模）。
3. 方程组在模 $n$ 意义下的唯一解为：$x=\sum_{i=1}^k a_ic_i \pmod n$。

证明

我们需要证明上面算法计算所得的 $x$ 对于任意 $i=1,2,\cdots,k$ 满足 $x\equiv a_i \pmod {n_i}$。

当 $i\neq j$ 时，有 $m_j \equiv 0 \pmod {n_i}$，故 $c_j \equiv m_j \equiv 0 \pmod {n_i}$。又有 $c_i \equiv m_i \cdot (m_i^{-1} \bmod {n_i}) \equiv 1 \pmod {n_i}$，所以我们有：

$$
\begin{aligned}
x&\equiv \sum_{j=1}^k a_jc_j &\pmod {n_i} \
&\equiv a_ic_i &\pmod {n_i} \
&\equiv a_i \cdot m_i \cdot (m^{-1}_i \bmod n_i) &\pmod {n_i} \
&\equiv a_i &\pmod {n_i}
\end{aligned}
$$

即对于任意 $i=1,2,\cdots,k$，上面算法得到的 $x$ 总是满足 $x\equiv a_i \pmod{n_i}$，即证明了解同余方程组的算法的正确性。

因为我们没有对输入的 $a_i$ 作特殊限制，所以任何一组输入 ${a_i}$ 都对应一个解 $x$。

另外，若 $x\neq y$，则总存在 $i$ 使得 $x$ 和 $y$ 在模 $n_i$ 下不同余。

故系数列表 ${a_i}$ 与解 $x$ 之间是一一映射关系，方程组总是有唯一解。

解题脚本

from Crypto.Util.number import *
from gmpy2 import *
from libnum import *
e1=14606334023791426
p1=121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q1=130968576816900149996914427770826228884925960001279609559095138835900329492765336419489982304805369724685145941218640504262821549441728192761733409684831633194346504685627189375724517070780334885673563409259345291959439026700006694655545512308390416859315892447092639503318475587220630455745460309886030186593
c1=11402389955595766056824801105373550411371729054679429421548608725777586555536302409478824585455648944737304660137306241012321255955693234304201530700362069004620531537922710568821152217381257446478619320278993539785699090234418603086426252498046106436360959622415398647198014716351359752734123844386459925553497427680448633869522591650121047156082228109421246662020164222925272078687550896012363926358633323439494967417041681357707006545728719651494384317497942177993032739778398001952201667284323691607312819796036779374423837576479275454953999865750584684592993292347483309178232523897058253412878901324740104919248

e2=13813369129257838
p2=121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q2=94582257784130735233174402362819395926641026753071039760251190444144495369829487705195913337502962816079184062352678128843179586054535283861793827497892600954650126991213176547276006780610945133603745974181504975165082485845571788686928859549252522952174376071500707863379238688200493621993937563296490615649
c2=7984888899827615209197324489527982755561403577403539988687419233579203660429542197972867526015619223510964699107198708420785278262082902359114040327940253582108364104049849773108799812000586446829979564395322118616382603675257162995702363051699403525169767736410365076696890117813211614468971386159587698853722658492385717150691206731593509168262529568464496911821756352254486299361607604338523750318977620039669792468240086472218586697386948479265417452517073901655900118259488507311321060895347770921790483894095085039802955700146474474606794444308825840221205073230671387989412399673375520605000270180367035526919
n2=p2 * q2
phi1=(p1-1)*(q1-1)
phi2=(p2-1)*(q2-1)
d1=inverse(e1,phi1)
d2=inverse(e2,phi2)
res1=pow(c1,d1,p1*q1)
res2=pow(c2,d2,p1*q2)
print(res2)
'''
res1%q1=m^14%q1
res2%q2=m^14%q2
res1%p=m^14%p
'''
a1=res1%q1
a2=res2%q2
a3=res1*res2%p1
n=p1*q1*q2
n1=n//q1
n2=n//q2
n3=n//p1
m1=inverse(n1,q1)
m2=inverse(n2,q2)
m3=inverse(n3,p1)
res=(n1*m1*a1+n2*m2*a2+n3*m3*a3)
n=q1*q2
e=14
c=res%n
phi=(q1-1)*(q2-1)
d=inverse(e,phi)
m=pow(res,d,n)
l=iroot(m,2)
print(long_to_bytes(int(l[0])))
#flag{gcd_e&φ_isn't_1}