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 * |