2021 绿城杯 Crypto WP

绿城杯 Crypto WP"/>

2021 绿城杯 Crypto WP

2021 绿城杯 Crypto WP

• 第1题 [Warmup]加密算法
• 第2题 RSA-1
• 第3题 RSA-2
• • • 前半部分
    • 后半部分

第1题 [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 += iprint(cipher_text)encode(flag,37,23,52)
# cipher_text = 'aoxL{XaaHKP_tHgwpc_hN_ToXnnht}'

传统的仿射加密方法。
明确给出了加密方式和加密的参数。

即：将明文中的每一个字母，一对一地映射到密码表的一个字母，类似键值对的关系。
将每一个字符通过加密函数得到对应的加密集，反过来就是对应的解密集。

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 += ireturn cipher_textdec = {}
for ch in str1:enc_ch = encode(ch,37,23,52)dec[enc_ch] = ch  # 将一个密文字符映射到一个明文字符def decode(enc):if enc in str1:return dec[enc]return enc # 若字符未经加密则直接返回cipher_text = 'aoxL{XaaHKP_tHgwpc_hN_ToXnnht}'
print(''.join(decode(i) for i in cipher_text)) #打印明文

即可得到flag

flag{AffInE_CIpheR_iS_clAssiC}

经典仿射加密

第2题 RSA-1

题目：

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

已知e,c,n,要求出flag，也就是要求出M
网站尝试分解n无果，只能从已知条件入手

>>> gmpy2.gcd(c,n)
mpz(150290608270992439844054823303154263794197803561695786056860615174575181277160032222859532335454486914357850849343036173838960820180867595169623670363963732315901587946639577107202780317748525709407153327463601548012321945759392416846089189522151851138821377551427960151260776474250605261723480167088408148729) 

于是成功分解n。

暂时将值分别赋值给p和q

>>> p = gmpy2.gcd(c,n)
>>> n%p
mpz(0)
>>> q = n//p

按步骤求出M

>>> e = 0x10001
>>> d = gmpy2.invert(e,p*q-p-q+1)
>>> M = pow(c,d,n)
>>> M
mpz(839557191476857941665476233330553501713716497294339152125932992839650592721485160403872136110418315458948348727530876368684706703897783475419961094360953385279781752500013759979228820668731130857877240875446092111185288540800083174791533659316206649254642561508806513443981994150015387695427576272218347161581110192205737072101697927873587752287392581838322987297150976125070114122865)

简单验算一下

>>> M%(2021*1001)
mpz(0)
>>> M%p
mpz(0)
>>> M%q
mpz(65474612994490743595307567400845726353964817450673526189849002591413379171120763579510522074305688595930063254638994149917069894951411587526157497240809530223522800190882193052998942162841327139276763569667223325545897581055534679226351135493091367975534910324477596809108688286418194639519316314924020879894)

这里 M % p == 0,直接除去即可得到m，即flag

>>> m = M//2021//1001//p
>>> import binascii
>>> binascii.unhexlify(hex(m)[2:])
b'flag{Math_1s_1nterest1ng_hah}'

既得flag:

flag{Math_1s_1nterest1ng_hah}

数学真有趣2333

完整代码：

from Crypto.Util.number import *
import gmpy2
import binasciin = 17365231154926348364478276872558492775911760603002394353723603461898405740234715001820111548600914907617003806652492391686710256274156677887101997175692277729648456087534987616743724646598234466094779540729413583826355145277980479040157075453694250572316638348121571218759769533738721506811175866990851972838466307594226293836934116659685215775643285465895317755892754473332034234495795936183610569571016400535362762699517686781602302045048532131426035260878979892169441059467623523060569285570577199236309888155833013721997933960457784653262076135561769838704166810384309655788983073376941843467117256002645962737847
c = 6944967108815437735428941286784119403138319713455732155925055928646536962597672941805831312130689338014913452081296400272862710447207265099750401657828165836013122848656839100854719965188680097375491193249127725599660383746827031803066026497989298856420216250206035068180963797454792151191071433645946245914916732637007117085199442894495667455544517483404006536607121480678688000420422281380539368519807162175099763891988648117937777951069899975260190018995834904541447562718307433906592021226666885638877020304005614450763081337082838608414756162253825697420493509914578546951634127502393647068722995363753321912676
e = 0x10001p = gmpy2.gcd(c,n)
q = n // pphin = (p-1) * (q-1)
d = gmpy2.invert(e,phin)
M = pow(c,d,n)
assert M % (2021*1001) == 0 and M % p == 0m = M // 2021 // 1001 // p
print(binascii.unhexlify(hex(m)[2:]))

第3题 RSA-2

题目：

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分为了两部分，分别加密。

前半部分

给出的条件

p  = getPrime(512)
p1 = gmpy2.next_prime(p)
q  = getPrime(512)
q1 = gmpy2.next_prime(q)
n1 = p*q*p1*q1

n1不是两个质数的乘积，而是4个。易得p,q,p1,q1两两互素，所以
φ ( n ) = φ ( p ) ⋅ φ ( p 1 ) ⋅ φ ( q ) ⋅ φ ( q 1 ) = ( p − 1 ) ⋅ ( q − 1 ) ⋅ ( p 1 − 1 ) ⋅ ( q 1 − 1 ) \varphi (n)=\varphi (p)\cdot \varphi(p1)\cdot \varphi(q)\cdot \varphi(q1)=(p-1)\cdot (q-1)\cdot (p1-1)\cdot (q1-1) φ(n)=φ(p)⋅φ(p1)⋅φ(q)⋅φ(q1)=(p−1)⋅(q−1)⋅(p1−1)⋅(q1−1)

题目给出的条件并不多，网站在线分解n1也失败了
这里需要用到 费马因式分解 ,可以参考 此处 。

from gmpy2 import *
from Crypto.Util.number import *
def fermat(n):factor_list = []get_context().precision = 2048x = int(sqrt(n))while 1:x += 1y2 = x ** 2 - nif is_square(y2):#print('x = ',x)y2 = mpz(y2)get_context().precision = 2048y = int(sqrt(y2))factor_list.append([x+y, x-y])if len(factor_list) == 2:breakreturn factor_list

可求出p1q1,p1q2,p2q1,p2q2的值，
再通过gcd求出分别的值。

完整代码

from Crypto.Util.number import *
from gmpy2 import *n1 = 6348779979606280884589422188738902470575876294643492831465947360363568026280963989291591157710389629216109615274754718329987990551836115660879103234129921943824061416396264358110216047994331119920503431491509529604742468032906950984256964560405062345280120526771439940278606226153077959057882262745273394986607004406770035459301695806378598890589432538916219821477777021460189140081521779103226953544426441823244765828342973086422949017937701261348963541035128661464068769033772390320426795044617751909787914185985911277628404632533530390761257251552073493697518547350246993679844132297414094727147161169548160586911
c1 = 6201882078995455673376327652982610102807874783073703018551044780440620679217833227711395689114659144506630609087600915116940111002026241056808189658969089532597757995423694966667948250438579639890580690392400661711864264184444018345499567505424672090632235109624193289954785503512742400960515331371813467034511130432319427185134018830006918682733848618201088649690422818940385123599468595766345668931882249779415788129316594083269412221804774856038796248038700275509397599351533280014908894068141056694660319816046357462684688942519849441237878018480036145051967731081582598773076490918572392784684372694103015244826
e = 0x10001def fermat(n):factor_list = []get_context().precision = 2048x = int(sqrt(n))while 1:x += 1y2 = x ** 2 - nif is_square(y2):y2 = mpz(y2)get_context().precision = 2048y = int(sqrt(y2))factor_list.append([x+y, x-y])if len(factor_list) == 2:breakreturn factor_listt = fermat(n1)
x1,y1 = t[0]
x2,y2 = t[1]p = gcd(x1,x2)
p1 = gcd(y1,y2)
q = x1 // p
q1 = y1 // p1phin1 = (p-1) * (q-1) * (p1-1) * (q1-1)
d1 = invert(e,phin1)
flag1 = long_to_bytes(pow(c1,d1,n1))
print(flag1,end='')

得到flag的前半段：

flag{Euler_funct1ons

欧拉函数 φ ( n ) \varphi_{(n)} φ(n)​ .

后半部分

已知的条件

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

已知 q 2 + p 2 q2+p2 q2+p2 和 p 2 ⋅ q 2 p2\cdot q2 p2⋅q2 ,通过解方程可求得 p 2 p2 p2 和 q 2 q2 q2 .

这里使用sympy来解二元二次方程组

from sympy import Symbol,solve
a = Symbol('a')
b = Symbol('b')
t = solve([a+b-add,a*b-mul],[a,b])q2,p2 = t[0]
assert n2 == q2**3 * p2**2
# 如果出错就换一组解或交换p2和q2

这里的 n 2 = q 2 3 ⋅ p 2 2 n_2=q_2 ^3\cdot p_2^2 n2​=q23​⋅p22​
由 q 2 ⋅ q 2 ⋅ q 2 q_2\cdot q_2\cdot q_2 q2​⋅q2​⋅q2​ 与 p 2 ⋅ p 2 p_2\cdot p_2 p2​⋅p2​ 互素，所以 φ ( n 2 ) = φ ( q 2 3 ) ⋅ φ ( p 2 2 ) \varphi (n_2)=\varphi (q_2^3)\cdot \varphi (p_2^2) φ(n2​)=φ(q23​)⋅φ(p22​)
当p为素数时，有公式 φ ( p α ) = p α − p α − 1 \varphi(p^\alpha)=p^{\alpha}-p^{\alpha-1} φ(pα)=pα−pα−1
所以 φ ( n 2 ) = ( q 2 3 − q 2 2 ) ⋅ ( p 2 2 − p 2 ) \varphi(n2)=(q_2^3-q_2^2)\cdot (p_2^2-p_2) φ(n2)=(q23​−q22​)⋅(p22​−p2​)

按步骤解出m即可

phin2 = (q2**3-q2**2) * (p2**2-p2)
d2 = invert(e,phin2)
m2 = pow(c2,int(d2),n2)
print(binascii.unhexlify(hex(m2)[2:]))

正常来说应该能得到flag
但有可能gmpy2库出bug会报错，可能是因为数字太大的原因
TypeError: invert() requires 'mpz','mpz' arguments

加上mpz()也无济于事

这里提几个解决方法
1.给过大的数字加上int()

d2 = invert(e,int(phin2))

如果pow函数也报错

Traceback (most recent call last):File "D:\Desktop\1.py", line 28, in <module>m2 = pow(c2,d2,n2)
TypeError: unsupported operand type(s) for pow(): 'int', 'Integer', 'int'

则给pow中出问题的数字加上int()即可

m2 = pow(c2,int(d2),n2)

2.手搓invert

phin2 = (q2**3-q2**2) * (p2**2-p2)
d2 = 0
for k in range(1,100000):if (phin2*k+1)%e == 0:d2 = (phin2*k+1) // ebreak
#d2 = invert(e,phin2)
m2 = pow(c2,pow(d2),n2)
print(binascii.unhexlify(hex(m2)[2:]))

最终得到flag的后半部分
与之前的组合起来得到完整flag

flag{Euler_funct1ons_1s_very_interst1ng}

欧拉函数真有趣