CTF Crypto --- orz!

news/2024/11/28 11:53:11/

文章目录

      • 题目
      • 解题过程

题目

from Crypto.Util.number import *
from gmpy2 import *flag = b'xxx'
t = len(flag)//3
part1 = bytes_to_long(flag[:t])
part2 = bytes_to_long(flag[t:2*t])
part3 = bytes_to_long(flag[2*t:])
q = getPrime(1024)
p = next_prime(q)
n = p * qo = getPrime(11)
r = pow(part1, o, p)
z = pow(part2, o, p)h1 = (13 * o + 14 * r + r * z + o * z ** 13) % p
h2 = (o ** 13 + r ** 12 + 3 * o * r + o * z * 233) % p
h3 = pow(part3,65537,n)print(f'n = {n}')
print(f'h1 = {h1}')
print(f'h2 = {h2}')
print(f'h3 = {h3}')# n = 10850335281775104384842309756387507121367947910896225110655535291748404338588972388693259827067445607230128971155491201985083085890729703137967791325100758142692285049056390126354246953310462082980059949946896088251642305978444680455930662301007461492978866538439458231120357274252592800042668860820459885960472737650446805378098344941597805604577797736381125259746781740429143953876454912647201590679786164678547559344304709889497251430904453036692562053570137262921657887410908992378188055660327282373869435308218926170927366572909858720457530661616332620263301130036238239402855045548920085800254012799063199438351
# h1 = 68971374440570454964336249870184699116849273092766598492393855724166755705038579719086135125490382149633066088736614770735555426661202444613481222308690955829177344713094803125405000495549811601138114210065623933916822257443366983845366477473811412048210602195672314631662681949260715610527325398006214477393
# h2 = 89557070262276493140173989636483552685176823962865601733383032051273942127575151309428084885522955047935745792156087951603894535351765100905696886714983834431355512680521411571740092935206188975497781396247799052916245218545834226095135276633422884113241438747017792108934964361391672183324214279475682695463
# h3 = 1311626365146856567785446974305480952394390450877042514912868019585929680223703697129400820765966547191027907141852232429577556122050933660875292235305985538892538821817570539411355339774474418018682334787217004485252794403892893871864009361554731318803763221581009731474777526380398647174787569510518293833348676730943915073911916070766302422834190969513630361764429111809259665372926096307389623440860840605142551951919723403665762066543095024186705959708920942727754417048332722263643582752118944418881587666520088786189326167958303315156763867706697503512512849397447463575294489956813935149823414834222869976238

解题过程

根据题目代码p = next_prime(q)可知,pq相邻,直接对n开方然后取下一个素数,直到被n整除为止,此时的p为所求。之后简单RSA解密即可求得flag3

#sage
n = 10850335281775104384842309756387507121367947910896225110655535291748404338588972388693259827067445607230128971155491201985083085890729703137967791325100758142692285049056390126354246953310462082980059949946896088251642305978444680455930662301007461492978866538439458231120357274252592800042668860820459885960472737650446805378098344941597805604577797736381125259746781740429143953876454912647201590679786164678547559344304709889497251430904453036692562053570137262921657887410908992378188055660327282373869435308218926170927366572909858720457530661616332620263301130036238239402855045548920085800254012799063199438351
p_near = gmpy2.iroot(n,2)[0]
while n%p_near!=0:p_near = gmpy2.next_prime(p_near)
p = p_near
q = n//p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m3 = pow(h3,d,n)
flag3 = long_to_bytes(int(m3))

接下来,我们已知条件
h 1 = 13 ∗ o + 14 ∗ r + r ∗ z + o ∗ z 13 m o d p h_1 = 13*o+14*r+r*z+o*z^{13} \space mod \space p h1=13o+14r+rz+oz13 mod p
h 2 = o 13 + r 12 + 3 ∗ o ∗ r + 233 ∗ z ∗ o m o d p h_2 = o^{13}+r^{12}+3*o*r+233*z*o \space mod \space p h2=o13+r12+3or+233zo mod p

h 2 h_2 h2变换,可得
⇒ 233 ∗ o ∗ z = ( h 2 − o 13 − r 12 − 3 ∗ o ∗ r ) m o d p \Rightarrow 233*o*z = (h_2-o^{13}-r^{12}-3*o*r) \space mod \space p 233oz=(h2o13r123or) mod p
⇒ z = ( h 2 − o 13 − r 12 − 3 ∗ o ∗ r ) ∗ ( 233 ∗ o ) − 1 m o d p \Rightarrow z = (h_2-o^{13}-r^{12}-3*o*r)*(233*o)^{-1} \space mod \space p z=(h2o13r123or)(233o)1 mod p

o已知时,z是一个在模p下关于r的等式(等下会用到)

那么,我们利用 h 1 h_1 h1构建一个在模p上面的多项式环,设r为变量,方程如下
f = 13 ∗ o + 14 ∗ r + r ∗ z + o ∗ z 13 − h 1 f = 13*o+14*r+r*z+o*z^{13} -h_1 f=13o+14r+rz+oz13h1
方程中的z其实是一个关于r的等式,也就是说这个方程只有一个变量r
由于o = getPrime(11),它是一个11bit的素数,其范围在 [ 2 10 , 2 11 − 1 ] [2^{10},2^{11}-1] [210,2111],可以使用爆破的方法来找到合适的o

爆破素数o,然后计算出方程的解,也就是r。遍历每一个方程的解(解出的方程可能不止一个解),然后普通RSA解密,判断其明文是否包含flag{字符串,包含的话,此时的o即为所求。

正向爆破代码:

#sage
#find o,r,z
Flag = False
for o in trange(2**10+1,2**11,1):if is_prime(o):P.<r> = PolynomialRing(GF(p))z = inverse_mod(o*233,p)*(h2 - o^13 - r^12 -3*o*r)f = (13 * o + 14 * r + r * z + o * z ** 13) - h1result = f.roots()if result!=[]:for r in result:try:d1 = gmpy2.invert(o,p-1)find_m = pow(int(r[0]),d1,p)find_flag = long_to_bytes(int(find_m))if b'flag{' in find_flag:print(f'o = {o}')Flag=Truebreakexcept:passif Flag==True:break

爆破时间约为40分钟,🐏慢,慢得流脓!
在这里插入图片描述

逆向爆破代码:

#sage
#find o,r,z
Flag = False
for o in trange(2**11-1,2**10,-1):if is_prime(o):P.<r> = PolynomialRing(GF(p))z = inverse_mod(o*233,p)*(h2 - o^13 - r^12 -3*o*r)f = (13 * o + 14 * r + r * z + o * z ** 13) - h1result = f.roots()if result!=[]:for r in result:try:d1 = gmpy2.invert(o,p-1)find_m = pow(int(r[0]),d1,p)find_flag = long_to_bytes(int(find_m))if b'flag{' in find_flag:print(f'o = {o}')Flag=Truebreakexcept:passif Flag==True:break

逆向爆破,因为o=1949靠近 2 11 − 1 2^{11}-1 2111,所以花费时间比较短,大概5分钟左右。
PS:至于为什么要写逆向爆破代码,主要是因为从头爆破起太慢了。而笔者一个很懒的人,懒得等。
在这里插入图片描述

最后将o=1949带入,求解出r,再把r带入解出z,分别RSA解密即可得到flag1flag2,然后把flag1、flag2、flag3拼接起来即可得到最终的flag

#sage
from  Crypto.Util.number import *
import gmpy2
from tqdm import *
n = 10850335281775104384842309756387507121367947910896225110655535291748404338588972388693259827067445607230128971155491201985083085890729703137967791325100758142692285049056390126354246953310462082980059949946896088251642305978444680455930662301007461492978866538439458231120357274252592800042668860820459885960472737650446805378098344941597805604577797736381125259746781740429143953876454912647201590679786164678547559344304709889497251430904453036692562053570137262921657887410908992378188055660327282373869435308218926170927366572909858720457530661616332620263301130036238239402855045548920085800254012799063199438351
h1 = 68971374440570454964336249870184699116849273092766598492393855724166755705038579719086135125490382149633066088736614770735555426661202444613481222308690955829177344713094803125405000495549811601138114210065623933916822257443366983845366477473811412048210602195672314631662681949260715610527325398006214477393
h2 = 89557070262276493140173989636483552685176823962865601733383032051273942127575151309428084885522955047935745792156087951603894535351765100905696886714983834431355512680521411571740092935206188975497781396247799052916245218545834226095135276633422884113241438747017792108934964361391672183324214279475682695463
h3 = 1311626365146856567785446974305480952394390450877042514912868019585929680223703697129400820765966547191027907141852232429577556122050933660875292235305985538892538821817570539411355339774474418018682334787217004485252794403892893871864009361554731318803763221581009731474777526380398647174787569510518293833348676730943915073911916070766302422834190969513630361764429111809259665372926096307389623440860840605142551951919723403665762066543095024186705959708920942727754417048332722263643582752118944418881587666520088786189326167958303315156763867706697503512512849397447463575294489956813935149823414834222869976238
e = 65537#get flag3 and p
p_near = gmpy2.iroot(n,2)[0]
while n%p_near!=0:p_near = gmpy2.next_prime(p_near)
p = p_near
q = n//p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m3 = pow(h3,d,n)
flag3 = long_to_bytes(int(m3))o = 1949
P.<r> = PolynomialRing(GF(p))
z = inverse_mod(o*233,p)*(h2 - o^13 - r^12 -3*o*r)
f = (13 * o + 14 * r + r * z + o * z ** 13) - h1
r = f.roots()[0][0]
z = inverse_mod(o*233,p)*(h2 - o^13 - r^12 -3*o*r)d = gmpy2.invert(o,p-1)
#get flag1
m = pow(r,d,p)
flag1 = long_to_bytes(int(m))
#get flag2
m2 = pow(z,d,p)
flag2 = long_to_bytes(int(m2))print(flag1+flag2+flag3)

flag:

flag{c8f3ad650e7075488801e0e4cb91a4ba}

【许多今日之心心念念,无非是来年之付诸一笑。】


http://www.ppmy.cn/news/350485.html

相关文章

UPnP实现中的常见脆弱性与风险分析

UPnP 协议栈的脆弱性 与风险分析 由于 UPnP 协议栈包含的协议较多&#xff0c;在实现过程中&#xff0c;容易存在脆弱性。而在 UPnP 工作流程的六个 阶段中&#xff0c;发现、描述、控制三个阶段出现过比较严重的脆弱性问题。这些脆弱性广泛存在于支持 UPnP 技术的物联网 设备…

UPNP自动端口映射的实现与路由器UPNP相关资料

UPNP的全称是 Universal plug-and-play( 通用即插即用).UPnP 是针对智能家电、无线设备以及各种外观尺寸的个人电脑的普遍对等&#xff08;peer-to-peer&#xff09;网络连接而设计的一种架构。它旨在为家庭、小型企业、公共场 所中或连接到互联网的ad-hoc 网或未管理网络提供易…

显示upnp服务器 sonos,四步解决UPNP功能被阻塞的问题

6. ESET NOD32 安全套装/EAV的下载杀毒参数(如迅雷的下载后扫描,虽然感觉没必要,但还是写出来啦) ESET NOD32安全套装、EAV是用“ecls.exe”来进行下载后杀毒的,在迅雷下载软件中添加“ecls.exe” 例如: ESET NOD32安全套装:“C:\Program Files\ESET\ESET Smart Security\…

UPNP编程

零、SDK的安装 upnp的概念就不理会了&#xff0c;网上很多&#xff0c;这里偏向于具体编程。 SDK使用upnp1.6.17版本&#xff0c;这是一个linux下的开源版本&#xff0c;目前仍然在维护&#xff0c;下载地址&#xff1a; http://pupnp.sourceforge.net/ 安装SDK相对比较简单&am…

QQ相册加密?!

从今 年很黄很暴力的艳照门不难看出 对照片的隐私的保存是多么重要 QQ相册是很多朋友存放照片的地方,不想给陌生人看的照片加个密,或者干脆在空间里设置个密码,但是这真的安全么? 在没有密码的情况下 我们很难进入对方的QQ空间,虽然TX的漏洞不断,但是总是能及时补上 可是...…

直流充电桩产品主控模块软硬件源码资料/支持以太网

直流充电桩产品主控模块软硬件源码资料/支持以太网/刷卡等功能 直流充电桩产品硬件控制源码/支持以太网&#xff0c; 重要提醒 &#xff1a;原理 图和源码不对应&#xff0c;原理图PCB为单枪&#xff0c;源码为双枪&#xff0c;使用STM32主控&#xff0c;只有充电控制器不包含整…

iPhone X 不充电维修案例

送修一台iPhone X &#xff0c;故障描述是手机用着用着没电了&#xff0c;关机了&#xff0c;却怎么充电也充不进。不充电&#xff0c;问题应该不麻烦&#xff0c;用充电器试充了一下&#xff0c;关机状态插充电器没发现有任何反应&#xff0c;是不是电池完全耗光了&#xff1f…

手机QQ怎样破解闪照

手机QQ怎样破解闪照 我们先讲方法一&#xff1a; 第一步&#xff0c;找到你的手机U盘&#xff0c;打开tencent. 第二步&#xff0c;找到mobileQQ&#xff0c;打开 第三步&#xff0c;打开之后会有diskcache,打开~ 第四步&#xff0c;你会发现有好多的文件&#xff0c;这时你就…