首页密码学公钥密码整数环上的密码学

RSA 的运行过程中，对于一个公钥(n,e)(n,e)，加密过程计算的是明文mm 的幂次即memod  nm^e\mod n，常见的一个ee 的取值是 65537 即 0x10001，通过快速幂计算这个过程一般来说还是比较容易的。但是问题在于，私钥指数(n,d)(n,d) 中的d≡e−1(mod ϕ(n))d\equiv e^{-1}({\rm mod}\ \phi(n))，这个dd 的取值可能是十分大的，相应带来的也就是巨大的解密计算量。这个加解密计算量不对等的问题，对于一些缺少计算能力的嵌入式设备可以说是致命的。

一个加速的思想在于，构造一个比较小的私钥指数dd，这样解密的过程可以得到显著的加快。但是这样的构造实际上会破坏 RSA 的安全性。

# 连分数

Wiener 的思路是构造连分数以攻破解密指数。

连分数是下面这样形式的分数：

a1q1+a2q2+a3......qm−1+amqm=a1/(q1+a2/(q2+a3/(../(qm−1+am/qm)...)))\begin{aligned} &\cfrac{a_1}{q_1+\cfrac{a_2}{q_2+\cfrac{a_3}{...\cfrac{...}{q_{m-1}+\cfrac{a_m}{q_m}}}}} \\[2ex] =&a_1/(q_1+a_2/(q_2+a_3/(../(q_{m-1}+a_m/q_m)...))) \end{aligned}

在 Wiener 的构造中，定义下面的式子为：

<q0,q1,...,qm>=q0+1/(q1+1/(q2+1/(.../(qm−1+1/qm)...)))=q0+1q1+1q2+1......qm−1+1qm\begin{aligned} &<q_0,q_1,...,q_m>\\[2ex] =&q_0+1/(q_1+1/(q_2+1/(.../(q_{m-1}+1/q_m)...)))\\[2ex] =&q_0+\cfrac{1}{q_1+\cfrac{1}{q_2+\cfrac{1}{...\cfrac{...}{q_{m-1}+\cfrac{1}{q_m}}}}} \end{aligned}

例如<0,2,1,3>=0+1/(2+1/(1+1/3))=411<0,2,1,3> = 0+1/(2+1/(1+1/3))=\frac{4}{11}，在这里称<0,2,1,3><0,2,1,3> 就是411\frac{4}{11} 的连分数扩展。

通过这样的方式可以将一个整数ff 表示成连分数：每一层连分数中，都用qiq_i 表示整数部分（商），用rir_i 表示剩余部分（余数），带入下一步的连分数中得到ri=qi+1+ri+1r_i=q_{i+1}+r_{i+1}：

q0=⌊f⌋,r0=f−q0qi=⌊1ri−1⌋,ri=1ri−1−qi,i=1,2,3,...,m(1)\tag{1} \begin{aligned} &q_0=\lfloor f\rfloor,r_0=f-q_0\\[2ex] &q_i=\lfloor \frac{1}{r_{i-1}}\rfloor,r_i=\frac{1}{r_{i-1}}-q_i,i=1,2,3,...,m \end{aligned}

这样到rm=0r_m=0 时，就能够构造出f=<q0,q1,...,qm>f=<q_0,q_1,...,q_m>。

这边可以注意到最后一项的qmq_m 必定是大于等于 2 的，如果qm=1q_m=1，那么必定会有rm−1=1r_{m-1}=1，显然这是不可能的，因为rir_i 表示的是小数部分。

另外需要注意的一个性质是这样的：

对于偶数 m，有：

⟨q0,q1,...,qm⟩<⟨q0,q1,...,qm−1,qm+x⟩,(x>0)(2.1)\tag{2.1} \langle q_0,q_1,...,q_m\rangle < \langle q_0,q_1,...,q_{m-1},q_m+x\rangle,(x>0)

而对于奇数 m，则是：

⟨q0,q1,...,qm⟩>⟨q0,q1,...,qm−1,qm+x⟩,(x>0)(2.2)\tag{2.2} \langle q_0,q_1,...,q_m\rangle > \langle q_0,q_1,...,q_{m-1},q_m+x\rangle,(x>0)

从直观上理解来说，当最后一位从qmq_m 变为了qm+xq_m+x 也就是增大了，那么外面一层的分数即qm−1+1qm+xq_{m-1}+\frac{1}{q_m+x} 则会变小，再外面一层则会增大……

完成了连分数的构建，接下来的问题就是怎么样从一个连分数去恢复出原来的数ff。

最简单的方法也就是从qmq_m 开始，从最底层向上逐级计算。Wiener 的思路则采用的是一种自顶向下的方法。

构建这样的两个序列nin_i 和did_i，其中i=0,1,...,mi=0,1,...,m：

nidi=⟨q0,q1,...,qi⟩, gcd⁡(ni,di)=1 \frac{n_i}{d_i}=\langle q_0,q_1,...,q_i\rangle,\ \gcd(n_i,d_i)=1\

这样也就是有（i=2,3,...,mi=2,3,...,m）：

n0=q0,d0=1n1=q0q1+1,d1=q1...ni=qini−1+ni−2,di=qidi−1+di−2\begin{equation}\tag{3} \begin{aligned} &n_0=q_0,&d_0=1\\[2ex] &n_1=q_0q_1+1,&d_1=q_1\\[2ex] &...&\\[2ex] &n_i=q_in_{i-1}+n_{i-2},&d_i=q_id_{i-1}+d_{i-2} \end{aligned} \end{equation}

这样就可以重建整个连分数对应的f=nmdmf=\cfrac{n_m}{d_m} 了。

此外，可以通过上面的式子构造得到：

nidi−1−ni−1di=−(−1)in_id_{i-1}-n_{i-1}d_i=-(-1)^i

这会在后面被用到。

# 连分数算法

我们令f′=f⋅(1−δ),δ>0f'=f\cdot(1-\delta),\delta>0。

如果δ\delta 足够小的话，那么f′f' 非常趋近于ff，也就可以通过f′f' 去求到ff。

这里令qi,riq_i,r_i 和qi′ri′q_i'r_i' 分别是ff 和f′f' 按照前面公式 (1) 形式得到的商和余数。我们可以通过这样的方法计算出ff：

  • 计算f′f' 连分数扩展的下一个对应的商qi′q_i'。
  • 使用上面公式 (3) 构造下面形式的连分数：

    ⟨q0′,q1′,...,qi′+1⟩,if i is even,⟨q0′,q1′,...,qi′⟩,if i is odd\begin{aligned} \langle q_0',q_1',...,q_i'+1\rangle,&{\rm if}\ i\ {\rm is\ even},\\[2ex] \langle q_0',q_1',...,q_i'\rangle,&{\rm if}\ i\ {\rm is\ odd} \end{aligned}

  • 如果上面构造的连分数等于ff，那么算法结束，否则继续。

如果ff 比f′f' 要大，又根据公式 (2.1)(2.2)，在ii 为奇数，有⟨q0′,q1′,...,qi−1′,qi′⟩<⟨q0′,q1′,...,qi−1′,qi′+ri′\langle q_0',q_1',...,q_{i-1}',q_i'\rangle < \langle q_0',q_1',...,q_{i-1}',q_i'+r_i'，所以说上面的式子中，在奇数的情况下最后一项为qi′+1q_i'+1。

当满足

⟨q0,q1,...,qm−1⟩<f′≤⟨q0,q1,...,qm⟩,if m is even,⟨q0,q1,...,qm+1⟩<f′≤⟨q0,q1,...,qm−1⟩,if m is odd\begin{aligned} \langle q_0,q_1,...,q_m-1\rangle < f' \leq \langle q_0,q_1,...,q_m\rangle,&\\[2ex] &{\rm if}\ m \ {\rm is\ even},\\[2ex] \langle q_0,q_1,...,q_m+1\rangle < f' \leq \langle q_0,q_1,...,q_{m-1}\rangle,&\\[2ex] &{\rm if}\ m \ {\rm is\ odd} \end{aligned}

在这种情况下，这个算法能够成功地求出ff。Wiener 求出，对应的情况下δ\delta 的取值满足：

δ<132nmdm(4)\tag{4} \delta < \cfrac{1}{\cfrac{3}{2}n_md_m}

nm,dmn_m,d_m 为满足上文公式 (3) 的构造。这个算法的时间复杂度是O(log⁡x)O(\log x)，其中xx 为max⁡(nm,dm)\max(n_m,d_m)。

# RSA

一种 RSA 的构造中，私钥指数的取值是这样的：

ed≡1(mod LCM(p−1,q−1))ed\equiv 1(mod\ LCM(p-1,q-1))

也就是存在一个KK 满足

ed=K⋅LCM(p−1,q−1)+1ed=K\cdot LCM(p-1,q-1)+1

如果G=gcd⁡(p−1,q−1)G=\gcd(p-1,q-1)，有LCM(p−1,q−1)=(p−1)(q−1)/GLCM(p-1,q-1)=(p-1)(q-1)/G，可以得到

ed=KG(p−1)(q−1)+1ed=\frac{K}{G}(p-1)(q-1)+1

其中KK 和GG 有比较大的概率是有公因数的，那么我们定义k=K/gcd⁡(K,G)k=K/\gcd(K,G)，g=G/gcd⁡(K,G)g=G/\gcd(K,G)，就有k/g=K/Gk/g=K/G，且gcd⁡(k,g)=1\gcd(k,g)=1，这样子就会得到：

ed=kg(p−1)(q−1)+1ed=\frac{k}{g}(p-1)(q-1)+1

在等式两边同时除以dpqdpq 能够得到

epq=kdg(1−δ), δ=p+q−1−gkpq\frac{e}{pq}=\frac{k}{dg}(1-\delta),\ \delta=\frac{p+q-1-\frac{g}{k}}{pq}

这条式子可以构造前面连分数的形式。考虑到gcd⁡(K,d)=1,gcd⁡(k,d)=1,gcd⁡(k,g)=1\gcd(K,d)=1,\gcd(k,d)=1,\gcd(k,g)=1，能够得出，

kdg<pq32(p+q)kdg<\frac{pq}{\frac{3}{2}(p+q)}

这足够能计算出kk 和dgdg。

我们可以假设ed>pqed>pq，在这种情况下，有

edg=k(p−1)(q−1)+gedg=k(p-1)(q-1)+g

对于k>gk>g，两边同时除以k(k>g)k(k>g) 能够得到(p−1)(q−1)(p-1)(q-1) 和一个余数gg。如果能够猜测出(p−1)(q−1)(p-1)(q-1)，那么

pq−(p−1)(q−1)+12=p+q2\frac{pq-(p-1)(q-1)+1}{2}=\frac{p+q}{2}

如果上面等式右边不是整数，那么上面的猜测就是错误的。此外又有

(p+q2)2−pq=(p−q2)2(\frac{p+q}{2})^2-pq=(\frac{p-q}{2})^2

如果等式右边是一个完美平方数，那么猜测就是正确的。从这正确的猜测中就能够得到私钥指数dd。

# 参考资料

【1】 M. J. Wiener, "Cryptanalysis of short RSA secret exponents," in IEEE Transactions on Information Theory, vol. 36, no. 3, pp. 553-558, May 1990, doi: 10.1109/18.54902.

此文章已被阅读次数:正在加载...更新于