[数据结构与算法]RSA中coppersmith定理的应用条件

$Introduction$

一般来说，coppersmith在RSA中应用最多的就是，高位攻击一类的已知部分二进制位，通过coppersmith定理（里面应用了LLL算法）求得剩余的二进制位

大家有没有想过，究竟在已知多少二进制位数的情况下，coppersmith定理能够生效？

$Deduction$

（本文提到的coppersmith定理均只针对单变量）

先来看看coppersmith定理本身的应用场景是：

现有一个$e$阶的多项式$f$，那么可以：

• 给定$\beta$，快速求出模某个$n$的因数$b$意义下较小的根，其中$b\ge n^{\beta }$，（$0<\beta \le 1$）
• 在模$n$意义下，快速求出$n^{\frac{{\beta }^2}{e}}$以内的根

而前面提到的高位攻击显然是应用了第二条性质，此时构造的多项式$f=p_{high}+p_{unknown}$，阶数$e=1$

应用coppersmith定理求解$p_{unknown}$，前提条件是$p_{unknown}\le n^{\frac{{\beta }^2}{e}}$

那么$n^{\frac{{\beta }^2}{e}}$究竟有多大呢？在高位攻击的情况下$e=1$，所以转换为是求$n^{{\beta }^2}$

而$\beta$的定义是

$n$的某个因数$b$使得$b\ge n^{\beta }$，（$0<\beta \le 1$）

当然，在RSA中$n$的因数也就是组成$n$的大素数，一般来说，$n=p?q$，其中$p,q$均为大素数

python中的实现代码（这里以$1024bits$为例）

from Crypto.Util.number import getPrime
p = getPrime(1024)
q = getPrime(1024)
n = p * q

那么就意味着$n$的大小为$2048bits$或者$2047bits$（大小涉及到乘法对二进制位数的关系，这里就不过多讲述了）

很显然$n^{0.5}$就是$1024bits$左右的数，与$p,q$很接近，但是仍有可能不满足$p,q\ge n^{0.5}$

检验一下

import gmpy2
assert gmpy2.iroot(n,2)[0] <= p
assert gmpy2.iroot(n,2)[0] <= q
'''
>>> assert gmpy2.iroot(n,2)[0] <= p
>>> assert gmpy2.iroot(n,2)[0] <= q
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError
'''

此时不满足条件

回到问题的开头，我们想要知道的是在已知多少$p$或者$q$的二进制位数下，我们能够通过coppersmith定理求得剩下的二进制位（所需构造的多项式前面已经构造好了）

所以我们可以来看看如果此时满足条件，那么我们至少需要已知多少二进制位数（这里假设求$p$）

计算此时$n^{{\beta }^2}$（$e=1$，所以就忽略不代入运算了）的二进制位数，我们未知的二进制位数需要小于$n^{{\beta }^2}$的二进制位数

gmpy2.iroot(n,2**2)[0].bit_length()
'''
>>> gmpy2.iroot(n,2**2)[0].bit_length()
512
'''

这里我们看到如果$p,q\ge n^{\beta }$，那么我们未知的$p$或者$q$（任意一个均可）的二进制位数必须小于$512$

以上都是假设的，我们来看看真实地满足$p,q\ge n^{\beta }$情况下，我们未知的二进制位数必须小于多少？

既然$n^{0.5}$（即是$\beta =0.5$情况下）不满足条件，那么与之最接近的$\beta =0.49$的情况（也就是$\beta <0.5$时）一定能满足条件（这里又涉及到指数运算对二进制位数的影响，也不过多讲述了，可以自己计算试一试）

还是刚才那套检验过程以及计算$n^{{\beta }^2}$的过程

assert gmpy2.iroot(n**49,100)[0] <= p
assert gmpy2.iroot(n**49,100)[0] <= q
gmpy2.iroot(n**(49**2),100**2)[0].bit_length()
gmpy2.iroot(n**(48**2),100**2)[0].bit_length()
gmpy2.iroot(n**(47**2),100**2)[0].bit_length()
'''
>>> assert gmpy2.iroot(n**49,100)[0] <= p
>>> assert gmpy2.iroot(n**49,100)[0] <= q
>>> gmpy2.iroot(n**(49**2),100**2)[0].bit_length()
492
>>> gmpy2.iroot(n**(48**2),100**2)[0].bit_length()
472
>>> gmpy2.iroot(n**(47**2),100**2)[0].bit_length()
453
'''

本来按照定理条件的推导，只要未知二进制位数少于$492$均可应用coppersmith定理求解

在sagemath中应用coppersmith定理的函数有两个：small_roots，coppersmith_howgrave_univariate

后者的使用方法可以参考 Coppersmith 相关攻击 - CTF Wiki (ctf-wiki.org)

对RSA-Factoring with High Bits Known理解 - 简书 (jianshu.com)

这里求解coppersmith我们统一使用sagemath的small_roots()函数；该函数导入的$\beta$ 起作用的只有一位小数（如果是两位小数，其求解范围还是相当于一位小数的求解范围），这就意味着一般形如p = getPrime(bits),q = geyPrime(bits)的RSA应用coppersmith求解p的低位时，$\beta$只能是最接近$0.5$的$0.4$

关于small_roots的使用方法：

small_roots(X = ,beta = ) 有两个参数

X代表所需要求解根的上限；虽然是根的上限，并不是说上限越高越好，当上限超过某个值的时候就会计算失效，即使已知二进制位数满足条件，也无法用此函数求得结果；所以一般来说X取在给定情况下的最大求解上限

beta即是前面提到的$\beta$ ，当p,q二进制位数相同时一般只能取$0.4$；如果p,q二进制位数不同，就按照之前的方法具体问题具体分析

那么实际操作下，使用small_roots()我们至少需要已知多少二进制位数呢？（以下是sagemath环境）

from Crypto.Util.number import getPrime
p = getPrime(int(1024))
q = getPrime(int(1024))
n = p * q
test_bits = 454
p_h = p >> test_bits
R.<x> = PolynomialRing(Zmod(n))
f = (p_h << test_bits) + x
f.small_roots(2**test_bits,0.4)

经过测试得到，当未知量小于等于$454bits$时（p,q为$1024bits$），coppersmith定理可以求解

之后改变了p,q的大小，经过测试发现，当p,q同二进制位数时，要使用small_roots()应用coppersmith定理求解$n$的某个因数的低位，需要满足未知的二进制位数与因数之间的二进制位数的关系是
$$unknown\_bits÷p\_bits\le 0.44$$
下面来以例题为标准应用一下small_roots的灵活应用

$Problem$

问题来自鹤城杯2021，babyrsa

$Description$

from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 724
hint2 = q % (2 ** 265)
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)

$Analysis$

显然是应用高位攻击

但是由于之前测试的结果，未知的二进制位数需要小于$454$，而这里p未知的二进制位数达到了$724$，而q则更多；

但是这里既然给出了p,q两者分别的高位，低位；按照高位攻击的思路，需要是某一个因数的多个二进制位数，所以找方法能不呢把q的低位转换为p的低位，或者相反
$$?\begin{array}{l}{q}_{low}\equiv q(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{265})\\ q_{high}=k?2^{265}\\ n=p?(q_{high}+q_{low})\end{array}?n=p?k?2^{265}+p?q(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{265})$$
等式两边同时求余$2^{265}$
$$\begin{gathered} n_{low}\equiv p?k?2^{265}+p?q_{low}(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{265}) \\ ?p_{low}\equiv n_{low}?q_{low}^{?1}(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{265}) \end{gathered}$$
这样一来我们就知道了$p$的低$265$位，此时未知的二进制位数仍然有$459$位，而我们需要的是未知二进制位要在$454$之下

只剩下$5$位了，那么直接就可以爆破剩余的$5$位二进制

$Solvingcode$

from Crypto.Util.number import *
import gmpy2
p_high = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q_low = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
enc = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
e = 65537

mod = pow(2,265)
p0 = n * inverse_mod(q_low,mod) % mod
PR.<x> = PolynomialRing(Zmod(n))
for i in range(2**5):
    f = p_high * (2^724) + p0 + (x * 32 + i) * mod
    f = f.monic()
    out_p = f.small_roots(2^454,0.4)
    if len(out_p) != 0:
        print(out_p[0])
        break
p = out_p[0] * 32 + i * mod + p_high * (2^724) + p0
# print(p)
p = 133637329398256221348922087205912367118213472434713498908220867690672019569057789598459580146410501473689139466275052698529257254973211963162087316149628000798221014338373126500646873612341158676084318494058522014519669302359038980726479317742766438142835169562422371156257894374341629012755597863752154328407
assert n % p == 0
q = n // p
fai_n = (p-1) * (q-1)
d = inverse_mod(e,fai_n)
m = pow(enc,d,n)
print(bytes.decode(long_to_bytes(m)))

$Other$

关于RSA中应用coppersmith还有部分私钥泄露攻击等等

这里就不过多阐述了，可以参考 CTF中的RSA基本套路(3) - 食兔人的博客 (ycdxsb.cn)