RSA专题——”误用“攻击
在前面一篇文章中,我们介绍了 RSA 公钥密码体制,了解到其安全性是基于平均困难的大数分解问题,并介绍了一些 ”特殊情况“ 下的大数分解算法。
而除了模数构造上存在问题,其他参数的不正确设置也会影响 RSA 公钥密码体制的安全性。即使理论上的安全性检查通过了,在实际操作中也可能会引入很多新的问题。那么这一节,我们将讨论 RSA 公钥密码体制中一些误用情况导致的攻击。
低加密指数攻击
由于 RSA 加密公式为 ,因此公钥 的大小会决定计算密文 时的计算量。如果为了降低计算量而选取了小的加密指数,如 ,那么首先会面临的一个问题就是 很有可能会与 不互素,那么就需要重新选取合适的模数。
其次,如果加密的明文消息 较小,且满足 ,那么我们仅需对密文 开 3 次根即可获取明文 。如果 仅仅是略大于 ,同余式 可转化为等式有 ,此时 值很小,我们可以通过一定的爆破再开 3 次根来尝试获取明文 。
那么如何避免这种情况发生呢?一般我们会选取加密指数 ,小一点也可以选择 。其实只要满足明文的比特长度乘以 比 的比特长度长 30 比特以上即可。
低加密指数广播攻击
上面我们提到,如果选取了合适的公钥,就可以抵御低加密指数攻击,即简单的爆破+开根运算已无法恢复明文。但是如果我们在实际操作中,如果对同一密文进行了多次加密,但是在加密时使用了相同的”安全的“加密指数和不同的模数,这也可能会产生相应的安全问题。
上述的情况,再结合 RSA 加密公式,我们可以得到以下同余式组
由于一般情况下 之间都是两两互素的,(如果不互素就可以使用 gcd 算法求其最大公约数从而分解 ,即可直接解密密文了)此时,如果使用中国剩余定理,我就可以计算得到
当 时,上式同余式就可以改成等式,那么就可以对密文进行相应的开 次根操作,从而恢复明文。
共模攻击
对同一密文的多次加密,不能使用不同的模数和相同的加密指数,那么可以使用不同的加密指数和相同的模数么?
我们考虑这样的情况,使用不同且互素的加密指数 和模数 分别加密相同的明文 ,那么我们可以得到这样两条密文
注意到上式,由于 ,那么使用拓展欧几里得算法我们可以计算出 满足
从而在不知道私钥 ,不知道模数 的分解下恢复了明文 。
所以这又该如何进行防范呢?如果需要对相同的消息进行加密广播传递,由于不同的接收者肯定会拥有不同的公钥,因此我们没法仅加密一次就达到消息广播的目的。但是在加密的时候我们需要注意到,每一次加密使用的公钥不能够有任意部分的相同,即不能拥有相同的加密指数 ,也不能拥有相同的模数 。
但其实在实际操作中,我们并不会对不同公钥间进行检查,一个可选择的方案是对明文进行额外处理,每一次加密时对明文进行随机填充,这样每一次的 都不会相同,从而得到的多组密文间也就难以进行联系。
低解密指数攻击
前面我们提到,为了效率,在使用 RSA 公钥密码体制加密的时候,我们可能会选择较小的加密指数 以提高加密效率。但是当我们选择加密指数 时,解密指数 ,其大小与 相当。因此,为了提高解密效率,我们是否可以选择较小的解密指数 呢?
答案是不可以,并且由小解密指数带来的”破坏力“比加密指数要大的多的多。
wiener‘s attack
令 且 $q<p<2q$,$d<frac13n^{frac14}$,给定 $⟨n,e⟩=”” $且满足$ed=”1″ pmod=”” {varphi(n)}$,攻击者可以有效计算出$d$。<=”” p=””>
,如果 足够小,则 是 的逼近,尽管我们不知道 ,但是我们可以用 来近似。
因为 $kvarphi(N)=ed−1<ed$,并且 $e<varphi(n)$,所以有=”” $d=”” gt=”” k$<=”” p=””>
因此如果私钥较短,满足 ,我们就有 $k <d<frac13n^{frac14}$,也就能得到$3k<3d3d^2$)。 </d<frac13n^{frac14}$,也就能得到$3k<3d
根据 Legendre’s theorem ,分数 会在 的收敛分数上。因此我们要做的便是计算 的收敛分数,因为 ,所以我们有 ,那么其中一个收敛分数就等于 。
除去 这一条件对应的 wiener‘s attack ;杰出的密码学家们在这一基础上不断地探索发现,后续已经出现了很多的攻击变体。当小解密指数结合小素数差( Cryptanalysis of RSA with Small Prime Difference ),de weger 也发现了连分数的妙用。当 越过了边界,达到了 时, Boneh Durfee Attack 横空出世。
补充:连分数知识相关
定义一:连分数
连分数,就是对于任何一个有理数 ,我们可以化成如下形式:
定理 1 任何一个有理数与其连分数形式是一一对应的。
证明: 对于任意一个有理数 ,且 (即 互素),我们可以写出如下等式
def continued_fraction (dn,n) : res = [] while dn % n: res.append(dn//n) dn, n = n, dn % n res.append(dn//n) print(res) print(continued_fraction(5 ,3 ))
可以看到和求 的整个过程是比较类似的,所以求一个数的连分数形式也是多项式时间复杂度(说白点就是非常的快)。
定义二:收敛分数
说白点就是把连分数某一项后面的全扔掉,得到一个 的近似值。有 定理 1 我们可以知道收连分数是有限的,并且越后面(就是项数越多)就越逼近 。
例 3: 计算 的收敛分数
def Convergence_function (continued) : res =[] for i in range(1 ,len(continued)+1 ): tmp = 1 conver = continued[:i][::-1 ] tmp = conver[0 ] for j in conver[1 :]: tmp = j + 1 /tmp res.append(tmp) return res print(Convergence_function(continued_fraction(1234 ,32 )))
明白了这两个定义后,我们再给出一个定理2,也就是著名的Legendre’s theorem:
定理 2 (Legendre’s theorem)
小结
在这一节中,我们介绍了 RSA 公钥加密体制的一些误用情况,包括低加密指数攻击、低加密指数广播攻击、共模攻击、低解密指数攻击等。可以看到,即使 RSA 公钥加密体制在理论上依赖的大数分解问题是足够安全的,但是如果实际操作不当,即使我们不用解决大数分解问题也可以解密获得消息明文。因此,即使工具本身足够安全有效,不当地使用还是造成难以估量的后果。我们在使用工具时应该严格遵照”使用说明书“,以发挥其真正的价值。
原文始发于微信公众号(山石网科安全技术研究院):RSA专题——参数误用