上一篇日志说的两个密码模型,DES和AES都是基于一种叫REESSE Symmetric KeyCrypto system(对称密钥密码体制)的,这个体制有这样的共同特点,就是decrypt function和encrypt function是相同的(或者是很易于推出的也算),这样,encrypt function泄露将会导致及其严重的后果,也就是说,密钥的交换必须建立在发送者和接收者之间的一条安全的信道上进行,很多情况下,这种安全性是无法保证的(例如wireless communication),于是,就产生了另外一种密码体制-Public KeyCrypto system(公钥密码体制).公钥密码体制要求找到一个方法,是由encrypt function来推出decrypt function是不可行的(或者说是要花费一个相当大的代价, e.g. a very long computation time or huge storage space).这样,就不需要预先在一个可能不安全的信道上传输密钥信息了.发送者可以利用一个公开的encrypt function来加密消息后发送个指定接收者,而这个接收者是唯一能够利用decrypt function获取明文的.
Diffie-Hellman Key Exchange Protocol就是公钥密码体制的一个典型,我这里撇开number theory,用简单的数字解释一下什么是Diffie-Hellman Key Exchange Protocol.
1.选取两个公开数q=37,a=7(这里不是随便选的,q必须是一个素数,a必须是q的一个primitive root,如果不知道是什么,不管它,继续往下看)
2.Sender随便选择一个数,xa=14,receiver随便选择一个数,xb=18
3.sender和receiver分别做如下处理, ya = 7^14 = 9 mod 37, yb = 7^18 = 1 mod 37, 公开交换9和1这两个数
4.sender计算ka = 1^14 = 1 mod 37,receiver计算kb = 9^18 = 1 mod, so ka=kb=1 37,这样两人得到了相同的密钥1,而攻击者只知道9和1这两个数,是无法完成密钥计算的(为什么?看下面)
先说Diffie-Hellman难计算假设.简单地说,就是知道x^a和x^b,无法高效的计算出x^(a*b).为什么说是Diffie-Hellman"假设"呢?因为到现在为止,没有任何人能证明确实存在一种解决这个问题的高效算法,也没有人能证明这样的算法不存在),所以,如果你找到一种高效的算法计算这个,下一个Turing Award很有可能是你的了.
根据上面的例子,攻击者能得到的信息(最多)是两个全局公开的数,a,q,两个sender和receiver交换的数ya和yb,攻击者要想得出k,就相当于知道ya = a^xa mod q, yb = a^xb mod q然后去计算k = ya*yb mod q = a^(xa*xb) mod q,问题转化到上面的Diffie-Hellman难计算假设上去了.
最后说明一下,我举的这个例子完全是便于理解,实际运用中不可能用这么小的数(因为数字太小完全可以穷举拼凑出来),而可能是几百位的数字,这样再去拼凑,就很难了.
