糖醋小鸡块的blog
0%

Crypto趣题-DLP

发表于 更新于 分类于 Valine：

该文章主要记录一些离散对数相关的趣题

LCG_getn

题目来源：暂不明确

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
from random import *

flag=b"xxx"

p = 54652877966498174351366784061030941540826109780679767812638885938702023311073348172671269559746951554247092305850067866703779230619519047541036253311250412466443049505699771781919268578313412843196495008809132067113297376693264085286413313110640544744871885363521805202464017885850100288070851518716948912763
a = randint(1, p)
b = randint(1, p)
s = randint(1, p)
n = bytes_to_long(flag)
w=s

for i in range(n):
    w=(a*w+b)%p

print("w =", w)
print("a =", a)
print("b =", b)
print("s =", s)

# w = 45260711485867413779000039767671034310702875593332662748555320224906545365554170110949539036859843730784214686503912104285690508613273585625200010294558934989365549837830937722020828604189890519693227340880703315693705242316707543693923876818002374458929661657478657015556029058691793765311471853536999728095
# a = 48971444119769808567235868690448906239564969042250773366602052091584947357482111194551805793917339304979214302903321173854777686459558987828324146105464727334291096913040974329068646352169555875473254644341551758096967146463887075885459513015418793985654070835966250474489149215017332659976431908899883075451
# b = 41431597971174895116159534256023499341950550092310958530514478990317523065020737452786308814902366495344759036892471030280016939718362179920001980632686064327381708613306810839684102705939569434751140239433742455076828057785026744706949885961770693799072605278910197649006648865172715746263760943017995064476
# s = 40591085096279567372215447069043586704185332353065048038060554508569817563633133729571174498948047412713943422549121053099203747227568766567100905468380508721248880476131212092521246665670757585737204962567688062946799557019445118729948361267403108325647850072311709196263096458304871305953385062547211896996

题目基于LCG，给定了这个LCG的所有参数a、b、p，并且给定LCG的种子s以及LCG计算n次后得到的结果w，要求解出n作为flag。

那么第一个做法是把LCG迭代的过程写成展开的形式，令：

所以有：

因此就得到：

而可以发现，后面这个其实是一个以a为公比的等比数列求和，所以用求和公式又可以把式子写成如下形式：

然后移项就有：

即：

然后代入我们已知的值s和w，就可以求出a^n了，然后发现p-1光滑，所以直接求DLP就能得到n。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *

p = 54652877966498174351366784061030941540826109780679767812638885938702023311073348172671269559746951554247092305850067866703779230619519047541036253311250412466443049505699771781919268578313412843196495008809132067113297376693264085286413313110640544744871885363521805202464017885850100288070851518716948912763
w = 45260711485867413779000039767671034310702875593332662748555320224906545365554170110949539036859843730784214686503912104285690508613273585625200010294558934989365549837830937722020828604189890519693227340880703315693705242316707543693923876818002374458929661657478657015556029058691793765311471853536999728095
a = 48971444119769808567235868690448906239564969042250773366602052091584947357482111194551805793917339304979214302903321173854777686459558987828324146105464727334291096913040974329068646352169555875473254644341551758096967146463887075885459513015418793985654070835966250474489149215017332659976431908899883075451
b = 41431597971174895116159534256023499341950550092310958530514478990317523065020737452786308814902366495344759036892471030280016939718362179920001980632686064327381708613306810839684102705939569434751140239433742455076828057785026744706949885961770693799072605278910197649006648865172715746263760943017995064476
s = 40591085096279567372215447069043586704185332353065048038060554508569817563633133729571174498948047412713943422549121053099203747227568766567100905468380508721248880476131212092521246665670757585737204962567688062946799557019445118729948361267403108325647850072311709196263096458304871305953385062547211896996

k = b*inverse(1-a,p)
an = (w - k)*inverse(s-k,p)
n = discrete_log(mod(an,p),mod(a,p))
print(long_to_bytes(int(n)))

#flag{lcg_th1s_an_iterater_4unction!!}

然后我还有另外一个思路，这是基于之前尝试完成2022广东强网杯的dangerousRSA的想法，那就是对于这种线性递推的关系式，用矩阵来表示一般是比较简明的。比如LCG的单次递推过程就可以表示成：

所以n次递推自然也就可以写成：

代入本题的数据就有：

所以如果可以根据s和w的向量求出这个n次矩阵的话，就可以用矩阵DLP解出n。但是这样表示向量的话是解不出这个n次矩阵的，但是目前我还没有想到能如何表示，但感觉这个思路应该可行所以写在这里，如果有师傅想到了欢迎随时告诉我。



111

题目来源：暂不明确

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
c = pow(m, e, n)
print("n = %s" % str(n))
print("c = %s" % str(c))

g = 23
G = 11
x = 403638639297424424030427248437292930901426348835802538164151760802964623822045794500939051975836868693929980721020252046582234954683741983106400414344716052437631852316722239725845579202592686299335379402696402426374492134051721258686792647746078809606686805108337953402269205238590881513586553277287068954382
y = 2788042276518515357450960102700140012515982479659057104181173132696595727177169896340844620440016059927182507197941000790257318837349294378321194646380886927861234824905576296807661416166077156207249648372928455517246584917020679149653861285226961170842021388854323284132579306053835679130563246044941718724356142
assert pow(g, pow(G, x), n)==pow(g, pow(G, y), n)

# n = 97556864962789127824701383242111068245641430412088446049554987171631796271268013457675328750740703181455093780021347024032292309660522866063731237500797701206940725352099428514342659100771939441946971272319151463476877708240447532346101326328206390117414020245045680514443093718216781806739876823259237682041
# c = 97506619181657974835472296128714598728435343734591865967781506389027493446492338931895061849567882930303570448811849167940548090710640607320028639112831504753106905840969732206394654206682020482058950978096138227623007427344924113713884121137383236661810418984400003458312561214376484805408760046782907944992

题目内容很简单，给定x、y，满足：

其中n是RSA公钥，题目用e=65537和n加密flag得到密文，要求还原明文。因此我们要做的就是根据x、y的关系式来得到n的分解从而解密RSA。

首先摘掉第一层指数：

然后摘掉第二层指数：

至于为什么两层分别是23、11，我思考了一下觉得应该没什么特别的意义，应该就是分别取了两个原根。

那么对于摘掉第一层指数的结果，因为有：

所以如果我们可以计算出11^x-11^y，就可以直接求e关于kphin的逆元从而解密密文。但是x、y太大了，不进行模运算的话，没有办法计算幂次。因此主要还是要想办法从摘掉第二层指数的结果入手。

因为有：

所以：

而我们的目的是找到phin或者phin的倍数，又已知phin等于：

为了得到phi(phi(n))的表示结果，我们把phin展开为标准素数分解的形式：

那么phi(phi(n))就应该等于：

而现在我们有x、y，就可以计算y-x得到k倍的phi(phi(n))的值，然后可以去factordb上查他的分解：

image-20231114152241975

其中最后那个大数是一个无法进一步分解出因子的合数。而现在，我们是期望通过y-x的因子分解，去找到形如下面这样的素因子幂次：

然后就可以通过这些素因子幂次还原phin。但是实际上，基本没有能直接判别的素因子幂次。因此可以认为phi(phi(n))的因子分解应该是如下形式：

以上的分析都是没有仔细考虑2这个因子的，现在我们把2加入进来细化一下思考。首先由于p-1和q-1都是偶数，所以phin就至少含有2^2，且现在我们认为phin的分解中没有素数幂次：

更进一步来说，phi(phi(n))的因子分解为：

显然，后面的pi-1也都是偶数，所以可以至少提出一个2，进一步写为：

而事实上，我们factordb分解出的结果只含有2^5，所以可以认为phin中除了2以外，最多只有4个其他素因子。而我们的目的就是把这四个素因子全部找到。

怎么找呢？毕竟我们现在只拥有y-x，也就是k倍的phi(phi(n))的因子分解结果：

image-20231114152241975

他其实等价于：

那我们可以这样考虑：我们设一个乘积结果t，其初值为1，然后我们遍历factordb分解出的因子的所有可能乘积并对乘积+1，如果说这个结果是素数的话，那么它就有可能是phin的一个素因子，我们就把他乘到t中去。这样得到的t按理来说会包含phin的所有素因子，所以他应该满足：

那么我们求e关于t的逆元d，这个d满足下式：

对于RSA解密而言正确性如下：

所以这个d也可以用于RSA解密。

但是事实上这样解密得不到正确结果。我认为问题是出在y-x的最后一个合数因子没有被完全分解，所以会对phin的可能素因子有遗漏。

然后我就在想，如果不能完全覆盖phin的素因子，有没有可能能覆盖到p-1或q-1其中一个的全部素因子？这样我们可以用如下方式来分解n，因为：

所以：

但事实上这样也不行。但是如果能够获得y-x的完整的分解的话，上面的两个方法应该都能做出来，exp如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from Crypto.Util.number import *
from tqdm import *
from gmpy2 import powmod
from factordb.factordb import FactorDB

e = 65537
g = 23
G = 11
x = 403638639297424424030427248437292930901426348835802538164151760802964623822045794500939051975836868693929980721020252046582234954683741983106400414344716052437631852316722239725845579202592686299335379402696402426374492134051721258686792647746078809606686805108337953402269205238590881513586553277287068954382
y = 2788042276518515357450960102700140012515982479659057104181173132696595727177169896340844620440016059927182507197941000790257318837349294378321194646380886927861234824905576296807661416166077156207249648372928455517246584917020679149653861285226961170842021388854323284132579306053835679130563246044941718724356142

n = 97556864962789127824701383242111068245641430412088446049554987171631796271268013457675328750740703181455093780021347024032292309660522866063731237500797701206940725352099428514342659100771939441946971272319151463476877708240447532346101326328206390117414020245045680514443093718216781806739876823259237682041
c = 97506619181657974835472296128714598728435343734591865967781506389027493446492338931895061849567882930303570448811849167940548090710640607320028639112831504753106905840969732206394654206682020482058950978096138227623007427344924113713884121137383236661810418984400003458312561214376484805408760046782907944992

f = FactorDB(y-x)
f.connect()
fs = f.get_factor_list()
print(fs)

t = 1
for i in trange(2**len(fs)):
    prime = 1
    binlist = bin(i)[2:].zfill(len(fs))
    choice = [int(j) for j in binlist]
    for j in range(len(fs)):
        if(choice[j] == 1):
            prime *= fs[j]
    prime += 1
    if(isPrime(prime)):
        t *= prime

#try to factor p
temp = powmod(2,2**10*t,n)-2
print(GCD(temp,n))

#try to get kphi(n)
d = inverse(e, 2**10*t)
print(long_to_bytes(powmod(c,d,n)))

然后我就在思考一个问题：题目中的p、q真的是简单的用getPrime生成的吗？之所以有这个怀疑是基于以下两个原因：

  • 本身这个脚本就执行不了，因为x和y作为指数部分太大了。出题人跑出数据肯定是用的其他脚本。

  • 出题人能给出x和y的值，就说明出题人不仅能够获得phi(n)的值，还需要知道phi(phi(n))的值。但这好像并不是随随便便取p、q都能实现的，因为无法保证p-1和q-1能分解出所有因数，就无法求解phi((p-1)*(q-1))。

所以，p和q应该是特殊结构的素数，这个特殊结构应该要能保证p-1和q-1能分解出所有因数，从而计算出phi((p-1)*(q-1))，进一步才能给出x和y的值。

到这一步，最容易想到的特殊结构就是p-1光滑型的素数，他符合我们的基本要求：p-1的所有因数都较小，因此很容易求出p-1和q-1的完整分解，进一步求解phi((p-1)*(q-1))。但是这与题目的实际情况又有一点不符——kphiphin出现了无法分解的大因子，这对于p-1光滑型的素数是不可能的。

于是就继续想，p还可能是什么样的素数能够符合题目要求，然后我就想到了下面结构的素数：

这也是很多时候取安全素数会用到的产生方式。而这个素数也完美符合要求：p-1易求欧拉函数，这是因为：

那么我们就顺着这个思路继续往下，假设：

就有：

同时，我们有：

由于y-x=kphiphin，并且phiphin的数量级应该与n近似，因此我们可以爆破k，就可以得到phiphin，得到phiphin后，为了得到n的分解p和q，我们就联立如下的两个式子解方程：

事实上p0和q0确实可以求出来，但是并不需要，因为注意到：

所以：

直接用3phin解密即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from Crypto.Util.number import *
from tqdm import *
from gmpy2 import invert,powmod

e = 65537
g = 23
G = 11
x = 403638639297424424030427248437292930901426348835802538164151760802964623822045794500939051975836868693929980721020252046582234954683741983106400414344716052437631852316722239725845579202592686299335379402696402426374492134051721258686792647746078809606686805108337953402269205238590881513586553277287068954382
y = 2788042276518515357450960102700140012515982479659057104181173132696595727177169896340844620440016059927182507197941000790257318837349294378321194646380886927861234824905576296807661416166077156207249648372928455517246584917020679149653861285226961170842021388854323284132579306053835679130563246044941718724356142

n = 97556864962789127824701383242111068245641430412088446049554987171631796271268013457675328750740703181455093780021347024032292309660522866063731237500797701206940725352099428514342659100771939441946971272319151463476877708240447532346101326328206390117414020245045680514443093718216781806739876823259237682041
c = 97506619181657974835472296128714598728435343734591865967781506389027493446492338931895061849567882930303570448811849167940548090710640607320028639112831504753106905840969732206394654206682020482058950978096138227623007427344924113713884121137383236661810418984400003458312561214376484805408760046782907944992

#print(len(bin(y-x)))
#print(len(bin(n)))
kphiphin = y-x
for k in trange(1,2**16):
    phiphin = kphiphin // k
    phin = 2*(n + phiphin - 3)
    try:
        d = invert(e,phin)
        flag = long_to_bytes(powmod(c,d,n))
        if(b"flag" in flag):
            print(flag)
    except:
        pass

#flag{90ccb0c9-8700-41cb-9d62-b630cf8f1821}



EzLog

题目来源：广东省大学生攻防大赛 2022

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from secret import flag
assert len(flag)<118
from Crypto.Util.number import long_to_bytes,bytes_to_long
from Crypto.Util.Padding import pad

p=100380180012669637378744942171261398091918624065560475592116442008723831000724625143134783707140522784290998397673597179788440926203643287774297527809892664834392514365222771089497090006645985087685142898313371176199974996077656302299931624478967894041880873282005346940525877863969908284953093553124147377177
g=5

x=bytes_to_long(pad(flag,128))
assert bytes_to_long(pad(flag,128)) < p-1

print("I believe you have no way to catch me even though Pohlig has smooth weapons.")
print(f"y={pow(g,x,p)}")

# I believe you have no way to catch me even though Pohlig has smooth weapons.
# y=96684738736980459903034929785324785968796025930893469779531286222406396988966715592949333235326832011076688325476630562163362584667393368651336925308324274452289994386658111183814813840211779123227496106401048680166365937882835154692663834966767665274167877263256747696012785293060701554746392300871850636481

题目内容是一个直白的离散对数问题，并且提示了pohlig-hellman，但是有一些地方需要注意：

  • flag本身小于118个字节
  • 作为离散对数指数的x是flag填充至128字节后的值

然后我们看一看p-1的构成，除去最后一个大因子，剩余都是较小的因子：

image-20231117091459512

那么抛去最后一个大因子，我们用pohlig-hellman的思路，记前面所有的小因子乘积为t，我们可以求出一个c满足：

然后就进入了这个题目的主要问题：t仅有860多比特，而x是一个1024比特的数，所以我们求出来的c是远不够x的数量级的。因此需要进一步处理。

注意到他的填充用的是标准库中的pad也就是pkcs7，其具体实现为：

1
2
3
padding_len = block_size-len(data_to_pad)%block_size
    if style == 'pkcs7':
        padding = bchr(padding_len)*padding_len

而flag小于118字节，因此填充的长度应该在11-128之间，所以所有填充的可能性也最多就100多种，是可以爆破的，而我的思路就是利用这一点来进一步缩短需求解flag的比特长度。而之所以可以缩短是因为，假设padding长度为i个字节，那么x可以表示成：

代入到我们求解的c中：

那么就应该有：

此时要注意，2^8i的逆元按理来说在模t下是不存在的，因为t含有p-1的一个因子2^3，但是处理这一点也很简单，我们把2^3在求pohlig-hellman的过程中去掉就可以了。

但是直接这样处理的话，无法得到我们期望的flag串，这就说明，去除了padding的flag串依然大于模数t，而模数t是860比特左右，所以原本的未经填充的flag串应该大于107字节，落在了108-117的范围内；同时也说明padding在11-21字节之间。

而我们的目标是缩短flag串的需求解比特长度，使其小于t，才可以直接得出正确结果，那么就要进一步缩短flag。

然后我的想法就是利用上已知的flag串开头”flag{“和结尾”}”(这是我搜索其他这场比赛的其他题解看到的flag头尾)，进一步缩小6个字节，这一步缩小的原理如下，我们把flag表示成：

1
flag = b"flag{"*2^8k + 2^8flag  + b"}"

但是这样会有一个小问题存在：既然flag长度达到了107字节以上，那么他的开头或结尾会不会可能也是填充而非flag头尾？所以我只使用了flag头来缩短5个字节，而并没有用flag尾。

如此一来，记flag头为prefix，我们可以进一步改变刚才的等式：

其中，k是可以根据当前的padding长度计算出来的，那么我们进一步缩短了flag的比特长度。但是实际上测试出来即使缩短到这样，依然还不够。这说明了两种可能性：

  • flag本身去除前五个字节后依然大于t，所以flag在112-117字节之间，同时也说明padding的长度在11-16之间
  • flag本身的前缀不是flag{

而如果是第二种可能性的话，我就没什么好办法了。因此我先假设是第一种可能性。由于同一场比赛的其他flag串我查到有一些是uuid格式。所以假设flag的前面是flag串的话，我们可以爆破其开始的几个十六进制字符，来进一步缩短flag，也就是现在我们将flag前缀表示为如下形式，xxxxx是待爆破的5个十六进制字符：

1
prefix = "flag{xxxxx"

那么仍然用刚才的表达式：

而之所以是爆破5个十六进制字符，是因为我们用最坏的情况考虑，flag最长的时候是117字节，我们去除前10个字节后，flag还有107字节，就一定小于t，所以求解出来的就是flag本身。然而这样依然是没有结果的，这说明以下几种可能：

  • flag不是以”flag{+十六进制串”开头，此时可以尝试把后面换成可打印字符，爆破四个试一试(爆破5个复杂度太高)
  • flag不是以”flag{“开头，这个我没有什么办法
  • 代码写错了或者推导有问题，但是我自己本地生成的117长度的十六进制串flag确实是可以跑出来的，所以只要是以flag{开头，这个方法就可以用，只是如果是可见字符的话会显著影响爆破时间。各位师傅也可以试试。

pohlig-hellman代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
from tqdm import *
import string

p=100380180012669637378744942171261398091918624065560475592116442008723831000724625143134783707140522784290998397673597179788440926203643287774297527809892664834392514365222771089497090006645985087685142898313371176199974996077656302299931624478967894041880873282005346940525877863969908284953093553124147377177
g=5
y=96684738736980459903034929785324785968796025930893469779531286222406396988966715592949333235326832011076688325476630562163362584667393368651336925308324274452289994386658111183814813840211779123227496106401048680166365937882835154692663834966767665274167877263256747696012785293060701554746392300871850636481
factors = [56989,60217,538687139,560945999,571334087,610502371,631183649,632950873,635821279,650856469,655219333,656624429,681519161,718737731,731233123,733484177,763003931,789196883,819494821,819518603,844402217,857626969,895870279,907446997,908829937,950563309,972564941,1030070381,1048221233,1063554559]
modd = prod(factors)

#part1
G = Zmod(p)
order = p - 1
m = G(g)
c = G(y)
dlogs = []
for i in factors:
    t = order // i
    y = c ^ t
    g = m ^ t
    dlog = discrete_log(c ^ t, m ^ t)
    dlogs.append(int(dlog))
c=crt(dlogs, factors)
print("Pohlig-Hellman Done!")

然后就是sage对于后面爆破可见字符的步骤会比python慢很多，所以我是把pohlig-hellman的结果复制粘贴出来用python跑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
from Crypto.Util.number import *
from tqdm import *
from math import prod
import string

factors = [56989,60217,538687139,560945999,571334087,610502371,631183649,632950873,635821279,650856469,655219333,656624429,681519161,718737731,731233123,733484177,763003931,789196883,819494821,819518603,844402217,857626969,895870279,907446997,908829937,950563309,972564941,1030070381,1048221233,1063554559]
c = 597203058296870944998511276315050809375979978968706561575747725745150339335125598197249750399194119950950292435476589291604850459941807224219515716186297039137935899709305293092200672388736033486662307607585762588006264600250852113260919705803916526786928158
modd = prod(factors)
prefix = "flag{"

#假设开头是flag{uuid}，则爆破前5个十六进制字符
if(0):
    table = "0123456789abcdef"
    dic = [ord(i) for i in table]
    result_list = []
    for char1 in table:
        for char2 in table:
            for char3 in table:
                for char4 in table:
                    for char5 in table:
                            current_string = char1 + char2 + char3 + char4 + char5
                            result_list.append(current_string)
    #爆破填充
    for j in tqdm(result_list):
        for i in range(11,16):
            # delete padding
            padding = long_to_bytes(i)*i
            padding = bytes_to_long(padding)
            temp = (c - padding)*inverse(256**i,modd) % modd

            #delete prefix
            k = 128 - i - 10
            tmp_prefix = prefix + j
            tmp_prefix = bytes_to_long(tmp_prefix.encode())*256**k
            temp = (temp - tmp_prefix) % modd

            #check
            final = long_to_bytes(temp)[:10]
            error = 0
            for tt in final:
                if(tt not in dic):
                    error = 1
                    break
            if(error == 0):
                print(long_to_bytes(temp))


#假设开头是flag{+可见字符，则爆破4个可见字符
if(1):
    table = string.printable
    dic = [ord(i) for i in table]
    for char1 in tqdm(table):
        for char2 in table:
            for char3 in table:
                for char4 in table:
                    j = char1 + char2 + char3 + char4
                    for i in range(11,16):
                        # delete padding
                        padding = long_to_bytes(i)*i
                        padding = bytes_to_long(padding)
                        temp = (c - padding)*inverse(256**i,modd) % modd

                        #delete prefix
                        k = 128 - i - 10
                        tmp_prefix = prefix + j
                        tmp_prefix = bytes_to_long(tmp_prefix.encode())*256**k
                        temp = (temp - tmp_prefix) % modd

                        #check
                        final = long_to_bytes(temp)[:20]
                        error = 0
                        for tt in final:
                            if(tt not in dic):
                                error = 1
                                break
                        if(error == 0):
                            print(j)
                            print(long_to_bytes(temp))

希望能给各位师傅一些启发。

(2.24更新)

在之前”Thoughts”一文的评论区师傅的点拨下明白了这题的解法，在这里整合一下他的思路记录一下题解。

首先就是，由前面的推导爆破无果，可以知道flag串应该并不是以常规的”flag{}”作为开头和结尾的，因此会产生一个猜想：既然他尾部本来就是填充，那么前面未填充的部分应该都有意义，因此可以猜想其大致格式应该是：

1
sentence + flag

比如说有时候见到的flag会是：

1
You are so smart and Here is your flag:flag{xxx}.

就是这个意思。然后评论区的师傅就想到了一点，既然这样的话，那虽然开头不是很好猜，但是结尾是”}.”(或者”}!”之类)的可能性就相当大，又因为验证过填充字节长度在13以上的时候都没有解，所以不妨先假设填充长度就是13(如果求不出，再假设为12、11)，那么加上已知的flag尾部”}.”，就知道了15个字节，未知的字节还剩下113个。而又因为我们用Pohlig-Hellman可以求出860bit左右的信息，那么剩下的信息就只有：

就很好用bsgs来处理了，最后就能得到flag。

还是简单写一下这个推导过程吧，首先把已知的后缀”}.”+padding当作长为15的suffix，那么就有：

这里说一下Pohlig-Hellman其实只要用一点技巧，就可以直接用sage来完成，而并不需要像上文中那样写，方法如下。假设我们用Pohlig-Hellman求出的为m0，就有：

其中phi就是用p-1的光滑因子乘积构成的指数上的模数(要去除2，不然无法求256的逆)，在这里我们把p-1写成：

h就是除去这些光滑数的因子，那么由于有：

就一定有：

而这样写的好处是g^h是个phi阶的元素，因此其阶光滑，用sage内置的discrete_log就可以很轻松求出来模phi下的x，也就是m0了。所以Pohlig-Hellman的求解过程其实就可以写为：

1
m0 = discrete_log(Mod(pow(y,h,p),p),Mod(pow(g,h,p),p),ord = phi)

然后继续接着上面的说，现在有：

就有m1在模phi下的值：

计算出这个值后，又因为知道真实的m1和计算出的这个m1的关系是：

其中k是一个44bit数量级的数，那么代回原dlp就有：

整理得到：

所以就最终整理得到：

然后就可以在p-1的阶下bsgs求出k的值了(可以直接用sage)，求出k之后计算得到flag：

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from Crypto.Util.number import *

p = 100380180012669637378744942171261398091918624065560475592116442008723831000724625143134783707140522784290998397673597179788440926203643287774297527809892664834392514365222771089497090006645985087685142898313371176199974996077656302299931624478967894041880873282005346940525877863969908284953093553124147377177
g = 5
y = 96684738736980459903034929785324785968796025930893469779531286222406396988966715592949333235326832011076688325476630562163362584667393368651336925308324274452289994386658111183814813840211779123227496106401048680166365937882835154692663834966767665274167877263256747696012785293060701554746392300871850636481
factors = [3^2,56989,60217,538687139,560945999,571334087,610502371,631183649,632950873,635821279,650856469,655219333,656624429,681519161,718737731,731233123,733484177,763003931,789196883,819494821,819518603,844402217,857626969,895870279,907446997,908829937,950563309,972564941,1030070381,1048221233,1063554559]
phi = prod(factors)
h = (p-1) // phi

#part1 use Pohlig-hellman to get first-step m0(use sage)
m0 = discrete_log(Mod(pow(y,h,p),p),Mod(pow(g,h,p),p),ord = phi)


#part2 guess the suffix is "}."" and padlen is 13
padlen = 13
suffix = bytes_to_long(b"}." + long_to_bytes(padlen)*padlen)
length = padlen + 2
m1 = (m0-suffix)*inverse(256^length,phi) % phi


#part3 bsgs(use sage)
y1 = y * pow(g,-(256^length*m1+suffix),p) % p
g1 = pow(g,256^length*phi,p)
k = discrete_log(Mod(y1,p),Mod(g1,p),ord = p-1,bounds = (0,2^(1024-860-length*8)))


#part4 get flag
flag = 256^length*(k*phi+m1)+suffix
print(long_to_bytes(flag))

#b'You are a master of the dlp algos! Here is your flag: flag{S0_Smooth_ord3r_pr1me_dlp!_pohlig_hellman_with_padding}.\r\r\r\r\r\r\r\r\r\r\r\r\r'



dlp

题目来源：NCTF 2021

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import socketserver
from Crypto.Util.number import *
import os
import signal
import string
import random
from hashlib import sha256
from secret import flag

class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'> '):
        self.send(prompt, newline=False)
        return self._recvall()

    def proof_of_work(self):
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
        _hexdigest = sha256(proof.encode()).hexdigest()
        self.send(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
        x = self.recv(prompt=b'Give me XXXX: ')
        if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
            return False
        return True

    def handle(self):
        if not self.proof_of_work():
            return

        p = 144622268328968993341365710278894755118767129325286994164661347213200068288320713151689155598130690763440455157929587751885813242814750422828312072382119518429040602281694119210475772654999865828418886175678335978908269120940864300610431302161143383386149363868608635140950451657400233892787130315426229955639
        s = [getPrime(100)]
        for i in range(1023):
            s.append(s[i]*s[i]%(p-1))
        while True:
            self.send(b'>', newline=False)
            choice = self.recv()
            if choice == b"1":
                try:
                    self.send(b"Give me m:")
                    m = int(self.recv()) % p
                    self.send(b"Give me k:")
                    k = int(self.recv())
                    if k not in range(1024):
                        break
                    c = pow(m, s[k], p)
                    self.send("c = {}".format(c).encode())
                except:
                    break
            elif choice == b"2":
                self.send(b"Give me the secret:")
                secret = int(self.recv()) % p
                if pow(secret, s[0], p) == 0xdeadbeef:
                    self.send(flag)
                else:
                    self.send(b'flag')
                break
        self.request.close()


class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass


class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10001
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

依然是一个交互题，连接上靶机后首先需要通过proof，然后就进入题目。靶机会生成一个素数p，以及一个100位的素数s0，并以s0按如下方式生成列表s：

1
2
3
s = [getPrime(100)]
for i in range(1023):
    s.append(s[i]*s[i]%(p-1))

也就是：

然后题目提供了两种交互：

  • 输入1，可以输入一个明文m以及一个索引k，靶机会返回$c = m^{s_k} \; (mod\;p)$
  • 输入2，可以输入一个明文m，如果m满足$m^{s_0} = 0xdeadbeef \;(mod\;p)$，则可以得到flag

如果能求解DLP的话，那么求出s0过后就很好办，但是分解一下p-1可以发现，p是2q+1型的安全素数，所以求DLP并不可能。那么核心思路就是要利用第一个交互去想办法找到能满足第二个交互要求的m。

那么就要仔细想下怎么利用，首先可以发现s列表其实可以看作是一个比特串，因为他的每个位置都和对应位置的比特一一对应。

这是什么意思呢？比如我们想要利用靶机计算出$c = m^{s_0^{11}}$的值，我们只需要把11拆成二进制串1011，然后第一次送给靶机$(m,0)$，得到$c_1 = m^{s_0}$，第二次送给靶机$(c_1,1)$，得到$c_2 = m^{s_0^{2^0+2^1}}$，第三次给靶机$(c_2,3)$，就得到$c_3 = m^{s_0^{2^0+2^1+2^3}}$，也就得到我们需要的$c = m^{s_0^{11}}$的值了。

而回看一下题目任务，我们是想找到一个满足下式的m：

我们不妨取m=0xdeadbeef，那么问题其实可以转化成找出一个满足如下条件的二进制序列k：

也就是：

而由于p-1是可以完全分解的，那么令q=(p-1)/2，就可以把指数上的运算单独写出来：

又因为q也是个素数，所以由费马小定理就有：

那么我们其实就找到了我们需要的二进制序列k：

然后就照上面的例子，先利用交互1去得到计算结果：

然后输入2把这个m发过去就可以了。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from Pwn4Sage.pwn import *
from Crypto.Util.number import *
from tqdm import *
from hashlib import *
import string

sh = remote("node5.anna.nssctf.cn",28301)

#part1 proof
def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = sh.recvuntil(b"sha256(XXXX+")
	temp = sh.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						sh.sendline(temp1.encode())
						return
proof_of_work()


#part2 
p = 144622268328968993341365710278894755118767129325286994164661347213200068288320713151689155598130690763440455157929587751885813242814750422828312072382119518429040602281694119210475772654999865828418886175678335978908269120940864300610431302161143383386149363868608635140950451657400233892787130315426229955639
q = (p-1) // 2
m = 0xdeadbeef
k = q-2

for i in trange(1024):
	if(k % 2):
		sh.recvuntil(b'>')
		sh.sendline(b'1')
		sh.recvuntil(b"Give me m:")
		sh.sendline(str(m).encode())
		sh.recvuntil(b"Give me k:")
		sh.sendline(str(i).encode())
		sh.recvuntil(b'c = ')
		m = int(sh.recvline().strip().decode())
	k = k // 2

sh.recvuntil(b'>')
sh.sendline(b'2')
sh.recvuntil(b"Give me the secret:")
sh.sendline(str(m).encode())
sh.recvline()
print(sh.recvline())


#NSSCTF{58de53dd-16af-4912-8de1-a2f510e6c174}