基于格理论来破解RSA公钥密码（1）

一. 介绍

二. RSA密码系统

2.1 生成公私钥

2.2 加密

2.3解密

三. 中国剩余定理攻击低指数的RSA

3.1 介绍

3.2 中国剩余定理

四. 基于多项式的RSA加密

五. 小结

一. 介绍

我们生活中常使用的网络浏览器，智能卡片都有RSA公钥密码的影子。从1977年，RSA密码系统提出，五十年来涌现出了大量的攻击算法。Hastad和Coppersmith创新性的用格密码理论来攻击RSA系统，尤其是公开指数较小的时候。

实际上，对于低次数的多项式，可以利用LLL算法来找到其小解。这种思想便可以用来攻击RSA系统。

二. RSA密码系统

2.1 生成公私钥

假定有两个尺寸类似的大素数p和q，运算得到最大的N，如下：

N=pq

利用欧拉函数，计算N的互素的元素个数：

$phi(N)=(p-1)(q-1)$

随机选择整数r,接着计算s使其满足：

$rcdot s=1quad mod phi(N)$

此时的 $phi(N)$ 即为如下乘法群的阶（order）：

$Z_N^*$

以上N叫RSA的模数，r叫公开的指数（public exponent），两者即可形成公钥。

s叫做保密的指数（private exponent），也叫做私钥。

备注：因为N在加密和解密时都有用，所以有些地方把N既看成公钥又看成私钥，这种也是对的。

要求私钥只有合法的接收者才拥有，用来解密密文。

2.2 加密

在乘法群内选择一个正整数M，即为明文，如下：

$Min Z_N^*$

执行如下指数运算，即可得到密文：

$C=M^rquad mod N$

2.3解密

利用密文也进行指数运算，根据欧拉定理不难得到：

三. 中国剩余定理攻击低指数的RSA

3.1 介绍

由于智能卡片的运算能力有限，电池供能限制等等，如果在这些系统内部部署RSA时，加密过程的运算我们希望越简单越好。比如可以让以上公开的指数r尽可能小一点，比如r=3等等。在这时，加密过程只需要进行两次乘法运算即可。

在未知N的分解情况下，我们来看一下此加密过程

$M^3quad mod N$

那么有一个问题，这安全吗？

3.2 中国剩余定理

Chinese Remainder Theorem，翻译为中国剩余定理，简称CRT。此定理在网络安全等领域非常重要。

假定r个等式，如下：

$xequiv a_iquad mod m_i$

以上模数 $m_1,cdots,m_r$ 是两两互素的。

中国剩余定理告诉我们，可以在多项式时间内很容易找出唯一的x满足：

$xquad mod m_1cdot m_2cdots m_r$

3.3 攻击低指数的RSA

我们来假设一种场景，ALICE想要给三个不同的人传递同一个明文，比如Bob, Charlie, 和 Dave。注意这三个人的私钥均不一样，模数也不一样，自然密文也不一样。假定这三个人的公钥分别是：

$N_B,N_C,N_D$

那么可以计算出三个密文为：

当窃听者获得这三个密文时，看起来是不是可以利用中国剩余定理进行解？先不要着急。

首先这三个模数N一定是两两互素的，如果不互素就可以直接求出里面的素数q和p，那么根据一个密文就可以直接解出明文了。

首先明文m的大小肯定满足：

$m<N_B,N_C,N_D$

所以可得：

$m^3<N_BN_CN_D$

接着根据中国剩余定理，可得：

$c=m^3quad mod N_BN_DN_D$

根据以上讨论可以直接去掉模数，所以可得：

$c=m^3$

这就是一个整数上的不等式，直接开三次方便可以得到明文m了。

四. 基于多项式的RSA加密

在以上的破解算法中，存在的问题是传给每个人的明文完全一样，那如果传给每个人的明文不一样呢？

比如，每个都有一个自己的ID，可以看成每个人公钥的一部分，假如ALICE原本想传的是明文M，实际给每个人传的都不一样，如下：

$M+2^kcdot ID$

其中k是明文M的比特长度，也是一个保密量，这样就可以保证给每个人的对应明文都不一样。当然解密是正确的。

其实这种改进，基于格理论也是不安全的。考虑更加一般的情况。

可以将公钥看成多项式函数（N,g），其中g看成关于M的多项式。

比如当我们想加密消息M时，我们可以运算：

$g(M)quad mod N$

比如在刚才的例子中，该多项式如下：

$g(M)=(M+2^kID)^3$

当然现实生活中，这种RSA系统依旧是有用的，比如指数可以选择：

$r=2^{16}+1$

另外明文消息通常会加入随机的比特串，这些都会让其更加安全。

五. 小结

在 RSA 体制及其变体的分析方面, 格基约化算法也得到一些很好的分析结果. RSA 是第一个公钥
密码体制, 1977 年由麻省理工学院的 Rivest, Shamir 和 Aldeman设计, 可以同时用于数据加密和数字签名, 是迄今为止最著名的公钥密码算法之一.

RSA 公钥密码算法的安全性依赖于 $Z_N$ 环中求解 e 次根的(平均)困难性. 其中 N=pq , p 和 q 是两个大素数. 通常把求解 e 次根问题简称为 RSA 问题. 如果 N的分解已知则计算解密密钥 d 容易, 因此求解 RSA 问题不比求解 d 和分解 N 困难.虽然直接求解 RSA 问题是困难的, 但在知道一些额外信息的情况下, 破解 RSA 体制可以转化成求解格中困难问题, 进而利用 LLL 算法来求解. 这方面开创性的工作是 Coppersmith 在 1996 年提出的。他的工作是通过构造格求解单变元模方程的小值解和两个变元整系数方程的小值解. 这两个重要定理的提出, 使得 RSA 体制的分析得到非常多的结果.

注意到, 因子分解问题可以很容易的转化成求解一个二元方程的根的问题，也就是说已知 p 或 q 的高一半比特, 可以在多项式时间内分解 N , 这个结果也可以通过构造单变元模多项式求解, 并且比双变元构造方法更有效.

为了提高加密的速度, 加密者希望选择小的加密指数 e . Coppersmith著名的一个结果是针对加密指数 e=3 的 RSA 体制的攻击: 如果知道明文的 2/3 , 即可以恢复整个明文.

未完待续。