you_raise_me_up

发表于 | 阅读次数:

第二篇CTF密码笔记，拖了好久QAQ~
题目来源：2020年网鼎杯青龙组crypto 1

Quick Start

题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
import random

n = 2 ** 512
m = random.randint(2, n-1) | 1
c = pow(m, bytes_to_long(flag), n)
print 'm = ' + str(m)
print 'c = ' + str(c)

# m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
# c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499

题目已知n,m,c,求flag。
关键代码c = pow(m, bytes_to_long(flag), n),指m^flag ≡ c (mod n)
一开始以为是RSA加密，后来看到dalao的wp才知道这个用的是离散对数，即求：
对 a^x ≡ b(mod m) 求解 x

在python中的sympy库，有函数discrete_log(),可以快速求解离散对数，如：

其中,discrete_log(n,c,m),函数内依次为模值，余数，底数。对于本题：

1
2
3
4
5
6
from sympy.ntheory import discrete_log
n = 2**512
m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
flag = discrete_log(n,c,m)
print(hex(flag)) #十六进制

得到十六进制的结果为
0x666c61677b35663935636139332d313539342d373632642d656430622d6139313339363932
636234617d
然后十六进制字符转换，得到flag：flag{5f95ca93-1594-762d-ed0b-a9139692cb4a}