RSA 加密算法

RSA 加密算法是一种公钥加密算法。为了更好地理解 RSA，我们首先来了解什么是公钥加密算法。

公钥加密算法

公钥加密算法也称为非对称算法。非对称算法是指加密和解密使用不同密钥的算法。每个发送者都分配有一对密钥。

• 公钥
• 私钥

公钥用于加密，私钥用于解密。无法使用公钥进行解密。这两个密钥是关联的，但私钥无法从公钥推导出来。公钥是众所周知的，而私钥是保密的，只有拥有该密钥的用户才知道。这意味着任何人都可以使用用户的公钥向该用户发送消息。但只有用户才能使用其私钥解密消息。

公钥算法的运行方式如下：

• 要发送的数据由发送者 A 使用接收者的公钥进行加密。
• B 使用其私钥（只有 B 知道）解密接收到的密文。B 通过使用 A 的公钥加密其消息来回复 A。
• A 使用其私钥（只有他自己知道）解密接收到的密文。

RSA 加密算法

RSA 是最常见的公钥算法，以其发明者 Rivest、Shamir 和 Adelman（RSA）的名字命名。

RSA 算法使用以下过程生成公钥和私钥：

• 选择两个大的素数 p 和 q。
• 将这两个数相乘得到 n = p x q，其中 n 称为加密和解密的模数。
• 选择一个小于 n 的数 e，使得 n 与 (p - 1) x (q - 1) 互质。这意味着 e 和 (p - 1) x (q - 1) 除了 1 之外没有公因子。选择“e”使得 1<e < φ (n)，e 与 φ (n) 互质。
  gcd (e,d(n)) =1
• 如果 n = p x q，则公钥为 <e, n>。明文消息 m 使用公钥 <e, n> 进行加密。为了从明文得到密文，使用以下公式得到密文 C。
  C = m^e mod n
  此处，m 必须小于 n。较大的消息（>n）被视为消息的连接，每条消息都单独加密。
• 为了确定私钥，我们使用以下公式计算 d，使得
  D_e mod {(p - 1) x (q - 1)} = 1
  或
  D_e mod φ (n) = 1
• 私钥为 <d, n>。密文消息 c 使用私钥 <d, n> 进行解密。为了从密文 c 计算明文 m，使用以下公式得到明文 m。
  m = c^d mod n

让我们举一个 RSA 加密算法的例子。

示例 1

这个例子展示了我们如何使用 RSA 公钥加密算法加密明文 9。本例使用素数 7 和 11 来生成公钥和私钥。

说明

步骤 1：选择两个大的素数 p 和 q。

p = 7

q = 11

步骤 2：将这两个数相乘得到 n = p x q，其中 n 称为加密和解密的模数。

首先，我们计算

n = p x q

n = 7 x 11

n = 77

步骤 3：选择一个小于 n 的数 e，使得 n 与 (p - 1) x (q - 1) 互质。这意味着 e 和 (p - 1) x (q - 1) 除了 1 之外没有公因子。选择“e”使得 1<e < φ (n)，e 与 φ (n) 互质，gcd (e, d (n)) =1。

其次，我们计算

φ (n) = (p - 1) x (q-1)

φ (n) = (7 - 1) x (11 - 1)

φ (n) = 6 x 10

φ (n) = 60

现在让我们选择 60 的相对素数 e 为 7。

因此，公钥为 <e, n> = (7, 77)

步骤 4：明文消息 m 使用公钥 <e, n> 进行加密。为了从明文得到密文，使用以下公式得到密文 C。

为了从明文得到密文，使用以下公式得到密文 C。

C = m^e mod n

C = 9⁷ mod 77

C = 37

步骤 5：私钥为 <d, n>。为了确定私钥，我们使用以下公式计算 d，使得

D_e mod {(p - 1) x (q - 1)} = 1

7d mod 60 = 1，得到 d = 43

私钥为 <d, n> = (43, 77)

步骤 6：密文消息 c 使用私钥 <d, n> 进行解密。为了从密文 c 计算明文 m，使用以下公式得到明文 m。

m = c^d mod n

m = 37⁴³ mod 77

m = 9

在此示例中，明文 = 9，密文 = 37。

示例 2

在 RSA 密码系统中，某个 A 使用两个素数 13 和 17 来生成公钥和私钥。如果 A 的公钥是 35。那么 A 的私钥是...........？。

说明

步骤 1：第一步，选择两个大的素数 p 和 q。

p = 13

q = 17

步骤 2：将这两个数相乘得到 n = p x q，其中 n 称为加密和解密的模数。

首先，我们计算

n = p x q

n = 13 x 17

n = 221

步骤 3：选择一个小于 n 的数 e，使得 n 与 (p - 1) x (q - 1) 互质。这意味着 e 和 (p - 1) x (q - 1) 除了 1 之外没有公因子。选择“e”使得 1<e < φ (n)，e 与 φ (n) 互质，gcd (e, d (n)) =1。

其次，我们计算

φ (n) = (p - 1) x (q-1)

φ (n) = (13 - 1) x (17 - 1)

φ (n) = 12 x 16

φ (n) = 192

g.c.d (35, 192) = 1

步骤 3：为了确定私钥，我们使用以下公式计算 d，使得

计算       d = d_e mod φ (n) = 1

d = d x 35 mod 192 = 1

d = (1 + k.φ (n))/e           [令 k=0, 1, 2, 3………………]

令 k = 0

d = (1 + 0 x 192)/35

d = 1/35

令 k = 1

d = (1 + 1 x 192)/35

d = 193/35

令 k = 2

d = (1 + 2 x 192)/35

d = 385/35

d = 11

私钥为 <d, n> = (11, 221)

因此，私钥即 d = 11

示例 3

RSA 密码系统使用素数 3 和 13 来生成公钥= 3 和私钥= 7。明文的密文值是多少？

说明

步骤 1：第一步，选择两个大的素数 p 和 q。

p = 3

q = 13

步骤 2：将这两个数相乘得到 n = p x q，其中 n 称为加密和解密的模数。

首先，我们计算

n = p x q

n = 3 x 13

n = 39

步骤 3：如果 n = p x q，则公钥为 <e, n>。明文消息 m 使用公钥 <e, n> 进行加密。因此，公钥为 <e, n> = (3, 39)。

为了从明文得到密文，使用以下公式得到密文 C。

C = m^e mod n

C = 5³ mod 39

C = 125 mod 39

C = 8

因此，由明文生成的密文为 C = 8。

示例 4

RSA 密码系统使用素数 3 和 11 来生成私钥= 7。使用 RSA 公钥加密算法，明文为 5 的密文值是多少？

说明

步骤 1：第一步，选择两个大的素数 p 和 q。

p = 3

q = 11

步骤 2：将这两个数相乘得到 n = p x q，其中 n 称为加密和解密的模数。

首先，我们计算

n = p x q

n = 3 x 11

n = 33

步骤 3：选择一个小于 n 的数 e，使得 n 与 (p - 1) x (q - 1) 互质。这意味着 e 和 (p - 1) x (q - 1) 除了 1 之外没有公因子。选择“e”使得 1< e < φ (n)，e 与 φ (n) 互质，gcd (e, d (n)) =1。

其次，我们计算

φ (n) = (p - 1) x (q-1)

φ (n) = (3 - 1) x (11 - 1)

φ (n) = 2 x 10

φ (n) = 20

步骤 4：为了确定公钥，我们使用以下公式计算 d，使得

计算 e x d = 1 mod φ (n)

e x 7 = 1 mod 20

e x 7 = 1 mod 20

e = (1 + k. φ (n))/ d              [令 k=0, 1, 2, 3………………]

令 k = 0

e = (1 + 0 x 20) / 7

e = 1/7

令 k = 1

e = (1 + 1 x 20) / 7

e = 21/7

e = 3

公钥为 <e, n> = (3, 33)

因此，公钥即 e = 3