you_raise_me_up

点击此处获得更好的阅读体验


题目考点

  • 离散对数

解题思路

1
2
3
4
5
6
7
8
9
10
11
#!/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

题中我们的flag在m的指数位置,所以这题是解一个DLP(离散对数问题)

发现题中的n = 2 ** 512, 所以phi(n) = 2 ** 511;即本题模数的欧拉函数具有smooth的性质,即其是由很多小素数乘积而来,所以可用Pohlig Hellman 算法来解决这个DLP,sage的discrete_log用的方法就包括Pohlig Hellman算法,exp:

1
2
3
4
5
6
m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
n = 2 ** 512
m = Mod(m,n)
c = Mod(c,n)
discrete_log(c,m)

得到结果之后数字转字符串即可

1
2
3
import libnum
d = 56006392793405651552924479293096841126763872290794186417054288110043102953612574215902230811593957757
print(libnum.n2s(d))

Flag

1
flag{5f95ca93-1594-762d-ed0b-a9139692cb4a}