公钥加密

公钥密码学

与对称密钥加密不同，我们没有发现公钥加密的历史使用情况。这是一个相对较新的概念。

对称密码学非常适合政府、军队和大型金融公司等参与机密通信的组织。

在过去的几十年里，随着越来越不安全的计算机网络的传播，人们真正需要更大规模地使用密码学。由于对称密钥在密钥管理方面面临挑战，因此被发现不实用。这产生了公钥密码系统。

加密和解密的过程如下图所示 -

公钥密码学

公钥加密方案最重要的属性是 -

  • 加密和解密使用不同的密钥。这是将该方案设置为不同于对称加密方案的属性。

  • 每个接收者都拥有唯一的解密密钥，通常称为他的私钥。

  • 接收者需要发布一个加密密钥，称为他的公钥。

  • 该方案需要对公钥的真实性进行一定程度的保证，以避免对手作为接收者进行欺骗。一般来说，这种类型的密码系统涉及受信任的第三方，该第三方证明特定的公钥仅属于特定的个人或实体。

  • 加密算法足够复杂，足以阻止攻击者从密文和加密（公钥）密钥中推导出明文。

  • 尽管私钥和公钥在数学上是相关的，但从公钥计算私钥是不可行的。事实上，任何公钥密码系统的智能部分都在于设计两个密钥之间的关系。

共有三种类型的公钥加密方案。我们在以下部分讨论它们 -

RSA密码系统

该密码系统是最初的系统之一。即使在今天，它仍然是最常用的密码系统。该系统由三位学者Ron Rivest、Adi Shamir和Len Adleman发明，因此被称为 RSA 密码系统。

我们将看到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 5 = {1, 2, 3, 4})。

氮 3n _ 3 n模 5
1 3 3
2 9 4
3 27 2
4 81 1

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

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

y = gx mod p

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

    例如，假设p=17，g=6（可以确认6是群Z 17的生成元）。私钥 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系统中，每个用户都有一个私钥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方案。

RSA 埃尔加马尔
加密效率更高。 解密效率更高。
解密效率较低。 解密效率更高。
对于特定的安全级别，RSA 中需要较长的密钥。 对于相同级别的安全性，需要非常短的密钥。
它被广泛接受和使用。 它是新产品，在市场上不太受欢迎。