24Nov1

huangx607087 11月的切题1

0.Introduction

上一篇是 5 月的切题，这一篇是 11 月的切题。看似隔了半年，实际隔了 $3$ 年半，也就是 $\mathrm{(1+kun) years}$。

1.[强网杯2024] eazyRSA

从题目的模数生成代码来看，可以知道 $n=4g^2ab+2ga+2gb+1=(2ga+1)(2gb+1)$，其中 $g$ 是 $500$位，$a,b$ 是 $524$ 位。

可以推式子：$n-1=4g^2ab+2g(a+b)$，那也就有：

$$
\frac{n-1}{2g}=2gab+(a+b)
$$
也就是：
$$
\frac{n-1}{2g} \equiv (a+b) \pmod {2g}
$$
和
$$
\frac{n-1}{4g^2}=ab+\frac{a+b}{2g}
$$

设
$$
s=(a+b)\bmod 2g,t=ab+\frac{a+b}{2g}
$$

如果 $a+b<2g$，那么构造方程 $x^2-sx+t=0$ 就已经出了。但这里 $a+b>2g$。本地测了几组，$\frac{a+b}{2g}$ 的值大概是两千万($(2^{23}+2^{22})\sim 2^{25}$)左右。

因此写个脚本爆破就可以，设 $(a+b)=s+2kg$，$ab=t-k$，爆破$k$即可，大概需要 40 分钟。

解出来之后，复制 $a,b$，就可以完成这个题了。

from Crypto.Util.number import *
from tqdm import *
n=282...
e=65537
g=169...
enc=713...
s=int(((n-1)//(2*g))%(2*g))
t=(n-1)//(4*g**2)
PR.<x>=PolynomialRing(ZZ)
for k in tqdm_notebook(range(2**24,2**25)):
    T=(n-1)//(4*g**2)-k
    S=s+2*k*g
   # print(T,S)
    L=list(factor(x**2-S*x+T))
    if(len(L)==2):
        print(L)
        break
#About 33 minutes... ...
#[(x - 54722203851071002380640637783364295778615257147150541196711959753700451263333616989065849396687025501437950790074260319502675063161775706578982408368898972337, 1), (x - 44622831196150967536480715584711535584181586357962911905789372910901564430321427024174796137209528941353858108707886896337555315598122100856203421182547788460, 1)]

获取 $a,b$ 后，直接解就可以得到 flag了。

a=54722203851071002380640637783364295778615257147150541196711959753700451263333616989065849396687025501437950790074260319502675063161775706578982408368898972337
b=44622831196150967536480715584711535584181586357962911905789372910901564430321427024174796137209528941353858108707886896337555315598122100856203421182547788460
phi=4*g**2*a*b
d=inverse(int(65537),int(phi))
long_to_bytes(pow(int(enc),int(d),int(n)))
#b'flag{4bda6015-2fe8-43f2-96c3-0ce1d6c71ab2}'

自己的脚本跑了 $30$ 分钟，因为用了factor，但其实还有更多的方法，比如糖醋小鸡快的博客中的bsgs方法：

#reference: https://tangcuxiaojikuai.xyz/post/df3f7032.html#more
N=186...
e=65537
g=215...
enc=170...
gamma = 500/(1024*2)
cbits = ceil(nbits * (0.5 - 2 * gamma))

M = (N - 1) // (2 * g)
u = M // (2 * g)
v = M - 2 * g * u
GF = Zmod(N)
x = GF.random_element()
y = x ^ (2 * g)
# c的范围大概与N^(0.5-2*gamma)很接近
c = bsgs(y, y ^ u, (2**(cbits-1), 2**(cbits+1)), operation='*')
#(a, b, bounds, operation='*', identity=None, inverse=None, op=None)
ab = u - c
apb = v + 2 * g * c
P.<x> = ZZ[]
f = x ^ 2 - apb * x + ab
a = f.roots()
if a:
    a, b = a[0][0], a[1][0]
    p = 2 * g * a + 1
    q = 2 * g * b + 1
    assert p * q == N

from Crypto.Util.number import *
print(long_to_bytes(int(pow(enc,inverse(e,(p-1)*(q-1)),N))))

2. [强网杯2024]apbq

题目第一关很简单，给出了$h=p+q$ ，结合 $n=pq$，直接解方程 $x^2-hx+n=0$。放到 sage中因式分解，就能得到$p,q$，然后解密就行了

题目第二关给出了一百组 $ap+bq$，其中$a,b$未知，规模约为 $180$位。这个题就跟今年华为杯CTF 和2023 年 DownUnderCTF的那个题一样。不过那个题是解3组，这边给出了100组。

看了下那个题题解，其实原理就是解ACD问题。假设只有三组数据，那就是 $x_1=a_1p+b_1q,x_2=a_2p+b_2q,x_3=a_3p+b_3q$，对这三个数模$q$，就会有
$$
x_1\equiv a_1p,x_2\equiv a_2p,x_3\equiv a_3p \pmod q
$$

如果能够找到一组$u_1,u_2,u_3$，使得
$$
u_1x_1+u_2x_2+u_3x_3\equiv 0\pmod q
$$
那么就可以与 $n$做 $\gcd$ 得到$q$。

根据参考文献中的方法，构造$(t+1)\times (t+1)$的格($t$为数据组数)，我在解题时取了 10 组数据。

Harr =  #复制题目中给出的数据
n,e = (73566307488763122580179867626252642940955298748752818919017828624963832700766915409125057515624347299603944790342215380220728964393071261454143348878369192979087090394858108255421841966688982884778999786076287493231499536762158941790933738200959195185310223268630105090119593363464568858268074382723204344819, 65537)
c = 30332590230153809507216298771130058954523332140754441956121305005101434036857592445870499808003492282406658682811671092885592290410570348283122359319554197485624784590315564056341976355615543224373344781813890901916269854242660708815123152440620383035798542275833361820196294814385622613621016771854846491244

vh=Matrix(ZZ,Harr[:10]).T
E100=Matrix(ZZ,[[i==j for j in range(10)]for i in range(10)])
L1=block_matrix([vh,E100],ncols=2)
L1=list(L1)
L1.append([0]*10+[n])
L1=Matrix(ZZ,L1)
V=L1.LLL()

然后对这个格进行LLL之后，可以发现这个格前 $t-2$ 个向量都非常小，且第一个分量都是 $0$，因此可以保留这 $t-2 $个向量，求这$t-2 $个向量的核空间。

之所以第一个分量为 $0$，是因为这 t-2个向量的第一个分量为 $\sum_{i=1}^t x_iu_i$，在我们的设定中，这个值模 $q$ 就应该为 $0$。剩下的值其实就是约简后的 $x$值。但我们的目标是要求 $u$，且满足 $\sum_{i=1}^t x_iu_i=0$，因此对这个 $t-2 $ 个向量求核空间即可，然后根据论文中的方法，对核空间LLL。

listV=list(V)
listV=listV[:8]
V2=Matrix(ZZ,listV)
B=V2.right_kernel().matrix()
B=B.LLL()
for b in B:
    print(b)
C,D=B[1],B[2]
#(1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
#(0, 189054094845986711998601686638484899186928349869787764,-280260848759201243491139877993231433651309260321040422,-191419885782217555958459422458916080605185847352273281,80130022117941963164030469836409979879630589989718363,223374223525189873441521908177956783831422862962061407,-89593942049506075242290992587826902438240116945004863,30786784715283690213436728841096788963107064929499390,-366749089468309096269501995562509974553537779662708024,-318033151667809147614797636609797089137748229551489277,31066526775222212141169199486975191411844689712886217)
#(0,-1346279784706528250600681657984465653742744965149886725,-558376165928956918779997224381914383468803211678279444,-699816315320719608537550250769699566822298049653746205,-1593643074383414877869701641804189953765209179320460752,-1657915058789773997163001981126904902500418293868719109,-1053323500669935374421749709512602723352760224623425605,-1012154622528129384834327358953617453656985712746546759,-794684381522339277259854046745294719668955559599542526,-476952930272344315432888118863605062412545884787988052,-1040134187110594696346363876254412992508481258190444762)

核空间中包含三个 $t+1$维向量，第一个是 $(1,0,0,…,0)$，因为第一个分量是 $\sum_{i=1}^t x_iu_i$，它当然等于 $0$。剩下两个向量记为 $\vec C$ 和 $\vec D$ ，其中 $\vec C$ 的每个分量（除第一个分量，$\vec D$下同）大约为 $175\sim178 \mathrm{bit}$，$\vec D$ 的每个分量为 $179\sim181 \mathrm{bit}$。但因为 $ap+bq$ 中， $a$是$180\mathrm{bit}$ (对应我们想求的 $u$)，所以我们想求的向量 $\vec U$ 应该是 $\vec C$和$\vec D$ 线性组合，枚举一下小系数，根据线性组合结果尝试对 $n$求最大公约数，就可以出解了。

found=0
for i in range(-32,33):
    for j in range(-32,33):
        w=i*C+j*D
        kq=abs((w[1])*Harr[1]-w[2]*Harr[0])
        if(GCD(n,kq)!=1 and GCD(n,kq)!=n):
            print(GCD(n,kq))
            found=1
            break
    if(found):
        break
#9067773077510925207378520309595658022345214442920360440202890774224295250116442048990578009377300541280465330975931465993745130297479191298485033569345231

测试比特数：

Update 11.10 然后这个题就出了一个乌龙，就是第三部分用了第二部分的加密参数，也就是只需要解出第二部分，就可以完成解题，第三部分其实完全多余了。但这里还是看一下第三部分内容吧。

第三部分给出了 $c_1=ap+q$ 和 $c_2=p+bq$。此处 $a,b,p,q$ 均为 $512$ 位。

当时自己在做的时候，打算把 $c_1$ 和 $c_2$ 相乘的，但总时看不出来东西，只能作罢。但实际上正确做法是 $(c_1-q)$ 和 $(c_2-p)$ 相乘，展开得到 $c_1c_2-pc_1-qc_2$。

然后构造了一个，解不出来，$K$ 从 $2^{800}$ 提升到 $2^{3840}$ 最终也没有出

然后看了 N0WayBack 那边的题解，结果发现要爆破？$512$ 的界不够，什么鬼？那边爆破了 $2$ 位，向量上界为 $2^{510}$。（所以为啥 $2^{512}$ 就解不出来呢，这个界又得怎么算）。。。

也就是爆破的时候，使用这个公式爆破 $p_h$ 和 $q_h$。
$$
c_1c_2-c_1(2^2p_h+i)-c_2(2^2q_h+j)=0
$$

from Crypto.Util.number import *

#stage3

n3,e3 = (9478..., 65537)
enc3 = 
c1 = ...
c2 = ...

brute = 2
for i in range(2**brute):
    for j in range(2**brute):
        L = Matrix(ZZ, [
            [1,0,0,2**brute*c1],
            [0,1,0,2**brute*c2],
            [0,0,2**(512-brute),c1*i+c2*j-c1*c2],
            [0,0,0,n3]
        ])
        L[:,-1:] *= n3
        res = L.LLL()[0]

        p = 2**brute*abs(res[0])+i
        if(n3 % p == 0):
            print(p)

3.[强网杯2024]21 steps

算法构造题，如何使用 $21$ 步单步计算求出一个 $128\mathrm{bit}$ 的数 $A$ 里面有几个 $1$，有一个变量 $B$ 作为辅助。

求一个数的bitcount，在不用循环的情况下，可以使用比特聚合法。原理在这个网站中讲得很详细。

写成C语言代码就是：

unsigned countOnes(unsigned x)
{
    x = (x & 0x55555555) + ((x >> 1) & 0x55555555); /* 计算相邻 2 位中 1 的个数。 */
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333); /* 计算相邻 4 位中 1 的个数。 */
    x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F); /* 计算相邻 8 位中 1 的个数。 */
    x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF); /* 计算相邻 16 位中 1 的个数。 */
    x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF); /* 计算相邻 32 位中 1 的个数。 */
    return x;
}

第一个式子写成简单步骤，就是：

B=A>>1;
A&=0x55555555;
B&=0X55555555;
A=A+B;

但对于128bit来说，这么做远远超过了21步。根据上面的代码，这样做需要28步。考虑改善。

注意到结果一定不超过128，因此在八位聚合之后，可以使用二分法折半相加。

（下图是对$\mathtt{0x00112233445566778899aabbccddeeff}$聚合前三步的结果）

1
2
3

0x001111224455556644555566889999AA
0x00111122112222331122223322333344
0x00020204020404060204040604060608

比如 $\mathtt{0x0002020402040406}$ 可以直接和 $\mathtt{0x0204040604060608}$，也就是

1
2
3

B=A>>64;
A=A+B;
#0x00020204020404060206060A060A0A0E

这样其实最高64位就不管了。同理，32位、16位、8位也可以这么玩。也就是在聚合的后4步，不断地将考虑内容减半，逐步舍弃高64、高32、高16、高8位。这样四组，会用掉8步，加上前面12步，就是20步了。

最后一步为A=A&255，上面不要的东西清零，得到 $\mathtt{0x40}$ 为最终答案。

（下图是对 $\mathtt{0x00112233445566778899aabbccddeeff}$ 聚合前三步的结果）

0x00020204020404060206060A060A0A0E
0x000202040206060A040A0A1008101018
0x00020206040A08100A140E1A12201828
0x000204080A0E12181A1E22282C323840
0x00000000000000000000000000000040

因为题目要求常数只能用十进制表示，因此可以得到payload

payload="B=A>>1;A=A&113427455640312821154458202477256070485;B=B&113427455640312821154458202477256070485;A=A+B;B=A>>2;A=A&68056473384187692692674921486353642291;B=B&68056473384187692692674921486353642291;A=A+B;B=A>>4;A=A&20016609818878733144904388672456953615;B=B&20016609818878733144904388672456953615;A=A+B;B=A>>64;A=A+B;B=A>>32;A=A+B;B=A>>16;A=A+B;B=A>>8;A=A+B;A=A&255;"

其中：$\mathtt{113427455640312821154458202477256070485=0x5555 5555 5555 5555 5555 5555 5555 5555}$

贴一下测试代码：

M1=0x55555555555555555555555555555555
M2=0x33333333333333333333333333333333
M4=0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f
M8=0x00ff00ff00ff00ff00ff00ff00ff00ff
def bc(A):
    B=A>>1
    A=A&M1
    B=B&M1
    A=A+B
    print('{:032X}'.format(A))
    B=A>>2
    A=A&M2
    B=B&M2
    A=A+B
    print('{:032X}'.format(A))
    B=A>>4
    A=A&M4
    B=B&M4
    A=A+B
    print('{:032X}'.format(A))
    B=A>>64
    A=A+B
    print('{:032X}'.format(A))
    B=A>>32
    A=A+B
    print('{:032X}'.format(A))
    B=A>>16
    A=A+B
    print('{:032X}'.format(A))
    B=A>>8
    A=A+B
    print('{:032X}'.format(A))
    A=A&0xFF
    print('{:032X}'.format(A))
    return A
print(bc(0x00112233445566778899aabbccddeeff))
"""
001111224455556644555566889999AA
00111122112222331122223322333344
00020204020404060204040604060608
00020204020404060206060A060A0A0E
000202040206060A040A0A1008101018
00020206040A08100A140E1A12201828
000204080A0E12181A1E22282C323840
00000000000000000000000000000040
64
"""

4.[网鼎杯2024] Crypto01

个RSA题目，给出了 $(n,e,c)$，以及 $(p,q)$ 的高 $70$ 位。密钥生成时，解密指数 $d$ 的位数为 $299$ ，对应 $\ln d=0.29199\ln n $。这个上限已经达到了extend wiener attack对应的 $\ln d=0.292\ln n$ 极限。

感觉像是wiener attack 和copper结合解题，搜一下，发现了鸡快师傅的博客。看来今年密码挑战赛出过类似的题目。

点进去并参考博客内容，发现第一章第3条符合条件，只不过那个需要爆破高位，这个高位直接给了出来。

在Linux 环境(Ubuntu20.04,Sagemath9.0,python3.8.10)下，下载并安装flatter[2]，就可以解出来了。。

import time
from subprocess import check_output
from multiprocessing import Pool

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    from re import findall
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

debug = False

strict = False


helpful_only = True
dimension_min = 7 # 如果格达到该尺寸，则停止移除

# 显示有用矢量的统计数据
def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1

    print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

# 显示带有 0 和 X 的矩阵
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60: 
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        #print (a)

# 尝试删除无用的向量
# 从当前 = n-1（最后一个向量）开始
def remove_unhelpful(BB, monomials, bound, current):
    # 我们从当前 = n-1（最后一个向量）开始
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB

    # 开始从后面检查
    for ii in range(current, -1, -1):
        #  如果它没有用
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
             # 让我们检查它是否影响其他向量
            for jj in range(ii + 1, BB.dimensions()[0]):
                # 如果另一个向量受到影响：
                # 我们增加计数
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj

            # 等级：0
            # 如果没有其他载体最终受到影响
            # 我们删除它
            if affected_vectors == 0:
                #print ("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB

           # 等级：1
            #如果只有一个受到影响，我们会检查
            # 如果它正在影响别的向量
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # 如果它影响哪怕一个向量
                    # 我们放弃这个
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # 如果没有其他向量受到影响，则将其删除，并且
                # 这个有用的向量不够有用
                #与我们无用的相比
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    #print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    # nothing happened
    return BB

""" 
Returns:
* 0,0   if it fails
* -1，-1 如果 "strict=true"，并且行列式不受约束
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May
    
 在以下情况下找到解决方案：
* d < N^delta
* |x|< e^delta
* |y|< e^0.5
每当 delta < 1 - sqrt（2）/2 ~ 0.292
    """

    # substitution (Herrman and May)
    PR.<u, x, y> = PolynomialRing(ZZ)   #多项式环
    Q = PR.quotient(x*y + 1 - u)        #  u = xy + 1
    polZ = Q(pol).lift()

    UU = XX*YY + 1

    # x-移位
    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
            gg.append(xshift)
    gg.sort()

    # 单项式 x 移位列表
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials(): #对于多项式中的单项式。单项式（）：
            if monomial not in monomials:  # 如果单项不在单项中
                monomials.append(monomial)
    monomials.sort()
    
    # y-移位
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift) # substitution
    
    # 单项式 y 移位列表
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)

    # 构造格 B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)

    #约化格的原型
    if helpful_only:
        #  #自动删除
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
        # 重置维度
        nn = BB.dimensions()[0]
        if nn == 0:
            print ("failure")
            return 0,0

    # 检查向量是否有帮助
    if debug:
        helpful_vectors(BB, modulus^mm)
    
    # 检查行列式是否正确界定
    det = BB.det()
    bound = modulus^(mm*nn)
    if det >= bound:
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print ("size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1, -1
    else:
        print ("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")

    # display the lattice basis
    if debug:
        matrix_overview(BB, modulus^mm)

    # LLL
    if debug:
        print ("optimizing basis of the lattice via LLL, this can take a long time")

    #BB = BB.BKZ(block_size=25)
    BB = flatter(BB)
    
    if debug:
        print ("LLL is done!")

    # 替换向量 i 和 j ->多项式 1 和 2
    if debug:
        print ("在格中寻找线性无关向量")
    found_polynomials = False
    
    pol1_idx = 0
    pol2_idx = 1
            
    # 对于i and j, 构造两个多项式
    
    PR.<w,z> = PolynomialRing(ZZ)
    pol1 = pol2 = 0
    for jj in range(nn):
        pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
        pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)

    # 结果
    PR.<q> = PolynomialRing(ZZ)
    rr = pol1.resultant(pol2)

    
    if not (rr.is_zero() or rr.monomials() == [1]):
        found_polynomials = True

    if not found_polynomials:
        print ("no independant vectors could be found. This should very rarely happen...")
        return 0, 0
    
    rr = rr(q, q)

    # solutions
    soly = rr.roots()

    if len(soly) == 0:
        print ("Your prediction (delta) is too small")
        return 0, 0

    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]
    return solx, soly


def example(pM,qM):
    t1 = time.time()

    size=512     #The size of p; size=1024 in Tables 10
    length_N = 2*size
    s=70;      #s is the number of MSBs exhaustion,  which can be chosen as we need.
    nw=3     #2^nw windows
    delta = 0.292

    N = 107892573713246099817538936816485851035053538530228178586297516104462355899705036416845549988000543254717342505493461294554541098637839010844819316344397595836466293908827352240852019945855020602201742694540642287347823025883131162483705106324646432257707195307227627208850506071985510840207212074649893852289;
    e = 106026779355993573435326995058838659695563314723896436315704944869047461810171317853485834578907922477225219563648678852066399786593146779733369104463848604460901829459576565561299893410357693816050012889075185831684944657633027210516389798278082334754603104594287285628025433146548664548308055805258965566543;
    c = 74801258971353592087655273561994005413765184821038662179717923534370360999501931581907306714940348903440446458261785275314423770475637996343903355116249112854972152857616186571871846360852766323423533588570164035716759526288174656142706806500076294386681134096440267098094279442917447969106043371238327287569;
    # The parameters (N, e) can be chosen as we need. 
    m = 12   # 格大小（越大越好/越慢）
    #guess=100
    # you need to be a lattice master to tweak these
    t = round(((1-2*delta) * m))  # 来自 Herrmann 和 May 的优化
    X = floor(N^delta)  # 
    Y = 2*floor(N^(1/2)/2^s)    # 如果 p、 q 大小相同，则正确
    
    p0=pM*2^(size-s)+2^(size-s-1);
    q0=qM*2^(size-s)+2^(size-s-1)
    #qM=int(q0/2^(size-s))
    A = N + 1-pM*2^(size-s)-qM*2^(size-s);
    P.<x,y> = PolynomialRing(ZZ)
    pol = 1 + x * (A + y)  #构建的方程
    if debug:
        ##print ("=== running algorithm ===")
        start_time = time.time()
            

    solx, soly = boneh_durfee(pol, e, m, t, X, Y)


    if solx > 0:
    #print ("=== solution found ===")
        if False:
            print ("x:", solx)
            print ("y:", soly)

        d_sol = int(pol(solx, soly) / e)
        #print ("私钥d:", d)
        #if(d_sol==d):
        print ("=== solution found ===")
        print ("p的高比特为：",pM)
        print ("q的高比特为：",qM)
        #print("p的真实高比特：",int(p/2^(512-s)))
        #print("q的真实高比特：",int(q/2^(512-s)))
        print ("d=",d_sol)
        
    t2 = time.time()
    print(t2-t1)

example(895381917907042032873,934258518638868635029)

输出内容：

det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)
=== solution found ===
p的高比特为： 895381917907042032873
q的高比特为： 934258518638868635029
d= 686044856631363471654750621230244587429581968036750428251137157884014229839209884769622191
225.63660335540771

~~rec和鸡块师傅tql，看来自己还是太菜了~~

5.[网鼎杯2024] Crypto02

一个简单题:(，混合了好几个密码，主要是椭圆曲线签名中的随机数 $k$ 复用导致私钥泄露。

5o01 题目回顾

# coding: utf-8
#!/usr/bin/env python2

import gmpy2
import random
import binascii
from hashlib import sha256
from sympy import nextprime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
from FLAG import flag
#flag = 'wdflag{123}'

def victory_encrypt(plaintext, key):
    key = key.upper()
    key_length = len(key)
    plaintext = plaintext.upper()
    ciphertext = ''

    for i, char in enumerate(plaintext):
        if char.isalpha():
            shift = ord(key[i % key_length]) - ord('A')
            encrypted_char = chr((ord(char) - ord('A') + shift) % 26 + ord('A'))
            ciphertext += encrypted_char
        else:
            ciphertext += char

    return ciphertext

victory_key = "WANGDINGCUP"
victory_encrypted_flag = victory_encrypt(flag, victory_key)

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
a = 0
b = 7
xG = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
yG = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
G = (xG, yG)
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
h = 1
zero = (0,0)

dA = nextprime(random.randint(0, n))

if dA > n:
    print("warning!!")

def addition(t1, t2):
    if t1 == zero:
        return t2
    if t2 == zero:
        return t2
    (m1, n1) = t1
    (m2, n2) = t2
    if m1 == m2:
        if n1 == 0 or n1 != n2:
            return zero
        else:
            k = (3 * m1 * m1 + a) % p * gmpy2.invert(2 * n1 , p) % p
    else:
        k = (n2 - n1 + p) % p * gmpy2.invert((m2 - m1 + p) % p, p) % p
    m3 = (k * k % p - m1 - m2 + p * 2) % p
    n3 = (k * (m1 - m3) % p - n1 + p) % p
    return (int(m3),int(n3))

def multiplication(x, k):
    ans = zero
    t = 1
    while(t <= k):
        if (k &t )>0:
            ans = addition(ans, x)
        x = addition(x, x)
        t <<= 1
    return ans

def getrs(z, k):
    (xp, yp) = P
    r = xp
    s = (z + r * dA % n) % n * gmpy2.invert(k, n) % n
    return r,s

z1 = random.randint(0, p)
z2 = random.randint(0, p)
k = random.randint(0, n)
P = multiplication(G, k)
hA = multiplication(G, dA)
r1, s1 = getrs(z1, k)
r2, s2 = getrs(z2, k)

print("r1 = {}".format(r1))
print("r2 = {}".format(r2))
print("s1 = {}".format(s1))
print("s2 = {}".format(s2))
print("z1 = {}".format(z1))
print("z2 = {}".format(z2))

key = sha256(long_to_bytes(dA)).digest()
cipher = AES.new(key, AES.MODE_CBC)
iv = cipher.iv
encrypted_flag = cipher.encrypt(pad(victory_encrypted_flag.encode(), AES.block_size))
encrypted_flag_hex = binascii.hexlify(iv + encrypted_flag).decode('utf-8')

print("Encrypted flag (AES in CBC mode, hex):", encrypted_flag_hex)

# output
# r1 = 79874160726532694994695169930412771917232180361879898603881940022649943683773
# r2 = 79874160726532694994695169930412771917232180361879898603881940022649943683773
# s1 = 29358608937016239753744265269188516080175172712689524937715100977220465955435
# s2 = 67554961634695394998835343503747996265453236901689755090159384880221643931064
# z1 = 111511522136129031618364434769531873844221489323948711851532783654702149742966
# z2 = 47212724661755436010060930908038151157054551065082199607150851950104041315615
# ('Encrypted flag (AES in CBC mode, hex):', u'103fb6abfe2757b21f6f9ce6901af904cee9f46ce8adb7d42d0c52e968c6bb5ba0bd2b526db879c5e1fd2f452a2bb67eba3f45fac530f43d878408a763e900eb')

5o02 WP

题目过于简单，不细说了，直接上代码

#!/usr/bin/env python
# coding: utf-8

# In[1]:

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
a = 0
b = 7
xG = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
yG = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
h = 1
E=EllipticCurve(GF(p),[a,b])
G = E(xG, yG)


# In[2]:

r1 = 111817653331957669294460466848850458804857945556928458406600106150268654577388
r2 = 111817653331957669294460466848850458804857945556928458406600106150268654577388
s1 = 86614391420642776223990568523561232627667766343605236785504627521619587526774
s2 = 99777373725561160499828739472284705447694429465579067222876023876942075279416
z1 = 96525870193778873849147733081234547336150390817999790407096946391065286856874
z2 = 80138688082399628724400273131729065525373481983222188646486307533062536927379


# In[3]:

from Crypto.Util.number import *
assert r1==r2
r=r1
#k*s1-r*dA=z1
#k*s2-r*dA=z2
#unknown k,dA
M=matrix(GF(n),[[s1,s2],[-r,-r]])
v=vector(GF(n),[z1,z2])
veckda=v*(M**(-1))
print(veckda)
k,dA=int(veckda[0]),int(veckda[1])
assert isPrime(dA)


# In[4]:

from hashlib import sha256
key = sha256(long_to_bytes(dA)).digest()


# In[5]:

from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
encFlagHex='6c201c3c4e8b0a2cdd0eca11e7101d45d7b33147d27ad1b9d57e3d1e20c7b3c2e36b8da3142dfd5abe335a604ce7018878b9f157099211a7bbda56ef5285ec0b'
ivHex,ciph1=encFlagHex[:32],encFlagHex[32:]
cipher = AES.new(key, AES.MODE_CBC,iv=bytes.fromhex(ivHex))
cipher.decrypt(bytes.fromhex(ciph1))

# Out[5]:
# b'SDSRDO{58UT00432L8228R9E3G927HDWS8D67G2}\x08\x08\x08\x08\x08\x08\x08\x08'

# In[6]:

ciph2='SDSRDO{58UT00432L8228R9E3G927HDWS8D67G2}'


# In[7]:

def victory_encrypt(plaintext, key):
    key = key.upper()
    key_length = len(key)
    plaintext = plaintext.upper()
    ciphertext = ''

    for i, char in enumerate(plaintext):
        if char.isalpha():
            shift = ord(key[i % key_length]) - ord('A')
            encrypted_char = chr((ord(char) - ord('A') + shift) % 26 + ord('A'))
            ciphertext += encrypted_char
        else:
            ciphertext += char
    return ciphertext
def victory_decrypt(plaintext, key):
    key = key.upper()
    key_length = len(key)
    plaintext = plaintext.upper()
    ciphertext = ''

    for i, char in enumerate(plaintext):
        if char.isalpha():
            shift = ord(key[i % key_length]) - ord('A')
            encrypted_char = chr((ord(char) - ord('A') - shift) % 26 + ord('A'))
            ciphertext += encrypted_char
        else:
            ciphertext += char
    return ciphertext
vk = "WANGDINGCUP"
# print(victory_decrypt(ciph2,vk))
flagg=victory_decrypt(ciph2,vk)
assert victory_encrypt(flagg,vk)==ciph2
print(flagg.lower())
assert victory_encrypt(flagg.lower(),vk)==ciph2

# Out[7]:
# wdflag{58ae00432d8228c9e3a927bbcd8d67d2}

6.总结

两个比赛，网鼎杯和强网杯，只能说网鼎杯密码题质量确实挺差的，强网杯题目质量很好。。

强网杯出了 7 个题目，自己做了 3 个，最后队伍第 98 名，距离 32 名线确实还是挺远的。。。

后面等有空补一下强网杯的题目，然后后半学期还有两个pre…和考试。。。也是够忙的:(

CTFSeason4

#ExpLog

24Nov1

http://example.com/2024/11/08/24Nov1/

作者

huangx607087

发布于

2024年11月8日

许可协议

BlockCipher5 上一篇

BlockCipher4 下一篇