RSA

RSA是目前最有影响力的公钥加密算法，公开密钥密码*就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码*。

算法原理

RSA公开密钥密码*的原理是：
根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥

算法描述

1. 任意选取两个不同的大素数p和q，这两个值越大，破解RSA越困难，而执行加密和解密所用时间也越长。
   计算乘积n = p*q、z = (p-1)(q-1)
2. 选择一个小于 n 的数e，且 e 和 z 互质(没有非1的公因数)(此时 e 和 z 互素)。使用字母 e 表示是因为这个值将被用于加密。
3. 求一个数d，使得 ed -1 可以被 z 整除。使用字母 d 表示是因为这个值将被用于解密。即给定 e ，我们选择 d ，使得
   ed mod z = 1
4. 得到公钥 \(K_B^+=(n,e)\) 和私钥 \(K_B^-=(n,d)\)

加解密过程

能够实现加解密这个恒等式(模运算性质)很有用    \((a\;mod\;n)^d\;mod\;n\;=\;a^d\;mod\;n\)

1. 加密
   假设A向B发送一个由整数m表示的比特组合，且 m < n 。为了进行编码，A利用公钥 \(K_B^+=(n,e)\) 执行指数运算 \(m^e\) ，然后计算 \(m^e\) 被 n 除的整数余数c。密文c的比特模式发送给B。
   即

\[c\;=\;m^e\;mod\;n \]

2. 解密
   要求B使用私钥 \(K_B^-=(n,d)\)计算

\[c^d\;mod\;n=m \]

工作原理

在RSA加密过程中，一个报文m(唯一地表示为整数)使用模n算术做e次幂运算，即

\[c\;=\;m^e\;mod\;n \]

解密则先对该值执行d次幂运算，再做模n运算。因此先加密再解密的结果就是

\[(m^e\;mod\;n)^d\;mod\;n=m \]

下面我们来看看关于这个量能够得到什么。正如前面提到的，模算术的一个重要性质是对于任意值 a 、n 和 d 都有\((a\;mod\;n)^d\;mod\;n\;=\;a^d\;mod\;n\) 。因此在这个性质中使用\(a=m^e\)，则有

\[(m^e\;mod\;n)^d\;mod\;n\;=\;m^{ed}\;mod\;n \]

因此剩下证明 \(m^{ed}\;mod\;n=m\)，为了证明这一点，需要用到数论中一个相当神奇的结论：如果 p 和 q 是素数，且有 n = p * q 和 z = (p-1)(q-1) ，则\(x^y\;mod\;n\)与\(x^{y\;mod\;z}\;mod\;n\)是等同的。应用这个结论，对于 x=m 和 y=ed ，可得

\[m^{ed}\;mod\;n\;=\;m^{ed\;mod\;z}\;mod\;n \]

但要记住，我们是这样选择e和d的，即ed mod z = 1。这告诉我们

\[m^{ed}\;mod\;n\;=\;m^1\;mod\;n\;=\;m \]

这正是我们希望得到的结果！先对m做e次幂运算(加密)再做d次幂运算(解密)，然后做模n的算术运算，就可得到初始明文m。甚至更为奇妙之处是，如果我们先对m做d次幂运算(加密)，再做e次幂运算，即颠倒加密和解密的次序，先执行解密操作再执行加密操作，也能得到初始明文m 这个奇妙的结果完全遵循下列模算术：

\[(m^d\;mod\;n)^e\;mod\;n=m^{de}\;mod\;n=m^{ed}\;mod\;n=(m^e\;mod\;n)^d\;mod\;n \]

参考链接：
https://baike.baidu.com/item/RSA算法/263310#2
参考书籍：
《计算机网络 自顶而下方法(原书第7版)》/(美)詹姆斯·F·库罗斯等；陈鸣译