RSA加密明文的大体步骤

当我们使用 RSA 算法加密一个明文消息时，我们需要遵循以下步骤：

首先选择两个大质数 p 和 q，然后计算它们的乘积 n = p * q。这个值 n 就是我们的模数，也是公钥和私钥的一部分。通常，n 的位数应该在 1024 位到 4096 位之间。

接下来，我们计算欧拉函数值 φ(n) = (p-1) * (q-1)。这个值 φ(n) 也是公钥和私钥的一部分。

选择一个整数 e，使得 1 < e < φ(n) 且 e 与 φ(n) 互质。这个整数 e 就是公钥的一部分。

假设我们选择 e = 65537。

计算一个整数 d，使得 d * e ≡ 1 (mod φ(n))。这个整数 d 就是私钥的一部分。

需要使用扩展欧几里得算法求解 d。

将公钥 (e, n) 公开，保密私钥 d。

要加密一个明文消息 m，使用公钥 (e, n) 并计算密文 c = m^e mod n。

假设我们要加密的消息为 "Hello, world!"，它的 ASCII 码值为 "72 101 108 108 111 44 32 119 111 114 108 100 33"。我们将这个消息转换为一个十进制数，即 m =

72101108108111144463211911111410810033。

然后，我们使用公钥 (e, n) 进行加密。因为我们选择的 e = 65537，所以我们需要计算 c = m^65537 mod n。

要解密密文 c，使用私钥 d 并计算明文 m = c^d mod n。

假设我们收到的密文 c =

23456789123456789012345678901234567890。我们使用私钥 d = 1234567890123456789012345678901234567890 进行解密。因为我们知道 d 和 n，所以我们可以计算出明文消息 m = c^d mod n。

最后，我们将这个十进制数转换回 ASCII 码值，并得到明文消息 "Hello, world!"。

证明过程

假设Alice想要向Bob发送一条加密信息，她使用Bob的公钥（n，e）来加密消息，其中n是两个大质数p和q的乘积，e是一个与phi(n)互质的整数。Alice将消息m用以下公式加密：

c = m^e mod n

然后，Alice将加密后的消息c发送给Bob。Bob使用自己的私钥（d）来解密消息，其中d是一个满足以下条件的整数：

d * e ≡ 1 mod phi(n) -- 1式

Bob用以下公式解密消息：

m = c^d mod n

这里

d 是 Bob 的私钥指数。e 是 Bob 的公钥指数。phi(n) 是欧拉函数，n 是 Bob 的公钥中的两个大质数的乘积。c 是加密后的密文。m 是解密后的明文。

由于 d * e ≡ 1 mod phi(n)

接下来，我们将 c 的表达式带入 RSA 解密的公式中，得到：

m ？≡ c^d mod n ≡ (m^e)^d mod n ≡ m^(e*d) mod n

由于根据欧拉定理，对于任何与 n 互质的正整数 a，都有：

a^phi(n) ≡ 1 mod n

证明：a = k*phi(n) + 1

a ≡ a^(k+1-k) mod n，即a ≡ (a^k)^1 * a^1-k mod n。这个表达式可以表示为a ≡ 1 * a^1-k mod n，也就是a ≡ a^1-k mod n。

综上所述，我们得到了a ≡ a^1-k mod n的表达式，也就是a = k*phi(n) + 1，其中k为常数。

因此，我们可以将1式 ed 表示为 ed = k*phi(n) + 1，其中 k 是一个正整数。代入上式中得到：

m^(ed) ≡ m^(kphi(n)+1) mod n

进一步得到：

m^(e*d) ≡ m * (m^(phi(n)))^k mod n

由于 m 与 n 互质，因此根据欧拉定理，有：

m^(phi(n)) ≡ 1 mod n

将上式带入，得到：

m^(e*d) ≡ m * 1^k mod n ≡ m mod n

即 (m^e)^d ≡ m mod n。由欧拉定理，m^phi(n) ≡ 1 mod n，因此，我们可以将 (m^e)^d 重写为 m^(d * e)，然后使用 d * e ≡ 1 mod phi(n) 将其进一步重写为 m^(k * phi(n) + 1)，其中 k 是一个整数。由于 m^phi(n) ≡ 1 mod n，所以 m^(k * phi(n) + 1) ≡ m mod n，即 m 就是我们要解密的明文。

所以，Bob 可以使用上述公式来解密消息。