FCTF

2023-05-13

校赛的题目都好难啊！！

OhMySubstitution

上来给了三个文件，依次打开后虽然看不懂是怎么转换的，但是发现已经给了task.py和task.py.sub，并且也给了转换之后的flag。

并且比对转换之后的头部恰好对应着“flag”，发现了这个之后，就进行了漫长的对比过程。。。最后一个个对比LEXx{AabPEFwmhSLZICtK4V7PEF53XdEF1xv}在task.py和task.py.sub中的相对位置，最后得到flag为：flag{SImpleFLAGf0rth3siMpleCHa1lengE}。

OhMyBabyRSA

from Crypto.Util.number import *
from gmpy2 import *
from flag import flag

assert len(flag) == 64
m = bytes_to_long(flag)
e = 0x10001
p = getPrime(512)
q = next_prime(p)
r = next_prime(p ** 2)
s = next_prime(p ** 2 + 2 * p)
n = p * q * r * s
enc_flag = pow(m, e, n)
print('enc_flag = {}'.format(enc_flag))
print('n = {}'.format(n))
# enc_flag = 558836963892291103066012094226404872594845364724579579991939237075579471649022307274993648128182517068287908608655415311755710090008211573414344029835353781291323908206471422281147726239928360761865479544172749805334616301957959278310473294247847521324572903221325229335022712401334502115695904656113962454250581526487895617076665754872131186428648736058458412272765528707432325958141098175330803091489468724702305686936229775407901818600060946741408743919586767495259761367467476503780543279625798302542584588978511276728664944144579409952017206450866041923826806704052807019813067433837160952899733154934186413925841253118812554800888389368694102120865165465433259165138659414714776140989544202661327846864680898295330274677583542546296074123273743756046577717820668548175691681620322220047893114528135863551048011715129345653970540952003136382932332819185050051737497246260600134821357970479905685544379854114544905948675
# n = 4585220815776999590055268112030603818021191370301120880780222364392250014983314932723298191358652879592967574345478779616485618832169592564777281575229501545712411843629202396154469247865107402975392888995304852104947403496017764676587445201431113495491552183361767761315150187982631812381238087947034846562736655789319024873832925979674088032852318237995824554295270982389181363828453148263620332874085992344607610869015297326907819850433565724104404950554547589126111382147046243321683721375936214001147848535405650428880055597764068065280248888037305689827899917209188622887273812501048396659996613733703663885928471971978569071784449540183594649965515643612482274284037115014264632840294739610331402567051615488750578731580283981608846801850905256596712916241406828340016173069989416184703050234519900628400339072501951161184622923080534399066722460909462250943918523149342428697097029180299994056867709033999356912758167

由题目可知，n由四个素数构成，本来以为可以暴力破解，但是不知道为什么在yafu上分解不了，其他在线网站也无济于事。所以只好找其他办法，从题目发现，p，q非常接近，r，s非常接近p^2和（p+1)^2,所以想到了直接将n开6次方。得到了一个与p很接近的实数。

from sympy import nextprime

n = 4585220815776999590055268112030603818021191370301120880780222364392250014983314932723298191358652879592967574345478779616485618832169592564777281575229501545712411843629202396154469247865107402975392888995304852104947403496017764676587445201431113495491552183361767761315150187982631812381238087947034846562736655789319024873832925979674088032852318237995824554295270982389181363828453148263620332874085992344607610869015297326907819850433565724104404950554547589126111382147046243321683721375936214001147848535405650428880055597764068065280248888037305689827899917209188622887273812501048396659996613733703663885928471971978569071784449540183594649965515643612482274284037115014264632840294739610331402567051615488750578731580283981608846801850905256596712916241406828340016173069989416184703050234519900628400339072501951161184622923080534399066722460909462250943918523149342428697097029180299994056867709033999356912758167

near_p1 = int(n**(1/6))
p = nextprime(near_p1)
q = nextprime(p)
r = nextprime(p**2)
s = nextprime(p**2 + 2 * p)

print('p=',p)
print('q=',q)
print('r=',r)
print('s=',s)

在sagemath中跑完发现得到的值并不相等，因为n^(1/6)>p,所以得到是一个比p大的一个素数，但是又非常接近，所以就减小near_p1，发现当near_p1-3时，p,q,r,s的值发生改变，并且经过验证之后发现n==p* q * r * s

最后将得到的值拿到python中解决就能拿到flag了

import gmpy2
from Crypto.Util.number import *
import math

e = 65537
c = 558836963892291103066012094226404872594845364724579579991939237075579471649022307274993648128182517068287908608655415311755710090008211573414344029835353781291323908206471422281147726239928360761865479544172749805334616301957959278310473294247847521324572903221325229335022712401334502115695904656113962454250581526487895617076665754872131186428648736058458412272765528707432325958141098175330803091489468724702305686936229775407901818600060946741408743919586767495259761367467476503780543279625798302542584588978511276728664944144579409952017206450866041923826806704052807019813067433837160952899733154934186413925841253118812554800888389368694102120865165465433259165138659414714776140989544202661327846864680898295330274677583542546296074123273743756046577717820668548175691681620322220047893114528135863551048011715129345653970540952003136382932332819185050051737497246260600134821357970479905685544379854114544905948675
n = 4585220815776999590055268112030603818021191370301120880780222364392250014983314932723298191358652879592967574345478779616485618832169592564777281575229501545712411843629202396154469247865107402975392888995304852104947403496017764676587445201431113495491552183361767761315150187982631812381238087947034846562736655789319024873832925979674088032852318237995824554295270982389181363828453148263620332874085992344607610869015297326907819850433565724104404950554547589126111382147046243321683721375936214001147848535405650428880055597764068065280248888037305689827899917209188622887273812501048396659996613733703663885928471971978569071784449540183594649965515643612482274284037115014264632840294739610331402567051615488750578731580283981608846801850905256596712916241406828340016173069989416184703050234519900628400339072501951161184622923080534399066722460909462250943918523149342428697097029180299994056867709033999356912758167
p= 12889222157689481670246473135005825250630401991073722080055662757971514279409143880875414854378230689212076117760050469978076846937944856563667923585241491
q= 12889222157689481670246473135005825250630401991073722080055662757971514279409143880875414854378230689212076117760050469978076846937944856563667923585241501
r= 166132047830273497491447803339250536606519563835673905705150928156122916145824954729515830070099322846248800665090035695746709638696855950019640580027151550765537519056301227563988435125025526734768241420829952154653584047587790039630279710081142538235144138748803163102172486912968081338232713293988787904569
s= 166132047830273497491447803339250536606519563835673905705150928156122916145824954729515830070099322846248800665090035695746709638696855950019640580027151576543981834435264568056934705136676027995572223568274112265979099990616348857918041460910851294696522562901038683203112443066661957227945840629835958386073
d = gmpy2.invert(e, (p-1)*(q-1)*(r-1)*(s-1))
m = pow(c, d, p * q*r*s)
print(d)
print(m)
print(long_to_bytes(m))

flag为：FCTF{it_easy_pqrst_RSA_also_baby_with_Monotonically_increasing!}