Crypto - Common
CHS version
-
简单的
Factoring with High Bits Known, sage 构造对应 polynomial 使用自带的small_roots可以解出hint = '3-540-46701-7_14 or 2009/037' -
记 Wiener equations 和 Guo equations 为
$$ W_i : e_i d_i g − k_i N = g − k_i s \ G_{i,j} : k_i d_j e_j − k_j d_i e_i = k_i − k_j $$
则 $k_1 k_2 = k_1 k_2, k_2 W_1, g G_{1,2}, W_1 W_2$ 转化成矩阵形式, 有 $x B = v$, 其中 $$ x = (k_1 k_2, k_2 d_1 g, k_1 d_2 g, d_1 d_2 g^2 ) \
B = \begin{bmatrix} 1 & −N & 0 & N^2 \ & e_1 & −e_1 & −e_1 N \ & & e_2 & −e_2 N \ & & & e_1 e_2 \end{bmatrix} \
v = ( k_1 k_2, k_2 (g − k_1 s), g(k_1 − k_2 ), (g − k_1 s)(g − k_2 s) )
$$
令 $D = diag(N, N^{1/2}, N^{1+δ}, 1)$, 使其满足 Minkowski’s bound, 有 $||vD|| < vol(L) = |det(B) det(D)|$
即 $N^{2(1/2+δ)} < 2N^{(13/2+δ)/4}$, $\delta < 5/14 - \epsilon$.
-
利用
LLL求出最短向量 $vD$, 进而求出 $x$, 根据Wiener’s attack,$\phi(N) = g(ed-1)/k = floor(edg/k)$
-
有了 $\phi(N)$ 即可构造一元二次方程分解 $N$.
EN version
The first part is a typical Factoring with High Bits Known problem, we can solve it with small_roots in sage.
hint = '3-540-46701-7_14 or 2009/037'The two related paper [1] [2] were given in the hint, each enough to get the flag.
Denote Wiener equations and Guo equations by
$$ W_i : e_i d_i g − k_i N = g − k_i s \ G_{i,j} : k_i d_j e_j − k_j d_i e_i = k_i − k_j $$
Then we have $k_1 k_2 = k_1 k_2, k_2 W_1, g G_{1,2}, W_1 W_2$. Write them in a matrix form, we get $x B = v$, where $$ x = (k_1 k_2, k_2 d_1 g, k_1 d_2 g, d_1 d_2 g^2 ) \
B = \begin{bmatrix} 1 & −N & 0 & N^2 \ & e_1 & −e_1 & −e_1 N \ & & e_2 & −e_2 N \ & & & e_1 e_2 \end{bmatrix} \
v = ( k_1 k_2, k_2 (g − k_1 s), g(k_1 − k_2 ), (g − k_1 s)(g − k_2 s) ) $$ Multiply the equation by the diagonal matrix $D = diag(N, N^{1/2}, N^{1+δ}, 1)$, from Minkowski's Theorem, $||vD|| < vol(L) = |det(B) det(D)|$, yields $\delta < 5/14 - \epsilon$. Since our problem satisfies this condition, we can find the shortest vector $vD$ with LLL algorithm.
Then we can get the $\varphi(N)$ and factor the modulus.