构造简单的非对称 RSA 密钥对的示例

Question

我试图理解 RSA 非对称密钥生成中的数学原理。我在网上找了几篇文章，我的想法不是很清楚，所以我带着希望终于能够完成一个例子来到这里。我非常了解数学，但我对这些步骤有点困惑，所以我会一步一步地进行，直到我理解为止。

我将尝试使用低于 16[0..15]（4 位）的数字来加密/解密消息：“hello world”

步骤1：随机选择2个质数

P = 11 Q = 5

步骤2：计算H [(P-1)*(Q-1)]

H = (11-1) * (5-1) = 10* 4= 40

步骤3：选择一个低于H（E）的随机质数（我相信H的互质数也适用于E）

E = 7

现在？

Answer 1

我们可以从步骤 2 继续：

步骤 3)选择E这样Greatest Common Divisor(H,E)=1并且(1 < E < H)

在您的示例中，我们有gcd(40,?)=1 and 1<?<40--> 7 满足此要求，因此我们选择 E=7

步骤 4 )计算d并且(dE) mod H =1d<H

在示例中，我们有 (d*7) mod 40=1 且 d< 40，因此我们得到 d= 23

步骤5)公钥是{E,n}，私钥是{d,n}其中n = P * Q。在示例中，我们有公钥={7,55} 和私钥={23,55}

步骤6）计算C= M^E(mod n)加密，其中M是我们要加密的消息的数字表示。

在示例中，我们必须将 M="hello world" 解释为数字。在这里，为了简单起见，我假设它等于 39（这个数字应该小于n）。您可以参考此处了解有关如何将文本编码为数值的更多信息。

C= 39 ^7 mod 55 = 19（M的加密值）

步骤7）M= C^d(mod n)解密19的计算

在示例中，我们有 M=19^23 mod 55 = 39（应解码为“hello world”的消息）。