DASCTF2024八月CRYPTO-EZsquares

Rxw
  2024-08-26 23:34:25 2024-08-26 23:34:25 作成   2024-11-12 10:42:15 2024-11-12 10:42:15 更新      208 字  1 分  

题目描述：

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

p=getPrime(512)
q=getPrime(512)
n0=p**2+q**2
print('n0 =',n0)

e=65537
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
print('c =',c)

# n0 = 192573744538639130845868727014075967669513667763315934161849620531683536696376138303320681922782003088094539724238109116416456294472461075668568088688287209898850985024632463251984323888765249950269595045648435192047990940593817086918399212487934262786817996341234806934640246045717955941049031252181676005098

# c = 1541487946178344665369701061600511101386703525091161664845860490319891364778119340877432325104511886045675705355836238082338561882984242433897307540689460550149990099278522355182552369360471907683216881430656993369902193583200864277424101240184767762679012998894182000556316811264544736356326198994294262682

其实主要是根据n0=p2+q2，来求解两个质数。

这里用到：

from sympy.solvers.diophantine.diophantine import cornacchia
cornacchia(2, 3, 35) # equation 2x**2 + 3y**2 = 35
cornacchia(1, 1, 25) # equation x**2 + y**2 = 25

https://github.com/sympy/sympy/blob/2197797741156d9cb73a8d1462f7985598e9b1a9/sympy/solvers/diophantine/diophantine.py#L2140-L2191

最后，得到：

#from sympy.solvers.diophantine.diophantine import cornacchia
#n0 = 192573744538639130845868727014075967669513667763315934161849620531683536696376138303320681922782003088094539724238109116416456294472461075668568088688287209898850985024632463251984323888765249950269595045648435192047990940593817086918399212487934262786817996341234806934640246045717955941049031252181676005098
#cornacchia(1,1,n0)
#{(10086734295867809031933000602297655421857339182506197435775807151492625332977658377903887871194246780561421872540211079513620256179009798242872323279273643, 9530557999571864814846813802848820053359900696259942450377418829177567701059753389296838605189717543060884246576192261705743587980887069176763775622017593), 
 #(12632497198655018753940994235529831902846639993049627558288710168983045920727975240491841587947979671253523689130316079012044108703675345097883692492940233, 5744019417151393517201147996544238832575904167000638284699999275764955825442147786230883695332679801091726652964437735284799527167106211953304439659981947), 
 #(13850105486554633527019260685209688225762807153985235251116023247160784491373688971369063780575923349115802935585810749774267006906993846398668456246644903, 865056385415638059136671409462863871746373933704068917534280105839113126158473951278906078992199456513574612084203858088772124545245752057954755735368117), 
 #(13859122362410648020675457028666154546388932598960760555730846929654249865572473296198127251245880137442392812529009142220332194552889906719572630605375943, 706025411984745396948497381538076394629302196765359656142463898306216415289544488923349607398368989805348708367497395762244629842441902990748539823230293), 
 #(11902265017193255514381686804589948942351813100767943273349247290945499466994655883435686822454794625831069638735275526469535462413065469698668888764904143, 7135112612926075174581896396551030270669894577611882325973046002808363480772914355626186650143420888914666635854758972890852967780613146013587765350787907), 
 #(12880999398393398269196189930401580875353000394660602799374866912384436440853027878374439419049334511697826052381225708880126790574103889170163772792145797, 5162712372118753111927105208049365631586291029035586881993416205312664133027128018018777385780904764662051852519203204278987794030274202305704607056150583), 
 #(13382009963632427842035518402591714982774452367403569210796545268126940938161643281439570412650370559384216164608481690247692182061830639152671703715053757, 3673629522948872169039125105170703329676502653194065159451147980042174445430748090855866286545516194903095237948178215248221073616224995533935270924914993), 
 #(10609624909695451277917476095523390453558596416908951369979664259179424741378050622922831746607493692486112646479455955913899443818330966131340498715038553, 8944808763423001105631791389244212154980397935014470990690462247280868096636161720344183756329642195597606425012906371668743393813241451007847511420599733)}

然后我们验证，得到一组全是质数的解。

from Crypto.Util.number import *
n0 = 192573744538639130845868727014075967669513667763315934161849620531683536696376138303320681922782003088094539724238109116416456294472461075668568088688287209898850985024632463251984323888765249950269595045648435192047990940593817086918399212487934262786817996341234806934640246045717955941049031252181676005098
c = 1541487946178344665369701061600511101386703525091161664845860490319891364778119340877432325104511886045675705355836238082338561882984242433897307540689460550149990099278522355182552369360471907683216881430656993369902193583200864277424101240184767762679012998894182000556316811264544736356326198994294262682
p = 11902265017193255514381686804589948942351813100767943273349247290945499466994655883435686822454794625831069638735275526469535462413065469698668888764904143
q = 7135112612926075174581896396551030270669894577611882325973046002808363480772914355626186650143420888914666635854758972890852967780613146013587765350787907
e=65537
n=p*q
phi=(p-1)*(q-1)
d=inverse(e,phi)
print(long_to_bytes(int(pow(c, int(d), n))))

# DASCTF{4028d59bb18028e2df8d5d51b376908c}

最后得到解

  • タイトル: DASCTF2024八月CRYPTO-EZsquares
  • 作者: Rxw
  • で作成されました : 2024-08-26 23:34:25
  • で更新されました : 2024-11-12 10:42:15
  • リンク: https://rxw2023-github-io.pages.dev/2024/08/26/DASCTF2024八月CRYPTO-EZsquares/
  • 著作権宣言: この文章は CC BY-NC-SA 4.0 を使用して許可します。
コメント
目次
DASCTF2024八月CRYPTO-EZsquares