公钥加密

我们将看到 RSA 密码系统的两个方面，首先是密钥对的生成，其次是加解密算法。

RSA密钥对的生成

希望参与加密通信的每个人或一方都需要生成一对密钥，即公钥和私钥。 生成密钥的过程如下所述 −

• 生成 RSA 模数 (n)

  • 选择两个大素数，p 和 q。

  • 计算 n=p*q。 为了获得强大且牢不可破的加密，请让 n 为一个很大的数字，通常至少为 512 位。

• 查找派生数 (e)

  • 数字e必须大于1且小于(p − 1)(q − 1)。

  • 除了 1 之外，e 和 (p − 1)(q − 1) 一定没有公因数。换句话说，两个数 e 和 (p – 1)(q – 1) 是互质的。

• 构建公钥

  • 这对数字 (n, e) 形成 RSA 公钥并公开。

  • 有趣的是，虽然 n 是公钥的一部分，但分解大素数的困难确保攻击者无法在有限时间内找到用于获得 n 的两个素数(p 和 q)。 这就是 RSA 的优势。

• 生成私钥

  • 私钥 d 由 p、q 和 e 计算得出。 对于给定的 n 和 e，有唯一的数字 d。

  • 数字 d 是 e 模 (p - 1)(q – 1) 的倒数。 这意味着 d 是小于 (p - 1)(q - 1) 的数，因此当乘以 e 时，它等于 1 模 (p - 1)(q - 1)。

  • 这种关系用数学方式表示如下 −

ed = 1 mod (p − 1)(q − 1)

扩展欧几里得算法将 p、q 和 e 作为输入，并给出 d 作为输出。

示例

下面给出了生成 RSA 密钥对的示例。 (为了便于理解，这里的素数p和q取的值很小。实际上，这些值非常高)。

• 设两个素数为 p = 7 和 q = 13。因此，模数 n = pq = 7 x 13 = 91。

• 选择 e = 5，这是一个有效的选择，因为除了 1 之外，没有任何数字是 5 和 (p − 1)(q − 1) = 6 × 12 = 72 的公因数。

• 数字对 (n, e) = (91, 5) 构成公钥，我们希望向我们发送加密消息的任何人都可以使用它。

• 将 p = 7、q = 13 和 e = 5 输入到扩展欧几里德算法。 输出将为 d = 29。

• 通过计算检查计算出的d是否正确 −

de = 29 × 5 = 145 = 1 mod 72

• 因此，公钥是 (91, 5)，私钥是 (91, 29)。

加密与解密

一旦生成密钥对，加密和解密的过程就相对简单且计算容易。

有趣的是，RSA 并不像对称密钥加密那样直接对字符串进行操作。 它对以 n 为模的数字进行运算。 因此，有必要将明文表示为一系列小于n的数字。

RSA 加密

• 假设发件人希望向公钥为 (n, e) 的人发送一些短信。

• 然后发送者将明文表示为一系列小于 n 的数字。

• 加密第一个明文 P，它是一个模 n 的数字。 加密过程是简单的数学步骤，如下所示 −

C = Pe mod n

• 换句话说，密文C等于明文P与其自身相乘e倍，然后再对n取模。 这意味着C也是小于n的数。

• 回到我们的密钥生成示例，明文 P = 10，我们得到密文 C −

C = 105 mod 91

RSA 解密

• RSA 的解密过程也非常简单。 假设公钥对(n,e)的接收者收到了密文C。

• 接收者将 C 提升到他的私钥 d 的幂。 对 n 取模的结果将是明文 P。

Plaintext = Cd mod n

• 再次回到我们的数值示例，密文 C = 82 将使用私钥 29 解密为数字 10 −

Plaintext = 8229 mod 91 = 10

RSA 分析

RSA 的安全性取决于两个独立功能的强度。 RSA 密码系统是最流行的公钥密码系统，其强度基于分解非常大的数字的实际难度。

• 加密函数 − 它被认为是一种将明文转换为密文的单向函数，只有知道私钥 d 才能逆向转换。

• 密钥生成 − 从 RSA 公钥确定私钥的难度相当于对模 n 进行因式分解。 因此，攻击者不能使用 RSA 公钥的知识来确定 RSA 私钥，除非他可以分解 n。 它也是一个单向函数，从 p 和 q 值到模 n 很容易，但反向是不可能的。

如果这两个函数中的任何一个被证明是非单向的，那么 RSA 将被破坏。 事实上，如果开发出一种高效分解技术，那么 RSA 将不再安全。

如果数字 p 和 q 不是大素数和/或选择的公钥 e 是小数字，那么 RSA 加密的强度会急剧下降以抵御攻击。

ElGamal 加密系统

除了 RSA 之外，还提出了其他公钥密码系统。 其中许多都是基于不同版本的离散对数问题。

ElGamal 密码系统，称为椭圆曲线变体，基于离散对数问题。 它的强度来源于这样的假设:在实际时间范围内无法找到给定数字的离散对数，而幂的逆运算可以有效计算。

让我们看一下 ElGamal 的简单版本，它可以对 p 进行模运算。 对于椭圆曲线变体，它基于完全不同的数字系统。

ElGamal 密钥对的生成

ElGamal密码系统的每个用户通过以下方式生成密钥对 −

• 选择大的素数p。一般选择1024到2048位长度的素数。

• 选择生成器元素 g。

  • 该数字必须介于 1 和 p − 1 之间，但不能是任何数字。

  • 它是整数模 p 的乘法群的生成器。 这意味着对于每个与 p 互质的整数 m，都有一个整数 k 使得 g^k=a mod n。

    例如，3 是组 5 的生成器 (Z₅ = {1, 2, 3, 4})。

• 选择私钥。私钥 x 是大于 1 且小于 p−1 的任何数字。

• 计算公钥的部分。 值 y 由参数 p、g 和私钥 x 计算得出，如下所示 −

y = gx mod p

• 获取公钥。ElGamal公钥由三个参数(p、g、y)组成。

  例如，假设p = 17，g = 6(可以确认6是群Z₁₇的生成元)。 私钥 x 可以是大于 1 且小于 71 的任何数字，因此我们选择 x = 5。然后计算值 y 如下 −

y = 65 mod 17 = 7

• 因此私钥是 62，公钥是 (17, 6, 7)。

加密与解密

ElGamal 密钥对的生成比 RSA 的等效过程相对简单。 但加密和解密比RSA稍微复杂一些。

ElGamal 加密

假设发送者希望将明文发送给 ElGamal 公钥为 (p, g, y) 的人，则 −

• 发送方将明文表示为一系列以 p 为模的数字。

• 加密第一个明文P，它表示为对p取模的数字。 得到密文C的加密过程如下 −

  • 随机生成一个数字k;
  • 计算两个值 C1 和 C2，其中 −

C1 = gk mod p
C2 = (P*yk) mod p

• 发送密文 C，由两个单独的值(C1、C2)组成，一起发送。

• 参考上面给出的 ElGamal 密钥生成示例，明文 P = 13 加密如下 −

  • 随机生成一个数字，假设 k = 10
  • 计算两个值 C1 和 C2，其中 −

C1 = 610 mod 17
C2 = (13*710) mod 17 = 9

• 发送密文C = (C1, C2) = (15, 9)。

ElGamal 解密

• 要使用私钥x解密密文(C1，C2)，需要执行以下两个步骤 −

  • 计算(C1)^x模p的模逆，即(C1)^-x ，一般称为解密因子。

  • 通过以下公式获取明文 −

C2 × (C1)-x  mod p = Plaintext

• 在我们的示例中，使用私钥 x = 5 解密密文 C = (C1, C2) = (15, 9)，解密因子为

15-5  mod 17 = 9

• 提取明文 P = (9 × 9) mod 17 = 13。

ElGamal 分析

在ElGamal系统中，每个用户都有一个私钥x。 并具有公钥的三个组成部分 − 质数模 p、生成元 g 和公共 Y = g^x mod p。 ElGamal 的强度基于离散对数问题的难度。

安全密钥大小一般为 > 1024 位。 如今甚至使用 2048 位长的密钥。 在处理速度方面，Elgamal 相当慢，它主要用于密钥认证协议。 由于处理效率更高，ElGamal 的椭圆曲线变体变得越来越流行。

椭圆曲线密码学 (ECC)

椭圆曲线密码学 (ECC) 是一个术语，用于描述一套密码工具和协议，其安全性基于离散对数问题的特殊版本。 它不使用以 p 为模的数字。

ECC 基于与称为椭圆曲线的数学对象相关联的数字集。 存在对这些数字进行相加和计算倍数的规则，就像对 p 取模的数字有规则一样。

ECC 包括许多加密方案的变体，这些方案最初是为模块化数字设计的，例如 ElGamal 加密和数字签名算法。

据信，离散对数问题应用于椭圆曲线上的点时要困难得多。 这提示从以 p 为模的数字切换到椭圆曲线上的点。 如果我们使用基于椭圆曲线的变体，还可以使用较短的密钥获得等效的安全级别。

较短的键有两个好处 −

• 易于密钥管理
• 高效计算

这些优势使得基于椭圆曲线的加密方案变体对于计算资源受限的应用程序极具吸引力。

RSA 和 ElGamal 方案 – 比较

让我们从各个方面简单比较一下RSA和ElGamal方案。