EzECC:
题面:
1 | from Crypto.Util.number import * |
分析:
add()和mul()是用python写的椭圆曲线的加法和乘法
$$
\begin{align}C_1 &= M+rK\
&C_2 = rG
\end{align}
$$
可以通过先求出r,然后再用减法来求M
题解:
1 | from Crypto.Util.number import * |
LLL-FirstBlood:
题面:
1 | from random import randrange |
分析:
$$
M = \begin{pmatrix}m_1 &m_2 &m_3 &m_4\
noise_{1,1} &noise_{1,2} &noise_{1,3} &noise_{1,4}\
noise_{2,1} &noise_{2,2} &noise_{2,3} &noise_{2,4}\
noise_{3,1} &noise_{3,2} &noise_{3,3} &noise_{3,4}
\end{pmatrix}\ \ \ A=\begin{pmatrix}
A_{1,1} &A_{1,2} &A_{1,3} &A_{1,4}\
A_{2,1} &A_{2,2} &A_{2,3} &A_{2,4}\
A_{3,1} &A_{3,2} &A_{3,3} &A_{3,4}\
A_{4,1} &A_{3,2} &A_{3,3} &A_{3,4}
\end{pmatrix}
$$
又 C = A*M
对C用LLL算法,可以得到m~1~,m~2~,m~3~,m~4~
题解:
1 | from Crypto.Util.number import * |
LLL-SecondBlood:
题面:
1 | from Crypto.Util.number import * |
分析:
$$
C_i ≡ a_i*m +b_i\ \ (mod\ p)\
b_i = C_i-a_im+kp
$$
构造格:
$$
\begin{pmatrix}k_1&k_2&k_3&k_4&m&1\end{pmatrix}
\begin{pmatrix}p &0&0&0&0&0\
0 &p &0&0&0&0\
0 &0 &p&0&0&0\
0 &0&0&p&0&0\
-a_1 &-a_2 &-a_3 &-a_4 &1 &0\
C_1 &C_2 &C_3 &C_4 &0 &2^{318}
\end{pmatrix}=\begin{pmatrix}b_1&b_2&b_3&b_4&m&2^{318}\end{pmatrix}
$$
题解:
1 | from Crypto.Util.number import * |
EzMatrix:
题面:
1 | from Crypto.Util.number import getPrime |
分析:
$$
可知A^m=C,由线性代数知识可知,存在可逆矩阵P\
使得P^{-1}AP=B\ \ (B为对角矩阵)\
故B^m=P^{-1}A^mP=P^{-1}CP\
$$
$$
根据对角矩阵次方的性质(即对角线上的元素自乘),这样就把矩阵的乘法转化为了\
b^m ≡c\ mod\ p这样的离散对数问题,只要用B和C中任意对应的元素即可
$$
可以利用sage自带的diagonalization()求解
题解:
1 | from Crypto.Util.number import * |