密码学的基本思想是伪装信息,使未授权者不能理解它的含义
密码系统的安全性不应该取决于不易改变的算法,而应取决于可随时改变的密钥

概述

信息安全的目标:

  1. 机密性:保证信息不泄露给非授权的用户和实体
  2. 完整性:保证信息处于保持完整或未受损的状态,防止对信息特性和状态的中断,窃取,篡改,伪造
  3. 可用性:授权用户按需随时访问所需信息而不被非法拒绝
  4. 认证性:确保消息的来源,可分为消息认证实体认证
  5. 不可否认性:保障用户无法在事后否认曾经对消息的生成、签发、接收

密码体制,也称密码系统,5部分组成:

  • 明文空间 M
  • 密文空间 C
  • 密钥空间 K,加密密钥 Ke 和解密密钥 Kd
  • 加密算法 E,M–>C 的加密变换
  • 解密算法 D,C–>M 的解密变换

根据密码分析者对明文、密文等数据资源的掌握程度,可以将密码分析攻击分为以下几种:

  • 惟密文攻击 -被动攻击 密码分析者仅能根据截获的密文进行分析,以得出明文或密钥(破译难度最大)穷举和统计分析都是惟密文攻击
  • 已知明文攻击 -被动攻击 密码分析者除了有截获的密文外,还有一些已知的明文–密文对来破译密码
  • 选择明文攻击 -主动攻击 密码分析者除得到一些“明文-密文对”外,还可以选择加密的明文,并获得相应的密文 攻击者短暂控制加密机
  • 选择密文攻击 -主动攻击 密码分析者可以选择一些密文,并获得相应的明文 攻击者控制解密机,多用于攻击公钥密码体制
  • 选择文本攻击 -主动攻击 密码分析者同时控制加密机和解密机

密码体制安全性

  • 无条件安全(理论安全性) 即使密码分析者具有无限的计算能力,密码体制也不能被攻破
  • 计算安全性 攻破一个密码体制的最好算法用现在或将来可得到的资源不能再足够长的时间内破译
  • 可证明安全性(规约安全性) 密码体制的安全和一个问题是相关的

古典密码体制

置换密码,对符号重新排序,明文字符集保持不变,但顺序被打乱,栅栏加密

代换密码,用一个符号代替另一个符号

单表代换

凯撒密码

  • 加密:c = (m + k) mod 26
  • 解密:m = (c - k) mod 26

乘数密码

  • 加密:c = (m * k) mod q
  • 解密:m = (c * k-1) mod q

仿射密码 密钥空间:φ(26)*(26-1)

  • 选取 K1,K2 两个参数,其中gcd(K1, 26)=1
  • 加密:C = K1 * M + K2 mod 26
    • k1 = 1 时,移位密码
    • K2 = 0 时,乘数密码
      • 解密:M = (C - k2) * k1^-1^ mod 26

多表代换:

Playfair密码

  • 思想:双字母转换
  • 密钥:5×5矩阵(由一个关键词构造)I/J视为相同

一次一密:每个明文字母都采用不同的替换表或密钥进行加密

维吉尼亚密码

  • 26 * 26的方阵
  • 密钥:k = k1k2k3……kn
  • 明文:m = m1m2m3……mn
  • 加密:ci = mi + ki mod 26
  • 解密:mi = ci - ki mod 26

希尔密码

  • 密钥:k = n * n 可逆矩阵,明文m和密文c均为n维向量
  • 加密:c = k * m mod 26
  • 解密:m = k-1 * c mod 26
  • k-1 为k在模26上的逆矩阵

单表替换密码分析:穷举分析 统计特性(字母出现的频率)

多表替换密码分析

  • 确定密钥长度 即确定使用的加密表个数
    • Kasiski测试法
    • 重合指数法
  • 确定具体的密钥字
    • 重合互指数

序列密码

使用随机序列(密钥流)与明文序列按位叠加产生密文,用同一随机序列与密文序列叠加来恢复明文

密钥流的要求:

  1. 极大的周期 真正的随机序列是非周期的,但算法产生的序列都是周期的
  2. 良好的统计特性 随机序列有均匀的游程分布
    • 游程:序列中相同符号的连续段,前后均为不同符号,如 0111000010 有长为3的1游程,长为4的0游程,长为1的1游程
    • 一般要求周期内满足同样长度0游程1游程的个数相等或近似相等
  3. 很好的线性复杂度 不能用级数较小的线性反馈移位寄存器近似代替
  4. 用统计方法由密钥序列提取密钥生成器结构或种子密钥在计算上不可行

线性反馈移位寄存器LFSR

GF(2)上的一个n级反馈移位寄存器由n个二元存储器和一个反馈函数 f(a1a2……an) 组成

  • 每个存储器成为移位寄存器的一级
  • 在任意时刻,这些级的内容构成该LFSR的状态,n维向量共有2n种可能的状态
  • 初始状态为0,则其状态恒为0,初始状态非0,则其后续状态不会为0
  • n级LFSR的状态周期 ≤ 2n-1
  • 选择合适反馈函数可使周期达到最大 2n-1,周期达到最大的序列称为m序列

LFSR示例:

m-序列密码的破译

假设破译者已知2n对明-密文对,即可确定反馈多项式的系数,以及LFSR接下来的状态
示例:

可得密钥序列的递推关系为ki+5 = ki + ki+3

Golomb对伪随机周期序列提出的3个随机性公设:

  • 在一个周期内,0和1的个数相差至多为1,即{ai}中0和1出现的概率基本相同
  • 在一个周期内,长为1的游程占游程总数的1/2,长为2的游程占总数的1/22,长为i的游程占总数的1/2i,且等长的游程中0游程和1游程的个数相等 即0和1在序列的每一位置出现的概率相同
  • 异相自相关函数是一个常数,即通过对序列与其平移后的序列相比较,不能给出其他任何信息

常见流密码算法

  1. RC4 – 基于非线性数组变换的序列密码,以一个足够大的数组为基础,对其进行非线性变换,产生非线性的密钥流序列
  2. A5 – 由3个长度不同的线性移位寄存器组成,A(19位),B(22位),C(23位),移位由时钟控制,遵循择多原则,即从每个寄存器中取出一个中间位,3个数中占多位的寄存器参加移位,其余的不移位

分组密码

分组密码特点:速度快,安全性较高,易于标准化和便于软硬件实现

分组密码的设计要求:

  • 分组长度足够大
  • 密钥量足够大
  • 密码变换要足够复杂
  • 加密和解密运算简单
  • 无数据扩展和压缩

分组密码的设计思想:

  1. 扩散(移位):密钥或明文的每一比特影响密文的许多比特变化,以便隐蔽明文的统计特性(雪崩效应)
  2. 混淆(替代):密钥和明文以及密文之间的依赖关系尽可能的复杂化,以防通过统计分析法进行破译

数据加密标准DES

DES算法描述:

  • 明文分组和密文分组均为64bit,有效密钥56bit
  • 初始置换,16轮迭代,逆初始置换组成
  • DES的加解密算法相同,只是解密子密钥和加密子密钥的使用顺序相反

加密:

  • L0R0 = IP <64位明文>
  • Li = Ri-1 i =1~15
  • Ri = Li-1 ⊕ F(Ri-1,Ki) i =1~15
  • L16 = L15 ⊕ F(R15,K16)
  • R16 = R15
  • IP^-1^(L0R0) = 密文

解密:

  • L16R16 = IP <64位密文>
  • Li-1 = Ri i = 16~2
  • Ri-1 = Li ⊕ F(Ri,Ki) i = 16~2
  • L0 = L1 ⊕ F(R1,K1)
  • R0 = R1
  • IP^-1^(L0R0) = 明文

加密流程图:

初始置换IP和初始逆置换-1

在第一轮迭代之前进行,将原明文块的位进行换位操作

16轮迭代

在每轮迭代中,64位的中间结果被分成左右两部分,且作为相互独立的32位数据进行处理。每轮迭代的输入是上轮的结果 Li-1 和 Ri-1

F函数

E盒-扩展置换

将32bit扩展为48bit,每个输入分组的4位作为6位输出分组的中间4位,6位输出分组中的第1、6位分别由相邻两个4位分组的最外面两位扩散进入到本分组

扩展示例:

01 02 03 04 --> 32 | 01 02 03 04 | 05
05 06 07 08 --> 04 | 05 06 07 08 | 09
密钥加

E盒扩展得到的48位输出与子密钥𝐾𝑖进行异或运算

S盒

由8个S盒构成,每个S盒都是6bit的输入,4bit的输出

示例:输入b1b2b3b4b5b6=110011,查找S盒,行:b1b6=11=3,列:b2b3b4b5=1001=9,查找3对应的行9对应的列的数值

良好的非线性,输出与全部输入有关

P盒

P置换对8个S盒的输出进行变换,查表置换

子密钥生成

DES子密钥是从初始密钥(种子密钥)产生的,种子密钥𝐾为64位,其中有8位用于奇偶校验,因此DES的密钥实际上只有56位

DES的安全性

DES安全性的主要争议:

  • 对DES的S盒、迭代次数、密钥长度等设计准则的争议
  • DES存在一些弱密钥和半弱密钥
  • DES的56位密钥无法抵抗穷举攻击
  • DES代数结构存在互补对称性

主要安全问题

  1. 互补性:c = Ek(m)则 $ \overline{c} = E\overline{k} (\overline{m})$,成为算法上的互补性,互补性使DES再选择明文攻击下所需的==工作量减半==,由 2^56^ 变为 2^55^

  1. 多重DES:

    • 2DES可用中间相遇攻击使复杂度由2^112^减小到2^57^,中间相遇攻击:将所有的明文加密一次后的结果放到一张表中,使用密钥解密一次密文后得到的结果与表中结果相比较,牺牲空间换取时间

  2. 三重DES:

    • EEE3/EDE3 3 x 56
    • EEE2/EDE2 2 x 56

高级加密标准AES

分组长度128bit,密钥长度可以为1258bit,192bit,256bit,一般使用密钥长度128bit,迭代轮数为10轮

AES的处理单位时字节,128bit的明文分组和输入密钥都被分为16个字节,一般明文分组用以字节为单位的正方形矩阵描述,称为状态矩阵,算法的每一轮中,状态矩阵的内容不断发生变化,最后的结果作为密文输出

AES的加解密流程:解密时加密的逆过程

AES每轮由4个阶段组成:(第一轮开始前异或原始密钥,最后一轮不执行列混合)

  • 字节代换

  • 行移位

  • 列混合

  • 轮密钥加

字节代换(S盒)

简单的查表,16x16字节组成的矩阵,每个元素的内容是一个字节的值

行移位

左循环移位,第0行不变,第1行左移1个字节,第2行左移2个字节

列混合

对一个状态逐列进行变换,将每列视为有限域GF(2^8^)上的一个多项式

乘法:

  • 乘 0x01,不变

  • 乘 0x02:

    • 最高位为0,直接左移一位
    • 最高位为1,左移一位后与0001 1011异或
  • 乘 0x03,0000 0011= 0000 00100000 0001

示例:(模多项式m(x)=x^8^+x^4^+x^3^+x+1)

轮密钥加

将轮密钥与状态按比特异或

密钥扩展

包括两个部分:密钥扩展轮密钥选取

首先将种子密钥输入到4x4矩阵中,每列组成一个字,w[0],w[1],w[2],w[3]

对 w 数组扩展40个新列构成44列的密钥数组

  • 若 i 不是4的倍数,那么 w[i] = w[i-4] ⊕ w[i-1]
  • 若 i 是4的倍数,那么w[i] = w[i-4] ⊕ T (w[i-1])

T函数,由字循环、字代替和轮常量异或组成

  • 字循环:将一个字的4个字节循环左移一个字节
  • 字节代换:对字循环的结果使用S盒进行字节代换
  • 轮常量异或:将前两步的几个同轮常量 Rcon[j] (轮数)进行异或

典型分组密码

IDEA算法

明文分组长度64bit,密钥长度128bit,迭代8轮,构成64bit的密文块

SMS4密码算法

分组长度128bit,密钥长度128bit,加密算法与密钥扩展算法都采用32轮非线性迭代结构

分组密码的工作模式

电子密码本模式(ECB)

加解密:

特点:并行计算,速度快,相同密钥作用下,相同明文加密后将产生相同密文,易暴露明文的固有格式和统计特性

密文中数据出了错,解密时会使得相对应的整个明文分组解密错误,但不会影响其他密文块解密

密码分组链接模式(CBC)

加密:

解密:

CBC的传播错误

  • 明文有一分组有错,会使以后的密文组都受影响,但经解密后,除原来有误的一组外,其后各组明文都正确地恢复
  • 若传送过程中某组密文组出错时,则该组恢复的明文和下一组恢复数据出错。再后面的组将不受影响

密码反馈模式(CFB)

加解密:

CFB的优点:自同步能力强,可以处理任意长度的消息

CFB的缺点:

  • 明文某一组中有错,使以后的密文组都受影响,但经解密后,除原有误的一组外,其后各组都正确地恢复

  • 密文里的一位错误会引起明文的一个单独错误,此错误进入移位寄存器,导致密文成为无用信息,直到该错误从移位寄存器中移出

输出反馈模式(OFB)

特点:

  • 无错误传播
  • 失去同步是致命的,移位寄存器需要同步
  • 对密文的篡改难以检测

计数器模式(CTR)

特点:

  • 随机访问特性:可以随机的对任意一个密文分组进行解密,对该密文分组的处理与其它密文无关
  • 高效率:能并行处理; 可以提前进行预处理,这也可以极大的提高处理效率
  • 可以处理任意长度的数据,而且加解密过程仅涉及加密运算,不涉及解密运算,因此不用实现解密算法

Hash函数

Hash函数的性质:

  • 可应用于任意长度的消息
  • 固定长度的输出
  • 对任意给定消息 x,计算 H(x) 比较容易,软硬件均可实现
  • 单向性(抗原像性),已知 H(x) 找到 x 在计算上是不可行的
  • 抗弱碰撞性,对任意给定x,找到 y≠x 且 H(x)=H(y) 在计算上是不可行的
  • 抗强碰撞性,找到任意满足 H(x)=H(y) 的偶对 (x,y) 在计算上是不可行的

Hash函数架构

数据填充

填充消息,使消息长度模512 = 448

  • 如果消息长度模512恰好等于448,则增加512个填充比特,即填充的个数位1~512
  • 填充方法:第1比特为1,其余全部为0
  • 补足长度,将一个表示数据原始长度的64bit数补在最后,512比特按32比特分为16组
  • 最终消息长度为512bit的整数倍

MD5算法

分组长度为512bit,输出128bit的消息摘要

共4轮,每轮16步

SHA1算法

分组长度为512bit,输出160bit的消息摘要,有更强的抗穷举能力

共4轮,每轮20步

MD5安全性

攻击者的目标:找到两个不同的消息映射为同一杂凑值

对Hash函数的基本攻击方法

  1. 穷举攻击:
  • 最典型的方法是生日攻击:给定初值 H0,寻找M’ ≠ M,使 h(M’) = H0,MD5算法抗密码分析的能力较弱,生日攻击所需代价是试验2^64^个消息
  1. 密码分析法:依赖于Hash函数的结构和代数性质分析,采用针对Hash函数弱性质的方法进行攻击,中间相遇攻击修正分组攻击差分攻击

消息认证码

消息认证码(MAC)是一种消息认证技术,利用消息和双方共享的密钥通过认证函数来生成一个固定长度的数据块,并将该数据块附加在消息后 –带密钥的Hash函数

基于DES的消息认证码

采用DES运算的密码分组链接模式(CBC),初始向量为0

需要认证的数据分为连续的64bit分组

基于Hash的认证码

HMAC:将散列函数嵌入到消息认证码的构造过程中

在安全协议SSL和IPSec中使用HMAC实现消息认证功能

对消息认证码的穷举攻击比对使用相同长度密钥的加密算法的穷举攻击更困难

应用:

通信双方A和B有一个共享密钥K。当A有要发往B的消息时,发送方A利用共享密钥K计算MAC,然后将消息和MAC一起发往预定的接收者B

在接收端B,使用相同的密钥K对收到的消息执行相同的计算并得出新的MAC,将收到的MAC与计算得出的MAC进行比较

  • 如果相同,则消息的确来自A,且没有被更改过

  • 如果不同,丢弃消息

公钥密码

单向陷门函数

  1. 正向计算容易,已知密钥 P 和消息 M,容易计算 C = fp (M)
  2. 不知道密钥 S 的情况下,反向计算不可行,即只知道 C,不知道 S,计算 M = f-1(M)不可行
  3. 知道密钥 S 的情况下,反向计算容易,即同时知道 C 和 S,则计算 M = f-1(M)是容易的,S相当于陷门,和P配对

RSA公钥加密体制

算法描述

  1. 密钥生成
    • 选取两个大素数p和q,(p≠q,且p和q须保密) 1024bit的密钥
    • 计算 n=p×q,φ(n)=(p-1)×(q-1),φ为n的欧拉函数
    • 选择整数e,e与φ(n)互素,1<e<φ(n)
    • 计算d,d = e^-1^ mod φ(n),公钥为{e,n},私钥为{d}
  2. 加密
    • 明文 M<n,密文 C = Me mod n
  3. 解密
    • 密文 C,明文 M = Cd mod n

快速幂

c = 1, t = 0
t = 2 * t
c = c * c mod n
if b = 1
c = c * a mod n
t = t + 1

RSA的攻击

针对n分解的攻击
  1. 试除法:完全尝试所有小于√n的素数
  2. 因式分解法
    • 二次筛法
    • 连分数法
    • 椭圆曲线筛法
循环攻击
  1. 设m为明文,(n,e)为公钥,密文 c = me mod n
    • 攻击者得到密文c后,对c依次进行如下变换:
      c1 = ce mod n
      c2 = c1e mod n
      …… ……
      ck = ck-1e mod n
      ck+1 = cke mod n
    • k+1次迭代后,如果ck+1=c,由c=me mod n,则ck= m,获得明文
  2. 避免循环攻击:
    • ordn(m)要大,且φ(ordn(m))要有大的素因子
    • ordn(m)是φ(n)的因子,所以需要p-1和q-1都有大的因子
共模攻击
  • m为明文,两用户的公钥分别为e1和e2,且互素,共同的模数n,两个密文分别为c1和c2
  • 攻击者知道n,e1,e2,c1和c2
  • 恢复明文m:由欧几里得算法可找出r和s满足 re1+se2=1,假定r是负数,那么 (c1-1)-r c2s = mre1+se2 = m mod n
  • 无需私钥d即可获得明文m

防御:使用RSA公钥加密的通信中,不同用户的密钥不能有相同的模值

低加密指数攻击

小的公钥e可以加快加密的速度,但过小的公钥易受到攻击

  • 如果3个用户都使用3作为公钥,对同一个明文 m 加密,则 c1=m3 mod n1,c2=m3 mod n2,c3=m3 mod n3,且n1,n2,n3互素,m小于模数
  • 中国剩余定理可从c1,c2,c3计算出c,且 c = m3mod (n1n2n3),m = c1/3
  • 如果采用不同的n,相同的e,对e(e+1)/2个线性相关的消息加密,系统就会受到威胁,所以一般选取16位以上的素数(速度快且可防止攻击)
  • 对短消息,用随机数填充以保证me ≠ me mod n,从而杜绝低加密指数攻击

防范措施

  1. 密钥长度:至少1024bit

  2. 选择素数p和q时,应使其欧拉函数j(p)和j(q)的最小公倍数尽可能大(φ(p)和φ(q)有大的素因子)。最小公倍数越大,幂剩余函数的周期就越长—避免循环攻击

  3. 密钥中的各项参数应选得足够大—避免穷举攻击

  4. 在同一个通信网络中,不同的用户不应该使用共同的模数—避免共模攻击

EIGamal公钥加密体制

算法描述

密钥生成:选择随机数 x,计算 y = g ^x^ (mod p),则公钥为(y, g, p),私钥为 x

加密过程:

  1. 得到接收方的公钥 (y, g, p)
  2. 随机选择整数 r
  3. 计算 c1 = g^r^ (mod p),c2 = m y^r^ (mod p)

解密过程:使用私钥 x 和解密算法 m = c 2 * (c 1 ^x^ ) ^-1^

验证正确性:

数字签名

数字签名的目的和要求

目的:保证信息的完整性和真实性,即消息没有被篡改,而且签名也没有被篡改,消息只能始发于所声称的一方

要求:

  1. 不可否认性,签名者事后不能否认或抵赖自己的签名
  2. 不可伪造性,其他任何人均不能伪造签名,也不能对接收或发送的信息进行篡改、伪造和冒充
  3. 公正的仲裁,若当事双方对签名真伪发生争执时,能通过公正的仲裁验证签名来确定其真伪

RSA签名

密钥生成:(与公钥加密系统一样) 公钥P={e,n};私钥S={d}

签名过程:A对消息m进行签名,计算签名 s = h(m)^d^ mod n,将(s,m)发送给B,h为安全的Hash函数

验证过程:B收到消息m和签名s后,计算 h(m),检验 h(m) = s^e^ mod n 是否成立,成立则签名有效

对RSA签名的攻击

一般攻击:攻击者任选一个数据 Y,用A的公钥计算 X = Y^e^ mod n,于是便可以用 Y 伪造对消息 X 的签名,因为 Y = X^d^ mod n,实际意义不大,伪造的消息 X 具有实际意义的概率很小

利用已有签名进行攻击:消息 M1、M2 的签名分别是 S1 和 S2,则任何知道 M1、S1,M2,S2的人可以伪造对消息 M1M2的签名S1S2,使用安全的Hash函数可以避免这样的攻击

利用签名获得明文:

  1. 攻击者截获密文 C = M^e^ mod n,选择随机数 r,并计算 x = r^e^ mod n,y = x * C mod n
  2. 攻击者设法让发送者对y进行签名,获得 S = y^d^ mod n
  3. 攻击者计算 r^-1^ * S mod n = r^-1^ y^d^ mod n = r^-1^ x^d^ C^d^ mod n = C^d^ mod n = M
  4. 防范:对数据的Hash值签名

H(M)的重要性

  1. 加快签名速度,消息比较长时,使用公钥加密速度比较慢,对消息的Hash值签名,签名只与Hash值的长度有关
  2. 比单纯对消息本身进行签名具有更好的抗攻击性

EIGamal签名体制

安全性:

  1. 非确定性数字签名算法,同一消息M的签名依赖于随机数k
  2. 安全性基于有限域上计算离散对数的困难性
  3. 随机数k不能泄露(已知k可以计算x)
  4. 随机数k不能被重复使用(可计算出k进而计算出私钥x)