### RSA - How to Use openssl

Given flag.enc, pubkey.pem/pub.key

Then we get (e, n), after getting d:

### RSA - Given (e, d, (n))

#### Theorem

1. [Initialize] Set $k\leftarrow d\cdot e-1$
2. [Try a random g] Choose random small primes g = 2, 3, 5, 7, …
3. [Next k] If $2\mid k,k\leftarrow\frac{k}{2}$ and $x\leftarrow g^k$ mod n, else go to step 2 (g $\leftarrow$ next_prime(g))
4. [Finish?] If $y\leftarrow gcd(x-1,n)\ mod\ n>1,p\leftarrow y,q\leftarrow n//y$, quit. Else go to step 3.

#### Note

Given only (e, d) - [NCTF2019] babyRSA

### RSA - Given (e, dp, n)

#### Theorem

$\because dp\cdot e\equiv d\cdot e\equiv 1(mod\ (p-1))$

$\therefore dp\cdot e-1=k\cdot (p-1)$

$\because dp\cdot e\equiv d\cdot e\equiv 1(mod\ (p-1))$

$\therefore dp\cdot e-1=k\cdot (p-1)$

$\therefore (dp\cdot e-1)\cdot d\cdot e=k’\cdot (p-1),\quad k’=k\cdot d\cdot e$

$\Leftrightarrow d*e=-k’\cdot (p-1)+dp\cdot e\cdot d\cdot e\equiv 1(mod\ \varphi(n))\Leftrightarrow -k’\cdot (p-1)+dp\cdot e\equiv 1(mod\ \varphi(n))$

$\therefore k_{1}\cdot (p-1)+dp\cdot e-1=k_{2}\cdot (p-1)\cdot (q-1)\Leftrightarrow (p-1)\cdot (k_{2}\cdot (q-1)-k_{1})+1=dp\cdot e$

$\because dp<p-1\quad \therefore (k_{2}\cdot (q-1)-k_{1})\in (0, e)$

$\therefore$遍历i in range(1, e)，当同时满足

$(dp\cdot e-1)\%i==0$和$n\%((dp\cdot e-1)//i+1)==0时$，N成功分解.

### RSA - Given (p, q, dp, dq)

#### Theorem

$d\equiv dp(mod\ (p-1)),d\equiv dq(mod\ (q-1))\rightarrow ext_CRT\ (\because gcd(p-1,q-1)$不一定等于1)

$\because d=k_{1}(p-1)+dp=k_{2}(q-1)+dq\Leftrightarrow k_{1}(p-1)=(dq-dp)+k_{2}(q-1)$

$\Leftrightarrow k_{1}\frac{p-1}{gcd(p-1,q-1)}=\frac{dq-dp}{gcd(p-1,q-1)}+k_{2}\frac{q-1}{gcd(p-1,q-1)}$

$\Rightarrow k_{1}\frac{p-1}{gcd(p-1,q-1)}\equiv\frac{dq-dp}{gcd(p-1,q-1)}(mod\ \frac{q-1}{gcd(p-1,q-1)})$

$\Leftrightarrow k_{1}\equiv invert(\frac{p-1}{gcd(p-1,q-1)},\frac{q-1}{gcd(p-1,q-1)})\cdot \frac{dq-dp}{gcd(p-1,q-1)}(mod\ \frac{q-1}{gcd(p-1,q-1)})$

$d=k_{3}\frac{(p-1)(q-1)}{gcd(p-1,q-1)}+invert(\frac{p-1}{gcd(p-1,q-1)},\frac{q-1}{gcd(p-1,q-1)})\cdot \frac{(dq-dp)(p-1)}{gcd(p-1,q-1)}+dp$

$\Rightarrow d\equiv invert(\frac{p-1}{gcd(p-1,q-1)},\frac{q-1}{gcd(p-1,q-1)})\cdot \frac{(dq-dp)(p-1)}{gcd(p-1,q-1)}+dp(mod\ \frac{(p-1)(q-1)}{gcd(p-1,q-1)})$

### RSA - Wiener’s Attack

#### Theorem

$Since\ ed\equiv 1(mod\ \varphi(N)),\exists k\in N,s.t.\ ed=k\varphi(N)+1\Rightarrow\left|\frac{e}{\varphi(N)}-\frac{k}{d}\right|=1.$
From q<p<2q, it follows $\sqrt{N}<p<\sqrt{2N}$, hence
$N-\varphi(N)=p+q-1=p+\frac{N}{p}-1<\frac{3\sqrt{2}}{2}\sqrt{N}<3\sqrt{N}$
$\therefore\left|\frac{e}{N}-\frac{k}{d}\right|=\left|\frac{ed-k\varphi(N)+k\varphi(N)-kN}{Nd}\right|=\left|\frac{1+k(\varphi(N)-N)}{Nd}\right|\leq\left|\frac{3k\sqrt{N}}{Nd}\right|=\left|\frac{3k}{\sqrt{N}d}\right|$
$\because k\varphi(N)=ed-1<ed,\ e<\varphi(N)\quad \therefore k\varphi(N)<d\varphi(N)\rightarrow k<d<\frac{1}{3}N^{\frac{1}{4}}$
$\therefore\left|\frac{e}{N}-\frac{k}{d}\right|\leq\left|\frac{3k}{\sqrt{N}d}\right|<\left|\frac{3k}{\sqrt{N}d}\right|<\frac{1}{3d\cdot d}<\frac{1}{2d^2}$

Therefore,we can get $\frac{k}{d}$ from the convergents of $\frac{e}{N}$.

### RSA - Partial_m

#### Theorem

$|x_{0}|\leq \frac{1}{2}N^{\frac{\beta^{2}}{\delta}-\epsilon}$

$|x_{0}|\leq N^{\frac{1}{\delta}}$

$\therefore$ e足够小，且部分明文泄露时，可以采用coppersmith单变量模等式的攻击，如下：

$c:=m^{e}\ mod\ n=(mbar+x_{0})^{e}\ mod\ n$ , (mbar = (m >> kbits) << kbits)

#### Note

m高位泄露是coppersmith的原版结论，实际上可以扩展到高位/低位/高低位泄露的一般情况

$m=M+x_{0}\cdot 2^{k}+M’$

$f_{n}(x):=(M+x_{0}\cdot 2^{k}+M’)^{e}-c$

### RSA - Partial_p

#### Theorem

Proof：

$f_{p}(x):=x+\widetilde{p}$的一个解$x_{0}=(kp-\widetilde{p})\ mod\ p$ 满足$x_{0}\leq 2N^{\frac{1}{4}}$。该多项式首1，且$p\geq N^{\frac{1}{2}}$，由定理1知该方程有解

#### Note

sage的small_root传参X不能过大，需自行判断阈值并调整（如果X过大，即使存在X内的解，也无法求出）

### RSA - Partial_d

#### Theorem

Given the $\frac{n.nbits()}{4}$ least significant bits of d，we can compute all of d in polynomial time in n and e.

Proof：

$s \leftarrow p+q$，$ed=1+k\phi (n)=1+k(n-s+1)$

$\therefore ed_{0}\equiv 1+k(n-s+1)\ mod\ 2^{\frac{n}{4}}\quad (1)$

$\because p^{2}-sp+n\equiv 0\ mod\ 2^{\frac{n}{4}}\quad (2)$

$\therefore p\cdot(1),k\cdot(2)\rightarrow ed_{0}p\equiv p+kpn-kp^{2}-kn+kp\ mod\ 2^{\frac{n}{4}}\quad (2)$

$\therefore$解一元同余方程$ed_{0}x-kx(n-x+1)+kn\equiv x\ (mod\ 2^{d_{0}.nbits()})$即可得到p的部分低位$p_{0}$

#### Theorem

sage里可以用resultant来实现结式计算，$g_{1}.resultant(g_{2})$默认将结式以第二个变量来表示，也可以指定$g_{1}.resultant(g_{2},y)$来将结式以x表示

#### Note

exp的change_ring缺失即报错，但同环下转换的具体原因，估计要翻sage手册orz

### RSA - $gcd(e,\varphi(n)\neq 1)$

#### Theorem

$gcd(e,\varphi(n))\neq 1$时，$e’\leftarrow e//gcd(e,\varphi(n)),d\leftarrow invert(e’,\varphi(n))$，$c^{d}\equiv m^{gcd(e,\varphi(n))}\ mod\ n$

#### Example

De1CTF2019 - Baby RSA

p, q1, q2 均为素数，$f_{1}=gcd(e_{1},\varphi(pq_{1}))\neq 1,f_{2}=gcd(e_{2},\varphi(pq_{2}))\neq 1$

$m_{3}\equiv m^{2}\ mod\ n_{3}$

### RSA - Polynomial based RSA

#### Theorem

$\because$ P, Q均为既约多项式，
$\therefore\varphi(P)=p^{P.degree()}-1,\varphi(Q)=p^{Q.degree()}-1,\varphi(N)=(p^{P.degree()}-1)\cdot (p^{Q.degree()}-1)$

1. 对应ascii码作多项式系数

2. 在$GF(p^{nbits})$上fetch_int

### RSA - Large Common Factor of p-1 and q-1

#### Theorem

Given $N=pq,g|(p-1),g|(q-1)$. (We call it common prime RSA)

If g is large enough, we have an efficient factoring method for N. (魔改rho)

[可行分析]

$p-1=ga,q-1=gb,N-1=gh(h=gab+a+b)$
$\therefore x^{N-1}\ (mod\ p)$至多有a个值
$\therefore$用$x\rightarrow x^{N-1}+3$代替rho中的迭代函数，能在$O(\sqrt a)=O(N^{1/4-\gamma /2})$下分解N.

#### More

common prime RSA在g过小时，g也能轻易通过分解N-1来解出（rho等算法分解出的小因子尝试即可）

### RSA - Small CRT Private Exponents

#### Theorem

LLL计算后的约化基$\\{b_{1},b_{2},b_{3}\\}$，选取一个适当的上界M，令$|a_{i}|\leq M$, 则验证线性组合$v=a_{1}b_{1}+a_{2}b_{2}+a_{3}b_{3}$对应的$x,y,z,\omega$，看得到的数据能否正确分解N即可.

M视具体情况而定

### RSA - Parity Oracle

#### Theorem

$c\equiv m^{e}(mod\ N)$, 向oracle机发送$2^{e}c\equiv (2m)^{e}(mod\ N)$,则返回奇时，说明$2m>N$，反之$2m<N$

### RSA - William’s p+1 and Pollard’s p-1

#### Theorem

• William’s p+1 Algorithm

Step 1：选择整数A(A>2)来表征卢卡斯序列$V_{j}=AV_{j-1}-V_{j-2}$，并初始化$V_{0}=2,V_{1}=A$.

Step 2：计算序列到$j=m!$.

​ ps：这步有很大的操作空间（在More里会涉及相关简化计算和证明）

Step 3：计算$gcd(V_{j}-2,N)$，如果结果等于1或N，则m++并返回Step2，否则进入Step4.

Step 4：检查p+1是否是m!的因子，如果是，则说明找到的p是p+1平滑的.

因为我们事先不知道p，所以也就无从计算雅各比符号(D/p)，但平方非剩余概率趋于1/2，考虑选取多个A多线程即可（n个A就能使互斥事件的概率降到大约$\frac{1}{2^{n}}$）

• Pollard’s p-1 Algorithm

p-1是B-smooth时，很大概率上$(p-1)|B!$（不考虑p-1有很多重复的趋近于B的质因子）

所以计算$a^{m!}-1$，以及校验gcd即可，$m_{max}$可以是B也可以适当上调.

#### More

Lucas Functions：设$\alpha,\beta$是$x^{2}-Px+Q=0$的根，且有

p为奇素数，且$p\nmid Q$，勒让德符号$(\frac{\Delta}{p})=\epsilon$，则有

https://math.boisestate.edu/~liljanab/BOISECRYPTFall09/Sundling.pdf

https://www.ams.org/journals/mcom/1982-39-159/S0025-5718-1982-0658227-7/S0025-5718-1982-0658227-7.pdf

### RSA - Square Root in $F_{p}$

#### Theorem

Given $b^{2}\equiv a(mod\ p)$

• Case 1：$p\equiv 3(mod\ 4)\rightarrow b:=\pm a^{\frac{p+1}{4}}(mod\ p)$

• Case 2：Cipolla’s algorithm（一般性）

• Step 1：在$F_{p}$上找到一个t，使得$u:=t^{2}-a$是一个模p的平方非剩余（因为平方非剩余的概率趋于1/2，所以随机选取并用欧拉判别即可）

• Step 2：定义$F_{p^{2}}=F_{p}(\sqrt{t^{2}-a})=\\{x+y\sqrt{t^{2}-a}:x,y\in F_{p}\\}$，关于$F_{p^{2}}$是域的证明此处略. （当然，$\omega:=\sqrt{t^{2}-a}$在$F_{p}$上不存在，因此类似虚数存在）.先来证明两个引理：(1) $(x+y\omega)^{p}=\sum_{i=0}^{p}C_{p}^{i}x^{p-i}(y\omega)^{i}$，因为u是平方非剩余，所以$\omega^{p-1}=(\omega^{2})^{\frac{p-1}{2}}=u^{\frac{p-1}{2}}=-1$. 且p均整除二项式展开中间系数，上式可转化为$x^{p}+y^{p}\omega^{p}(费马小定理)=x+y\omega^{p}=x-y\omega$.；(2) $((t+\omega)^{\frac{p+1}{2}})^{2}=(t+\omega)^{p+1}=(t+\omega)(t-\omega)=t^{2}-\omega^{2}=a$.

所以计算$(t+\omega)^{\frac{p+1}{2}}$即为二次根b.

• Case 3：Atkin’s algorithm（$p\equiv 5(mod\ 8)$）

$c\leftarrow (2a)^{\frac{p-5}{8}}$

$i\leftarrow 2ac^{2}$

$b\leftarrow ac(i-1)$

### RSA - $e\mid (p-1),e\mid (q-1)$

#### Theorem

• New r-th root extraction formula over $F_{q}$ for $q\equiv lr^{s}+1(mod\ r^{s+1})$ and r is a prime

[Theorem 1]

Proof：

$\because gcd(r,l)=1\quad \therefore\exists(\alpha,\beta),s.t.\ r\beta +r-1=l\alpha$.

$\alpha =\frac{r\beta +r-1}{l}$，令$\zeta=(c^{\alpha})^{\frac{q-1}{r^{s}}}=(c^{\alpha})^{\frac{q-1}{r^{s}}}c^{r\beta +r-1-l\alpha}=c^{r-1}(c^{\beta+\alpha\frac{q-1-lr^{s}}{r^{s+1}}})^{r}=c^{r-1}b^{r}$.

$\because c$是$F_{q}$上的r次剩余，且指数含$\frac{q-1}{r^{s}}$，则$ord_{q}(\zeta)=r^{t}.(t<s)$

[Theorem 2]

Proof：

$(cb\xi^{u})^{r}=cc^{r-1}b^{r}\xi^{ur}=c\zeta\xi^{ur}$.

$\because u=j(r^{t}-1)r^{s-t-1}+kr^{s-1},\xi^{r^{s}}=1.$

$\therefore \zeta\xi^{ur}=(\xi^{r^{s-t}})^{j}\xi^{ur}=\xi^{jr^{s-t}+ur}=\xi^{jr^{s-t}+kr^{s}+j(r^{t}-1)r^{s-t}}=\xi^{jr^{s}}=1.$

$\therefore (cb\xi^{u})^{r}=c.$

[Remark 1]

Theorem里的$r\beta +r-1=l\alpha$确定的$\alpha$ mod r和$\beta$ mod l是唯一的. 且上式可以扩展到$\frac{q-1}{r}$的模域上（$r\beta + r-1\equiv l\alpha(mod\ \frac{q-1}{r})$），因为c是$F_{q}$上的r次剩余，即$c^{\frac{q-1}{r}}=1$.

[Remark 2]

$cb=c^{\beta+1+\alpha\frac{q-1-lr^{s}}{r^{s+1}}}=c^{\frac{(\beta+1)r^{s+1}+\alpha(q-1)-\alpha lr^{s}}{r^{s+1}}}=c^{\frac{r^{s}((\beta+1)r-\alpha l)+\alpha(q-1)}{r^{s+1}}}=c^{\frac{1+\frac{\alpha(q-1)}{r^{s}}}{r}}.$

[Remark 3]

Theorem 1结尾提到的$(i,j)$在$r^{t}$较大时求解困难，因此本方法在r和t过大时并不高效.

[利用]

• s = 1时（即$q\equiv lr+1(mod\ r^{2})$时）

$\because t<s\quad\therefore t=0,u=0.$

$cb\xi^{u}=cb$即为一个满足要求的r次根.

由Remark 3知，$cb=c^{\frac{1+\frac{\alpha(q-1)}{r^{s}}}{r}}=c^{\frac{1+\frac{\alpha(q-1)}{r}}{r}}$，至于$\alpha$可以通过扩展欧几里得算法很轻易得到.

• s > 1时，t可能落在{0, …, s - 1}上，因此分析时要分的情况会多不少（在这里就不占篇幅去写了，paper链接会在Link中给出）

• 上述算法给出的只是$G_{q}$上c的其中一个r次根，但要找出所有的r次根也很简单，只要借助r次单位根即可

$G_{q}$上的r次单位根($r\mid (q-1)$)为{$x^{i(\frac{q-1}{r})}$}($i\in[0,q)$), 我们取一个不为1的r次单位根与我们先前找到的特解生成一个r阶循环群即找到通解.

#### More

exp对应2019-NCTF-easyRSA.

http://www.soreatu.com/ctf/writeups/Writeup%20for%20Crypto%20problems%20in%20NCTF%202019.html#easyrsa

[注]

exp第一次调试的时候发现速度很慢-.-后来发现是大量crt的调用使得计算了接近$e^{2}$次的inverse(p, q)和inverse(q,p)，因此将这两个crt中用到的变量锁定即可.

https://eprint.iacr.org/2013/117.pdf

https://arxiv.org/pdf/1111.4877.pdf