密码技术学习笔记——公钥密码

学习《图解密码技术》补充密码学相关基础知识过程中所做的简单学习笔记,只记录要点,所用图例的来源均为《图解密码技术》一书。

本篇主要参考本书第五章——公钥密码

公钥密码也称非对称加密。

在对称密码中,加密与解密使用的是相同的密钥,所以在传递秘文之外,还需要向接收者传输密钥,这就引入了一个密钥配送的问题。

而如果使用公钥密码,则无需向接收者传输密钥,解决了密钥配送的问题。可以说公钥密码是密码学历史上最伟大的发明。

公钥密码

在公钥密码(public-key cryptography)中,密钥分为加密密钥和解谜密钥两种。加密密钥是发送者加密时使用的,解密密钥则是接受者解密时使用的。

加密密钥一般是公开的,也称为公钥(public key),解密密钥是不公开的,称为私钥(private key)。一对公钥与私钥成为密钥对(key pair)。密钥对中的两个密钥在数学上是有紧密相关的,是不能分别单独生成的。

由于加密时使用的密钥和解密时使用的密钥不一样,相对于对称密码的加解密使用同一对密钥来说,公钥密码也称为“非对称密码”

公钥通信的流程如下:

公钥通信的流程

可以看到,私钥并没有出现在通信内容中,因此窃听者无法对密文进行解密。

公钥密码的局限性

公钥密码也是面临着一些问题的,比如,需要判断所得到的公钥是否正确合法,这个问题被称为“公钥认证”问题,此外,公钥密码的处理速度只有对称密码的几百分之一。

RSA

现在最常用的公钥密码算法是RSA,但除了RSA外,还有很多其他的公钥密码。比如ElGamal方式、Rabin方式以及椭圆曲线密码等。这里我们重点介绍RSA密码。

RSA是现在使用最广泛的公钥密码算法。RSA可以被用于公钥密码和数字签名。

RSA加解密算法

RSA的加密过程: RSA的加密就是“求明文E次方的modN”(明文E次方以N为模求余),这里{E, N}就称为公钥。

RSA加密过程

RSA的解密过程: RSA的解密就是“求密文D次方的modN”(密文D次方以N为模求余),这里{D, N}就称为私钥,由于N也是公钥的一部分,也是公开的,所以也可以单独地把D称为私钥。

RSA解密过程

整理一下,RSA的加密和解密如下:

RSA的加密和解密

RSA密钥对的生成

现在可以看到,在RSA中,加密和解密的形式是相同的,而作为解密密钥的D,和数字E有着相当紧密的数学联系,才能实现用E加密的结果可以用D来解密的机制。

那么,在RSA加密算法中用到的E、D和N到底应该如何生成呢?

RSA密钥对的生成过程如下:

  • 求N
  • 求L(L是仅在生成密钥对过程中使用的数)
  • 求E
  • 求D

下面分步说明RSA密钥对的生成:

  1. 求N 首先准备两个很大的质数p和q,p和q太小的话,密码会变得容易被破译,太大的话计算时间又会变得很长。生成大质数的是要用到伪随机数生成器来生成的,如果生成的不是质数,就要用伪随机数重新生成另外一个数,然后再判断。 准备好着两个很大的质数之后,将其相乘,其结果就是数N。

  2. 求L L这个数载RSA的加密和解密过程中都不出现,只出现在生成密钥对的过程中。 L是p-1和q-1的最小公倍数(least common multiple, lcm)。

  3. 求E E是一个比1大,比L小的数。此外,E和L的最大公约数(greatest common divisor, gcd)必须为1,也就是说,E和L互质。生成E也是要使用到伪随机数生成器的,先用伪随机数生成器生成大于1小于L的候选E,然后再判断其是否满足E与L互质的条件。求最大公约数可以使用欧几里得的辗转相除法。

  4. 求D

    D是由E计算得到的,D、E和L之间必须具备下列关系:

要保证存在这样的D,就要求E和L必须得互质,否则是不存在满足公式的D的,这也正是第3步求E时的要求。 只要D满足上述条件,那么用E和N进行加密的密文,就可以通过D和N进行解密了。

经过上面四个步骤,已经求出了N和E、D,也就是生成了RSA的密钥对。整理一下以上生成密钥对的过程:

RSA密钥对生成

还需要注意的是,加密的明文必须是小于N的数,因为解密时最终要求mod N,算出的结果是一定小于N的,因此如果明文本身大于N,则解密后无法得到正确的明文。

RSA的机密性

相对于对称密码通过将明文转换为复杂形式来保证其机密性,公钥密码则是基于数学上的困难问题来保证机密性的。

可以看到,RSA主要是利用了离散对数求解的数学困难、以及大整数的质因数分解问题的数学困难来保证其机密性的。

  • 密文 = 明文的E次方 mod N,得到密文,想要求解明文的问题实际上就变成了一个求离散对数的问题,这是非常困难的,因为人类还没有发现求离散对数的高效算法。
  • 对于RSA来说,有一点非常重要,那就是大质数p和q不能被密码破译者知道,把p和q交给破译者与把私钥交给破译者是等价的。 由于N = pq,而且N是公开的,要想通过N求出p和q,这里就存在一个*对N进行质因数分解求p与q的问题。 因此可以说,一旦发现了对大整数进行质因数分解的高效算法,RSA就能够被破译。然而,目前还没有发现对大整数进行质因数分解的高效算法,而且也尚未证明质因数分解是否真的是非常困难的问题,甚至也不知道是否存在一种分解质因数的简单方法。

中间人攻击

中间人攻击虽然不能破译RSA,但却是一种针对机密性的有效攻击。

所谓中间人攻击,就是说攻击者混入到发送者和接受者中间,对发送者伪装接受者,对接受者伪装发送者的攻击方式。

假设存在这样一个场景,A和B使用公钥密码来加密通信,而他们之间的通信可以被主动攻击者C拦截,那么C就可以对A和B的加密通信进行中间人攻击:

  • A向B发送邮件:我要和你通信,把你的公钥发给我。
  • C通过窃听知道了A正在向B索取公钥。
  • B向A回复邮件:这是我的公钥!
  • C拦截了B对A的回复邮件,并获得了B的公钥。然后,C生成了自己的公钥和私钥,然后伪装成B将自己的C公钥发送给A,而把B的公钥保存好。
  • A收到了C伪装B发送的回复邮件,获得了C的公钥,当然了,A以为这是B的公钥,然后开始进行加密通信!
  • A将明文通过C的公钥加密后发送给B。
  • C拦截了A发送给B的密文,然后使用自己的私钥对密文解密(注意,A不知道自己得到的公钥是C的,以为是B的呢),得到了明文,然后将明文保存好,再将明文用B的公钥加密后,伪装成A将密文发送给B。
  • B收到了用自己的公钥加密的密文,然后用自己的私钥解密,正常读取到了明文内容。

在这个中间人攻击的过程中,非对称加密算法正常工作,而消息原本的发送者和接受者也能“正常地”发送接收信息,并不会意识到中间人的存在!因为中间人通过劫持信息和伪造信息,把两头都给欺骗了,成功截取了双方通信的内容,并且随时可以对信息内容进行篡改等进一步的恶意行为。

用一个图例更清晰地说明中间人攻击的过程:

公钥加密的中间人攻击

这种中间人攻击的方法不只是针对RSA,而是可以针对任何公钥密码,可以看到,仅靠公钥密码本身,是无法防御中间人攻击的。

要防御中间人攻击,还需要一种手段来确认收到的公钥是否真的属于消息的接受者,而不是中间人攻击的攻击者,这种手段我们称之为“认证”,在这种情况下,我们可以使用公钥的证书

End of article
感谢阅读 ♪(^∇^*)

相关文章

评论区