公钥密码

公钥密码密钥配送问题——key distribution problem事先共享密钥密钥分配中心Diffie-Hellman密钥交换公钥密码时钟运算mod运算减法乘法RSARSA密钥对的生成步骤对RSA的攻击中间人攻击选择密文攻击其他公钥密码ElGamalRabin椭圆曲线密码对称密码和公钥密码对比

密钥配送问题——key distribution problem

解决密钥配送问题的方法:

事先共享密钥

需要用一种安全的方式将密钥交给对方。

在人数很多的情况下,需要大量密钥。

密钥分配中心

Key Distribution Center —— KDC

Diffie-Hellman密钥交换

另章详述

公钥密码

公钥密码的加密密钥和解密密钥不同。

任何人都可以加密,但只有拥有解密密码的人才能解密。

公钥密码中,密钥分为加密密钥和解密密钥两种。

公钥和私钥一一对应,称为密钥对(key pair)。

非对称密码(asymmetric cryptography)

1976年Whitfield Diffie和Martin Hellman发表了关于公钥密码的设计思想。提出了应该将加密密钥和解密密钥分开,并描述了公钥密码应该具备的性质。但没有提出具体的算法。

1978年Ron Rivest、Adi Shamir、Reonard Adleman共同发表RSA公钥密码算法,是现代公钥密码的事实标准。

公钥密码的缺陷:

时钟运算

【这节看着怪怪的,不深究】

mod运算

除法求余运算

减法

乘法

RSA

RSA可被用于公钥密码和数字签名。

1983年取得美国专利,已过期。

密文 = 明文E mod N

明文 = 密文D mod N

E 是加密(Encryption)的首字母, N 是数字(Number)的首字母, D 是解密(Decryption)的首字母。

RSA的密文是对代表明文的数字的 E 次方求 mod N 的结果。即,将明文和自己做 E 次乘法,然后将其结果除以 N 求余数,这个余数就是密文。

加密和解密过程仅仅是对明文进行乘方运算并求mod。

作为解密密钥的 D ,和加密密钥的 E 有着密切的联系。

EN 就是RSA加密的密钥,也就是说,EN 的组合就是公钥

一般写成 ”公钥是(E,N)" 或者 “公钥是{E,N}”。

DN 就是RSA解密的密钥,也就是说,DN 的组合就是私钥

RSA密钥对的生成步骤

  1. N

    1. 准备两个很大的质数(pq)以增加破译难度,一般通过伪随机数生成器生成一个512比特大小的数,再判断(使用费马测试和米勒·拉宾测试等)其是否为质数。
    2. pq 相乘,得到 N
    3. 当代RSA中的 pq 长度在1024比特以上, N 的长度为2048以上。
  2. LL 是仅在生成密钥对的过程中使用的数)

    L 是( p -1)和( q -1) 的最小公倍数(least common multiple——lcm)。

  3. E

    E 是一个比1大,比 L 小的数;EL 的最大公约数必须为1,即 EL 互质。

    1 < E < L

    gcd(E,L) = 1

    要找出满足上式的数,需要使用伪随机数生成器,在 1 < E < L 的范围内生成 E 的候选数,然后判断是否满足 gcd(E,L) = 1 。

    求最大公约数可以使用欧几里得的辗转相除法。

    gcd(E,L) = 1 是为了保证一定存在解密时需要使用的数 D

    此时,已经生成了密钥对中的公钥。

  4. D

    D 由数 E 计算得到。DEL 之间必须具备以下关系:

    1 < D < L

    E x D mod L = 1

对RSA的攻击

密码破译者知道的信息:

密码破译者不知道的信息:

由于 mod N ,求明文就变成了求离散对数的问题。目前人类还没有发现求离散对数的高效算法。

可以通过暴力破解找出 D 。但随着 D 的长度增加,暴力破解的难度会变大,当 D 足够长时就不可能在现实的时间内通过暴力破解找出数 D 。当代 ED 的长度可以和 N 差不多,达到2048比特以上,基本上不可能被暴力破解。

无法通过 EN 求出 D 。 质数 pq 不能被密码破译者知道,这等于是把私钥交给破译者。

一旦发现了对大整数进行质因数分解的高效算法,RSA就能够被破译。目前还没有找到简单方法,甚至尚未证明是否存在简单方法。

但是 pq 是通过伪随机数生成器产生的,如果使用的伪随机数生成器算法很差,破译者就有可能推测出 pq

中间人攻击

man-in-the-middle attack

此方法不能破译RSA,但却是一种针对机密性的有效攻击。

攻击者混入发送者和接收者的中间,对发送者伪装成接收者,对接收者伪装成发送者。此时,攻击者被称为“中间人”。

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

针对中间人攻击,需要一种认证方法——证书——来确定收到的公钥属于真正的发送者的。

选择密文攻击

Chosen Ciphertext Attack

假设攻击者发送任意数据,服务器都会将其当作密文来解密并返回解密的结果,这种服务被称为解密提示(Decryption Oracle)。

网络上很多服务器在收到格式不正确的数据时都会向通信对象返回错误消息,并提示“这里的数据有问题”。攻击者可以向服务器反复发送自己生成的伪造密文,并通过分析服务器返回的错误消息和响应时间获得一些关于密钥和明文的信息。

RSA-OAEP(Optimal Asymmetric Encryption Padding,最优非对称加密填充)是一种RSA改良算法,对密文进行“认证”,以判断密文是否是由知道明文的人通过合法的方式生成的。

RSA-OAEP在加密时会在明文前面填充一些认证信息,包括明文的散列值以及一定数量的0,然后再对填充后的明文用RSA进行加密。在RSA-OAEP解密过程中,如果在RSA解密后的数据的开头没有找到正确的认证信息,则可以判定这段密文不是由知道明文的人生成的,并返回一条固定的错误信息“decryption error”。重点是,不能将具体的错误内容告知发送者。

RSA-OAEP在实际运用中,还会通过随机数使得每次生成的密文呈现不同的排列方式,从而进一步提高安全性。

其他公钥密码

ElGamal

RSA利用了质因数分解的困难度,ElGamal则利用了 mod N 下求离散对数的困难度。

缺点是经过加密的密文长度会变成明文的两倍。

密码软件 GnuPG 支持这种方式。

Rabin

利用了 mod N 下求平方根的困难度。

椭圆曲线密码

Elliptic Curve Cryptography——ECC

其特点是所需的密钥长度比RSA短。

椭圆曲线密码是通过将椭圆曲线上的特定点进行特殊的乘法运算来实现的,它利用了这种乘法运算的逆运算非常困难这一特性。

对称密码和公钥密码对比

具有同等抵御暴力破解强度的密钥长度比较:

对称密码AES公钥密码RSA
1283072
1927680
25615360

在具备同等机密性的密钥长度下,公钥密码的处理速度只有对称密码的几百分之一。公钥密码并不适合用来对很长的消息内容进行加密。

随着计算机技术的进步,以前被认为是安全的密码会被破译,这一现象称为密码劣化。这对这一点,NIST SP800-57给出了如下方针: