教材:应用密码学 (张仕斌 编著)

0x01 绪论

  • 信息安全的基本属性:

    • 真实性:确认和识别主体或资源就是其声称的。
    • 保密性:信息不泄露给非授权的用户、实体和进程。
    • 完整性:信息未经授权不被修改破坏。
    • 可用性:保证合法用户在需求时能够获得所需的信息和相关资源。
    • 可控性:可以控制授权范围内的信息流向及信息传播方式。
    • 可审查性(不可否认性):通信双方不能抵赖做出的行为。
    • 可靠性:信息以用户认可的质量连续服务于用户。
  • 信息安全机制

    • 通用安全机制:可信功能、安全标签、事件检测、安全审计跟踪、安全恢复机制
    • 特殊安全机制: 加密、数字签名、访问控制、数据完整性、鉴别、业务流量填充、路由控制、公正机制
  • 安全性攻击

    • 被动攻击:通常采用流量监听、无线截获等方式,难以检测,需采用防止策略。
    • 主动攻击:通常为伪造、重放、篡改信息和拒绝服务,主要防止途径是检测。
  • 密码体制及其分类

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

    • 分类:主要是对称密码体制和非对称密码体制

      1.密文数据段是否与明文数据段在明文的位置相观:分组密码体制与序列密码体制

      2.加密变换是否可逆:单向变换密码体制与双向变换密码体制

      3.加密过程是否引入客观随机因素:确定型密码体制和概率密码体制

  • 评价密码体制安全性

    • 评价安全性的方法:无条件安全(提供充足的资源)、计算安全性(算力不足)

    • 破译原则:

      1.成本是否超过被加密信息本身的价值

      2.时间是否超过被加密信息有用的生命周期

0x02 古典密码

替换密码

  • 单字符单表替换密码:凯撒密码、放射密码
  • 单字符多表替换密码:维吉尼亚密码、希尔密码

换位密码

  • 列换位:栅栏密码
  • 周期换位

0x03 数学基础

初等数论

  • 欧几里得算法

    定理:

    (说法一)设a,b,c是三个不全为0的整数,a=bq+c,其中q是整数,则(a,b)=(b,c)。

    (说法二)假如a>b,且r=a mod b,那么a = kb+r,假如d是a和b的公约数,即满足d|a和d|b,r可以表示为r=a-kb,因为a和b能被d整除,那么r也能被d整除,即d|r,所以d也是b和r的公约数。

    证明:

    进一步辗转:

    可得m是a和b的最大公约数。

  • 欧拉定理

    欧拉函数:设m为正整数,则1,2…,m中与m互素的整数个数记做φ(m),叫做欧拉函数。

    欧拉定理:设m是大于1的整数,若(a.m)=1,则 aφ(m)=1(modm)a^{φ(m)}=1(mod m)

  • 费马小定理

    若p为素数,a为任意正整数且不是p的倍数,则ap1=1(modp)a^{p-1}=1(mod p)==>ap=a(modp)a^{p}=a(modp)

  • 离散对数

    离散对数公钥加密算法安全性远高于基于大数分解的算法。

    离散对数问题:给定一个素数p,g为模p循环群的原根,对任意的a,b=ga(modp)b=g^a(modp),已知b计算a是困难的。

  • 模重复平方算法

    为了研究快速幂

    1
    2
    3
    4
    5
    6
    7
    8
    9
    //b^n mod m
    //bit(n)=(nk nk-1 ...n1n0)
    //list(n):n[0]=n0、n[1]=n1...
    s = 1
    for(i=0;i<=k;i++){
    if(n[i]==1)
    s = (s*b)%m;
    b = (b*b)%m;
    }
  • Miller-Rabin素性检测算法

    目的:基于费马小定理,用于判断模数是否是素数(伪素数)。

    问题:设n为正奇数,若bn1=1(modn)b^{n-1}=1(modn)不成立,则n为合数;若成立,n也可能是合数。

    内容:

  • 封闭性:

    a,bG,abG\forall a,b \in G,ab\in G

  • 结合律:

    a,b,cG,a(bc)=abcG\forall a,b,c \in G,a(bc)=abc \in G

  • 单位元:

    aG,ae=ea=a\forall a \in G,ae=ea=a

  • 逆元:

    aG,bG,s.t. ab=ba=e\forall a \in G,\exists b \in G,s.t.\ ab=ba=e

有限域

  • 加法交换群:零元和负元
  • 乘法交换群:单位元和逆元
  • 乘法对加法有分配律

0x04 分组密码

安全设计原则:

  • 分组长度足够长
  • 密钥量足够大
  • 密钥变换足够复杂
  • 数据扩展足够小
  • 差错传播尽可能小

分组密码原理:

两个基本方法:

  • 扩散:将明文和密钥的统计特性散布到密文中去,使得明文和密钥的每一位都影响密文中多位的值。
  • 混淆:使密文与对应的明文与密钥的统计关系尽可能的复杂

代替–置换网络(S-P结构)

S代替起到混淆的作用,P置换起到扩散的作用

Feistel密码结构

  • 基本过程:

    Li=Ri1L_i=R_{i-1}

    Ri=Li1F(Ri1,Ki)R_i=L_{i-1}⊕F(R_{i-1},K_i)

  • 保证安全性的参数:
    • 分组大小:普遍使用64bit或128bit
    • 密钥大小:通常128bit
    • 轮数:一般为16
    • 子密钥生成算法:越复杂越安全
    • 轮函数:越复杂越安全

数据加密标准DES

1.基础知识

  • 密钥有64bit,其中8bit是奇偶校验位,即有效密钥是56bit
  • 轮密钥:48bit
  • 分组:64bit
  • 过程:16轮迭代+最后左右交换

2.轮密钥生成

  • 若输入56bit,8位一组,末尾添加校验位(奇数校验位)。
  • 若64bit,直接使用

3.加密过程

  • 初始置换IPIP

    将64bit明文按下表重新排列输出:

  • 轮结构

    轮结构主要过程:

    F函数的主要过程:

    • E盒扩展:

      输入32位,输出48位。

    • S盒代替

      8个S盒,输入6位b5b4b3b2b1b0b_5b_4b_3b_2b_1b_0,输出4位;以b5b0b_5b_0为行,以b4b3b2b1b_4b_3b_2b_1为列,获得输出。

    • P盒置换

      P盒如下:输入32位,输出32位

  • 逆初始置换IP1IP^{-1}

高级加密标准AES(Rijndael算法)

1.基础知识:

明文分组长度:128bit

密钥长度:128bit、192bit、256bit

基本运算:是在GF(28)GF(2^8)的有限域上进行的。

不可约多项式:p(x)=x8+x4+x3+x+1p(x)=x^8+x^4+x^3+x+1

运算元素:一个字节(8bit)代表一个余式(256个)

加解密操作都是在一个4×4(128)的字节矩阵上完成的。

明文列数 密钥长度 密钥矩阵(4×NkN_k) 迭代轮数(NrN_r)
AES-128 4(4×4) 128bit 4×4 10
AES-192 6(4×6) 192bit 4×6 12
AES-256 8(4×8) 256bit 4×8 14

2.加密过程:

3.基本过程:

  • 字节代替

    非线性模块!

    只有一个S盒,输入字节的前4位为行,后4位位列,进行查表。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    SBox = {
    0:['0x63', '0x7c', '0x77', '0x7b', '0xf2', '0x6b', '0x6f', '0xc5', '0x30', '0x01', '0x67', '0x2b', '0xfe', '0xd7', '0xab', '0x76'],
    1:['0xca', '0x82', '0xc9', '0x7d', '0xfa', '0x59', '0x47', '0xf0', '0xad', '0xd4', '0xa2', '0xaf', '0x9c', '0xa4', '0x72', '0xc0'],
    2:['0xb7', '0xfd', '0x93', '0x26', '0x36', '0x3f', '0xf7', '0xcc', '0x34', '0xa5', '0xe5', '0xf1', '0x71', '0xd8', '0x31', '0x15'],
    3:['0x04', '0xc7', '0x23', '0xc3', '0x18', '0x96', '0x05', '0x9a', '0x07', '0x12', '0x80', '0xe2', '0xeb', '0x27', '0xb2', '0x75'],
    4:['0x09', '0x83', '0x2c', '0x1a', '0x1b', '0x6e', '0x5a', '0xa0', '0x52', '0x3b', '0xd6', '0xb3', '0x29', '0xe3', '0x2f', '0x84'],
    5:['0x53', '0xd1', '0x00', '0xed', '0x20', '0xfc', '0xb1', '0x5b', '0x6a', '0xcb', '0xbe', '0x39', '0x4a', '0x4c', '0x58', '0xcf'],
    6:['0xd0', '0xef', '0xaa', '0xfb', '0x43', '0x4d', '0x33', '0x85', '0x45', '0xf9', '0x02', '0x7f', '0x50', '0x3c', '0x9f', '0xa8'],
    7:['0x51', '0xa3', '0x40', '0x8f', '0x92', '0x9d', '0x38', '0xf5', '0xbc', '0xb6', '0xda', '0x21', '0x10', '0xff', '0xf3', '0xd2'],
    8:['0xcd', '0x0c', '0x13', '0xec', '0x5f', '0x97', '0x44', '0x17', '0xc4', '0xa7', '0x7e', '0x3d', '0x64', '0x5d', '0x19', '0x73'],
    9:['0x60', '0x81', '0x4f', '0xdc', '0x22', '0x2a', '0x90', '0x88', '0x46', '0xee', '0xb8', '0x14', '0xde', '0x5e', '0x0b', '0xdb'],
    10:['0xe0', '0x32', '0x3a', '0x0a', '0x49', '0x06', '0x24', '0x5c', '0xc2', '0xd3', '0xac', '0x62', '0x91', '0x95', '0xe4', '0x79'],
    11:['0xe7', '0xc8', '0x37', '0x6d', '0x8d', '0xd5', '0x4e', '0xa9', '0x6c', '0x56', '0xf4', '0xea', '0x65', '0x7a', '0xae', '0x08'],
    12:['0xba', '0x78', '0x25', '0x2e', '0x1c', '0xa6', '0xb4', '0xc6', '0xe8', '0xdd', '0x74', '0x1f', '0x4b', '0xbd', '0x8b', '0x8a'],
    13:['0x70', '0x3e', '0xb5', '0x66', '0x48', '0x03', '0xf6', '0x0e', '0x61', '0x35', '0x57', '0xb9', '0x86', '0xc1', '0x1d', '0x9e'],
    14:['0xe1', '0xf8', '0x98', '0x11', '0x69', '0xd9', '0x8e', '0x94', '0x9b', '0x1e', '0x87', '0xe9', '0xce', '0x55', '0x28', '0xdf'],
    15:['0x8c', '0xa1', '0x89', '0x0d', '0xbf', '0xe6', '0x42', '0x68', '0x41', '0x99', '0x2d', '0x0f', '0xb0', '0x54', '0xbb', '0x16']
    }
  • 行移位

    作用于S盒的输出。

    每行进行循环左移,左移距离:与列数和所在行相关。

NbN_b C0C_0 C1C_1 C2C_2 C3C_3
4 0 1 2 3
6 0 1 2 3
8 0 1 3 4
  • 列混合

    将状态矩阵的每列与一固定的多项式a(x)a(x)相乘(在域GF(28)GF(2^8)上运算),然后模多项式x4+1x^4+1

    其中a(x)={03}x3+{01}x2+{01}x+{02}a(x)=\{03\}x^3+\{01\}x^2+\{01\}x+\{02\}(其中一个):

    输入:状态矩阵BB

    输出:矩阵CC

    C=A4×4BC=A_{4×4}B

    其中:

    A4×4=[02030101010203010101020303010102]A_{4×4}=\left[ \begin{matrix} 02&03&01&01\\ 01&02&03&01\\ 01&01&02&03\\ 03&01&01&02\\ \end{matrix} \right]

  • 轮密钥加

    • 状态矩阵与轮密钥矩阵对应位置进行异或(xorxor)运算。

    • 密钥扩展过程(以Nk=4N_k=4为例):

      ii列密钥的生成:

      Ki={Ki4Ki1, (if i mod4 !=0)Ki4T(Ki1), (if i mod4 =0)K_i=\left\{ \begin{array}{} K_{i-4}\oplus K_{i-1},\ (if\ i\ mod4\ !=0)\\ K_{i-4}\oplus T(K_{i-1}),\ (if\ i\ mod4\ =0)\\ \end{array} \right.

      函数T(Ki1)T(K_{i-1}):

      • Ki1K_{i-1}以字节形式左移一位:FFEEEEAA ==> EEEEAAFF
      • 将左移后的进行字节替换(S盒)
      • 将结果与Rcon[i/Nk]Rcon[i/N_k]进行异或
i RCRC RconRcon
1 01 01000000
2 02 02000000
3 04 04000000
4 08 08000000
5 10 10000000
6 20 20000000
7 40 40000000
8 80 80000000
9 1B 1B000000
10 36 36000000

其中RC[i]=xi1RC[i]=x^{i-1}

0x05 序列密码*

0x06 非对称密码

RSA

  • 密钥生成

    1.选择两个大素数p,q.计算n=pq,φ(n)=(p1)(q1)n=pq,\varphi(n)=(p-1)(q-1)

    2.选择一个整数e,1<e<φ(n),gcd(φ(n),e)=1e,1<e<\varphi(n),gcd(\varphi(n),e)=1。通过de=1modφ(n)de=1mod\varphi(n)计算得到d。

    3.{e,n}为公钥,{d,n}为私钥。

  • 加密算法

    消息m,计算c=me(modn)c=m^e(modn)

  • 解密算法

    计算m=cd(modn)m=c^d(modn)

ELGamal

  • 密钥生成:

    gZpg\in Zp*是一个本原元,选择x,1<x<p1x,1<x<p-1,计算y=gxmodpy=g^xmodpg,y,p{g,y,p}是公钥,g,x,p{g,x,p}是私钥。

  • 加密算法:

    对于消息m,发送方随机选择秘密k,1<k<pk,1<k<p,计算C1=gkmodp,C2=mykmodpC_1=g^kmodp,C_2=my^kmodp,发送C1,C2C_1,C_2

  • 解密算法:

    计算C1xC2modp=mC_1^{-x}C_2modp=m,即为发送方的消息m。

0x07 认证–Hash函数

Hash函数是一个公开函数,不需要密钥,用于将任意长的消息m映射为较短的、固定长度的一个值H(m)。

对H的六个要求:

  • 能够接受任意长度的消息作为输入
  • 能够生成较短的、固定长度的输出
  • 对任何消息输入都应该能够容易快速地计算出哈希值
  • 单向性:H(m)不能恢复出m
  • 抵抗弱碰撞:给定消息m和H(m),找到 m'!= m 使得 H(m)=H(m')是不可能的
  • 抵抗强冲突:可以有两个有意义的消息m和m’,使得 H(m)=H(m')是不可能的

0x08 认证–数字签名

典型数字签名方案

  • RSA

    条件:{e,n}为公钥,{d,n}为私钥,信息为m

    签名过程:s=md(modn)s=m^d(modn)

    验证过程:m=se(modn)m=s^e(modn)是否成立

    缺点:都次使用同一个密钥签名,会出现m=m1m2m=m1*m2,其中m为恶意构造的信息

    改进:对H(m)进行签名

  • ElGamal

    条件:y=gx(modp)y=g^x(modp),g,y,p{g,y,p}为公钥,g,x,p{g,x,p}为私钥,信息为m

    签名过程:签名者随机选择秘密k,计算 γ=gk(modp),δ=(mxγ)k1mod(p1)\gamma=g^k(modp),\delta=(m-x\gamma)k^{-1}mod(p-1),其中(m,γ,δ)(m,\gamma,\delta)为对消息m的签名。

    验证过程:yγγδmodp=gm(modp)y^{\gamma}\gamma^{\delta}modp=g^m(modp)是否成立

盲签名方案

  • 基于大数分解问题

    过程如下:

  • 基于离散对数难题

    过程如下:

0x09 认证–身份认证