2021 绿城杯 Crypto Writeup

河南郑州的绿城杯，也是第一届绿城杯比赛。使用的比赛平台是安恒的比赛平台。比赛过程中出现了卡顿的问题。绿城杯的整体题目难度还是比较友好的，至少密码学方向是相对比较简单的一部分内容。

密码学题目有三道题目，一道古典密码学题目，两道RSA题目。本人太菜，仅仅做出了前两道题目。

0x0 [warmup]加密算法

直接看看题目的源码

from Crypto.Util.number import *
from flag import flag
assert flag[:5]=='flag{'

str1 = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
def encode(plain_text, a, b, m):
	cipher_text = ''
	for i in plain_text:
		if i in str1:
			addr = str1.find(i)
			cipher_text += str1[(a*addr+b) % m]
		else:
			cipher_text += i
	print(cipher_text)


encode(flag,37,23,52)
# cipher_text = 'aoxL{XaaHKP_tHgwpc_hN_ToXnnht}'

代码看样子是非常简单的，可以找到加密的关键代码：

def encode(plain_text, a, b, m):
	cipher_text = ''
	for i in plain_text:
		if i in str1:
			addr = str1.find(i)
			cipher_text += str1[(a*addr+b) % m]
		else:
			cipher_text += i
	print(cipher_text)

对加密函数进行审计可以发现有一个比较明显的数学运算：

$$ cipher\underline{~~}text \equiv a \times addr + b\ \text{mod}\ m $$

看到这个数学运算，应该可以自然而然的想到是仿射加密，对应的解密函数也就是该运算的逆运算：

$$ plain\underline{~~} text \equiv {addr}^{-1} \times (a-b)\ \text{mod}\ m $$

根据运算构造解密函数：

import libnum
def decode(cipher_text,a,b,m):
    plain_text = ''
    a_inv = libnum.invmod(a,m)
    for i in cipher_text:
        if i in str1:
            addr = str1.find(i)
            plain_text += str1[(a_inv*(addr-b))%m]
        else:
            plain_text += i
    print(plain_text)

根据解密函数进行求解即可求解

完整exp：

from Crypto.Util.number import *
import libnum
str1 = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
def encode(plain_text, a, b, m):
	cipher_text = ''
	for i in plain_text:
		if i in str1:
			addr = str1.find(i)
			cipher_text += str1[(a*addr+b) % m]
		else:
			cipher_text += i
	print(cipher_text)

def decode(cipher_text,a,b,m):
    plain_text = ''
    a_inv = libnum.invmod(a,m)
    for i in cipher_text:
        if i in str1:
            addr = str1.find(i)
            plain_text += str1[(a_inv*(addr-b))%m]
        else:
            plain_text += i
    print(plain_text)
cipher_text = 'aoxL{XaaHKP_tHgwpc_hN_ToXnnht}'

decode(cipher_text,37,23,52)

0x1 RSA-1

RSA的题目，康康题目源码

from Crypto.Util.number import *
import gmpy2
from flag import flag
assert flag[:5]==b'flag{'

m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
print('n =',n)
e = 0x10001
M = 2021 * m * 1001 * p 
c = pow(M,e,n)
print('c =',c)

#n = 17365231154926348364478276872558492775911760603002394353723603461898405740234715001820111548600914907617003806652492391686710256274156677887101997175692277729648456087534987616743724646598234466094779540729413583826355145277980479040157075453694250572316638348121571218759769533738721506811175866990851972838466307594226293836934116659685215775643285465895317755892754473332034234495795936183610569571016400535362762699517686781602302045048532131426035260878979892169441059467623523060569285570577199236309888155833013721997933960457784653262076135561769838704166810384309655788983073376941843467117256002645962737847
#c = 6944967108815437735428941286784119403138319713455732155925055928646536962597672941805831312130689338014913452081296400272862710447207265099750401657828165836013122848656839100854719965188680097375491193249127725599660383746827031803066026497989298856420216250206035068180963797454792151191071433645946245914916732637007117085199442894495667455544517483404006536607121480678688000420422281380539368519807162175099763891988648117937777951069899975260190018995834904541447562718307433906592021226666885638877020304005614450763081337082838608414756162253825697420493509914578546951634127502393647068722995363753321912676

进行代码审计，可以发现前面的加密过程是RSA的基本加密过程和步骤，但是到了后面的步骤，发现加密过程出现了异样，这很有可能就是我们的攻击点。找到题目源码中的可疑运算： $$ M = 2021 \times m \times 1001 \times p $$ 观察这个等式可以得出一些微妙的关系： $$ c \equiv M^e \ \text{mod}\ n \ n = p \cdot q $$ 根据这个关系进一步推到可以得到 $$ c \equiv {(2021 \times m \times 1001 \times p)}^e\ \text{mod}\ n $$ 观察这个等式可以显然发现 c 和 n 存在着有着微妙的关系，利用这个微妙的关系可以得到攻击这个密码体制的钥匙，即 $$ p = \gcd (c,n) $$ 利用这个关系即可求解本题

完整exp：

from Crypto.Util.number import *
import gmpy2
e = 0x10001
n = 17365231154926348364478276872558492775911760603002394353723603461898405740234715001820111548600914907617003806652492391686710256274156677887101997175692277729648456087534987616743724646598234466094779540729413583826355145277980479040157075453694250572316638348121571218759769533738721506811175866990851972838466307594226293836934116659685215775643285465895317755892754473332034234495795936183610569571016400535362762699517686781602302045048532131426035260878979892169441059467623523060569285570577199236309888155833013721997933960457784653262076135561769838704166810384309655788983073376941843467117256002645962737847
c = 6944967108815437735428941286784119403138319713455732155925055928646536962597672941805831312130689338014913452081296400272862710447207265099750401657828165836013122848656839100854719965188680097375491193249127725599660383746827031803066026497989298856420216250206035068180963797454792151191071433645946245914916732637007117085199442894495667455544517483404006536607121480678688000420422281380539368519807162175099763891988648117937777951069899975260190018995834904541447562718307433906592021226666885638877020304005614450763081337082838608414756162253825697420493509914578546951634127502393647068722995363753321912676
p = gmpy2.gcd(c,n)
q = n // p
assert(n == p*q)

phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
M = pow(c,d,n)
m = M//(2021*p*1001)
flag = long_to_bytes(m)
print(flag)

0x2 RSA-2

当时没做出来，没有认真进行数学分析，是本菜狗没错了，后来看大佬的Writeup发现是一道原题，大佬的博客：ISITDTU 2019 Quals CTF Writeups | Joseph Surin | joseph’s blog (jsur.in)

这道题目，我根据对博客的学习和理解进行简单地复现，这道题目其实也就是数学的推导和猜测，又是暴力的美学和优雅地求解。

看看题目源码：

from Crypto.Util.number import *
import gmpy2
from flag import flag
assert flag[:5]==b'flag{'

m1 = bytes_to_long(flag[:20])
p  = getPrime(512)
p1 = gmpy2.next_prime(p)
q  = getPrime(512)
q1 = gmpy2.next_prime(q)
n1 = p*q*p1*q1
print('n1 =',n1)
e = 0x10001
c1 = pow(m1,e,n1)
print('c1 =',c1)


m2 = bytes_to_long(flag[20:])
p2 = getPrime(1024)
q2 = getPrime(1024)
print('p2+q2 =',p2+q2)
print('q2*q2 =',p2*q2)
n2 = p2*p2*q2*q2*q2
print('n2 =',n2)
c2 = pow(m2,e,n2)
print('c2 =',c2)

#n1 = 6348779979606280884589422188738902470575876294643492831465947360363568026280963989291591157710389629216109615274754718329987990551836115660879103234129921943824061416396264358110216047994331119920503431491509529604742468032906950984256964560405062345280120526771439940278606226153077959057882262745273394986607004406770035459301695806378598890589432538916219821477777021460189140081521779103226953544426441823244765828342973086422949017937701261348963541035128661464068769033772390320426795044617751909787914185985911277628404632533530390761257251552073493697518547350246993679844132297414094727147161169548160586911
#c1 = 6201882078995455673376327652982610102807874783073703018551044780440620679217833227711395689114659144506630609087600915116940111002026241056808189658969089532597757995423694966667948250438579639890580690392400661711864264184444018345499567505424672090632235109624193289954785503512742400960515331371813467034511130432319427185134018830006918682733848618201088649690422818940385123599468595766345668931882249779415788129316594083269412221804774856038796248038700275509397599351533280014908894068141056694660319816046357462684688942519849441237878018480036145051967731081582598773076490918572392784684372694103015244826

#p2+q2 = 274773146761138462708137582309097386437793891793691383033856524303010811294101933454824485010521468914846151819876043508541879637544444256520741418495479393777132830985856522008561088410862815913292288683761657919121930016956916865849261153721097671315883469348972925757078089715102032241818526925988645578778
#q2*q2 = 18514724270030962172566965941723224386374076294232652258701085781018776172843355920566035157331579524980108190739141959926523082142273672741849552475156278397131571360099018592018959785627785130126477982765210498547680367230723634424036009539347854344573537848628061468892166199866227984167843139793429682559241317072979374002912607549039431398267184818771503468116379618249319324788996321340764624593443106354104274472601170229835219638093242557547840060892527576940077162990069687019966946826210112318408269749294366586682732614372434218768720577917368726530200897558912687470088583774711767599580037663378929000217
#n2 = 40588227045595304080360385041082238507044292731344465815296032905633525556943787610712651675460810768762763493579129831271018141591546207557410817432455139315527674932933085299277599173971912445226532235814580879585317211349524406424200622675880992390782025158621241499693400288031658194434641718026910652327933253877313106112861283314274635124734817398465059373562194694957841264834312640926278890386089611103714990646541470577351599526904458342660444968591197606820361364761648205241041444681145820799054413179462285509661124362074093583494932706249461954240408827087015525507173082129412234486228092002841868365895837463699200959915782767657258729794037776401995309244941171415842403617486719492483671490834562579225506831496881542530519595438932482796867853234159664409420977526102480385193101883785161080269573707156626838551506024455480650224305894501968583442346807126920740779780593650871645915149689424292912611578291912721896864772950410266629045542480009266574096080138709683466489568290569363478444349563498507530805502511051165160827192795520182720802422213364247355775222858214648603034743679187470844212529134374975737510982287957316878179964602394749601431823167982157434890459245394370728942790117156485268116758052636794417268680901420193002289035538753620555488506926366624641291881353268617130968991258983002165300186971963661666476600998389048880565199317280428349802824448329898502788492233381873026217202981921654673840142095839603360666049476100561268336225902504932800605464136192275593886736746497955270280541423593
#c2 = 25591090168544821761746024178724660839590948190451329227481168576490717242294520739865602061082558759751196452117720647426598261568572440942370039702932821941366792140173428488344932203576334292648255551171274828821657097667106792872200082579319963310503721435500623146012954474613150848083425126987554594651797477741828655238243550266972216752593788734836373144363217639612492397228808215205862281278774096317615918854403992620720969173788151215489908812749179861803144937169587452008097008940710091361183942268245271154461872102813602754439939747566507116519362821255724179093051041994730856401493996771276172343313045755916751082693149885922105491818225012844519264933137622929024918619477538521533548551789739698933067212305578480416163609137189891797209277557411169643568540392303036719952140554435338851671440952865151077383220305295001632816442144022437763089133141886924265774247290306669825085862351732336395617276100374237159580759999593028756939354840677333467281632435767033150052439262501059299035212928041546259933118564251119588970009016873855478556588250138969938599988198494567241172399453741709840486953189764289118312870580993115636710724139809708256360212728127786394411676427828431569046279687481368215137561500777480380501551616577832499521295655237360184159889151837766353116185320317774645294201044772828099074917077896631909654671612557207653830344897644115936322128351494551004652981550758791285434809816872381900401440743578104582305215488888563166054568802145921399726673752722820646807494657299104190123945675647

题目源码分为两个部分，将flag进行分割了，分成两个部分进行加密。

第一部分需要使用暴力的美学进行求解。

第二部分需要使用优雅的运算进行求解。

首先，看一下第一部分的加密代码：

m1 = bytes_to_long(flag[:20])
p  = getPrime(512)
p1 = gmpy2.next_prime(p)
q  = getPrime(512)
q1 = gmpy2.next_prime(q)
n1 = p*q*p1*q1
print('n1 =',n1)
e = 0x10001
c1 = pow(m1,e,n1)
print('c1 =',c1)

多素因子进行加密的，但是这几个素因子的生成是非常有意思的，有着微妙的关系，可以根据这个关系来寻找可能存在的漏洞 $$ p_1 = p + \epsilon \ q_1 = q + \delta $$ 根据这种关系可以进行发现： $$ \begin{aligned} p \cdot q_1 - q \cdot p_1 &= p \cdot (q+\delta) - q \cdot (p+\epsilon) \ &= p \cdot q + p \cdot \delta - p \cdot q - q\cdot \epsilon \ &= p \cdot \delta - q \cdot \epsilon \end{aligned} $$ 根据运算可以发现 pq1 和 qp1 之间相差不是非常大，可以使用 Alpertron’s Integer Factorization Calculator算法进行求解得到 pq1 和 qp1的数值

t1 = 79679231796035037354449627487236220201878797729093909877127396750043503300636464774059752126148617367251988043645511172901030621825575172979048675217345099706517900079260617448298874437193769061144201311929792287772928471712053565834702260975126852624433945451405258351557569670978748727663718174543709899747
t2 = 79679231796035037354449627487236220201878797729093909877127396750043503300636464774059752126148617367251988043645511172901030621825575172979048675217341753594180007984204016274224280609480494305040439035855109422239942522968468133274883986349646765947317076885918174299537297351936448296784166003890345486613

现在得到了一部分信息，继续进行求解： $$ \begin{aligned} t_1 &= p\cdot q_1 \ &= p \cdot (q+\delta) \ \Rightarrow p &= \frac{t_1}{q+\delta} \end{aligned} $$

$$ \begin{aligned} t_2 &= q\cdot p_1 \ &= q \cdot (p+\epsilon) \ \Rightarrow p &= \frac{t_2-q \cdot \epsilon}{q} \end{aligned} $$

组合这两个等式有 $$ \begin{aligned} \frac{t_2 - q \cdot \epsilon}{q} &= \frac{t_1}{q+\delta} \ (q+\delta) \cdot (t_2 - q\cdot \epsilon) &= t_1 \cdot q \ \epsilon \cdot q^2 + (\epsilon \cdot \delta+t_1-t_2)\cdot q - \delta\cdot t_2 &= 0 \end{aligned} $$ 下面就是需要进行小素数的爆破求解以及，方程的求解

根据式子可以写个程序进行求解，求解得到q然后可以根究q求出p1和q1，然后再根据求出的q1求出p，这道题目的前半部分就算是求解完成了

前半部分的exp：

def quadratic(a, b, c):
    try:
        (d, _) = gmpy2.iroot(b*b - (4*a*c),2)
        return ((-b-d)//(2*a), (-b+d)//(2*a))
    except:
        return 0
# flag[:20]
n1 = 6348779979606280884589422188738902470575876294643492831465947360363568026280963989291591157710389629216109615274754718329987990551836115660879103234129921943824061416396264358110216047994331119920503431491509529604742468032906950984256964560405062345280120526771439940278606226153077959057882262745273394986607004406770035459301695806378598890589432538916219821477777021460189140081521779103226953544426441823244765828342973086422949017937701261348963541035128661464068769033772390320426795044617751909787914185985911277628404632533530390761257251552073493697518547350246993679844132297414094727147161169548160586911
c1 = 6201882078995455673376327652982610102807874783073703018551044780440620679217833227711395689114659144506630609087600915116940111002026241056808189658969089532597757995423694966667948250438579639890580690392400661711864264184444018345499567505424672090632235109624193289954785503512742400960515331371813467034511130432319427185134018830006918682733848618201088649690422818940385123599468595766345668931882249779415788129316594083269412221804774856038796248038700275509397599351533280014908894068141056694660319816046357462684688942519849441237878018480036145051967731081582598773076490918572392784684372694103015244826
e = 0x10001

t2 = 79679231796035037354449627487236220201878797729093909877127396750043503300636464774059752126148617367251988043645511172901030621825575172979048675217341753594180007984204016274224280609480494305040439035855109422239942522968468133274883986349646765947317076885918174299537297351936448296784166003890345486613
t1 = 79679231796035037354449627487236220201878797729093909877127396750043503300636464774059752126148617367251988043645511172901030621825575172979048675217345099706517900079260617448298874437193769061144201311929792287772928471712053565834702260975126852624433945451405258351557569670978748727663718174543709899747
q = 0
epsilon = 0
delta = 0
for (epsilon, delta) in ((epsilon, delta) for epsilon in range(1, 5000) for delta in range(1, 5000)):
    q1 = quadratic(epsilon, epsilon*delta+t1-t2, -delta*t2)
    if q1 != 0:
        q1 = q1[1]
    res = q1*q1*epsilon + q1*(epsilon*delta+t1-t2)-delta*t2
    if res == 0 and isPrime(q1):
        q = q1
        epsilon = epsilon
        delta = delta
        break
q1 = gmpy2.next_prime(q)
p1= t2 // q
p = t1//q1
phi1 = (p-1)*(q-1)*(p1-1)*(q1-1)
d1 = libnum.invmod(e,phi1)
m1 = pow(c1,d1,n1)
flag1 = long_to_bytes(m1)

然后，看一下第二部分的代码，第二部分是非常优雅的进行求解的

m2 = bytes_to_long(flag[20:])
p2 = getPrime(1024)
q2 = getPrime(1024)
print('p2+q2 =',p2+q2)
print('q2*q2 =',p2*q2)
n2 = p2*p2*q2*q2*q2
print('n2 =',n2)
c2 = pow(m2,e,n2)
print('c2 =',c2)

对第二部分进行审计可以发现，第二部分就是一个解方程和Euler定理的应用，构造方程和Euler定理进行求解：

p2 = sympy.Symbol('p2')
q2 = sympy.Symbol('q2')

result = sympy.solve([p2+q2-274773146761138462708137582309097386437793891793691383033856524303010811294101933454824485010521468914846151819876043508541879637544444256520741418495479393777132830985856522008561088410862815913292288683761657919121930016956916865849261153721097671315883469348972925757078089715102032241818526925988645578778,p2*q2-18514724270030962172566965941723224386374076294232652258701085781018776172843355920566035157331579524980108190739141959926523082142273672741849552475156278397131571360099018592018959785627785130126477982765210498547680367230723634424036009539347854344573537848628061468892166199866227984167843139793429682559241317072979374002912607549039431398267184818771503468116379618249319324788996321340764624593443106354104274472601170229835219638093242557547840060892527576940077162990069687019966946826210112318408269749294366586682732614372434218768720577917368726530200897558912687470088583774711767599580037663378929000217],p2,q2)
n2 = 40588227045595304080360385041082238507044292731344465815296032905633525556943787610712651675460810768762763493579129831271018141591546207557410817432455139315527674932933085299277599173971912445226532235814580879585317211349524406424200622675880992390782025158621241499693400288031658194434641718026910652327933253877313106112861283314274635124734817398465059373562194694957841264834312640926278890386089611103714990646541470577351599526904458342660444968591197606820361364761648205241041444681145820799054413179462285509661124362074093583494932706249461954240408827087015525507173082129412234486228092002841868365895837463699200959915782767657258729794037776401995309244941171415842403617486719492483671490834562579225506831496881542530519595438932482796867853234159664409420977526102480385193101883785161080269573707156626838551506024455480650224305894501968583442346807126920740779780593650871645915149689424292912611578291912721896864772950410266629045542480009266574096080138709683466489568290569363478444349563498507530805502511051165160827192795520182720802422213364247355775222858214648603034743679187470844212529134374975737510982287957316878179964602394749601431823167982157434890459245394370728942790117156485268116758052636794417268680901420193002289035538753620555488506926366624641291881353268617130968991258983002165300186971963661666476600998389048880565199317280428349802824448329898502788492233381873026217202981921654673840142095839603360666049476100561268336225902504932800605464136192275593886736746497955270280541423593
c2 = 25591090168544821761746024178724660839590948190451329227481168576490717242294520739865602061082558759751196452117720647426598261568572440942370039702932821941366792140173428488344932203576334292648255551171274828821657097667106792872200082579319963310503721435500623146012954474613150848083425126987554594651797477741828655238243550266972216752593788734836373144363217639612492397228808215205862281278774096317615918854403992620720969173788151215489908812749179861803144937169587452008097008940710091361183942268245271154461872102813602754439939747566507116519362821255724179093051041994730856401493996771276172343313045755916751082693149885922105491818225012844519264933137622929024918619477538521533548551789739698933067212305578480416163609137189891797209277557411169643568540392303036719952140554435338851671440952865151077383220305295001632816442144022437763089133141886924265774247290306669825085862351732336395617276100374237159580759999593028756939354840677333467281632435767033150052439262501059299035212928041546259933118564251119588970009016873855478556588250138969938599988198494567241172399453741709840486953189764289118312870580993115636710724139809708256360212728127786394411676427828431569046279687481368215137561500777480380501551616577832499521295655237360184159889151837766353116185320317774645294201044772828099074917077896631909654671612557207653830344897644115936322128351494551004652981550758791285434809816872381900401440743578104582305215488888563166054568802145921399726673752722820646807494657299104190123945675647
P2 = 0
Q2 = 0
for test in result:
    _p2 = test[0]
    _q2 = test[1]
    if n2 == _p2*_p2*_q2*_q2*_q2:
        P2 = _p2
        Q2 = _q2
        break

phi2 = P2*(P2-1)*pow(Q2,2)*(Q2-1)
d2 = int(libnum.invmod(e,phi2))
m2 = pow(c2,d2,n2)
flag2 = libnum.n2s(m2)

完整exp：

import libnum
import sympy
import gmpy2
from Crypto.Util.number import *


def quadratic(a, b, c):
    try:
        (d, _) = gmpy2.iroot(b*b - (4*a*c),2)
        return ((-b-d)//(2*a), (-b+d)//(2*a))
    except:
        return 0
# flag[:20]
n1 = 6348779979606280884589422188738902470575876294643492831465947360363568026280963989291591157710389629216109615274754718329987990551836115660879103234129921943824061416396264358110216047994331119920503431491509529604742468032906950984256964560405062345280120526771439940278606226153077959057882262745273394986607004406770035459301695806378598890589432538916219821477777021460189140081521779103226953544426441823244765828342973086422949017937701261348963541035128661464068769033772390320426795044617751909787914185985911277628404632533530390761257251552073493697518547350246993679844132297414094727147161169548160586911
c1 = 6201882078995455673376327652982610102807874783073703018551044780440620679217833227711395689114659144506630609087600915116940111002026241056808189658969089532597757995423694966667948250438579639890580690392400661711864264184444018345499567505424672090632235109624193289954785503512742400960515331371813467034511130432319427185134018830006918682733848618201088649690422818940385123599468595766345668931882249779415788129316594083269412221804774856038796248038700275509397599351533280014908894068141056694660319816046357462684688942519849441237878018480036145051967731081582598773076490918572392784684372694103015244826
e = 0x10001

t2 = 79679231796035037354449627487236220201878797729093909877127396750043503300636464774059752126148617367251988043645511172901030621825575172979048675217341753594180007984204016274224280609480494305040439035855109422239942522968468133274883986349646765947317076885918174299537297351936448296784166003890345486613
t1 = 79679231796035037354449627487236220201878797729093909877127396750043503300636464774059752126148617367251988043645511172901030621825575172979048675217345099706517900079260617448298874437193769061144201311929792287772928471712053565834702260975126852624433945451405258351557569670978748727663718174543709899747
q = 0
epsilon = 0
delta = 0
for (epsilon, delta) in ((epsilon, delta) for epsilon in range(1, 5000) for delta in range(1, 5000)):
    q1 = quadratic(epsilon, epsilon*delta+t1-t2, -delta*t2)
    if q1 != 0:
        q1 = q1[1]
    res = q1*q1*epsilon + q1*(epsilon*delta+t1-t2)-delta*t2
    if res == 0 and isPrime(q1):
        q = q1
        epsilon = epsilon
        delta = delta
        break
q1 = gmpy2.next_prime(q)
p1= t2 // q
p = t1//q1
phi1 = (p-1)*(q-1)*(p1-1)*(q1-1)
d1 = libnum.invmod(e,phi1)
m1 = pow(c1,d1,n1)
flag1 = long_to_bytes(m1)

# flag[20:]
p2 = sympy.Symbol('p2')
q2 = sympy.Symbol('q2')

result = sympy.solve([p2+q2-274773146761138462708137582309097386437793891793691383033856524303010811294101933454824485010521468914846151819876043508541879637544444256520741418495479393777132830985856522008561088410862815913292288683761657919121930016956916865849261153721097671315883469348972925757078089715102032241818526925988645578778,p2*q2-18514724270030962172566965941723224386374076294232652258701085781018776172843355920566035157331579524980108190739141959926523082142273672741849552475156278397131571360099018592018959785627785130126477982765210498547680367230723634424036009539347854344573537848628061468892166199866227984167843139793429682559241317072979374002912607549039431398267184818771503468116379618249319324788996321340764624593443106354104274472601170229835219638093242557547840060892527576940077162990069687019966946826210112318408269749294366586682732614372434218768720577917368726530200897558912687470088583774711767599580037663378929000217],p2,q2)
n2 = 40588227045595304080360385041082238507044292731344465815296032905633525556943787610712651675460810768762763493579129831271018141591546207557410817432455139315527674932933085299277599173971912445226532235814580879585317211349524406424200622675880992390782025158621241499693400288031658194434641718026910652327933253877313106112861283314274635124734817398465059373562194694957841264834312640926278890386089611103714990646541470577351599526904458342660444968591197606820361364761648205241041444681145820799054413179462285509661124362074093583494932706249461954240408827087015525507173082129412234486228092002841868365895837463699200959915782767657258729794037776401995309244941171415842403617486719492483671490834562579225506831496881542530519595438932482796867853234159664409420977526102480385193101883785161080269573707156626838551506024455480650224305894501968583442346807126920740779780593650871645915149689424292912611578291912721896864772950410266629045542480009266574096080138709683466489568290569363478444349563498507530805502511051165160827192795520182720802422213364247355775222858214648603034743679187470844212529134374975737510982287957316878179964602394749601431823167982157434890459245394370728942790117156485268116758052636794417268680901420193002289035538753620555488506926366624641291881353268617130968991258983002165300186971963661666476600998389048880565199317280428349802824448329898502788492233381873026217202981921654673840142095839603360666049476100561268336225902504932800605464136192275593886736746497955270280541423593
c2 = 25591090168544821761746024178724660839590948190451329227481168576490717242294520739865602061082558759751196452117720647426598261568572440942370039702932821941366792140173428488344932203576334292648255551171274828821657097667106792872200082579319963310503721435500623146012954474613150848083425126987554594651797477741828655238243550266972216752593788734836373144363217639612492397228808215205862281278774096317615918854403992620720969173788151215489908812749179861803144937169587452008097008940710091361183942268245271154461872102813602754439939747566507116519362821255724179093051041994730856401493996771276172343313045755916751082693149885922105491818225012844519264933137622929024918619477538521533548551789739698933067212305578480416163609137189891797209277557411169643568540392303036719952140554435338851671440952865151077383220305295001632816442144022437763089133141886924265774247290306669825085862351732336395617276100374237159580759999593028756939354840677333467281632435767033150052439262501059299035212928041546259933118564251119588970009016873855478556588250138969938599988198494567241172399453741709840486953189764289118312870580993115636710724139809708256360212728127786394411676427828431569046279687481368215137561500777480380501551616577832499521295655237360184159889151837766353116185320317774645294201044772828099074917077896631909654671612557207653830344897644115936322128351494551004652981550758791285434809816872381900401440743578104582305215488888563166054568802145921399726673752722820646807494657299104190123945675647
P2 = 0
Q2 = 0
for test in result:
    _p2 = test[0]
    _q2 = test[1]
    if n2 == _p2*_p2*_q2*_q2*_q2:
        P2 = _p2
        Q2 = _q2
        break

phi2 = P2*(P2-1)*pow(Q2,2)*(Q2-1)
d2 = int(libnum.invmod(e,phi2))
m2 = pow(c2,d2,n2)
flag2 = libnum.n2s(m2)

flag = flag1+flag2
print(flag)