MENU

关于破解不可逆的加密算法那点事

July 10, 2013 • 乱七八糟

点击查看原图

往往存在一个误区,认为MD5、SHA1这样的摘要算法是加密算法,其实是不对的,可以说是一种密码算法。加密算法是要能把明文变成密文,密文再变回明文的,变不回来的不能算是加密。至于这个问题,则要从破解这个词在各种不同语境中不同的含义来说了。

一、加密算法的破解
加密算法能在加密密钥的作用下,把明文变成密文;在解密密钥的作用下,把密文变成明文。针对加密算法的破解,是在只有密文没有密钥的情况下,把明文给还原出来。另外值得说的是,密码学中有柯克霍夫斯基原则,即加密算法的安全性依赖的是密钥的保密而不是算法的保密,所以所有关于破解的讨论中,都是假定攻击者知道加密算法的全部细节。所以寻找密钥也是破解的途径之一。

二、摘要算法的破解
对于摘要算法(也就是我们常说的Hash算法),则不是这样了。不是对于这个单向算法求解一个反函数那么简单,因为我们都知道,hash函数是一个多对一的函数,多对一的函数没有办法得到一个反函数,所以对于摘要算法的破解,也不是把所谓的“密文”变成“明文”,数学家都知道这个算法是不存在的(该特性叫做原象稳固)。对于摘要算法的破解,往往指的是制造碰撞。碰撞有两种,一种是针对第二原象稳固的碰撞,就是在已知摘要值的情况下,求解另外一个消息使得该消息的摘要值等于已知摘要值,即已知d=H(m1),求解m2使得H(m2)=d;另一种是针对碰撞稳固的碰撞,是生成一对摘要值相同的消息,即计算产生m1和m2,使得H(m1)=H(m2)。针对现有摘要算法的攻击往往是第二种。

三、更广泛的破解
另外,破解还有另外一个含义,就是找到一种算法完成上述的几种破解,并且这种算法比穷举法(对于摘要算法则是生日攻击)要快,或者比已有的破解方法要快。这样子也叫做破解,不过这样的破解往往对于该算法的安全性影响不大,比如从原来的复杂度10^80降低到10^72,计算上依然是不可行,但是我们依然称作被破解了。

四、结论
不可逆算法(上文所说的单向算法)就是不可逆的,所以不可逆算法的破解不是让他可逆,而是制造碰撞,大家都混淆了破解这个词在不同语境下的意义。


author:余天升

Archives QR Code
QR Code for this page
Tipping QR Code