密码学基础与应用

梳理下最近学的密码学基础知识

密码学概论

基本概念

• 密码学是一门古老的学科，研究密码学编制的科学称为密码编制学(Cryptography),研究破译密码学的科学称为密码分析学(Cryptoanalysis),密码编制学和密码分析学共同组成密码学。
• 密码学的三个安全目标
  • 保密性
  • 完整性
  • 可用性

• 保密性是确保信息仅被合法用户访问，而不被泄露给非授权用户、实体或过程，或供其利用的特性。

• 完整性是指所有资源只能由授权方或以授权的方式进行修改，即信息未经授权不能进行改变的特性。
• 可用性是指所有资源在适当的时候可以由授权方访问，即信息可被授权实体访问并按需求使用的特性。

密码体制

• 明文空间M
• 密文空间C
• 密钥空间K
• 加密算法E
• 解密算法D

密码分析学

攻击方法

• 穷举法
• 数学分析攻击
• 基于物理的攻击

可利用的数学资源

• 仅知密文攻击(最不利的情况)
• 已知明文攻击(某些明文-密文对)
• 选择明文攻击(计算机系统和数据库系统特别容易受到这种攻击)
• 选择密文攻击(主要用于攻击公开密钥密码体制，特别是攻击其数字签名)
  

古典密码

• 置换密码
  将明文中的字母重新排列，字母本身不变，但其位置改变了，这样编成的密码称为置换密码。
• 代替密码
  用密文字母表中的字母或字母组来代替明文字母或字母组，各字母或字母组的相对位置不变，但其本身改变了，这样编成的密码称为代替密码。
  1. 加法密码：凯撒密码(Caesar)，右移3位
     
  2. 乘法密码
     
  3. 仿射密码：乘法密码与加法密码相结合
     
     简单代替密码
     多表代替密码：维吉尼亚密码(Vigenre)，密行、明列。
  4. 代数密码
     相同为0，不同为1
     

古典密码破解方法

穷举分析

• 加法密码：对k的可能取值逐一穷举
• 乘法密码：密钥k要满足(n,k)=1
• 放射密码：密钥k有$26*12-1=311$种

统计分析

• 统计密文的各种统计特性
• 分析双字母、三字母密文组，以区分元音和辅音字母
• 最后分析字母较多的密文
  
  
  
  

分组密码

概念

• 设M为明文，分组密码将M划分为一系列的明文块M_i,通常每块包含若干个位或字符，并且对每一块M_i都用同一个密文K_e进行加密。常用于商用领域。
  

分组密码算法结构

Feistel结构

• Feistel结构把任何函数(一般称为f函数，又称轮函数)转化为一个置换
  

SP结构

• SP结构是Feistel结构的一种推广，其结构清晰
  

  替换S：混淆的作用，即密文和密钥尽可能的复杂
  线性变换P：扩散的作用，即明文当中的每一位能够影响密文当中的每一位。

DES算法

DES算法流程

• 初始置换IP
• 生成16个48位的子密钥
• 16轮Feistel结构迭代
  • 扩展置换E
  • S盒代换
  • 置换P
• 逆初始置换IP^-1

初始置换IP

生成16个48位的子密钥

16轮Feistel结构迭代

逆初始置换IP^-1

DES算法的安全性

• 密钥较短
  面对计算能力高速发展的形势，DES采用56位密钥，密钥量仅为2⁵⁶，约为10¹⁷
• 存在弱密钥
  • 弱密钥K
    K₁=K₂=……K₁₆,弱密钥不受任何循环移位影响。
    全为0或全为1，被分割的两部分分别为全0或全1，共4种弱密钥。
  • 半弱密钥K
    有些种子密钥只能生成两个不同的子密钥，这样的种子密钥称为半弱密钥。DES至少存在12个半弱密钥，半弱密钥将导致把明文加密成相同的密文。

三重DES

优点

• 密钥长度为168位，能够抵挡有效攻击(第一次和第三次加密都是同一个密钥则为112位)
• 相当安全，而且经过实践检验
• 加密算法与DES相同，现有的DES软硬件产品都能方便实现3DES

缺点

• 用软件实现该算法的速度比较慢

考试知识点

在DES算法中

• 密钥的长度(有效)是56位
• 加密分组的长度是64位
• 子密钥的长度是48位
• 函数F输入时32位

AES算法

• 一个初始轮密钥加
• Nr-1圈的标准轮函数
• 最后一圈的非标准轮函数
• 最后一轮不进行列混淆变换

• RIJNDAEL算法
  数据块长度和密钥长度都可变的分组加密算法，其数据块长度和密钥长度都可独立地选定为大于等于128位、且小于等于256位的32位的任意倍数。
• AES(先进加密标准)算法
  数据块长度为128位，密钥的长度可分别选择为128位、192位或256位。

状态：在RIJNDAEL算法中，加解密要经过多次数据变换操作，每一次变换操作产生一个中间结果，称这个中间结果叫做状态。状态表示为二维字节数组(每个元素为一个字节)，它有四行，Nb列，Nb列等于数据块长度除以32。

密钥也可以表示为二维字节数组(每个元素为一个字节)，它有四行，Nk列，Nk列等于密钥块长度除以32。

迭代圈数Nr由Nb和Nk共同决定。

初始轮密钥加

• 将明文矩阵与子密钥矩阵的对应字节进行逐比特异或。
  $AddRoundKey(a_0,k_0)=a_0 \bigoplus k_0$

轮函数

• 采用替换/置换网络(SP)结构，组成：
  • 非线性层：S盒变换ByteSub，混淆作用。
  • 线性混合层：行位移变换ShiftRow和列混合变换MixColumn，扩散作用。
  • 密钥加层：圈密钥加变换AddRoundkey组成，最后一圈的轮函数没有列混合变换。

字节代换

字节代换：S盒变换ByteSub

• 一个关于字节的非线性变换，可以使用S盒查表得出输出。
• AES定义了一个S盒，由16*16个字节组成的方形表，包含了8位值所能表示的256种可能的变换。

• 高位为行，低位为列。即51对应5行1列的D1

AES算法与DES算法的S盒比较：

• AES，由16个S盒组成，运算是可逆的；输入输出位数相同。
• DES，由8个S盒组成，运算不可逆，每个S盒输入是6bit,输出是4bit。

行移位

行移位：ShiftRow

• 将状态矩阵的每行进行循环左移
• 第0行不移；第i行左移i个字节(i=1,2,3)

列混合

列混合：MixColumn

• 列混合变换将State乘以一个固定的矩阵A，对State逐列进行变换，每一列中的每个字节将变换成一个新值，直到4列均变换完毕。
• 相乘后得到的乘积矩阵，其中每个元素均是一行和一列中所对元素的乘积之和。

将固定矩阵中的第一行和State的第一列的每个字节分别相乘，再进行异或运算得到第一行第一列的值，即：
$(02*D1) \bigoplus (03*93) \bigoplus (01*CA) \bigoplus (01*40)=9D$
第二行第一列则通过固定矩阵中的第二行和State的第一列进行计算，即：
$(01*D1) \bigoplus (02*93) \bigoplus (03*CA) \bigoplus (01*40)=E9$
以此类推…

轮密钥加

轮密钥加：AddRoundkey(State,RoundKey)

• 将状态矩阵与子密钥矩阵的对应字节进行逐比特异或：
  $AddRoundKey(a_{ij},k_{ij})=a_{ij} \bigoplus k_{ij}$

轮函数：第一轮结束后，回到轮函数迭代10轮(主要针对数据块长度和密钥长度为128位)，最后一轮不需要进行列混合变换，结束迭代后输出密文。

解密算法

AES算法的解密过程中依次进行逆字节代换，逆行移位，逆列混合和轮密钥加。

• InvByteSub()是ByteSub()的逆变换，通过查逆S盒来实现。
• InvShiftRow()是ShiftRow()的逆变换，对State的各行进行一定量的循环移位(Nb=4)。第0行不移位，第1行循环右移1个字节，第2行循环右移2个字节，第三行右移3个字节。
• InvMixColumn()是MixColumn()的逆变换。
• AddRoundKey的逆就是他本身。

AES算法的安全性

• 不存在弱密钥
  该算法对密钥的选择没有任何限制，还没有发现弱密钥和半弱密钥的存在。

• 抗攻击能力强
  可抵抗穷举法密钥的攻击，密钥量为2¹²⁸/2¹⁹²/2²⁵⁶,足以抵抗穷举攻击。
  可抵抗线性攻击(已知明文攻击)，经4轮变换后，线性分析就无能为力了。
  可抵抗差分攻击(选择明文攻击)，经8轮变换后，差分攻击就无从着手了。
• 适应性强
  Rijindael的数据库长度和密钥长度都可变，因此能够适应不同的安全应用环境。

SM4算法

• 简介
  • 我国国家密码管理局公布的无线局域网产品使用的密码算法。
  • 数据分组为128位，密钥长度为128位，迭代32次。
  • 数据处理单位：字节(8位)，字(32位)。
• 特点
  • 对合运算：解密算法和加密算法结构相同
  • 子密钥生成算法与加密算法结构类似
• 结构
  • 采用非对称Feistel结构。

基本运算

• 模2加：$\bigoplus$，32位异或运算
• 循环移位：<<<i，把32位字循环左移i位

基本密码部件

1. S盒：
   • 非线性字节变换，起混淆作用
   • 8位输入，8位输出。
   • 本质上是8位的非线性置换。
   • 设输入字节为a，输出字节为b，则S盒的运算可表示为：b=S_Box(a)
   • S盒置换规则
     以输入的高半字节为行号，低半字节为列号，行列交叉点的数据即为输出。
     例：设S盒的输入为EF，则S盒的输出为E行F列交叉点的值，即
     Sbox(‘ef’)=’84’
     说明：在主要密码学指标上达到最佳，与AES的S盒相当

2. 非线性变换$τ$ :起混淆作用
   4个S和并行置换
   设输入字$A=(a_0,a_1,a_2,a_3)$,输出字$B=(b_0,b_1,b_2,b_3)$
   B=τ(A)=(S_box(a₀),S_box(a₁), S_box(a₂),S_box(a₃))

3. 字线性部件L变换：起扩散作用

   • 32位输入，32位输出。
   • 设输入为字B，输出为字C，则
     $C=L(B)=B \bigoplus (B<<<2) \bigoplus (B<<<10) \bigoplus (B<<<18) \bigoplus (B<<<24)$

4. 字合成变换$τ$：

   • 由非线性变换$τ$和线性变换L复合而成。
     $T(x)=L(τ(A))$

先S变换，再L变换

轮函数

• 输入数据：$(x_0,x_1,x_2,x_3)$，128位，四个32位字。
• 输入轮密钥：rk，32位字。
• 输出数据32位字。
• 轮函数：$F(x_0,x_1,x_2,x_3)=x_0 \bigoplus T((x_1 \bigoplus x_2 \bigoplus x_3 \bigoplus rk))$

加密算法

• 输入明文：$(M_0,M_1,M_2,M_3)=(X_0,X_1,X_2,X_3)$四个字，128位。
• 输入轮密钥：$rk_i,i=0,1,……,31$，共32个轮密钥。
• 输出密文：$(Y_0,Y_1,Y_2,Y_3)$，四个字，128位。
• 算法结构：轮函数32轮迭代，每轮使用一个轮密钥。
• 加密算法：
  • 加密变换 $X_{i+4}=F(x_i,x_{i+1},x_{x+2},x_{i+3},rk_i)=x_i \bigoplus T(x_{i+1} \bigoplus x_{i+2} \bigoplus x_{i+3} \bigoplus rk_i,i=0,1…31)$
  • 反序变换：$(Y_0,Y_1,Y_2,Y_3)=(X_{35},X_{34},X_{33},X_{32})$

解密算法

• SM4密码算法是对合的，因此解密与加密算法相同，只是轮密钥的使用顺序相反。
• 输入密文：$(Y_0,Y_1,Y_2,Y_3)=(X_35,X_34,X_33，X_32)$
• 输入轮密钥：$rk_i,i=31,30,……,0$
• 输出明文：(X_0,X_1,X_2,X_3)
• 算法：轮函数的32轮迭代，每轮使用一个轮密钥
• 解密算法：用符号X描述

密钥扩展算法

1. 常数FK
   在密钥扩展中使用一些常数(32位字)；
   $FK_0=(A3B1BAC6)$
   $FK_1=(56AA3350)$
   $FK_2=(677D9197)$
   $FK_3=(B27022DC)$

2. 固定参数CK，32位：32个固定参数CK_i,i=0,1,2,…,31

• 输入加密密钥：$MK=(MK_0,MK_1,MK_2,MK_3)$
• 输出轮密钥：$rk_i,i=0,1,…,30,31$
• 中间数据：$K_i,i=0,1,…,34,35$
• 密钥扩展算法：

SM4密码结构

• SM4密码与DES密码有相似性
• DES密码采用的是Feistel结构，SM4也采用Feistel结构。
• DES中参与交换的两个数据块的长度也是相等的，而在SM4中参与交换的两个数据块的长度是不相等的。
• 因此，密码届称DES密码采用的是对称Feistel结构，SM4密码采用的是非对称Feistel结构。
  
  
  

分组密码工作模式

• 分组密码可以按不同的模式工作，实际应用的环境不同应采用不同的工作模式。只有这样才能既确保安全，又方便高效。

电子密码本(ECB)

特点

• 数据的长度是密码分组长度的整数倍
• 容易暴露明文的数据模式
• 由于所有数据块分组的加密方式一致，难以抵抗统计分析攻击
• 操作简单，容易实现
• 由于每个块的加密和解密都是独立的，可并行进行加密
  

密码块链接(CBC)

明密文链接模式

• 解决了ECB的安全缺陷，可以让重复的明文分组产生不同的密文分组，可以抵御重放攻击。
• 适合传输数据长度大的报文
• 加解密传播无界，加密时，当明文块或密文块中发生一位错误时，自此以后的密文都发生错误
• 数据的长度是密码分组的整数倍
• 不能进行并行加密

密文链接模式

• 使用了不同的初始向量组，完全相同的明文在加密之后可以得到不同的密文，可以抵御重放攻击
• 适合传输数据长度大的报文
• 加密传播无界，但解密传播有界，解密时，当密文块中发生一位错误时，只影响其中相应解密的明文，其余不会发生错误，适合磁盘文件加解密
• 数据的长度是密码分组的整数倍
• 不能进行并行加密

CBC特点

• 解决了ECB的安全缺陷，可以让重复的明文分组产生不同的密文分组，可以抵御重放攻击。
• 适合传输数据长度大的报文
• 明密文链接模式加解密传播无界；密文链接模式加密错误传播无界，解密错误传播有界
• 数据的长度是密码分组的整数倍
• 不能进行并行加密
  

填充密码块链接(PCBC)

输出反馈(OFB)

密文反馈(CFB)

计数器模式(CTR)

例题

1. 明密文链接模式
2. 加解密错误传播无界
   数据的长度是密码分组的整数倍
   
   
   

序列密码

RC4序列密码

ZUC算法

ZUC算法，又称为祖冲之算法，是移动通信3GPP机密性算法EEA3和完整性算法EIA3的核心，是中国自主设计的加密算法。

例题

Hash函数

SHA算法

算法步骤

例题

公钥密码体制

对称密码存在哪些局限性

• 密钥分发的问题
• 密钥数量的问题
• 数字签名问题

公钥密码体制模型

公钥加密的安全性

• 确保数据的秘密性
• 确保数据的真实性
• 同时确保数据的秘密性和真实性

例题

RSA密码

• n,e公开

ELGamal密码

了解

例题

数字签名

RSA

ELGamal密码

RSA和ELGamal签名安全性

例题

认证

概念

• 认证，又称鉴别或确认，是证实某事是否名副其实或是否真实有效的一个过程。
• 认证和加密的区别
  • 加密用以确保数据的保密性，阻止对手的被动攻击，如截取、窃听等。
  • 认证用以确保报文发送者和接受者的真实性以及报文的完整性，阻止对手的主动攻击，如冒充、篡改、重播等。

• 认证和数字签名技术的区别
  • 认证总是基于某种收发双方共享的保密数据来认证被鉴别对象的真实性，数字签名中用于验证签名的数据是公开的。
  • 认证允许收发双方互相验证其真实性，不准许第三者验证，数字签名允许双方和第三者都能认证。
  • 数字签名具有发送方不能抵赖，接收方不能伪造和具有在公证人前解决纠纷的能力，而认证不一定具备。

身份认证

口令认证

• 利用单向函数加密口令
  用户口令在系统中以密文的形式存储。只能加密，不能解密。
• 利用数字签名方法验证口令
  用户的公钥存储在系统中。系统为用户设置了时间标志T_i,可以抵抗重播攻击。
• 口令的双向验证
  用户和系统相互平等地验证对方的身份
  选择一个单向函数f，假设A要求与B，则A和B可如下相互认证对方的身份：
  1. A->B:R_A
  2. B->A:f(P_B||R_A)||R_B
  3. A->B:f(P_A||R_B)
     由于f是单向函数，即使知道f(P_B||R_A)也不能计算出P_A，即使知道f(P_A||R_B)，也不能计算出P_B。可在f函数中加入时间参数，阻止重播攻击。
• 一次性口令
  一个口令只用一次，可以抵御重放攻击。

生物特征识别

• 通过识别用户的生理特征来认证用户的身份，具有唯一性和稳定性
• 如指纹、掌纹、面孔、发音、虹膜、视网膜、骨架等

报文认证

报文认证，必须是通信方能够验证每份报文的发送方、接收方、内容和时间性的真实性和完整性

报文源的认证

• 设A为报文发送方，简称为源，B是报文的接收方，简称为宿。
• A与B共享保密的密钥$K_S$。A的标识为$ID_A$，要发送的报文为$M$，那么B认证A的过程如下
  $A->B:E(ID_A||M,K_S)$
• A在发给B的每份报文中都增加标识$ID_A$，然后用$K_S$加密并发送给B。
• 公开密钥密码实现报文源的认证：$A->B:E(ID_A||M,K_{dA})$

报文宿的认证

• 在以密钥为基础的认证方案的每份报文中加入接受方标识符$ID_B$
  $A->B:E(ID_B||M,K_S)$
• 公开密钥密码实现报文宿的认证：$A->B:E(ID_B||M,K_{eB})$

报文内容的认证

报文内容认证使接收方确认报文内容的真实性，通过验证认证码的正确性来实现。

报文加密

将整个报文的密文作为认证码：发送方A要发送报文给接收方B，则A用他们的共享密钥K对发送的报文M加密后发给B；
$A->B:E(M,K)$

• 报文的密码性：如只有A和B知道密钥K，其他任何人均不能恢复出报文明文。
• 报文源的认证：除B外只有A拥有K，也就只有A可产生出B能解密的密文。
• 报文认证：如果B可以恢复出明文，则可认为M中的每一位都未被改变。

消息认证码(MAC)

消息认证的实质是：发送者通过双方协商的某种函数(如Hash函数)，以待发消息作为输入经过函数变换产生消息认证码(简称MAC)。
$MAC=C(M,K)$
$A->B:E(M||C(M,K_1),K_2)$
$A->B:E(M,K_2)||C(E(M,K_2),K_1)$

基于hash函数的消息认证码(HMAC)

带密钥的Hash函数构造方案

例题

密钥管理

概念

• 密钥管理包括密钥的产生、存储、分配、组织、使用、更换、销毁等一系列技术问题。

对称密码的密钥管理

非对称密码的密钥管理

公约基础设施PKI

• 签证机构CA：负责签发证书，管理和撤销证书
• 注册机构RA：专门负责受理用户申请证书的机构
• 证书的签发：CA签发
  CA签发过程：
  1. 用户向CA提交RA的注册批准信息及自己的身份等信息(或由RA向CA提交)；
  2. CA验证所提交信息的正确性和真实性；
  3. CA为用户产生密钥(或由用户自己产生并提供密钥)，并进行备份；
  4. CA生成证书，并施加签名；
  5. 将证书的一个副本交给用户，并存档入库。
• 证书目录
• 证书的认证
• 证书的撤销
• 信任模型