由古论今,三千年加密算法发展史

作者:星期日, 九月 17, 20170
分享:

导语

本文尝试由古及今,论述加密算法的发展演变,以及在整个过程中先后出现的集中关键加密算法。由于个人水平有限,如果出现谬误,还望不吝赐教。

加密算法那些事儿

加密算法乍一听貌似和大部分人的日常生活十分遥远,但实际却密切相关。从网络层到主机文件层,无论那层加密应用或协议背后都是由各种加密算法所支撑。即便你不用任何加密产品,凡是使用https的网站都已经使用了加密协议TLS/SSL。你也被动享受了加密算法带来的隐私保护,及通讯安全。今天我们抛开浅层的应用来扒一扒各种有趣的加密算法。

在扒加密算法前先稍微科普一下,加密算法主要作用是把明文变成密文。加密算法加密后,明文会变成密文,防止信息泄露。虽然看起来和乱码很像,但密文不是乱码。大部分乱码是由于编码不一致导致。编码不属于加密算法,编码无法把明文变成密文,只是改变了一种显示格式而已。所以base64只是一种编码而已,它不是加密算法,不具备加密能力,不能保障您的明文安全。所以,以后要听哪家说我们使用了base64进行加密,赶紧屏蔽。

加密算法的采用需要符合以下三点诉求:

  • 机密性:

保证数据即使被盗取,小偷也不知道是啥;

  • 完整性:

保证数据在传输过程中即使被劫持修改,接收方能够发现信息已被截取,而选择换掉;

  • 可用性:

保证加密算法的开销、复杂度都在可用范围。

结合上述诉求,加密算法的发展主要经历了古典密码和现代密码两个重要时期。

一、古代人民怎么加密?

1. 历史上最早的加密算法

早期加密算法主要使用在军事中,历史上最早关于加密算法的记载出自于周朝兵书《六韬.龙韬》中的《阴符》和《阴书》。其中记载:

太公曰:“主与将,有阴符,凡八等。有大胜克敌之符,长一尺。破军擒将之符,长九寸。降城得邑之符,长八寸。却敌报远之符,长七寸。警众坚守之符,长六寸。请粮益兵之符,长五寸。败军亡将之符,长四寸。失利亡士之符,长三寸。诸奉使行符,稽留,若符事闻,泄告者,皆诛之。八符者,主将秘闻,所以阴通言语,不泄中外相知之术。敌虽圣智,莫之能识。”

武王问太公曰:“… 符不能明;相去辽远,言语不通。为之奈何?” 太公曰:“诸有阴事大虑,当用书,不用符。主以书遗将,将以书问主。书皆一合而再离,三发而一知。再离者,分书为三部。三发而一知者,言三人,人操一分,相参而不相知情也。此谓阴书。敌虽圣智,莫之能识。”

简单来说,阴符是以八等长度的符来表达不同的消息和指令,属于密码学中的替代法,在应用中是把信息转变成敌人看不懂的符号,但知情者知道这些符号代表的含义。这种符号法无法表达丰富的含义,只能表述最关键的八种含义。阴书作为阴符的补充,运用了文字拆分法直接把一份文字拆成三分,由三种渠道发送到目标方手中。敌人只有同时截获三分内容才可能破解阴书上写的内容。

上述朴素的加密算法思想主要使用了替换法。无独有偶,在遥远的西方加密算法也大规模使用于战争之中。在希罗多德(Herodotus)的《历史》中记载了公元前五世纪,希腊城邦和波斯帝国发生多次冲突和战争。这些战争中希腊城邦中广泛使用了移位法进行加密处理战争通讯信息,使波斯帝国难以获得希腊城邦的军事情报,也就无法提前做军事部署。

希腊城邦用来传输军事信息、命令的每段文字都有固定的字数,接密者手中会有一份文字移位说明。解密者拿到密文后,根据文字移位说明进行解密,从而破解其中的军事命令或消息。

2. 古代密码演变的凯撒密码

古典密码主要采用的就是移动法和替换法。经过逐渐发展和完善,最有名的莫过于凯撒密码。凯撒密码有两种模式——移位法和替换法。其中,移位法就是让明文都向固定方向移动特定位数,例如I love you右移动4位就变成了M pszi csy。但英文或拉丁文,字母出现的频率并不一致。以英文字母为例:字母e出现频率明显高过其他字母。在获得足够多的密文样本后,可以通过频率计算准确找到移位规则,从而破解密文。同时由于需要可逆操作,所以实际上密钥的数量是有限的,只有25种可能。因此,完全可以通过暴力破解来对密文进行解密。

于是大部分凯撒密码在实际应用中都采用了第二种模式——替换法。定义一张明文密文映射表:

这种方式可以在一定程度上解决密钥可穷举的问题,但仍对大数据量的频率攻击束手无策。

后来,这种模式发展为,靠引入一些特定参数来扰乱频率,这在一定程度上提高了解密的难度,但仍属于替换法和移位法的范畴。

古典密码后期发展出维吉尼亚密码、ROT5/13/18/47、摩尔斯密码等一系列密码种类。但都是以替换法和移位法为核心基础,安全性也主要是靠算法不公开来保证。所使用的加密算法只能算是现在加密算法的雏形,或者仅作为可以借鉴的最初加密思路。

二、现代人更科学的加密算法

古典加密算法本质上主要考虑的是语言学上模式的改变。直到20世纪中叶,香农发表了《秘密体制的通信理论》一文,标志着加密算法的重心转移往应用数学上的转移。于是,逐渐衍生出了当今重要的三类加密算法:非对称加密、对称加密以及哈希算法。这三类算法在现实场景中也往往组合起来使用,以发挥最佳效果。

1. 对称加密算法

对称加密算法是使用最广泛的加密算法之一。常用的对称性加密算法有DES算法、AES算法、3DES算法、TDEA算法、Blowfish算法、RC5算法、IDEA算法等。对称加密的特点是,加密和解密两方使用同一密钥进行加、解密。加密算法本身泄露不会对安全性造成影响,密钥才是安全性的关键。按照原理不同,对称加密可以大体分成流加密和分组加密两种类型。

  • 流加密

流加密是将明文按字符逐位地,对应地进行加密的一类对称密码算法。流加密中最有名的算法是RC4和GSM。流加密算法相对简单,明文和密钥按位对其做约定的运算,即可获得密文。

最简单的模型是异或流加密例如:

由于流加密原理简单,其算法结构存在弱点,如果密钥流又多次重复使用,只要泄露局部明文,攻击者很容易算出密钥。另外,由于是按位进行加密,攻击者即使对数据进行篡改,也不会破坏原有数据结构,接收者很难发现其中变化。流加密虽然是一种快捷高效的加密方法,但其安全性较低,不建议用户使用流加密对关键信息进行加密。

  • 分组加密

分组加密内部实现则复杂的多,每一个加密块都会经历至少16轮运算,其代表算法有DES和AES。目前推荐使用AES,DES已经不在安全。

  • DES

DES是较早时期的对称加密标准,在当时得到了广泛的应用。随着计算机性能地不断提高,暴力破解DES变得越来越容易。所以DES已经不再安全,近十几年逐渐地被3DES和AES代替。

DES核心主要分成初始置换、轮函数、逆置换三步。

初始置换:把输入的64位数据块按位重新组合,并把输出分为L0、R0两部分,每部分长32位,其置换规则为将输入的第58位换到第1位,第50位换到第2位……依此类推,最后一位是原来的第7位。L0、R0则是换位输出后的两部分,L0是输出的左32位,R0是右32位,其置换规则见下表:

58,50,42,34,26,18,10,2,60,52,44,36,28,20,12,4,
62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8,
57,49,41,33,25,17,9,1,59,51,43,35,27,19,11,3,
61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,7,

轮函数:DES 使用一个 56 位的密钥以及附加的 8 位奇偶校验位(每组的第8位作为奇偶校验位),产生最大 64 位的分组大小。这是一个迭代的分组密码,使用称为 Feistel 的技术,其中将加密的文本块分成两半。使用子密钥对其中一半应用循环功能,然后将输出与另一半进行“异或”运算;接着交换这两半,这一过程会继续下去,但最后一个循环不交换。

逆置换:DES 使用 16 轮循环,使用异或、置换、代换、移位操作四种基本运算。最后经过16次迭代运算后,得到L16、R16,将此作为输入进行逆置换,逆置换正好是初始置换的逆运算,由此即得到密文输出,解密过程则是整套加密过程的逆运算。

  • AES

AES的诞生是为了替代原先的DES,它已经被多方分析论证,在全世界范围广泛使用,是目前最为安全的对称加密算法之一。近十年,AES已然成为对称密钥加密中最流行的算法之一。不同于它的前任标准DES,AES使用的是代换-置换网络,而非Feistel架构。

大多数AES计算是在一个特别的有限域内完成的,加密过程是在一个4×4的字节矩阵上运作,这个矩阵又称为“状态(state)”,其初值就是一个明文区块(矩阵中一个元素大小就是明文区块中的一个Byte)。加密时,各轮AES加密循环(除最后一轮外)均包含4个步骤:

AddRoundKey——矩阵中的每一个字节都与该次轮密钥(round key)做XOR运算;每个子密钥由密钥生成方案产生。
SubBytes——通过一个非线性的替换函数,用查找表的方式把每个字节替换成对应的字节。
ShiftRows——将矩阵中的每个横列进行循环式移位。
MixColumns——为了充分混合矩阵中各个直行的操作。这个步骤使用线性转换来混合每列的四个字节。最后一个加密循环中省略MixColumns步骤,以另一个ddRoundKey取代。

  • 加密模式

无论是AES还是DES他们内部都支持不同的加密模式,每一种模式的安全性和效率都大不相同。这里,只简单介绍两种最常见的模式ECB和CBC。

ECB模式加密效率高,但安全性低,模式如下图:

每次都是Key对单独块进行加密,容易被对方破解。但由于每个模块之间毫无关联,所以可以并发运算,极大地提高了加密效率。通常,ECB的加密效率比CBC高5-6倍。

CBC加密效率虽然没有ECB高,但安全性则高得多。模式如下图:

每块加密引入一个IV,每块的IV都不同,需要上一块进行迭代,最终完成整个加密过程。由于每块的IV和密文块有关,所以无法采用并发的模式,必须串行整个过程。

如果不是出于极高的性能要求,建议还是采用CBC模式进行加密,该模式更为安全、可靠。

2. 非对称加密算法

非对称加密算法和对称加密算法的最大区别在于,加密的密钥和解密的密钥不再是一个。这就像两个人互对暗号一样。这种加密方式主要为了应对“多个加密者,一个解密者”的模式,对称密钥只能解决解密用户为一对一的关系。

于是在这种多对一的关系中就出现了一个公钥体系。一个公钥对应一个私钥。公钥是公开的,任何数据发送者都用公钥对数据进行加密,但公钥加密的内容只有私钥才能解开。其中著名的算法包括DSA算法、RSA算法、Elgamal算法、背包算法、Rabin算法、D-H算法、ECC算法。背后的数学原理从大数分解到复杂的椭圆曲线上的离散对数问题,非常复杂。这里,笔者就不做展开。

虽然背后的数学支撑不同,但模式类似,均采用公私钥密钥对的方式,公钥解密私钥加密的信息,私钥解密公钥加密的信息。非对称加密算法的执行效率成为这种算法实际应用的最大阻碍。大部分应用主要把非对称加密算法用在身份验证中,并不会在通讯中使用。

3. 哈希算法

哈希算法也是非常常见的加密算法之一。他和对称算法以及非对称算法最大的区别是,它不是用来做数据传输,而是对数据是否被篡改加以验证,防止不法分子篡改数据。它的特点是无论原文多长都会变成固定长度的字符串,只能加密不能解密(只能单向运算)。对于不同的输入,理论上会生成不同的输出(部分算法已出现大规模碰撞,碰撞就是指不同明文相同密文的情况)。

常见哈希算法包含MD5、SHA-1和SHA 224/256/512等。其中,MD5和SHA-1已经被证明不再安全,所以,建议使用SHA256/512等安全性高的算法。

三、数据库加密算法

上述加密算法已经广泛应用在各个领域。随着云和大数据的高速发展,数据库也逐渐从安全的局域网环境,向私有云甚至公有云迁移。云环境下服务器变得不再可信,数据库迁移到云上,面临更加严峻的挑战,数据云上安全问题成为不可回避的问题。数据库中保存着关键数据,云上主机存在众多不安全隐患,所以云上数据库加密成为解决这些安全隐患的一剂良药。

1. 对称加密算法

数据库加密不同于文件加密和通讯加密等常见加密。数据库加密需要特别关注加密算法是否存在膨胀性,并对加密算法的性能有苛刻的要求。2009年,数据库安全厂商安华金和在进行数据库加密产品研发时,首先排除对称算法中的流加密算法,原因是这种算法虽然在运行效率和解决数据膨胀上有天然优势,但在一定情况下存在不安全性。为了追求加密的效率,目前国内依然有部分安全厂商采用这种方式提供数据库加密服务,却忽略了这种加密产品最基本的安全性要求。

更稳妥的做法是采用对称加密中的分组加密(AES)进行相关加密处理。分组加密安全性高,在安全方面比较有保障,但需要解决由于数据块大小限制带来的膨胀问题。这需要根据具体情况或字段设计足够精妙的使用方案,来针对不同字段或类型解决膨胀问题,最终形成完美的数据库加密方案。

2. 国产密码算法

密码算法是保障信息安全的核心技术,对于国家机密及各行业核心数据的保护起到至关重要的作用,使用3DES、SHA-1、RSA等国际通用的密码算法体系及相关标准,存在较大的安全隐患。因此,国家有关机关和监管机构站在国家安全和长远战略的高度提出了推动国密算法应用实施、加强行业安全可控的要求。目前国内的数据库加密产品在面对用户的选型评估时,相当一部分是以支持国密算法为首要条件,这对于政府、军工、保密等相关行业用户来说非常重要,国家信息安全的保障必须摆脱对国外技术和产品的过度依赖,加密算法作为关键安全技术更应国产化。

具体而言,国产密码算法(国密算法)是指国家密码局认定的国产商用密码算法,比如,在金融领域目前主要使用公开的SM2、SM3、SM4三类算法,分别是非对称算法、哈希算法和对称算法。

以SM4算法为例:SM4分组密码算法是我国自主设计的分组对称密码算法,用于实现数据的加密/解密运算,以保证数据和信息的机密性。要保证一个对称密码算法的安全性的基本条件是其具备足够的密钥长度,SM4算法与AES算法具有相同的密钥长度分组长度128比特,因此在安全性上高于3DES算法。

作者:安华金和 思成

 

分享:

相关文章

写一条评论

 

 

0条评论