huangx607087学习格密码的笔记6

100天的时间，自己终于把NCTF那道题研究了出来，wtcl

1. RSA WienerAttack

$$|a-\dfrac c d| < \dfrac 1 {2d^2}$$

$$|\dfrac e n - \dfrac k {dg}|=|\dfrac 1 {dn}-\dfrac {ks}{dgn}|<\dfrac {ks}{dgn}<\dfrac 1 {2(dg)^2}$$

$$edg=k(p-1)(q-1)+g,k>g$$

$$\mathrm{floor}(\dfrac{edg}{k})=(p-1)(q-1)$$

$$\dfrac{pq-(p-1)(q-1)+1} 2=\dfrac {p+q} 2$$

$$(\dfrac{p+q}2)-pq=(\dfrac{p-q}2)^2$$

2. Extend Wiener Attack 2D

$$edg=k(p-1)(q-1)+g,k>g$$

$$edg-kn=g+ks$$

$$e_1d_1g_1=g+k_1(p-1)(q-1),e_2d_2g_2=g+k_2(p-1)(q-1)$$

$$k_2d_1e_1-k_1d_2e_2=k_2-k_1$$

$$\dfrac {e_1} {e_2}-\dfrac{k_1d_2}{k_2d_1}=\dfrac {k_2-k_1}{k_2d_1e_2}$$

$$k_2d_1e_1g-k_1d_2e_2g=k_2g-k_1g[1]$$

$$d_1gk_2e_1-k_1k_2n=k_2g+k_1k_2(pq-p-q+1)=k_2g+k_1k_2s[2]$$

$$(e_1d_1g-k_1n)(e_2d_2g-k_2n)=(g+k_1s)(g+k_2s)[3]$$

$[3]$可以继续进行化简，得到：
$$d_1d_2g^2e_1e_2-d_1gk_2e_1n-d_2gk_1e_2n+k_1k_2n^2=(g+k_1s)(g+k_2s)[3]$$

$$\vec w=(k_1k_2n,k_2g-k_1g\sqrt{n},k_2g+k_1k_2sn^{1+b},(g+k_1s)(g+k_2s))$$

$$2\sqrt[4]{\det A}=2n \sqrt[8]{13+2b}$$

4. 3D & 4D Expand WienerAttack

$n$ $1$ $2$ $3$ $4$ $5$ $6$ $≥7$
$\dfrac{\ln d}{\ln n}$ $0.25$ $0.357$ $0.4$ $0.441$ $0.468$ $0.493$ $0.5$

$$[W_1]:e_1d_1g-k_1n=g+k_1s$$

$$[G_{(12)}]:e_2e_2k_1-e_1d_1k_2=k_2-k_1$$

$$\vec v_3=(k_1k_2k_3,d_1k_2k_3g,k_1d_2k_3g,d_1d_2k_3g^2,k_1k_2d_3g,d_1k_2d_3g^2,k_1d_2d_3g^2,d_1d_2d_3g^3)$$

$1$ $2$ $3$ $4$
$k_1k_2k_3$ $W_1k_2k_3$ $G_{12}k_3g$ $W_1W_2k_3$
$5$ $6$ $7$ $8$
$k_2G_{13}$ $W_1G_{23}g$ $W_{2}G_{13}g$ $W_1W_2W_3$

$$P_3=\mathrm{diag}(1,e_1,e_2,e_1e_2,e_3,e_1e_3,e_2e_3,e_1e_2e_3)$$

$Q_{ii}$ $n^{1.5}$ $n$ $n^{1.5+b}$ $n^{0.5}$

$Q_$ $n^{1.5+b}$ $n^{1+b}$ $n^{1+b}$ $1$

$$Q_3=\mathrm{diag}(n^{1.5},n,n^{1.5+b},n^{0.5},n^{1.5+b},n^{1+b},n^{1+b},1)$$

$$P_4=\mathrm{diag}(1,e_1,e_2,e_1e_2,e_3,e_1e_3,e_2e_3,e_1e_2e_3,e_4,e_1e_4,e_2e_4,e_1e_2e_4,e_3e_4,e_1e_3e_4,e_2e_3e_4,e_1e_2e_3e_4)$$

$$Q_4=\mathrm{diag}(n^2,n^{1.5},n^{2+b},n,n^{2+b},n^{1.5+b},n^{1.5+b},n^{0.5},n^{2+b},n^{1.5+b},n^{1.5+b},n^{1+b},n^{1.5+b},n^{1+b},n^{1+b},1)$$

6.总结

RSA与格密码的结合，还是比较难的（，自己NCTF在放题后100天，本地复现的时候才做出来（（（

目录