数论基础阅读笔记与习题解答之四:RSA加密系统

《数论基础》第四章介绍了著名的RSA加密算法,包括其基本原理、指数快速模算法、数字签名等等,以下是各节的习题解答:

4.2 RSA加密原理

4.2.1 易知\(\varphi(7\times11)=(7-1)(11-1)=60\),则\(gcd(5,\varphi(77))=5\ne1\),不符合加密指数要求。

4.2.2 据题意有\(gcd(13,\varphi(77))=1\),所以\(13\)是一个合适的加密指数,则\(13d\equiv1\pmod{60}\),则根据欧几里得算法有\(13d-60q=1\),解此线性丢番图方程可得\(d=37\)

4.2.3 显然有\(gcd(61,\varphi(77))=gcd(61,60)=1\),则\(e=61\)也是一个符合要求的加密指数。同时因为\(m\not\equiv0\pmod{77}\),则\(gcd(m,77)=1\),则根据欧拉定理有:

$$ m^{\varphi(77)}\equiv1\pmod{77}\Rightarrow m^{60}\equiv1\pmod{77} $$

两边同时乘以\(m\),则得\(m^{61}\equiv m\pmod{77}\)。所以使用\(e=61\)作为指数加密时,密文与原文会是一样的,所以不是一个有效的加密指数。

4.3 模\(n\)指数

4.3.1 数一下平方和乘号的数量即可,显然需要十次乘法。

4.3.2 因为\(89=91-2\),所以可以少一次乘法,故需要九次乘法。

4.4 RSA加密与解密

4.4.1 显然有\(((m^2\cdot m)^2)^2\cdot m=m^{13}\),且有\(gcd(13,77)=1\),则消息\(m\)可以这样加密。

4.4.2\(m=7\),则\(7^{13}\bmod77=35\)

4.4.3\(m=12\),则\(12^{13}\bmod77=12\)

4.4.4 据4.2.2有\(d=37\),则\(12^{37}\bmod77=12\)

4.4.5 显然有\(12^{13}\equiv(12^6)^2\times12\equiv12\pmod{77}\)\(12^{37}\equiv(12^6)^6\times12\equiv12\pmod{77}\)