对称密码

28 12月
  • 历史上的对称密码
  • XOR
  • DES(已淘汰)
  • AES
  • (补充一)分组密码
  • (补充二)伪随机数生成器

1. 对称密码(symmetric cryptography)

加密和解密使用相同的密钥被称为对称密码(symmetric cryptography)。

1.1 历史上的对称密码

历史上著名的对称密码有凯撒密码(Caesar cipher),即每个字母均向后平移生成密文,密钥就是平移的个数。例如密钥为 3 时,就是每个字母向后平移3位,a变成d,b变成e,依次类推:

加密解密时,都用相同的密钥3:

凯撒密码的破解方式很简单,26个罗马字母,密钥从1-25共25种,暴力破解(brute-force attack)将25种方式都尝试一遍,看哪种破译出来的结果是可读的自然语言即可。

因为破解方式太简单,凯撒密码也有个升级版,即生成一张罗马字母替换表,用它来进行加密和解密。发送者和接收者共享这张字母替换表。

字母替换表无法被暴力破解,a可以对应任意26个字母,b可以对应余下的任意25个字母,依次类推,密钥总数是:26 * 25 * 24 * 23 … * 1 = 403291461126605635584000000 种可能,即4兆的100兆倍,即使用现代计算机每秒遍历10亿个密钥,也要120亿年才能遍历完全部密钥。

对于这种无法暴力破解的密钥,通常会使用频率分析法来破解。分析一段密文中字母出现的次数和位置,和自然语言中字母出现的次数和位置相匹配,来尝试破译密码。例如密文:

将每个字母出现的频率分析出来:

自然语言中出现频次最高的字母是e,密文中的I,Y出现的频次最高,将其中某个转成e,依次类推再分析。反之低频字母也能成为线索,密文中B一次都没出现,自然语言中字母z的频次也很低。自然语言中出现频次较高的单词是the,结合上面可以尝试找一下以e为结尾的3个字母的固定组合,依次类推再分析。同一个字母连续出现也能成为线索,开头和结尾也能成为线索。

密码算法和密钥需要分开保管,以提升安全。

例如凯撒密码里,密码算法:字母向后平移,密钥:平移的个数

例如字母替换表,密码算法:字母替换的规则,密钥:字母表

字母替换表很好用,但每次加密解密需要人肉操作,疲劳容易出错,德国人阿瑟.谢尔比乌斯(Arthur Sherbius)在20世纪初发明了了能加密和机密操作的机器Enigma(德语中意为“谜”),被用于商业和军事领域。Enigma是一种又键盘,齿轮,电池,灯泡组成的机器,通过它可以完成加密和解密。发送者和接收者各自持有一台Enigma,还有一份国防军密码本,里面加载了每日字母替换表。

发送者每日根据字母替换表设置好Enigma后,输入明文就能通过Enigma机器转成密文发送。接受者每日根据字母替换表设置好Enigma后,收到密文就能通过Enigma机器转成明文。

随着现代计算机的发展,写一个简单的 encode 函数即可,Enigma这种机器已经退出了历史舞台。

1.2 XOR

异或xor:相同为0,不同为1

计算机中存储的不是26个字母,每个字符在计算机里都有ASCII码,由0/1数字组成,对称密码常借助 XOR 来进行加密解密:

异或规则:

  • 0 xor 0 = 0
  • 0 xor 1 = 1
  • 1 xor 0 = 1
  • 1 xor 1 = 0

可以将 0 理解为偶数,1 理解为奇数,xor 理解为加法:

  • 偶数(0)+ 偶数(0)= 偶数(0)
  • 偶数(0)+ 奇数(1)= 奇数(1)
  • 奇数(1)+ 偶数(0)= 奇数(1)
  • 奇数(1)+ 奇数(1)= 偶数(0)

结论:相同的数 xor 结果为 0,不同的数 xor 结果为 1。明文 xor 密钥,就能得到密文,反之就能解密:明文 xor 密钥 = 密文,密文 xor 密钥 = 明文,即:明文 xor 密钥 xor 密钥 = 明文,相当于加密解密过程中密钥被抵消了。

举例:明文midnight,密钥可以通过扔硬币生成,硬币正面为0,反面为1,扔64次硬币得到随机密钥,xor 就能得到密文:

解密就是密文 xor 密钥,就能得到明文。

同样,用XOR方式加解密的话,上面这种扔硬币的随机密钥是无法被暴力破解的,因为计算量实在太大,如果明文是个100m的文件,密钥的大小也必须是100m。

1.3 DES(已淘汰)

随着计算机算力的增强,现在DES已经能被暴力破解了,不应该再继续使用DES了。

上面说了XOR的缺点,密钥和明文必须一样长,如果明文是个100m的文件,密钥的大小也必须是100m。因此诞生了分组密码(block cipher)。

DES(Data Encryption Standard)是一种将每64比特的明文为一个单位(被称为“分组”),加密成64比特的密文的对称密码算法,也是一种分组密码。密钥长度是64比特,但由于每隔7比特会设置个校验码,因此实质上密钥长度是56比特。

DES的基本结构由 Horst Feistel 设计,因此也被称为 Feistel network,Feistel structure,Feistel cipher。在 Feistel network 中,加密的各个步骤被称为轮(round),整个加密过程就是不断地轮循环:

Feistel network中的的一轮(round):64比特明文进入Feistel network,被等分为左右两侧各32比特,中间的子密钥只在该轮中被使用,每轮的子密钥都不同。左侧32比特明文 xor (右侧的32比特明文 xor 子密钥)= 左侧32比特密文

每轮的结果:左侧32比特密文 = 左侧32比特明文 xor (右侧的32比特明文 xor 子密钥)。右侧32比特密文 = 右侧32比特明文,即右侧不加密。

因为右侧不加密,所以要将左右结果对调,再来一轮,这样左右两侧都加密了,但顺序变了,所以要再来一轮将左右顺序调换回来。解密利用 xor 的特性,只需要将子密钥逆序即可解密:

Feistel network的轮数可以任意增加,无论进行多少轮都不会出现无法解密的情况。而且加密和解密可以用完全相同的结构来实现,因此基于Feistel network的硬件设备的设计也变得容易了。密码设计者可以专注于设计轮函数,将轮函数从简单的xor设计的足够复杂。无论多复杂的轮函数,Feistel network都能进行解密。

暴力破解分组密码可以用差分分析法或线性分析法:

  • 差分分析的思路是:“尝试改变部分明文,并分析密文如何随之改变”。即尝试改变明文哪怕只改一个比特,密文的比特排列就会发生改变,分析改变的规律来获取破译密码的线索。
  • 线性分析的思路是:“将明文和密文的一些对应比特进行xor,并计算结果为0的概率”。如果密文具有足够的随机性,那么任选明文和密码对应的比特进行xor,结果为0的概率应该为1/2。如果偏离1/2的部分,可以获得一些与密钥有关的信息。

因为DES被暴力破解越来越容易,IBM公司又设计出了三重DES(triple-DES)。三重DES并不是简单地进行三次DES加密(加密 -> 加密 -> 加密),而是加密 -> 解密 -> 加密,这样能向下兼容普通的DES,只要三重DES中所有密钥都相同,就是普通的DES:

1.4 AES

AES(Advanced Encryption Standard)取代了DES成了新的对称密码算法标准。AES是公开全世界选拔出来的,评审由全世界知名企业和密码学家共同完成。参选的密码算法一旦被找到弱点就会落选,当然算法速度和实现的容易性也在评审范围内,即不仅密码本身无弱点,密钥的生成速度也要快,还要在各种设备如CPU,智能卡等设备上被使用。

从1997年开始公开募集AES,到1998年最终进入评审阶段的密码算法共15个(CAST-256,Crypton,DEAL,DFC,E2,Frog,HPC,LOK197,Magenta,MARS,RC6,Rijndael,SAFER+,Serpent,Twofish),到了2000年最终Rijndael算法被选为AES标准,它是由比利时密码学家Joan Daemen与Vincent Rijmen共同开发的分组密码算法。

AES(Rijndael)的分组长度为128比特,密钥长度有128,192,256比特三种,每轮分为SubBytes,ShiftRows,MixColumns,AddRoundKey共4个步骤,与DES使用Feistel network作为基本结构不同,AES(Rijndael)使用SPN structure:(解密就是逆运算)

SubBytes:输入分组的128比特明文,即16 byte,根据字母替换表(当然真实的替换比字母替换表复杂的多,仅仅可以类比帮助理解)将其4*4 byte进行处理

ShiftRows:按行(4 byte)进行左平移

MixColumns:每列4 byte进行运算变换

AddRoundKey:与轮密钥进行xor

Rijndael算法背后有严谨的数学结构,所有计算过程都能用公式来表达,这是之前的任何密码算法都不具备的。但这也意味着Rijndael能够用数学公式进行破译,只不过目前为止还没有出现针对Rijndael的有效攻击。

(补充一)分组密码

DES,AES都是分组密码。具体如何分组?有几种模式:ECB,CBC,CFB,OFB,CTR

不推荐使用ECB模式,推荐使用CBC,CFB,OFB,CTR模式

ECB(Electronic CodeBook)模式:将明文分组后,进行加密,最后一组不够长度,用特定数据填充。

缺点是:因为每个明文分组都被独立加密和解密,所以攻击者可以改变密文的顺序,这样明文的顺序也被改变了,即攻击者不用破译密码就能改变明文。例如明文被分成3组:A账号,B账号,付款金额。攻击者将密文分组改变,解密后变成:B账号,A账号,付款金额。所以使用ECB分组模式,一定要配合防篡改功能。但用下面介绍的其他模式,就不必配合防篡改功能。

CBC(Cipher Block Chaining)模式:将明文文组与前一个密文分组进行xor后,再加密。需要事先准备一个比特序列作为初始化向量(Initialization Vector)IV。CBC模式中,因为加密过程中前后分组相互依赖,我们无法单独对中间某个分组进行加密。

CFB(Cipher FeedBack)模式:前一个密文分组返给算法的输入端。与CBC的区别是加密算法的位置不同。Feedback反馈的意思是:密文分组会被返回给加密算法的输入端

OFB(Output Chaining)模式:与CBC,CFB模式相似,但密码算法的位置不同

优点是:加密和解密用相同的结构。缺点是:不支持并行计算。攻击者反转密文中的某些比特位,明文中相应的比特位也会被反转

CTR(Counter)模式:用逐次累加的计数器进行加密来生成密钥流的流密码

优点是:加密和解密用相同的结构,且均支持并行计算。缺点是:攻击者反转密文中的某些比特位,明文中相应的比特位也会被反转。

(补充二)伪随机数生成器

软件只能生成“强伪随机数”,无法生成“真随机数”。

RSA算法中,提到用伪随机数生成器生成个大质数。为什么是“伪随机数”?因为软件生成的随机数并不是“真随机数”。

随机数被广泛用于密钥,初始化向量,盐等领域。要给随机数下一个严格的定义是非常困难的,有时会进入哲学争论范畴。

随机数要满足以下3点,由弱到强依次是:

  • 随机性:不存在统计学偏差,是完全杂乱的数列,仅满足“随机性”的被称为“弱伪随机数”
  • 不可预测性:不能通过过去的已知的数列推测出下一个数列,满足“不可预测性”的被称为“强伪随机数”
  • 不可重现性:不能出现相同的数列,满足这条的被称为“真随机数”

计算机因为只具有有限的内部状态,相同内部状态下,必然生成相同的数列,因此软件所生成的数列在某时刻一定会出现重复,所以软件只能生成“强伪随机数”,无法生成“真随机数”。要生成“真随机数”,不能靠软件只能靠硬件,结合周围温度,声音等事实上无法预测和重现的自然现象来生成,这样的硬件设备被称为“随机数生成器(Random Number Generator,RNG)”

软件根据“内部状态”生成伪随机数:(伪随机数生成器可以公开,但种子(seed)需要保密,否则攻击者就可能生成相同的数列。)

常见的伪随机数生成器有:

线性同余法:最近一次生成的伪随机数就是当前伪随机数的内部状态。C的库函数rand,Java的java.util.Random等均使用了线性同余法。缺点是攻击者知道了A,C,M常量就可以预测出随机数列,因此线性同余法不具备不可预测性,高强度的伪随机数生成器推荐使用下面的方法。

第一个伪随机数:R0 = (A * seed +C) mod M,其中A,C,M都是常量

第二个伪随机数:R1 = (A * R0 +C) mod M,前一个生成的伪随机数就是当前伪随机数的内部状态

...

第N+1个伪随机数:R(N+1) = (A * RN +C) mod M

单向哈希函数法:可以使用SHA-1对内部状态计算出哈希值作为伪随机数

密码法:可以使用AES对称密码,或RSA公钥密码对内部状态进行加密,将密文作为伪随机数

ANSI X9.17:被用于密码软件PGP中,更多的加密

发表评论

电子邮件地址不会被公开。 必填项已用*标注