2023强网杯

强网是强者的网络安全竞赛，我太菜了。。慢慢复盘，估计得复盘到明年了。

not only rsa(118 solves)

from Crypto.Util.number import bytes_to_long
from secret import flag
import os

n = 6249734963373034215610144758924910630356277447014258270888329547267471837899275103421406467763122499270790512099702898939814547982931674247240623063334781529511973585977522269522704997379194673181703247780179146749499072297334876619475914747479522310651303344623434565831770309615574478274456549054332451773452773119453059618433160299319070430295124113199473337940505806777950838270849
e = 641747
m = bytes_to_long(flag)

flag = flag + os.urandom(n.bit_length() // 8 - len(flag) - 1)
m = bytes_to_long(flag)

c = pow(m, e, n)

with open('out.txt', 'w') as f:
    print(f"{n = }", file=f)
    print(f"{e = }", file=f)
    print(f"{c = }", file=f)

题目中n可分解且n=p^5，但e与phi不互素。好，接下来就是一个简单的有限域分解。

mp=GF(p)(c).nth_root(e, all=True)

在测试了GF(p)和GF(p^2)都可以开出根，但此题肯定无法使用CRT求m的，n的因子只有p，那么就只能尝试继续开根了。。。但是GF(p^3)域下开根我的sage已经跑不出来了，更何况直接去求GF(p^5)这题也就断在这里了，但是比赛时一直出解，怀疑是不是有别的简单解法。

赛后看wp真无语。。有限域开根做多了，没想到有限环也可以开根，域相对环来说更为严格，环上可以开根但域上不一定可以。此题在环Zmod(p^5)上可以实现秒开根。

直接搬别人脚本了

from tqdm import tqdm
from Crypto.Util.number import long_to_bytes
p = 91027438112295439314606669837102361953591324472804851543344131406676387779969
e = 641747
c = 730024611795626517480532940587152891926416120514706825368440230330259913837764632826884065065554839415540061752397144140563698277864414584568812699048873820551131185796851863064509294123861487954267708318027370912496252338232193619491860340395824180108335802813022066531232025997349683725357024257420090981323217296019482516072036780365510855555146547481407283231721904830868033930943
n = p ^ 5
K = Zmod(p ^ 5)
a = K(c).nth_root(e)
b = K(1).nth_root(e)
a = int(a)
b = int(b)
print(b, a)
for i in tqdm(range(e)):
    a = (a*b) % n
    m = long_to_bytes(int(a))
    if b"flag" in m:
        print(m)
        break

discrete_log_task(36 solves)

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
flag = 'flag{d3b07b0d416ebb}'

assert len(flag) <= 45
assert flag.startswith('flag{')
assert flag.endswith('}')

m = bytes_to_long(pad(flag.encode(), 128))

p = 0xf6e82946a9e7657cebcd14018a314a33c48b80552169f3069923d49c301f8dbfc6a1ca82902fc99a9e8aff92cef927e8695baeba694ad79b309af3b6a190514cb6bfa98bbda651f9dc8f80d8490a47e8b7b22ba32dd5f24fd7ee058b4f6659726b9ac50c8a7f97c3c4a48f830bc2767a15c16fe28a9b9f4ca3949ab6eb2e53c3
g = 5

assert m < (p - 1)

c = pow(g, m, p)

with open('out.txt', 'w') as f:
    print(f"{p = }", file=f)
    print(f"{g = }", file=f)
    print(f"{c = }", file=f)

非常标准的一个dlp，并且这个p是非常安全的，\(\frac{p-1}{2}\)也是一个素数，所以这题我也没想到有什么办法。赛时确实猜了一下这个假flag给的暗示，是不是flag只可能是16进制字符？但位数也不确定，还经过了pad，觉得不太好继续进行下去。

赛后wp看到确实是爆破的思路，采用的是meet in middle中间相遇攻击。首先我们需要构造出中间相遇的式子。 > 下面为了书写简便，flag未知位数为12位，这个可通过爆破求得。

确定好位数之后，flag的头尾分别是flag{和}+padding，这里padding是确定的。 \[m=mh\cdot 2^{(128-5)\cdot 8}+mm\cdot 2^{(128-5-12)\cdot 8}+ml\] \[c=g^m \;mod\; p\] \[g^{2^{888}\cdot mm}\equiv c\cdot (g^{2^{984}\cdot mh+ml})^{-1} \;mod\;p\] 等式中只有左侧mm是12位未知的字符串，想办法将其拆开，放到等式两侧就可进行中间相遇。 \[mm=half_1+half_2\] \[g^{2^{888}\cdot (half_1+half_2)}\equiv c\cdot (g^{2^{984}\cdot mh+ml})^{-1} \;mod\;p\] 下一步计算\(x=inverse(2^{888},\phi(p))\),得 \[g^{half_1+half_2}\equiv (c\cdot (g^{2^{984}\cdot mh+ml})^{-1})^x \;mod\;p\] 说实话当时看别的师傅博客时这个式子复杂的让我奇怪为什么乘了这样的一个x？其实就是rsa那套啊。。\(c=m^e\;mod\;p,c^d=m\;mod\;p\)

记\(A=(c\cdot (g^{2^{984}\cdot mh+ml})^{-1})^x\)

最后一步变换 \[g^{half_1}\equiv A\cdot g^{-half_2}\;mod\;p\] 由于A通过计算可求，接下来就是爆破half1和half2找到使等式成立的值，大大减小了爆破复杂度。

import itertools
from gmpy2 import *
from Crypto.Util.Padding import *
from Crypto.Util.number import *
from tqdm import tqdm
p = 173383907346370188246634353442514171630882212643019826706575120637048836061602034776136960080336351252616860522273644431927909101923807914940397420063587913080793842100264484222211278105783220210128152062330954876427406484701993115395306434064667136148361558851998019806319799444970703714594938822660931343299

g = 5

c = 105956730578629949992232286714779776923846577007389446302378719229216496867835280661431342821159505656015790792811649783966417989318584221840008436316642333656736724414761508478750342102083967959048112859470526771487533503436337125728018422740023680376681927932966058904269005466550073181194896860353202252854

q = 86691953673185094123317176721257085815441106321509913353287560318524418030801017388068480040168175626308430261136822215963954550961903957470198710031793956540396921050132242111105639052891610105064076031165477438213703242350996557697653217032333568074180779425999009903159899722485351857297469411330465671649

flag_len = 12
fake_flag_pad = 'flag{'.encode() + '\x00'.encode()*flag_len+'}'.encode()
flag_pattern = (pad(fake_flag_pad, 128))
flag_pattern = bytes_to_long(flag_pattern)
pattern = 1 << 888
cc = c * inverse(pow(g, flag_pattern, p), p) % p

cc = pow(cc, inverse(pattern, q), p)
table = ['0', '1', '2', '3', '4', '5', '6',
         '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f']

dic = dict()
gtemp = pow(g, 2**48, p)

for half_flag1 in tqdm(itertools.product(table, repeat=6)):
    half_flag1 = bytes_to_long(''.join(half_flag1).encode())
    temp = cc * powmod(gtemp, -(half_flag1), p) % p
    dic[temp] = half_flag1

for half_flag2 in tqdm(itertools.product(table, repeat=6)):
    half_flag2 = bytes_to_long(''.join(half_flag2).encode())
    temp = powmod(g, half_flag2, p)
    if temp in dic:
        print(long_to_bytes(dic[temp]) + long_to_bytes(half_flag2))

guess game(20 solves)

对称密码题，应该是差分分析，暂时没看到预期解。都是直接爆破碰运气😄，脚本就几行，一直发1就完了。

babyrsa(14 solves)

论文题，值得一复现。

1515(10 solves)

论文题，之后结合一道其他题目一起说明，像是之前做过的一道plus版本。

recovery(3 solves)

这个算了，肯定复不动。