RSA算法是如何计算的？

RSA 是一种用于公钥加密的密码系统，广泛用于保护敏感信息，尤其是在通过不安全的网络（包括互联网）发送时。

RSA算法是最流行的非对称密钥加密算法，它依赖于一个数学事实：发现和乘以大素数很容易，但分解它们的乘积却很复杂。它需要公钥和私钥。

RSA算法示例

让我们举一个这个过程的例子来学习这些概念。为了便于阅读，可以将示例值与算法步骤一起编写。

  • 选择两个大的素数 P 和 Q

    设 P = 47，Q = 17

  • 计算 N = P x Q

    我们有，N = 7 x 17 = 119。

  • 选择公钥（即加密密钥）E，使其不属于 (P -1) x (Q – 1)

    • 让我们找到 (7 - 1) x (17 -1) = 6 x 16 = 96

    • 96 的因子是 2、2、2、2、2 和 3（因为 96 = 2 x 2 x 2 x 2 x 2 x 3）。

    • 因此，可以选择 E 使得 E 的任何因子都不是 2 和 3。我们不能选择 E 为 4（因为它有因子 2），15（因为它有因子 3）和 6（因为它同时有因子 2 和 3）。

    • 让我们选择 E 为 5（它可以是任何其他数字，其因子不是 2 和 3）。

  • 选择私钥（即解密密钥）D，包括以下等式为真

    (D x E) mod (P – 1) x (Q – 1) = 1

    • 让我们将 E、P 和 Q 的值代入方程。

    • 我们有 (D x 5) mod (7 – 1) x (17 – 1) = 1。

    • 也就是说，(D x 5) mod (6) x (16) = 1。

    • 也就是说，(D x 5) mod (96) = 1

    • 经过一些计算，让我们取 D = 77。然后以下为真：(77 x 5) mod (96) = 385 mod 96 = 1，这就是我们想要的。

  • 对于加密，根据以下公式计算密文 (CT) 从明文 (PT)：

    CT = PTE mod N

    假设我们要加密明文 10。那么，我们有

    CT = 105 mod 119 = 100000 mod 119 = 40。

  • 将 CT 作为密文发送给接收者。

    将 40 作为密文发送给接收者。

  • 对于解密，根据以下公式计算明文 (PT) 从密文 (CT)：

    PT = CTD mod N

    执行以下操作

    PT = CTDmod N

    也就是说，

    PT = 4077mod 119 = 10，这是步骤 5 中的原始明文。

更新于： 2023年11月4日

21K+ 浏览量

开启你的职业生涯

通过完成课程获得认证

开始学习
广告