Python中的RSA算法

非对称加密算法是 RSA 算法。实际上，非对称性指的是它同时作用于公钥和私钥。正如名称所示，私钥是保密的，而公钥则分发给所有人。

非对称加密示例

• 例如，客户端通过将其公钥发送给服务器来请求数据，比如浏览器。
• 服务器使用客户端的公钥加密数据，然后发送。
• 客户端收到数据后进行解密。

由于这是非对称的，即使其他人拥有浏览器的公钥，也只有浏览器本身能够解码数据。

原理！ 大整数难以分解是 RSA 原理的基础。公钥由两个数字组成，其中一个是由两个大素数相乘得到的。私钥也是由这两个素数生成的。因此，如果大整数能够被分解，私钥就会泄露。结果，密钥的长度决定了加密的强度，并且随着密钥长度的加倍或三倍，加密的强度会呈指数级增长。RSA 密钥通常为 2048 或 1024 位长，但专家预测 1024 位密钥很快就会被破解。然而，目前来看这似乎是不可能完成的任务。

现在我们来分析 RSA 算法的工作原理

• 公钥生成

• 私钥生成

我们现在准备好了我们的私钥 (d = 2011) 和公钥 (n = 3127 和 e = 3)。现在我们将加密 "HI"

下面展示了 RSA 算法的实现

方法 1

加密和解密小数值。

输出

Message data = 12.000000
Encrypted data = 3.000000
Original Message Sent = 12.000000

方法 2

使用每个字母和数字的 ASCII 值来加密和解码明文消息

输出

Initial message:
Test Message

The encoded message(encrypted by public key)
863312887135951593413927434912887135951359583051879012887

The decoded message(decrypted by private key)
Test Message

使用本原根的 RSA 密码系统在 C++ 中实现

我们将以一种基本的方式使用本原根来实现 RSA。

步骤 1：生成密钥

首先，我们必须生成两个大素数 p 和 q。这两个素数的乘积，应该比我们要加密的消息稍大，并且长度大致相等。

任何素性测试算法，例如 Miller-Rabin 测试，都可以生成素数。获得两个素数后，我们可以计算它们的乘积 n = p*q，这构成了我们 RSA 系统的模。

为了计算 gcd(e, phi(n)) = 1，我们必须选择一个整数 e，使其满足 1 < e < phi(n)，其中 phi(n) = (p-1)*(q-1) 是欧拉的 totient 函数。此值 e 将是公钥指数。

为了计算私钥指数 d，我们必须找到一个整数 d，使得 d*e = 1 (mod phi(n))。您可以通过应用扩展欧几里得算法来完成此操作。

我们的公钥是 (n, e)，私钥是 (n, d)。

步骤 2：加密

消息 m 必须转换为介于 0 和 n-1 之间的整数才能被加密。UTF-8 或 ASCII 等可逆编码方案可用于此目的。

获得消息的整数表示后，我们使用公式 c = m^e (mod n) 计算密文 c。二进制指数运算是可用于此目的的有效模幂运算算法之一。

步骤 3：解密

为了解密密文 c，我们计算明文 m 为 m = c^d (mod n)。同样，模幂运算算法使我们能够快速完成此任务。

步骤 4：示例

让我们通过一个例子来展示 RSA 密码系统如何使用小数字来运行。

假设我们选择 p = 11 和 q = 13，得到的 n = 143 和 phi(n) = 120。鉴于 gcd (7, 120) = 1，我们可以选择 e = 7。由于 7*103 = 1 (mod 120)，我们可以使用扩展欧几里得算法计算 d = 103。

我们的公钥是 (143, 7)，私钥是 (143, 103)。

假设我们想加密 "HELLO" 消息。使用 ASCII 编码，我们可以将其转换为数字 726564766。我们使用公钥计算密文为 c = 726564766^7 (mod 143) = 32。

使用私钥，我们可以通过计算原始消息 m = 32^103 (mod 143) = 726564766 来解密密文。

示例代码

程序说明

这个 C++ 程序实现了 RSA (Rivest-Shamir-Adleman) 密码系统，这是一个流行的非对称加密技术。它在计算给定复合数 'n' 的欧拉 totient 函数 (phi) 后，会生成一个模 'n' 的随机本原根。该软件会计算一个由 'd' 和 'n' 组成的私钥，以及一个由 'e' 和 'n' 组成的公钥。通过将消息 'm' 的 'e' 次幂模 'n' 以及密文 'c' 的 'd' 次幂模 'n' 分别计算，可以展示加密和解密的工作原理。为了说明 RSA 加密和解密过程，程序会打印出原始消息、加密消息和解密消息。

输出

Public key: {3, 3233}
Private key: {2011, 3233}
Original message: 123456
Encrypted message: 855
Decrypted message: 123456

优点

• 安全性： RSA 方法因其高度安全性而常用于安全数据传输。
• 公钥密码学： RSA 算法使用两个独立的密钥进行加密和解密，使其成为一种公钥密码学算法。数据使用公钥加密，使用私钥解密。
• 密钥交换： 双方可以通过使用 RSA 方法进行安全密钥交换，在不实际通过网络发送的情况下交换一个秘密密钥。
• 数字签名： 发送者可以使用其私钥对消息进行签名，接收者可以使用发送者的公钥验证签名。这种技术被称为 RSA 方法。
• 速度： 由于其效率和速度，RSA 方法非常适合在实时应用程序中使用。
• 广泛使用： RSA 算法在许多行业和应用中得到广泛开发，包括在线银行、电子商务和安全通信。

缺点

• 处理速度慢： 与其他加密方法相比，RSA 算法处理数据的速度较慢，尤其是在处理大量数据时。
• 密钥长度大： RSA 方法的安全性依赖于很大的密钥长度，这需要更大的处理能力和存储容量。
• 易受侧信道攻击： RSA 方法容易受到侧信道攻击，攻击者可以通过利用通过侧信道释放的数据（包括电磁辐射、功耗和时序分析）来获取私钥。
• 在某些应用中的使用受限： 由于其处理速度缓慢，RSA 方法不适用于某些需要不断加密和解密大量数据的应用。
• 复杂性： RSA 算法是一种复杂的数学方法，对某些人来说可能难以理解和应用。
• 密钥管理： 尽管有时可能具有挑战性，但 RSA 技术需要对私钥进行安全管理。
• 处理量子计算的能力： RSA 算法容易受到量子计算机的攻击，这可能导致数据解密。