[NepCTF2022]中学数学
中学数学
p、q挣扎很久没分解出来,wp出来了赶紧复现试试。
题目
from gmpy2 import *
from Crypto.Util.number import *
from secret import flag
p=getPrime(1024)
q=next_prime(p+(p>>500)) #p>>500=(1/2^500)p
e=0x10001
n=p*q
c=pow(bytes_to_long(flag),e,n)
print("n=",n)
print("c=",c)
'''
n= 13776679754786305830793674359562910178503525293501875259698297791987196248336062506951151345232816992904634767521007443634017633687862289928715870204388479258679577315915061740028494078672493226329115247979108035669870651598111762906959057540508657823948600824548819666985698501483261504641066030188603032714383272686110228221709062681957025702835354151145335986966796484545336983392388743498515384930244837403932600464428196236533563039992819408281355416477094656741439388971695931526610641826910750926961557362454734732247864647404836037293509009829775634926600458845832805085222154851310850740227722601054242115507
c= 6253975396639688013947622483271226838902346034187241970785550830715516801386404802832796746428068354515287579293520381463797045055114065533348514688044281004266071342722261719304097175009672596062130939189624163728328429608123325223000160428261082507446604698345173189268359115612698883860396660563679801383563588818099088505120717238037463747828729693649297904035253985982099474025883550074375828799938384533606092448272306356003096283602697757642323962299153853559914553690456801745940925602411053578841756504799815771173679267389055390097241148454899265156705442028845650177138185876173539754631720573266723359186
'''
分析
出题人:“无脑爆破不够优雅”
这题关键就是把p和q分解出来,那我们就来优雅一下,缩小范围再爆破。
其中q=next_prime(p+(p>>500))指的是:\(q=[p+\frac{1}{2^{500}}p]+r\)
即:\(q=[(1+\frac{1}{2^{500}})p]+r\)
其中这个r是个为了凑到满足q为素数的最小整数。
则n为:\(n=p*q=[(1+\frac{1}{2^{500}})p^2]+rp\)
凑个平方。
得:\(\color {blue}{[(1+\frac{1}{2^{500}})n]}\color {black}{=[(1+\frac{1}{2^{500}})p]^2+(1+\frac{1}{2^{500}})rp}>\color {red} {[(1+\frac{1}{2^{500}})p]^2}\)
因为
\([(1+\frac{1}{2^{500}})n]=[(1+\frac{1}{2^{500}})p]^2+(1+\frac{1}{2^{500}})rp\) ------1式
\(q^2=[(1+\frac{1}{2^{500}})p+r]^2=[(1+\frac{1}{2^{500}})p]^2+[(1+\frac{1}{2^{500}})rp]+[(1+\frac{1}{2^{500}})rp]+r^2\) ------2式
显然2式大于1式。
因此,经过比较我们可以得到:
\([(1+\frac{1}{2^{500}})p]^2<[(1+\frac{1}{2^{500}})n]<[(1+\frac{1}{2^{500}})p+r]^2\)
这样一来,我们就可以通过开方进而缩小范围解出q:
\((1+\frac{1}{2^{500}})p<\sqrt{(1+\frac{1}{2^{500}})n}<(1+\frac{1}{2^{500}})p+r=q\)
由此,\(\sqrt{(1+\frac{1}{2^{2000}})n}\)的下一位质数即为q:
q = next_prime(iroot((n + (n >> 2000)), 2)[0])
但注意到next_prime算法的本质逻辑即是通过不断枚举奇数判断是否为素数,而这里n的分解保证了其必为素数,再判断素数的话属于是多此一举(浪费计算资源),所以我们可以根据素数分布公式或next_prime的方案向下枚举,得到唯一分解即可。
import gmpy2
from gmpy2 import *
from Crypto.Util.number import *
n = 13776679754786305830793674359562910178503525293501875259698297791987196248336062506951151345232816992904634767521007443634017633687862289928715870204388479258679577315915061740028494078672493226329115247979108035669870651598111762906959057540508657823948600824548819666985698501483261504641066030188603032714383272686110228221709062681957025702835354151145335986966796484545336983392388743498515384930244837403932600464428196236533563039992819408281355416477094656741439388971695931526610641826910750926961557362454734732247864647404836037293509009829775634926600458845832805085222154851310850740227722601054242115507
e = 0x10001
c = 6253975396639688013947622483271226838902346034187241970785550830715516801386404802832796746428068354515287579293520381463797045055114065533348514688044281004266071342722261719304097175009672596062130939189624163728328429608123325223000160428261082507446604698345173189268359115612698883860396660563679801383563588818099088505120717238037463747828729693649297904035253985982099474025883550074375828799938384533606092448272306356003096283602697757642323962299153853559914553690456801745940925602411053578841756504799815771173679267389055390097241148454899265156705442028845650177138185876173539754631720573266723359186
q = next_prime(iroot((n + (n >> 500)), 2)[0]) #优雅,太优雅了
p = int(n // q) #求出q就常规做题了
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
flag{never_ignore_basic_math}
总结
新手上路,当时没看懂next_prime(p+(p>>500))
尝试拿yafu暴力分解n,发现40分钟起步(。)
看了wp之后,才发现这道题还真就中学数学了…就像flag所说的一样,永远不要忽视基础数学。
最新文章
- 读书笔记--SQL必知必会22--高级SQL特性
- [LeetCode] Flatten 2D Vector 压平二维向量
- Java EE之一个表单两个按钮响应不同界面(登录与注册)
- 使用Ajax异步加载页面时,怎样调试该页面的Js
- C# Windows service 开发笔录
- scp不可用:WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED
- C# 有关命名法
- 【转】下载量最高的 100 个 Laravel 扩展包推荐
- php获取本周和上周的开始日期和结束日期
- jQuery图片无缝轮播插件;
- ms_sql:drop and create a job
- BI 多维立方体CUBE
- Perl 面向对象编程的两种实现和比较:
- 连载:面向对象葵花宝典:思想、技巧与实践(28) - 设计原则:内聚&;amp;耦合
- jquery:ajax不接收返回值回
- 【Direct2D开发】 通过操作像素实现纹理混合
- vue-cli脚手架npm相关文件解读(6)build.js
- 机器学习 F1-Score 精确率 - P 准确率 -Acc 召回率 - R
- IIS Express 域认证问题(https://stackoverflow.com/questions/4762538/iis-express-windows-authentication)
- SQL Server 2008 R2 根据WSDL访问WebService