离散数学中的RSA加密

RSA的缩写是Rivest Shamir Adleman。它是一种加密算法，用于通过互联网安全地传输消息。该算法背后的原理是，我们可以轻松地将大量数字相乘，但很难对大数进行因数分解。例如，当我们乘以31和37时，很容易得到结果1147，但确定1147的因数是一个非常漫长的过程。

RSA是一种公钥密码术。公钥密码术需要两个密钥。一个密钥用于解密消息，第二个密钥用于加密消息。这意味着一个密钥将是公钥，第二个密钥将对所有人保密。第二个密钥也可以称为私钥。

有各种类型的公钥密码术，但最著名的是RSA。RSA完全基于数论。RSA可用于文件加密、安全shell或ftp、发送信用卡/借记卡信息、保存密码、加密电子邮件等。

示例1：所有者可以公开的发送消息，并通过公钥对其进行加密，但只有所有者可以使用私钥对其进行解密。这就好像我们有一个私人的上锁盒子，里面装着消息的插槽。

也可能出现相反的情况，即所有者使用其私钥加密消息，而任何人都可以对其进行解密。但在这种情况下，只有所有者可以加密消息。

示例2：假设COMPSCI 2的一名学生想将他们的家庭作业解决方案发送到Piazza供Harry阅读，同时又不希望其他学生阅读他们的解决方案。现在，我们需要确定Harry如何能够轻松地让每个人都使用公共频道向他发送秘密，而没有人能够阅读。

解决方案：如果我们试图为每个配对建立一个单独的通信渠道，那么这个过程将非常漫长。这意味着如果我们使用公钥加密消息并用私钥解密，那将是冗长的。

情况是不对称的：Piazza上的每个人都可以给Harry发送消息。密文可以被任何人读取，但只有发送者（COMPSCI 2）和Harry能够阅读每条消息的明文。

为了在现实世界中更好地理解这个例子，我们可以将Harry替换为银行，家庭作业替换为信用卡号，学生替换为客户。因此，每个拥有银行账户的人都会向银行发送消息。其他客户只能知道某个客户拥有这家银行的信用卡，但只有银行和该客户知道信用卡的详细信息。

RSA密钥的生成

以下步骤将用于在RSA中生成公钥或私钥对

1. 假设存在一对p和q，它们表示大的随机素数，并且具有相同的位数。我们需要生成这些p和q。
2. 现在，我们必须计算n，形式如下：
   n = pq
   这里，模数由公有整数n表示。
3. 现在，我们将选择一个奇数公钥指数e，它与以下项互质：(p - 1)(q - 1) 且 1 < e < (p - 1)(q - 1)
4. 现在，我们必须计算p、q和私钥指数d。
5. 私钥将由对(n, d)计算，公钥由对(n, e)表示。

与密钥生成相关的问题

以下是一些与密钥生成相关的问题：

问题1：假设我们有Φ，并且我们需要确定e，使得1 < e < Φ 且 GCD(Φ, e) = 1

答案：正如我们所见，e小于Φ且大于1，并与Φ互质。

所以这里我们将尝试素数，并且必须注意这些素数不能整除Φ。

问题2：假设我们有e和Φ，并且我们需要确定d，使得d ⋅ e ≡ 1 (mod Φ)

答案：为了解决这个问题，我们有一个解决方案。因此，我们可以使用欧几里得扩展GCD算法。

RSA的工作场景

假设Alice想将办公室文件发送给Bob。她会在Piazza上发布成绩，但同时又不希望其他学生看到它们。为此，Alice和Bob需要一个密码系统。Bob同时拥有公钥和私钥。因此，Bob将为他们的办公室隐私设置私钥和公钥。公钥(n, e)设置为(3233, 17)，私钥(n, d)设置为(3233, 2753)。他会保密'd'，并将'n'和'e'发布在Piazza上。

在这里，Alice使用Bob的公钥加密消息。Alice也不知道私钥d。否则，如果Bob将私钥发送给Alice，就可能被别人截获。Bob能够使用自己的私钥解密消息。我们只能使用公钥加密消息，但我们不能解密它。因此，在这种情况下，Piazza上的任何人都能够给Bob发送消息。但每条消息的明文都可以由发送者和Bob阅读。

RSA加密

加密用于秘密发送消息。我们可以通过以下方式加密编码为整数的消息：

首先，我们将每个字母转换为一个整数。然后，我们通过将这些整数分组来形成一个更大的整数。一个字母块将由这些更大的整数表示。每个块都可以通过以下映射进行加密：

换句话说，RSA的加密操作可以描述为以以下形式进行e次幂模n的指数运算：

这里c用于表示生成的密文，输入m用于表示消息。实际上，消息m可以被描述为某种适当格式化的共享密钥。借助传统的加密算法，实际消息可以用共享密钥进行加密。借助这种结构，我们可以仅通过一次指数运算加密任意长度的消息。

例如

假设Anne想发送消息“gcd”给Chris。为此，她会将该消息编码为一个正整数m，该整数必须小于模数n = 3233。

如果消息更长，则会分成块。变换将是可逆的。在此示例中，将使用两个字符的块，并且字母最多为9个字符，如下所示：

这里的下划线用于表示填充。这显然是可逆的。到目前为止，没有什么秘密或神秘之处。我们将分别加密并发送73和40。首先，我们将发送m = 73，然后我们将发送m = 40。

RSA加密的工作原理

这里消息m = 73，公钥(n, e) = (3233, 17)。

当我们加密消息时，它会生成如下的密文：

c = m^e MOD n

代入值后，我们将得到以下结果：

c = 73¹⁷ MOD 3233

c = 4747758526700098686074966922953 MOD 3233 = 1486

正如我们所见，最终结果很小，但中间结果却非常大。我们可以借助pow函数来解决这个问题。然后将c（密文）的结果1486发布到Piazza上。

RSA加密示例

在此示例中，我们必须使用RSA加密消息“STOP”，其中p = 43，q = 59，e = 13。

解决方案

1. 我们必须首先使用以下公式确定n：
   n = p * q
   n = 43 * 59 = 2537
2. 之后，我们将每个字母转换为[0, 25]中的数字。
   S = 18, T = 19, O = 14, P = 15。
3. 现在，我们将序列分组为4位数字块，如下所示：
   m = 1819 1415
4. 现在，我们将使用以下公式加密每个块：
   c = m¹³ (mod 2537)
5. 现在，我们必须首先像这样确定第一个块：
   1819¹³ mod 2537 = 2081
6. 现在，我们必须像这样确定第二个块：
   1415¹³ mod 2537 = 2182

因此，密文c = 2081 2182