RSA

(一)简介

​ RSA 算法是非对称算法，由 Ronald Rivest 、 Adi Shamir 、 Leonard Adleman 三 人共同在 1977年公开发表。在 RSA 加密算法中，公钥和私钥都可以用于加密消息，用于加密消息的密钥与用于解密消息的密钥相反。 RSA 算法提供了一种保护网络通信和数据存储的机密性、完整性、真实性和不可否认性的方法。

​ 目前， SSH 、 OpenPGP 、 S/MIME 和 SSL/TLS 都依赖千 RSA 进行加密和数字签名功能。 RSA 算法在浏览器中使用，能够在不可信任的互联网中建立安全连接。RSA 签名验证是网络连接系统中最常见的执行操作之一。

RSA 算法基于大整数因子分解的困难性，该算法的步骤如下：

第 一 步，生成两个大素数 p 和 q。

第 二 步，计算这两个素数的乘积 n = p q 。

第三步，计算小于 n 并且与 n 互素的整数的个数，即欧拉函数 ɸ ( 𝓷 ) = ( p - 1 ) ( q - 1 ) 。

第四步，选取 一 个随机数 e ，且满足 1 < e < ɸ ( 𝓷 ) ,并且 e 和 ɸ ( 𝓷 ) 互素，即 gad( e , ɸ ( 𝓷 ) ) = 1.

第五步，计算 【e d ≡ 1 mod ɸ ( 𝓷 ) = K * ɸ ( 𝓷 ) + 1 (K ∈ N^*^)】

第六步，保密 d 、 p 和 q, 而公开 n 和 e, 即 d 作为私钥，而 n 和 e 作为公钥。

模运算

设 n 是一个正整数，a 是整数，如果用 n 除以 a ,得商为 q ,余数为 r ,则：
a = q * n + r, 0 <= r < n, q =
余数 r 用 a mod n 表示。
若(a mod n) = (b mod n)，则称两个整数 a 和 b 模 n 同余，记为 a ≡ b mod n 。

例题：

e * d ≡ 1 mod ɸ ( 𝓷 )

1 / ɸ ( 𝓷 ) = 0 …… 1

1 mod ɸ ( 𝓷 ) = 1

(二)加解密算法解析

加密

​ 加密时首先将明文比特串分组，使得每个分组对应的十进制数小于 n ，即分组长度小于 log2n 。然后对每个明文分组 ，作加密运算：

解密

例题：