巅峰极客2023 Crypto Rosita

偷偷更新应该没人发现吧

浅浅的记录一下。

跟强网杯2022 Lattice 这个有很大的相似之处。这个折磨我好久所以看着太熟悉了

可惜我太久没做ECC，忘记了smart attack 可恶

题目代码

from Crypto.Util.number import bytes_to_long
from hashlib import sha256
from os import urandom
# from secret import p, a, b, flag
p=getPrime(512)
flag=b'flag{??????????????}'
a=randint(1,p-1)
b=randint(1,p-1)
ECC = EllipticCurve(GF(p), [a, b])
R, E, C = [ECC.random_point() for _ in range(3)]
M=Matrix(ZZ,len(flag),3)
pad = lambda m: urandom(8) + m + b'\x00' * (ZZ(p).nbits() // 8 - len(m) - 8 - 1)
out = list()
for i in range(len(flag)):
    m = pad(chr(flag[i]).encode())
    nonce = urandom(16)
    sh = sha256(nonce + m).digest()
    Q = b2l(m)*R + b2l(nonce)*E + b2l(sh)*C
    out.append(Q)

with open('out.tuo', 'w') as f:
    f.write(str(out)

简短的题目

题目分析

很明显pad那部分后面全是0

所以$pad(m)R=m2^?R==mR^`$

转成矩阵表达咯

$$\begin{pmatrix} m_{0,0}&m_{0,1}&m_{0,2}\\ \vdots&&\vdots\\ m_{72,0}&m_{72,1}&m_{72,2} \end{pmatrix}\times \begin{pmatrix}R\\E\\C\end{pmatrix}= \begin{pmatrix}Q_1\\\vdots\\Q_{72}\end{pmatrix}$$

只给出了$Q_i$,还有就是M矩阵的第一列元素均为2^9*8^小bits

利用smart attack把离散对数问题变成可解

$$\begin{pmatrix}Q_1\\\vdots\\Q_{72}\end{pmatrix}=\begin{pmatrix}d_1\\\vdots\\d_{72}\end{pmatrix}*G$$

$d_i$是生成元G与$Q_i$的离散对数解

所以现在我们的问题换成了

$$\begin{pmatrix} m_{0,0}&m_{0,1}&m_{0,2}\\ \vdots&&\vdots\\ m_{72,0}&m_{72,1}&m_{72,2} \end{pmatrix}\times \begin{pmatrix}R\\E\\C\end{pmatrix}=\begin{pmatrix}d_1\\\vdots\\d_{72}\end{pmatrix}*G$$ $$M=\begin{pmatrix} m_{0,0}&m_{0,1}&m_{0,2}\\ \vdots&&\vdots\\ m_{72,0}&m_{72,1}&m_{72,2} \end{pmatrix}\\ D=\begin{pmatrix}d_1\\\vdots\\d_{72}\end{pmatrix}$$

求解正交格

$$假设存在一个与D正交的矩阵R=Matrix(73,73)\\ R*D=\begin{pmatrix}0\\\vdots\\0\end{pmatrix}\\ 那么R*M=\begin{pmatrix} 0&0&0\\ \vdots&&\vdots\\ 0&0&0 \end{pmatrix}$$

找到矩阵R，构建矩阵，这里求正交格就这样造的

$$\begin{pmatrix}E&D\\&p\end{pmatrix}$$

格基规约后,理想情况最后一列D均被规约成0

$$\begin{pmatrix}R&0\\&p\end{pmatrix}$$

但是不一定能把所有行都能规约成正交矩阵R。这题73行，有70行被规约成与D正交

看强网杯2022 Lattice的wp这里这样满足n>m/2就能通过右核矩阵还原出M。其中n是规约后正交的行数，m为给出的数据行数

所以对于得到的70行足够还原出小向量。

还原M

$$R*M=\begin{pmatrix} 0&0&0\\ \vdots&&\vdots\\ 0&0&0 \end{pmatrix}$$

所以M的每一列是矩阵R的右核解，我们要求的M的第一列是R的右核格上。

格基规约后的每行正交性是不变的。且M的第一列是短向量，期望对R求右核矩阵然后规约即可还原出M的第一列。

exp

from Crypto.Util.number import *
p=11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
a=(-10602337004611841904759335148883359090969653658510510358600275641050380448768874133472466281757169086931942865127222834826842856583448958195404187194601748)%p
b=(-3424757783971572799257324035329262490411658894172572005012994558801041224262349740588482997105623017991071214586261721870544696496442896621106306121614953)%p
def smart_attack(P, G, p):
    # https://crypto.stackexchange.com/a/70508
    E = G.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ZZ(t) + randint(0, p) * p for t in E.a_invariants()])

    P_Qps = Eqp.lift_x(ZZ(G.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == G.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == P.xy()[1]:
            break

    p_times_P = p * P_Qp
    p_times_Q = p * Q_Qp

    x_P, y_P = p_times_P.xy()
    x_Q, y_Q = p_times_Q.xy()

    phi_P = -(x_P / y_P)
    phi_Q = -(x_Q / y_Q)
    k = phi_Q / phi_P
    return ZZ(k)
E = EllipticCurve(GF(p), [a, b])
D=[]
G=E.gens()[0]
for i in range(len(res)):
    temp_Q=E(res[i][0],res[i][1])
    D.append(smart_attack(temp_Q,G,p))
#有亿点点久

M=Matrix(ZZ,74,74)
for i in range(73):
    M[i,i]=1
    M[i,-1]=D[i]
M[-1,-1]=p
R=M.LLL()
LK=[]
for i in R:
    if i[-1]!=0:
        break
    else:
        LK.append(i[:-1])
print(len(LK))
LK=Matrix(ZZ,LK)
key=Matrix(ZZ,LK.right_kernel().basis()).LLL()[0]
for i in key:
    print(chr(long_to_bytes(ZZ(i))[-1]),end='')