Crypto-you raise me up(Write up)

题目信息

技术要点

• 数学中离散对数知识的理解和应用

• 运用python将得到的字符串进行转换得到flag

解题思路

• 打开题目附件，能够得到一个python程序如下：

#!/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(离散对数问题)，因此只要求出最终的m值即可找到对应的flag信息。
发现题中的n = 2 ** 512， 所以phi(n) = 2 ** 511；即本题模数的欧拉函数具有smooth的性质，即其是由很多小素数乘积而来，所以可用Pohlig Hellman 算法来解决这个DLP，sage的discrete_log用的方法就包括Pohlig Hellman算法：

m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
n = 2 ** 512
m = Mod(m,n)
c = Mod(c,n)
discrete_log(c,m)

得到结果之后进行数字转字符串即可得到最终的flag信息

import libnum
d = 56006392793405651552924479293096841126763872290794186417054288110043102953612574215902230811593957757
print(libnum.n2s(d))

Flag

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

总结

• 经典离散对数问题的定义例如，对于n=7，Z/7Z是由3k构成的循环群，阶数是φ(7)=7−1=6，下面的每步推导都用到了上一步的模等结果，其中3是模7的原根(Primitive root)：

• 欧拉函数φ(n)表示1到n之间和n互素的整数的个数([15.d])，特别是对于素数p来说，φ(p)=p−1。

• 小于n且与n互素的集合是G={1,....,Pφ(n)}，例如当n=7，G={1,2,3,4,5,6}。

• 集合{… , a − 2n, a − n, a, a + n, a + 2n, …}构成了a对n的同余类(Congruence class, [15.c])

• G的元素对n的同余类全体构成了一个新的集合M，把M记做：Z/nZ。

• Z/nZ是一个阿贝尓群，直接从阿贝尓群的四个性质入手证明。

• Z/nZ是一个循环群，当且仅当n=1,2,4,pk或者2pk(k>0)

• p是一个素数,Z/pZ构成了一个循环群，生成元是g。

• 任意取一个整数k，gk属于Z/pZ，计算a=gk(mod p)，容易知道a也属于Z/pZ。

• 反之，已知a，要计算k=log(a)，称之为离散对数问题。

• 计算a=gk是容易的。

• 计算k=log(a)是困难的。

• 计算DLP问题的经典算法

#计算DLP的通用方法
discrete_log(y,g)==x
#n为合数（Pohlig-Hellman）
x = discrete_log(mod(b,n),mod(a,n))
#n为质数或质数幂（线性筛Index Calculus）
R = Integers(99)
a = R(4)
b = a^9
b.log(a)
#或
x = int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))"))
x = gp.znlog(b, gp.Mod(a, n))

#计算离散对数的lambda方法
discrete_log_lambda(y,g,(floor(ZZ(x)/2),2*ZZ(x)))==x

#小步大步法计算DLP
bsgs(g,y,(floor(ZZ(x)/2),2*ZZ(x)))==x

#GF(p)下计算DLP
F = GF(p)
ax = F(b + (a - 1) * A) / F(a * s - s + b)
x = discrete_log(F(ax), F(a))

• 纯粹数学，就其本质而言，是逻辑思想的诗篇。 👍💡