math - 构造简单的非对称 RSA key 对的示例

Question

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

我将尝试使用低于 16[0..15](4 位)的数字来尝试此示例加密/解密消息:“hello world”

第 1 步:随机选择 2 个素数

P=11Q=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 =1和d<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 )。您可以引用here了解有关如何将文本编码为数值的更多信息。

C= 39 ^7 mod 55 = 19(M的加密值)

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

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