week1:
EzAES
题面:
1 | from Crypto.Cipher import AES |
题解:
1 | from Crypto.Util.number import * |
Hello_Crypto
题面:
1 | from Crypto.Util.number import bytes_to_long |
题解:
1 | from Crypto.Util.number import * |
baby_mod
题面:
1 | from Crypto.Util.number import * |
分析:
tmp的位数比较小,可以爆破
$$
模去r:-(leak+tmp) ≡ q*t\ \ mod \ r\
q =-(leak+tmp)inv(t,r)\ \ mod\ r\
模去t:(leak+tmp) ≡ pr\ \ mod \ t\
q =(leak+tmp)*inv(r,t)\ \ mod\ t
$$
题解:
1 | from Crypto.Util.number import * |
factor
题面:
1 | from Crypto.Util.number import * |
题解:
1 | from Crypto.Util.number import * |
d_known
题面:
1 | from Crypto.Util.number import * |
分析:
已知d求n,由于e*d = 1+kphi,当e很小时k也会很小,可以爆破。
如果e很大的时候可以用更快的方法(wiener
题解:
1 | from Crypto.Util.number import * |
week2:
E&R
题面:
1 | #sage |
分析:
flag被分为了两段,第一段用RSA
加密,第二段用ECC
加密
先分析第一段:
p⊕(q的反序列) ,所以采用首尾剪枝,
搜索方式:
-
从两端向中间搜索
-
每一次搜索,需要利用当前p_xor_q 两端的bit位。这是因为,p_xor_q的当前最高位对应p的最高位以及q的最低位,p_xor_q的当前最低位对应p的最低位及q的最高位(最高与最低都是相对于当前搜索而言)
-
如果当前需要搜索的最高位为"1",则对应两种可能:p该位为1,q对应低位为0;p该位为0,q对应低位为1。剩下依此类推
剪枝条件:
- 将p,q未搜索到的位全填“0”,乘积应小于n
- 将p,q未搜索到的位全填“1”,乘积应大于n
- p,q低k位乘积再取低k位,应与n的低k位相同
如此进行剪枝即可:
先分析第一段:
已知 P = G * e,m1为G的横坐标x,现在我们要求的就是G
$$
\because y^2≡x^3+ax+b\ mod\ n,n=p×q\
\therefore y同时满足下列方程组\
y^2≡x^3+ax+b\ mod\ p\
y^2≡x^3+ax+b\ mod\ q\
将x代入计算:\
y^2 ≡y_p^2\ mod\ p\
y^2 ≡y_q^2\ mod\ q\
对于y^2 ≡y_p^2\ mop\ p\
有(y+y_p)(y-y_p) ≡ 0\ mod\ p\
\therefore y≡y_p\ mod\ p\
同理y≡y_p\ mod\ q\
令前式中的y_p,y_q对应的k为k_p,k_q \
y = k_pp+y_p = k_qq+y_q\
k_pp=k_qq+y_2-y_1\
设p对q取逆为p^{-1},有p^{-1}p≡1\ mod\ q\
(y_q-y_p)p^{-1} p≡y_2-y_1\ mod\ q\
k_p = (y_q-y_p)p^{-1}\
此时y^{'}=(y_q-y_p)p^{-1}p+y_1\
对n取模后,即可得到y
$$
接下来看下面的推导:
$$
P≡G ·e\
已知e和P,需要得到G\
记G生成元的阶为n,即nG= 0\
e与n互素时,记e^{-1} 为e对n的逆元,即e·e^{-1}≡1\ mod\ n \
有e·e^{-1} = kn+1\
\therefore e·e^{-1}P = e^{-1}Q = knP+P = P\
\therefore P = e^{-1}Q\
注意本题中的n不是素数,所以求不出阶Zmod(n)的椭圆曲线的阶\
$$
所以,先求模p,q下的阶,再相乘
题解:
1 | from Crypto.Util.number import * |
ezECC
题面:
1 | from Crypto.Util.number import * |
分析:
$$
M = C-A2\
又A2 = k*A1,则我们要先得到椭圆曲线的方程,即得到a,b\
目前我们已经知道了曲线上的两个点,A1和C的坐标\
$$
推导一下求a和b的公式:
$$
y_1^2 ≡ x_1^3+ax_1+b\ mod\ p\
y_2^2 ≡ x_2^3+ax_2+b\ mod\ p\
y_1^2-y_2^2 = x_1^3-x_2^3+ax_1-ax_2 \ mod\ p\
故a = (y_1^2-y_2^2-(x_1^3-x_2^3))*inv(x_1-x_2)\
b=y_1^2 - x_1^3-ax_1\ mod\ p
$$
至此我们就已经得到了椭圆曲线的方程了,接下来我们把A1,C代入曲线,然后计算出M即可
但此处的M是next_prime(bytes_to_long(flag)),所以需要爆破一下
题解:
1 | from Crypto.Util.number import * |
worde很大
题面:
1 | import gmpy2 |
分析:
dp泄露,
$$
dp ≡d\ mod\ (p-1)\
\because dp·e≡d·e≡1\ mod\ (p-1)\
\therefore dp·e-1 = k(p-1)\
\therefore d·e = -k^{‘}(p-1)+dp·e ≡ 1 \ mod\ (p-1)\
\Longleftrightarrow -k^{’}(p-1)+dp·e≡1\ mod\ \phi(n)\
\therefore k_1(p-1)+dp·e-1=k_2(p-1)(q-1)\
\Longleftrightarrow (p-1)(k_2(q-1)-k_1)+1=dp·e\
\because dp<p-1\
\therefore (k_2(p-1)-k_1)\in (0,e)\
\therefore 遍历(1,e),当满足(dp·e-1)\ mod\ i ==0及n\ mod\ ((dp·e-1)//i+1) == 0
$$
题解:
可以用轩禹RSA工具一把梭:
魔鬼的步伐
题面:
1 | from Crypto.Util.number import * |
分析:
n-1为光滑数,直接用工具或者在线工具不能分解出来,所以考虑使用Pollard’s p-1分解算法
$$
如果一个整数的所有素因子都不大于B,我们称之为B-smooth数\
设p-1是B-smooth,可设p-1=p_1p_2…p_n(\forall1\leq i\leq n,p_i\leq B)\
若p_1,p_2,…,p_n两两不同,则p_1p_2…p_n|B! \ \implies B!=k(p-1)\
因此a^{B!}≡a^{k(p-1)}≡ 1\ (mod\ p),假设N=pq,计算gcd(a^{B!}-1,N)\
只要结果大于0小于N,那么结果就为p
$$
所以先用题面里的primes生成素因子表,然后用Pollard算法
题解:
1 | from Crypto.Util.number import * |
week3:
Lattice
题面:
1 | import gmpy2 |
分析:
一眼NTRU格密码,这里解释一下NTRU的攻击手段
考虑等式
$$
h\ =\ gf^{-1}\ (mod\ p)
$$
对其变形得到
$$
f·h\ =\ g\ (mod\ p)\ = g+kp
$$
改写为矩阵乘法,得到
$$
(f,-k)*\begin{bmatrix}
1 & h\
0 & p
\end{bmatrix}\ =\ (f,g)
$$
注意:
这里我们建立的矩阵就是一个格
下面我们令:
$$
L\ =\ \begin{bmatrix}
1 & h\
0 & p
\end{bmatrix}
$$
而上面那个矩阵乘法说明**(f,g)在格L上,所以我们能用svp问题的解法来解,也就是LLL格基规约算法**来解。
题解:
1 | from Crypto.Util.number import * |