引言

今天的红帽杯，集体摸鱼我是没想到的
第一道 crypto 本质上是一个格密码问题（求助别人）
第二道是椭圆曲线加密（直接放弃）

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

最后一个有点像 RSA 加密最后一步
没什么思路，就去找 wp 了
原来是一道离散对数题

对于没学过群论的我来说，一些概念需要补充
群的阶：
参考知乎文章
首先是群元素的阶：

下面是两个例子：

循环群的阶（在加密中一般都考虑循环群）就是指：

而什么是循环群？举一个例子就是整数模 n ，容易发现在模 n 的情况下 1 和 n+1 是相等的，就像循环一样
光滑数：
参考 wiki

讲的很明白了

然而上面两个概念这道题不需要知道
ctfwiki 提供了暴力破解的方法：

from Crypto.Util.number import *

m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
n = pow(2, 512)

def bsgs(g, y, p):
    m = int(pow(p - 1, 1/2))
    S = {pow(g, j, p): j for j in range(m)}
    gs = pow(g, p - 1 - m, p)
    for i in range(m):
        if y in S:
            return i * m + S[y]
        y = y * gs % p
    return None
flag = bsgs(m, c, n)
print(long_to_bytes((flag)))

然而跑了几分钟没有反应
如 wp 所述，建议用 sympy 库求解：

from Crypto.Util.number import *
import sympy

m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
n = 2 ** 512

flag = sympy.discrete_log(2**512,c,m)
print(long_to_bytes(flag))

结果为：flag{5f95ca93-1594-762d-ed0b-a9139692cb4a}

结语

嘛，还差得远呢
希望继续坚持