# 0x02 ChildRSA

## problem

sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots(self, X=None, beta=1.0, epsilon=None, **kwds)

​ Let $N$ be the characteristic of the base ring this polynomial is defined over: N = self.base_ring().characteristic(). This method returns small roots of this polynomial modulo some factor $b$ of $N$ with the constraint that $b>=N^β$. Small in this context means that if $x$ is a root of $f$ modulo $b$ then $|x|<X$. This $X$ is either provided by the user or the maximum $X$ is chosen such that this algorithm terminates in polynomial time. If $X$ is chosen automatically it is $X=ceil(1/2N^{β^2/δ−ϵ})$. The algorithm may also return some roots which are larger than X. This algorithm in this context means Coppersmith’s algorithm for finding small roots using the LLL algorithm. The implementation of this algorithm follows Alexander May’s PhD thesis referenced below.

INPUT:

• X – an absolute bound for the root (default: see above)
• beta – compute a root mod $b$ where $b$ is a factor of N and $b ≥N^β.$ ( Default: 1.0, so $b=N$. )
• epsilon – the parameter $ϵ$ described above. (Default: $β/8$)
• **kwds – passed through to method Matrix_integer_dense.LLL().

REFERENCES:

Don Coppersmith. Finding a small root of a univariate modular equation. In Advances in Cryptology, EuroCrypt 1996, volume 1070 of Lecture Notes in Computer Science, p. 155–165. Springer, 1996. http://cr.yp.to/bib/2001/coppersmith.pdf

• $X$: 这个算是最好填的, 可以理解成smallroot的上界, 一般来说题目中给出了要解的小根的位数kbits就设置$X = 2^{kbits}$. 而在Csp atk中, 理论可解上界是$N.nbits \over e^2$
• $\beta$: 这个$\beta$可以理解成$N$的因子的下界, 对于常规RSA中的$N$, 一般就只有$1,N,p,q$四个因子, 我们可以选取$N,p,q$作为算法使用的因子, 所以其实$\beta$可以从0取到1, 因为都可能成立, 但真正用的时候一般取$[0.4,0.6] \cup {1}$.
• $\epsilon$: 神奇的参数, 不填就是$\beta \over 8$, 文档中给出了一个关系式$X=ceil(1/2N^{β^2/δ−ϵ})$, 其实这个$ceil$可以暂时忽略掉, 所以就有$2X=N^{\beta^2/\delta-\epsilon}$, 文档里并没有给出$\delta$ 到底该如何取, 但从这题的官方wp中是给出了$\delta = e^2$, 其实就是多项式的次数. 所以对于Csp atk来说, $\epsilon = \beta^{2} / e^2 - x$, $x$的取法为$N^x = X.nbits$

### exp

$$r_3 = 2^{1000}+ 2^{200}f \\ r_4 = 2^{1001}+ 2^{200}pd \\ (r_3r_4)^3 = c_3$$

## 解方程解法

$$2^{2001} + 2^{1200}pd +2^{1201}f+ 2^{400} pd \cdot f = r_{34} \tag1$$

$$2^{2001} + 2^{1200}pd +2^{1201}f+ 2^{400} pd \cdot f \equiv 2^{400}pd \cdot f \equiv r_{34} \mod 2^{1200} \\ 2^{400}pd \cdot f = r_{34} % \ 2^{1200}$$

$$2^{2001} \cdot f + 2^{1200} a +2^{1201}f^2+ 2^{400} a \cdot f = r_{34} \cdot f$$