如题所述
在对称密码中,由于加密和解密的密钥是相同的,因此必须向接收者配送密钥。用于解密的密钥必须被配送给接收者,这一问题称为 密钥配送问题 ,如果使用公钥密码,则无需向接收者配送用于解密的密钥,这样就解决了密钥配送问题。可以说公钥密码是密码学历史上最伟大的发明。
解决密钥配送问题的方法
在人数很多的情况下,通信所需要的密钥数量会增大,例如:1000名员工中每一个人都可以和另外999个进行通信,则每个人需要999个通信密钥,整个密钥数量:
1000 x 999 ÷ 2 = 499500
很不现实,因此此方法有一定的局限性
在Diffic-Hellman密钥交换中,进行加密通信的双方需要交换一些信息,而这些信息即便被窃听者窃听到也没有问题(后续文章会进行详解)。
在对称密码中,加密密钥和解密密钥是相同的,但公钥密码中,加密密钥和解密密钥却是不同的。只要拥有加密密钥,任何人都可以加密,但没有解密密钥是无法解密的。
公钥密码中,密钥分为加密密钥(公钥)和解密密钥(私钥)两种。
公钥和私钥是一一对应的,一对公钥和私钥统称为密钥对,由公钥进行加密的密文,必须使用与该公钥配对的私钥才能够解密。密钥对中的两个密钥之间具有非常密切的关系——数学上的关系——因此公钥和私钥是不能分别单独生成的。
发送者:Alice 接收者:Bob 窃听者:Eve
通信过程是由接收者Bob来启动的
公钥密码解决了密钥配送的问题,但依然面临着下面的问题
RSA是目前使用最广泛的公钥密码算法,名字是由它的三位开发者,即Ron Rivest、Adi Shamir和Leonard Adleman的姓氏的首字母组成的(Rivest-Shamir-Adleman)。RSA可以被使用公钥密码和数字签名(此文只针对公钥密码进行探讨,数字签名后续文章敬请期待)1983年在美国取得了专利,但现在该专利已经过期。
在RSA中,明文、密钥和密文都是数字,RSA加密过程可以用下列公式来表达
密文 = 明文 E mod N
简单的来说,RSA的密文是对代表明文的数字的 E 次方求mod N 的结果,换句话说:将明文和自己做 E 次乘法,然后将结果除以 N 求余数,这个余数就是密文。
RSA解密过程可以用下列公式来表达
明文 = 密文 D mod N
对表示密文的数字的 D 次方求mod N 就可以得到明文,换句话说:将密文和自己做 D 次乘法,在对其结果除以 N 求余数,就可以得到明文
此时使用的数字 N 和加密时使用的数字 N 是相同的,数 D 和数 N 组合起来就是RSA的解密密钥,因此 D 和 N 的组合就是私钥 。只要知道 D 和 N 两个数的人才能够完成解密的运算
根据加密和解密的公式可以看出,需要用到三个数—— E 、 D 和 N 求这三个数就是 生成密钥对 ,RSA密钥对的生成步骤如下:
准备两个很大的质数 p 和 q ,将这两个数相乘,结果就是 N
N = p x q
L 是 p-1 和 q-1 的最小公倍数,如果用lcm( X , Y )来表示 “ X 和 Y 的最小公倍数” 则L可以写成下列形式
L = lcm ( p - 1, q - 1)
E 是一个比1大、比 L 小的数。 E 和 L 的最大公约数必须为1,如果用gcd( X , Y )来表示 X 和 Y 的最大公约数,则 E 和 L 之间存在下列关系:
1 < E < L
gcd( E , L ) = 1 (是为了保证一定存在解密时需要使用的数 D )
1 < D < L
E x D mod L = 1
p = 17
q = 19
N = p x q = 17 x 19 = 323
L = lcm ( p - 1, q - 1) = lcm (16,18) = 144
gcd( E , L ) = 1
满足条件的 E 有很多:5,7,11,13,17,19,23,25,29,31...
这里选择5来作为 E ,到这里我们已经知道 E = 5 N = 323 这就是公钥
E x D mod L = 1
D = 29 可以满足上面的条件,因此:
公钥: E = 5 N = 323
私钥: D = 29 N = 323
要加密的明文必须是小于 N 的数,这是因为在加密运算中需要求 mod N 假设加密的明文是123
明文 E mod N = 123 5 mod 323 = 225(密文)
对密文225进行解密
密文 D mod N = 225 29 mod 323 = 225 10 x 225 10 x 225 9 mod 323 = (225 10 mod 323) x (225 10 mod 323) x (225 9 mod 323) = 16 x 16 x 191 mod 323 = 48896 mod 323 = 123(明文)
如果没有mod N 的话,即:
明文 = 密文 D mod N
通过密文求明文的难度不大,因为这可以看作是一个求对数的问题。
但是,加上mod N 之后,求明文就变成了求离散对数的问题,这是非常困难的,因为人类还没有发现求离散对数的高效算法。
只要知道 D ,就能够对密文进行解密,逐一尝试 D 来暴力破译RSA,暴力破解的难度会随着D的长度增加而加大,当 D 足够长时,就不能再现实的时间内通过暴力破解找出数 D
目前,RSA中所使用的 p 和 q 的长度都是1024比特以上, N 的长度为2048比特以上,由于 E 和 D 的长度可以和N差不多,因此要找出 D ,就需要进行2048比特以上的暴力破解。这样的长度下暴力破解找出 D 是极其困难的
E x D mod L = 1 L = lcm ( p - 1, q - 1)
由 E 计算 D 需要使用 p 和 q ,但是密码破译者并不知道 p 和 q
对于RSA来说,有一点非常重要,那就是 质数 p 和 q 不能被密码破译这知道 。把 p 和 q 交给密码破译者与把私钥交给密码破译者是等价的。
p 和 q 不能被密码破译者知道,但是 N = p x q 而且 N 是公开的, p 和 q 都是质数,因此由 N 求 p 和 q 只能通过 将 N 进行质因数分解 ,所以说:
一旦发现了对大整数进行质因数分解的高效算法,RSA就能够被破译
这种方法虽然不能破译RSA,但却是一种针对机密性的有效攻击。
所谓中间人攻击,就是主动攻击者Mallory混入发送者和接收者的中间,对发送者伪装成接收者,对接收者伪装成发送者的攻击,在这里,Mallory就是“中间人”
这种攻击不仅针对RSA,而是可以针对任何公钥密码。在这个过程中,公钥密码并没有被破译,所有的密码算法也都正常工作并确保了机密性。然而,所谓的机密性并非在Alice和Bob之间,而是在Alice和Mallory之间,以及Mallory和Bob之间成立的。 仅靠公钥密码本身,是无法防御中间人攻击的。
要防御中间人攻击,还需要一种手段来确认所收到的公钥是否真的属于Bob,这种手段称为认证。在这种情况下,我们可以使用公钥的 证书 (后面会陆续更新文章来进行探讨)
网络上很多服务器在收到格式不正确的数据时都会向通信对象返回错误消息,并提示“这里的数据有问题”,然而,这种看似很贴心的设计却会让攻击者有机可乘。 攻击者可以向服务器反复发送自己生成的伪造密文,然后分析返回的错误消息和响应时间获得一些关于密钥和明文的信息。
为了抵御这种攻击,可以对密文进行“认证”,RSA-OAEP(最优非对称加密填充)正是基于这种思路设计的一种RSA改良算法。
RSA-OAEP在加密时会在明文前面填充一些认证信息,包括明文的散列值以及一定数量的0,然后用RSA进行加密,在解密的过程中,如果解密后的数据的开头没有找到正确的认证信息,则可以判定有问题,并返回固定的错误消息(重点是,不能将具体的错误内容告知开发者)
RSA-OAEP在实际应用中,还会通过随机数使得每次生成的密文呈现不同的排列方式,从而进一步提高安全性。
随着计算机技术的进步等,以前被认为是安全的密码会被破译,这一现象称为 密码劣化 ,针对这一点: