巅峰极客2023 Crypto Rosita

偷偷更新应该没人发现吧

浅浅的记录一下。

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

可惜我太久没做ECC，忘记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)*Cout.append(Q)with open('out.tuo', 'w') as f:f.write(str(out)

简短的题目

题目分析

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

所以 p a d ( m ) ∗ R = m ∗ 2 ? ∗ R = = m ∗ R ‘ pad(m)*R=m*2^?*R==m*R^` pad(m)∗R=m∗2?∗R==m∗R‘

转成矩阵表达咯
( m 0 , 0 m 0 , 1 m 0 , 2 ⋮ ⋮ m 72 , 0 m 72 , 1 m 72 , 2 ) × ( R E C ) = ( Q 1 ⋮ Q 72 ) \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} ​m0,0​⋮m72,0​​m0,1​m72,1​​m0,2​⋮m72,2​​ ​× ​REC​ ​= ​Q1​⋮Q72​​ ​
只给出了 Q i Q_i Qi​,还有就是M矩阵的第一列元素均为2^9*8小bits

利用smart attack把离散对数问题变成可解
( Q 1 ⋮ Q 72 ) = ( d 1 ⋮ d 72 ) ∗ G \begin{pmatrix}Q_1\\\vdots\\Q_{72}\end{pmatrix}=\begin{pmatrix}d_1\\\vdots\\d_{72}\end{pmatrix}*G ​Q1​⋮Q72​​ ​= ​d1​⋮d72​​ ​∗G
d i d_i di​是生成元G与 Q i Q_i Qi​的离散对数解

所以现在我们的问题换成了
( m 0 , 0 m 0 , 1 m 0 , 2 ⋮ ⋮ m 72 , 0 m 72 , 1 m 72 , 2 ) × ( R E C ) = ( d 1 ⋮ d 72 ) ∗ G \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 ​m0,0​⋮m72,0​​m0,1​m72,1​​m0,2​⋮m72,2​​ ​× ​REC​ ​= ​d1​⋮d72​​ ​∗G

M = ( m 0 , 0 m 0 , 1 m 0 , 2 ⋮ ⋮ m 72 , 0 m 72 , 1 m 72 , 2 ) D = ( d 1 ⋮ d 72 ) 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} M= ​m0,0​⋮m72,0​​m0,1​m72,1​​m0,2​⋮m72,2​​ ​D= ​d1​⋮d72​​ ​

求解正交格

假设存在一个与 D 正交的矩阵 R = M a t r i x ( 73 , 73 ) R ∗ D = ( 0 ⋮ 0 ) 那么 R ∗ M = ( 0 0 0 ⋮ ⋮ 0 0 0 ) 假设存在一个与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} 假设存在一个与D正交的矩阵R=Matrix(73,73)R∗D= ​0⋮0​ ​那么R∗M= ​0⋮0​00​0⋮0​ ​

找到矩阵R，构建矩阵，这里求正交格就这样造的，自行理解下吧，我也是看相似的题wp才知道的
( E D p ) \begin{pmatrix}E&D\\&p\end{pmatrix} (E​Dp​)
格基规约后,理想情况最后一列D均被规约成0
( R 0 p ) \begin{pmatrix}R&0\\&p\end{pmatrix} (R​0p​)
但是不一定能把所有行都能规约成正交矩阵R。这题73行，有70行被规约成与D正交

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

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

还原M

R ∗ M = ( 0 0 0 ⋮ ⋮ 0 0 0 ) R*M=\begin{pmatrix} 0&0&0\\ \vdots&&\vdots\\ 0&0&0 \end{pmatrix} R∗M= ​0⋮0​00​0⋮0​ ​

所以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/70508E = 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]:breakQ_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]:breakp_times_P = p * P_Qpp_times_Q = p * Q_Qpx_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_Preturn 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]=1M[i,-1]=D[i]
M[-1,-1]=p
R=M.LLL()
LK=[]
for i in R:if i[-1]!=0:breakelse: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='')

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！