MENU

密码技术系列 Part 2 - 公钥加密

在对称密码中,由于加密和解密使用的密钥是相同的,因此必须向接受者配送密钥。而密钥在配送的过程中是存在风险的,虽然通过事前共享、分配中心可以一定上规避风险但是这些方案的灵活性和效率方面存在缺陷。但是,如果我们采用公钥密码方案的话就不存在配送问题,某种程度上可以说公钥密码是密码学史上目前为止最伟大的发明。

公钥密码中,密码分为加密密钥和解密密钥两种。发送者用加密密钥对消息加密,接受者使用解密密钥对消息进行解密。大致要点如下:

  • 发送者只需要加密密钥

  • 接受者只需要解密密钥

  • 解密密钥不可能被窃听者获取

  • 加密密钥被窃听截获也没有关系

公钥加密中的加密的公钥和解密的私钥有非常密切的数学关系,两者成对存在而无法单独生成。公钥密钥的使用者只需要将公钥发给别人,而私钥自己保留,简要的通信过程如下:

Public-Key-Encryption

数学基石 RSA 算法

可能你会问公钥加密方案中使用不同密码分别进行加解密操作是如何实现的?这就不得不提应用最广泛的 RSA 算法了。具体的数学证明过程比较复杂,使用到了欧拉定理等几个数学公式。而本文的重点不是数学证明是算法过程,所以如果你对证明感兴趣的话可以查看这两篇文章地址1地址2

RSA 加密与解密

在 RSA 算法中,明文、密钥、密文都是数字形式的。RSA 的加密过程可以用下面的公式来表达:

密文 = 明文 ^ E mod N

一言以蔽之就是密文是明文的 E 次方后求 mod N 的结果。操作非常的简单明了,没有之前对称加密中复杂的多轮比特位换来换去后异或操作。而公式中的 E 和 N 组合在一起就构成了加密时使用的公钥。

解密与加密一样的简单,操作形式都是相同的。用公式描述就是:

明文 = 密文 ^ D mod N

明文是密文的 D 次方后 mod N 的结果,而 D 和 N 组合在一起就构成了私钥。

当然 E、D、N 三个数之间存在紧密的数学关系的,并不是随便选择都可以的。

密钥对生成过程

虽然密钥的数学证明很复杂,但是我们可以简单了解下密钥对的生成过程以及其中的数学关系。密钥对的生成实际上就是 E、D、N 这三个数字的生成,RSA 算法的生成步骤如下:

  1. 求 N

  2. 求 L

  3. 求 E

  4. 求 D

第一步求 N 的步骤是:随机产生两个质数 p 和 q,两个质数要足够大这样才能增加破解难度。当然太大的也会让密钥对生成过程变慢。得到两个大质数 p、q 之后,将其相乘就得到了 N。

  1. = p * q

第二步所求的 L 在加密和解密过程中不会用到,它只是密钥生成过程中的变量。L 是 p-1、q-1 的最小公倍数。

  1. = lcm ( p-1, q-1 )

第三步求 E。E 是一个比 1 大,比 L 小的数字,且 E 和 L 的最大公约数为 1,也就是说 E 和 L 互质。

1 < E < L
gcd (E, L ) = 1

第四步求 D。D 由之前的结果推导而来。

1 < D < L

      1. mod L = 1

对 RSA 的攻击

RSA 的加解密过程非常简单,但是其机密性如何呢?在开始分析攻击可能之前,我们先来看看攻击者所知道的信息:

  • 密文:可以通过窃听来获取

  • 加密密钥对 E 和 N:对所有使用者公开

首先,最容易想到的方法就是暴力破解。因为要破解 RSA 加密算法,只需要知道解密密钥对中的数字 D。但是在 RSA 算法中 p、q 的长度都在 1024 比特位以上,这表明要暴力破解 D 的话需要面对的计算量可能是 2048 比特位的数量级。要在这种数量级上使用暴力破解几乎是没有现实意义的。

接下来就是通过密文来反向求解明文。已知RSA 的加密过程如下:

密文 = 明文 ^ E mod N

由于密文、E、N 已知,那么能否进行反向操作。如果没有后面的 mod N 的操作,既:

密文 = 明文 ^ E

那么就是一个简单的求对数操作,难度不大。但是加上 mod N 之后,就变成了求离散对数的问题,该问题还没有高效的算法,所以也行不通。

当然 RSA 并不是不能被攻击的,现实中存在一种中间人攻击的方式可以破解 RSA 。中间人攻击并不是破解了数字 D ,理论上来说中间人攻击对所有的加密都具有破坏性。一句话总结中间人攻击就是:它类似数字世界的中介,对于信息的接受者它在中间扮演发送者,而对于信息的发送者则扮演接受者。例如:

    1. 需要将使用 B 的公钥加密的信息发送给 B,而现在窃听者 C 偷偷的介入了信息的传输路线。

    1. 发送给 A 的加密公钥被 C 截获,然后 C 将自己的加密密钥发送给 A。

    1. 接收到 C 发送的加密密钥后默认是 A 发送的密钥并使用其加密发送的信息

    1. 接收到 A 发送信息,并使用自己的私钥进行解密。然后使用之前的到的A公钥将解密后信息加密发送给 B

    1. 收到信息后以为是 A 发送过来的并使用自己的私钥进行解密操作。

整个通信过程中 A 和 B 都没有感知 C 的存在,但是实际上 A 与 B 之间的加密通信已经被 C 所完全截获。即使 C 并不知道真实的解密密钥也对其的窃听不产生任何影响。中间人攻击图解如下:

RSA

总结

相比较对称加密而言,公钥加密并不存在密码分配的问题,这在实际的加密过程中带来了巨大的便利性。当然,这并不是说公钥加密就更加安全,对于安全性要求较高的项目来说一定都是采用混合加密方案。另外,对于中间人攻击的防范会在后面带来。

标签: 加密, RSA