buu [网鼎杯 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
c = pow(m, bytes_to_long(flag), n)
print 'm = ' + str(m)
print 'c = ' + str(c)
 
# m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
# c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499

首先，我们审计题目，可以发现题目中给予了我们m、c和n的值，其中n=2**512,m则是在（2，m）之间的值，c是m^flag = c mod n:

可以看出，这是一道求指标的题目，我们可以通过以下方法进行计算，已知的条件为：

2^e = c1 mod n   在这其中，除了e其余条件我们都已知，在这里，我们需要使用离散对数求解的思路：

Shanks’s Babystep-Giantstep Algorithm算法：
1、n=[ √n ]+1

2、构造两个列表

  list1=[1,g,g^2,g^3,......,g^n]

  list2=[h,hg^(-n),hg^(-2n),......,hg^(-n**2)]

3、在两个列表中，找到两个相同的数 g^i=hg^(-jn)

=>g^(i+jn)=h mod n

4、我们所求的e=i+jn
python库应用：

python(sympy库)  x=sympy.discrete_log(n,a,g)

exp：

m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
n=2**512
 
 
import gmpy2
from Crypto.Util.number import *
import sympy
x=sympy.discrete_log(n,c,m)
print(long_to_bytes(x))

 得到：

b'flag{5f95ca93-1594-762d-ed0b-a9139692cb4a}'