算法导论31.7 Exercises 答案

31.7-1

\(\begin{aligned} &\phi = (p-1)\cdot (q-1)=280\\ &d=e^{-1} \bmod \phi = 187\\ &P(M)=M^e\bmod n=100^3 \bmod 319 = 254 \end{aligned}\)

31.7-2

根据RSA公钥加密系统的定义，有\(ed\equiv 1 \pmod {\phi(n)}\).

也就是说，\(\exists k,ed-1=k\phi(n)\)。

由于\(p,q\)都非常大，因此可以假设\(p< n/3,q< n/3\)。

那么有\(\phi(n)=n-p-q+1>n/3+1>n/3\).

由于\(ed-1=3d-1<3n-1<3n\)，那么得到：

\(k(n/3)<k\phi(n)=3d-1<3n\)。这说明，\(k<9\)。

因此，枚举\(k\)值\(1,2,3,\dots,8\)，使得\(k\mid ed-1\)，并计算出\(\phi(n)=\dfrac{ed-1}{k}\)，并且计算二元二次方程组\(\left\{\begin{aligned}&pq=n\\&(p-1)(q-1)=\phi(n)\end{aligned}\right.\)，即可得到\(p,q\)的值。如果解出来是整数，那么分解完毕。

值得注意的是，这个方程组可以化成使用韦达定理来解。

\(\star\) 31.7-3

证明乘法性：\(P_A(M_A)\cdot P_A(M_B)\equiv M_A^{e}\cdot M_B^{e}\equiv (M_A\cdot M_B)^e\equiv P_A(M_A\cdot M_B)\pmod n\)

证明解密：如果我们打算解密密文\(C\)，那么随机选择\(a\in \mathbb{Z}_n^{\ast}\)，并且对\(a^e\cdot C\)进行题中所说的解密程序。如果解密得到正确的结果\(M'\)，那么返回\(M=a^{-1}\cdot M'\bmod n\)，否则重新随机选择\(a\)，继续尝试即可。