[网鼎杯2020]you_raise_me_up
2024-09-18 16:53:23
[网鼎杯2020]you_raise_me_up
题目
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
import random
n = 2 ** 512
m = random.randint(2, n-1) | 1 #返回2到n-1之间的任意整数
c = pow(m, bytes_to_long(flag), n)
print 'm = ' + str(m)
print 'c = ' + str(c)
# m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
# c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
分析
首先我们可以得到:$$c=m^{flag}mod,n$$
想要求出flag就要清楚:这是一道求离散对数的问题。
首先我们需要知道什么是离散对数:
\[a^x≡b(mod\,m)
\]已知a,b,m,求解x
可见这是一道非常标准的离散对数问题求解。
已知:$$c=m^{flag}mod,n$$ 和c,m,n的值。
求离散对数:
\[flag=log_{m\,mod\,n}(c\,mod\,n)
\]
\]
因为c是余数,所以:$$flag=log_{m,mod,n}c$$
解法一:sage
sage已经不陌生了,毕竟上次做一道羊城杯的题目用到了。
sage中的discrete_log()可以帮我们计算集散对数:
discrete_log()使用示例
由此编写脚本:
m=391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
n=2**512
c=6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
flag= discrete_log((mod(c,n)), (mod(m,n)))
print(flag)
得到flag值之后再进行一个转:
from Crypto.Util.number import *
flag=56006392793405651552924479293096841126763872290794186417054288110043102953612574215902230811593957757
print(long_to_bytes(flag))
#b'flag{5f95ca93-1594-762d-ed0b-a9139692cb4a}'
补充
sage中求解离散对数有四个比较常用的函数:
(1)discrete_log:通用的求离散对数的方法:discrete_log(a,base,ord,operation)
(2)discrete_log_rho:求离散对数的Pollard-Rho算法:discrete_log_rho(a,base,ord,operation)
(3)discrete_log_lambda:求离散对数的Pollard-kangaroo算法(也称为lambda算法):discrete_log_lambda(a,base,bounds,operation)
(4)bsgs:小步大步法:bsgs(base,a,bounds,operation)
在线运行sage脚本:https://sagecell.sagemath.org/
解法二:python
求解离散对数问题可以用到python的sympy库中的discrete_log()函数。
discrete_log()使用示例
from sympy.ntheory import discrete_log
discrete_log(41, 15, 7)
写脚本:
from Crypto.Util.number import *
from sympy.ntheory import discrete_log
n = 2**512
m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
flag= discrete_log(n,c,m)
print(long_to_bytes(flag))
#b'flag{5f95ca93-1594-762d-ed0b-a9139692cb4a}'
总结
考查离散对数的概念以及求解离散对数。
最新文章
- doc2vec使用说明(二)gensim工具包 LabeledSentence
- windows update一直卡住:“正在此计算机上搜索更新”
- ListView.post(Runnable {})和ListView.postDelayed
- libZPlay 音频编码解码器库
- my sql中join的操作
- 【BZOJ-4289】Tax 最短路 + 技巧建图
- 没人告诉你关于z-index的一些事
- 在Linux系统中如何装rpm,deb,tar.gz,tar.bz2,apt,bin 格式的文件
- noj [1482] 嘛~付钱吧!(完全背包)
- 关于win8.1“连接被远程计算机关闭”的一种解决方案
- Azure IoT Hub和Event Hub相关的技术系列-索引篇
- [转载] java多线程学习-java.util.concurrent详解(四) BlockingQueue
- UML之包图
- Oracle中计算两个日期时间的差
- 高并发编程基础Synchronized与Volatile
- LiveCharts文档-3开始-4可用的图表
- kubernetes控制器之DaemonSet
- [No0000128]SQL纵表与横表互转
- hashable/iterable与orderable
- css 兼容ie8 rgba()用法
热门文章
- python + mysql +djagno +unittest 实现WEB、APP UI自动化测试平台--------(一)基础表
- 有关WCH的CH42x以及CH45x选型,常见问题处理方法
- C语言两结构体之间的成员互换
- 我的基于 JamStack 的新博客
- NW js 打包入门教程
- [cocos2d-x]关于3.x的触摸机制
- 【译】15 个有用的 JavaScript 技巧
- Redis之key的淘汰策略
- 【模板】网络最大流 Dinic(多路增广+当前弧优化)
- 分布式事务 | 使用 dotnetcore/CAP 的本地消息表模式