密码学知识简单梳理

密码学学习笔记

 Liu Ke     2018-08-25   5326 words    & views

This document is not completed and will be updated anytime.

1. 密码

1.1 密码技术

信息安全面临的威胁有:

  • 窃听——机密性
  • 篡改——完整性
  • 伪装——认证
  • 否认——不可否认性

加密:对称加密、非对称加密。保证机密性

单向散列函数(hash函数):保证完整性,检测数据是否被篡改过。

消息认证码:能确认消息是否被篡改,也能确认消息是否来自所期待的通信对象。保证完整性,提供认证机制。

数字签名:防止伪装、篡改、否认。保证完整性、提供认证、防止否认

伪随机数生成器:密钥生成

1.2 安全常识

  • 不要使用保密的加密算法。
    • 加密算法的秘密早晚会公诸于世,无法一直保密
    • 开发高强度的加密算法非常困难
  • 使用低强度密码比不加密更危险
  • 任何密码总有一天会破解
  • 比密码更脆弱的是人心!!可以发明很难破解的密码,但是无法控制人性!

2. 历史著名密码

2.1 历史上著名密码

  • 凯撒密码:将明文中对应的字母在字母表中进行平移,平移后的字母即为对应的密文
  • 简单替换密码:依次将明文中的每个字母按照替换表替换成另一个字母
  • Enigama:恩尼格玛密码机,二战德国使用的密码机。接线板、转子

2.2 破解方法

  • 暴力攻击:对密钥空间进行遍历
  • 频率分析

密钥空间(keyspace):一种密码能够使用的所有密钥的集合。

密钥加密密钥(Key Encrypting Key, KEK):用来加密密钥的密钥。

加密算法和密钥分开进行考虑,能解决希望重复使用,但重复使用会增加风险这个难题。加密算法可以重复使用,但在使用的时候使用变化的密钥,每次通信的时候对密钥进行更改,提高了加密算法的复用性。所以,对密钥的管理是十分重要的。

3. 对称加密

使用相同的密钥进行加密和解密。主要有DES、AES。

3.1 一次性密码本

一次性密码本(one-time pad):将明文与一串随机的比特序列进行异或(XOR)运算得到密文。解密时,将密文与同样的密钥进行异或得到明文(异或的特性)。

一次性密码本又称维纳密码(Vernam cipher),因为是由维纳(G.S.Vernam)1917年提出来的。

一次性密码本是无条件安全的(unconditionally secure),在理论是无法破译的(theoretically unbreakable)。这一特性是由香农在1949年通过数学方法加以证明的。因为即使能够解密出对应的明文,我们无法判断出它是否是正确的明文

一次性密码本的问题:

  • 密钥的配送:能安全配送密钥,那岂不是也能安全配送明文?
  • 密钥的保存:能保存好密钥,那不一样可以保存好明文,那也不需要密钥了。
  • 密钥的重用:不能重复使用加密的比特序列,必须是“一次性的”,要不然一旦密钥泄露,之前的通信内容也会被破解。
  • 密钥的同步:密钥与明文长度相同,传送密钥时,必须保证密钥不能错位,否则无法解密
  • 密钥的生成:需要生成大量无重复的随机比特序列

3.2 DES

可参考文章DES加密

数据加密标准(Data Encryption Standard),64比特明文加密成64比特密文,已经能被计算机暴力破解。属于分组密码。密钥长度64比特,每隔7比特设置一个错误检查比特,实质密钥长度56位。

分组密码(block cipher):以分组为单位进行处理的密码算法。

DES是一种16轮循环的Feistel网络

输入左32比特右32比特,右32直接向下为加密后右侧,子密钥经轮函数的输出与左32异或得到加密后的左侧,左侧右侧组合输出,即为Feistel网络中的一轮。每一轮结束后,左右两侧进行对调,然后输入进入下一轮。

加密和解密实际上只是改变了子密钥的顺序,实际处理完全相同。

Feistel网络性质:

  • 轮数可以任意增加:再多轮不会发生无法解密情况。
  • 加密时使用任何函数作为轮函数都可以正确解密:不用考虑轮函数的逆向计算,轮函数可以设计得任意复杂
  • 加密和解密可以用完全想相同的机构来实现

3.3 差分分析与线性分析

差分分析:针对分组密码,改变一部分明文分析密文如何随之改变(分析密文改变所产生的偏差,获得破译线索)。

线性分析:将明文和密文的一些对应比特进行XOR并计算其结果为0的概率(密文如果有足够的随机性,则任选一些明文和密文的对应比特XOR结果为0的概率应为1/2,对于大幅偏离1/2的部分,可以获得破译线索,大幅减少计算量)。

差分分析和线性分析的前提都是:密码破译者可以任意选择明文并得到其加密结果(这种攻击方式即选择明文攻击)。

3.4 三重DES

3DES,将DES重复三次,增加强度。但处理速度不高。

加密过程:DES加密→DES解密→DES加密(DES密钥分别为1,2,3)

引入解密过程目的:使三重DES兼容普通DES(密钥1,2,3相同时,三重DES即为普通的DES)

解密过程:DES解密→DES加密→DES解密(DES密钥分别为3,2,1)

3.5 AES

可参考文章AES算法

高级加密标准(Advanced Encryption Standard),Rijndael对称加密算法,使用了SPN结构

AES分组长度固定为128比特,密钥长度有128,192和256比特三种。

Rijndael每一轮加密过程:

  • 逐字节替换:从一张拥有256个值的替换表中替换字节
  • 平移行:每行向左平移一定字节,每行平移字节数不同
  • 混合列:对一列中的4个字节值进行矩阵运算变成另外4个字节值
  • 与轮密钥进行XOR

Rijndael每一轮解密过程:

  • 与轮密钥XOR
  • 逆混合运算
  • 逆平移行
  • 逆逐字节替换

优势:

  • 输入所有比特在一轮中都会被加密,加密所需要的轮数更少(一般10~14轮)
  • 逐字节替换、平移行、混合列可分别以字节、行、列为单位进行并行计算

Rijndael从明文到密文的计算过程全部可以用数学公式来表达,可以假设通过数学方法进行破译,但是目前为止还没有出现针对Rijndael的有效攻击

4. 分组密码的模式

分组密码模式主要有:

  • ECB模式:电子密码本模式(Electronic CodeBook mode)
  • CBC模式:密码分组链接模式(Cipher Block Chaining mode)
  • CFB模式:密文反馈模式(Cipher FeedBack mode)
  • OFB模式:输出反馈模式(output FeedBack mode)
  • CTR模式:计数器模式(CountTeR mode)

流密码:对数据流进行连续处理的一类密码算法,需要保持内部状态来记录加密的进度。一次性密码本属于流密码。

分组密码:每次只能处理特定长度的一组数据,一个分组的比特数即为分组长度。分组密码处理完一个分组就结束了,不用保持内部状态。

明文长度超过分组密码的分组长度,需要对分组密码算法进行迭代,迭代的方式即为分组密码的模式

4.1 ECB模式

ECB模式:将明文分组加密后的结果直接成为密文分组

ECB模式的风险:

  • 明文中多个相同的分组对应的密文分组也相同。可以观察密文中的重复情况了解明文的重复组合,获得破译线索。
  • 攻击者无须破译密码就能操纵明文。有时候不需要知道分组密码的算法,也不需要破译密码,只需知道哪个分组记录的是什么意义的数据就行
    • 可以对分组密文进行对调,对应明文分组也会对调
    • 替换
    • 删除
    • 复制

可以通过消息认证码方法检测出来,但不使用ECB模式就不会有这些风险

4.2 CBC模式

密文分组链接模式(Cipher Block Chaining):将明文分组与前一个密文分组进行XOR运算,然后再进行加密得到当前的密文分组。

解密时,将密文分组进行解密,然后再与前一个密文分组进行XOR运算,得到明文分组。

加密第一个明文分组时,没有前一个密文分组,需要通过随机产生一个比特序列进行加密,称为初始化向量(IV,Initialization Vector)。

CBC模式特点:

  • 无法对中间一个明文分组单独进行加密
  • 解密时,只要密文分组长度没有变化,当一个密文分组数据损坏时,最多只有两个分组会受到影响
  • 密文分组中缺失比特位导致错位时,缺失比特位之后的密文分组全部无法解密

对CBC模式的攻击:

  • 对初始化向量进行攻击:将初始化向量中任意比特进行反转,解密时解密出的第一个明文分组对应比特也会反转(因为有XOR运算)
  • 填充提示攻击:利用分组密码中的填充部分来进行攻击。

明文长度不为分组长度的整数倍时,需要在最后一个分组中填充数据凑满一个分组长度。在填充提示攻击中,攻击者反复发送一段密文,每次发送时都对填充的数据进行少许修改。接收者无法正确解密时会返回一个错误消息,这个错误消息可以获得与明文相关的信息。防御这种攻击需要对密文进行认证,保证密文是由合法的发送者在知道明文内容的前提下生成的。

互联网安全通信协议SSL/TLS使用了CBC模式

4.3 CFB模式

密文反馈模式(Cipher FeedBack):将前一个密文分组进行加密,然后与当前明文分组进行XOR运算,得到当前的密文分组(前一个密文分组会送到密码算法的输入端,进行加密,这就是“反馈”)。

解密时,还是将前一个密文分组加密后与当前密文分组进行XOR运算(XOR运算的性质),得到当前明文分组。

对CFB的攻击为重放攻击:通过保留之前的密文,然后对当前的密文进行替换,可以解密出之前的部分明文。

4.4 OFB模式

输出反馈模式(Ouput-FeedBack):对初始化向量不断进行加密,将每一次加密后的结果与明文分组进行XOR运算,得到密文分组。

解密时:同样将初始化向量不断进行加密,将每次加密后的结果与密文分组进行XOR运算,得到对应明文分组。

生成密钥流的操作和进行XOR运算的操作可以并行进行:XOR所需的比特流(密钥流)可以提前准备,与明文分组无关。

4.5 CTR模式

计数器模式(Counter):通过逐次累加的计数器进行加密得到密钥流,然后与明文分组进行XOR运算,得到密文分组。

解密时,同样是对逐次累加的计数器进行加密,然后与密文分组进行XOR运算,得到明文分组。加密和解密结构完全相同。

每次加密时都会生成一个不同的值(nonce)来作为计数器的初始值。一般是“nonce+分组序号”构成不断累加的计数器,计数器的值每次都不同,每个分组将计数器加密得到的密钥流也不同,模拟生成了随机的比特序列。

CTR模式特点:

-CTR模式可以任意顺序对分组进行加密和解密(因为加密和解密需要用的的计数器的值可以由nonce和分组序号直接计算出),可以速度非常快的并行计算。

  • OFB模式中如果对密钥流的一个分组进行加密后其结果碰巧和加密前相同,那么这一分组之后的密钥流就会变成同一值不断反复。CTR模式中不存在这个问题。

5. 公钥加密(非对称加密)

非对称加密:用公钥加密,用私钥解密,公钥和私钥一一对应。

常见的公钥密码:

  • RSA算法:利用质因数分解的困难度.
  • ElGamal:利用modN下求离散对数的困难度。缺点:经过加密后密文长度变成明文的两倍.
  • Rabin:利用modN下求平方根的困难度.
  • 椭圆曲线加密:利用椭圆曲线上的特定点进行特殊的乘法运算来实现.

对于对称加密,加密解密密钥相同,需要解决密钥配送问题:

  • 通过事先共享密钥来解决
  • 通过密钥分配中心来解决
  • 通过Diffie-Hellman密钥交换来解决
  • 通过公钥密码来解决

乘方的逆运算为对数,模运算中的对数称为离散对数,例:

当数字很大时,求离散对数非常困难。目前还没有快速求出离散对数的算法。Diffie-Hellman密钥交换和ElGamal公钥算法运用了离散对数。

RSA算法

可参考文章RSA算法

加密,公钥为(E,N):

解密,私钥为(D,N):

求E、D和N三个数就是生成密钥对,步骤:

  • 求N:准备两个很大的质数p和q,N=p×q
  • 求L(仅在生成密钥对过程中使用):L是p-1和q-1的最小公倍数
  • 求E:1<E<L,E和L的最大公约数为1(E和L互质)
  • 求D:1<D<LE×DmodL=1(E的条件让D存在)

对RSA算法的攻击:

  • 暴力破解:p和q长度在1024比特以上,N长度在2014比特以上,暴力破解D极其困难.
  • 通过E和N求出D:数学方法证明“求D”与“对N进行质因数分解”在确定性多项式时间内是等价的.
    • 对N进行质因数分解攻击:目前没有发现对大整数进行质因数分解的高效算法
    • 通过推测p和q进行攻击:由伪随机数生成器产生,破解伪随机数生成器算法
  • 中间人攻击:对发送者伪装成接收者,对接收者伪装成发送者。单靠公钥密码本身无法防御中间人攻击,通过证书等认证方法防御.
  • 选择密文攻击: 向服务器发送自己生成的的伪造密文,通过分析服务器返回的错误消息和响应时间获得线索.

参考资料:《图解密码技术》 [日] 结城浩 著;周自恒 译