search

SylverQG / Blogs

存放文章和一些自定义页面内容
https://sylverqg.github.io/Blogs/
MIT License
0 stars 0 forks source link

Crypto #3

Open SylverQG opened 1 year ago

SylverQG commented 1 year ago

现代密码学目录(仅目录)

1. 基础

1.1 威胁

1.2 信息安全模型

1.3 密码学基本概念

1.4 古典密码

2. 流密码

2.1 基本概念

2.2 线性反馈移位寄存器

2.3 线性移位寄存器的一元多项式表达式

2.4 m序列的伪随机性

2.5 m序列密码的破译

2.6 非线性序列

3. 分组密码体制

3.1 概述

3.2 数据加密标准

3.3 差分密码分析与线性密码分析

3.4 分组密码的运行模式

3.5 IDEA

3.6 AES|Rijindael

3.7 SM4

3.8 祖冲之

4. 公钥密码

4.1 数学知识

4.2 基本概念

4.3 RSA

4.4 背包密码体制

4.5 NTRU

4.6 椭圆曲线密码体制

4.7 SM2椭圆曲线公钥密码加密算法

5. 密钥分配与密钥管理

5.1 单钥加密体制的密钥分配

5.2 公钥加密体制的密钥分配

5.3 随机数的产生

5.4 秘密分割

6. 消息认证与哈希函数

6.1 消息认证

6.2 哈希函数

6.3 MD5

6.4 安全哈希算法

6.5 HMAC

6.6 SM3

7. 数字签名和认证协议

7.1 基本概念

7.2 数字签名标准

7.3 其他签名方案

7.4 SM2椭圆曲线公钥密码签名算法

7.4 认证协议

8. 密码协议

8.1 基本协议

8.2 零知识证明

8.3 安全多方计算

9. 可证明安全

9.1 语义安全的公钥密码体制定义

9.2 语义安全的RSA的加密方案

9.3 Paillier公钥密码系统

9.4 Cramer-Shoup密码系统

9.5 RSA-FDH签名方案

9.6 BLS短签名方案

9.7 基于身份的密码体制

10. 网络加密与认证

10.1 网络通信加密

10.2 Kerberos认证系统

10.3 X.509认证业务

10.4 PGP

SylverQG commented 1 year ago

复习概要

一、引言

  1. 密钥体制组成
    1. 明文、密文、密钥、加密算法、解密算法
  2. 好的密钥体制
    1. 两类计算容易
      1. 已知明文和加密密钥
      2. 已知密文和解密密钥
    2. 一个不能
      1. 不知道解密密钥时，不能由密文推知明文
  3. 攻击分析密码体制方法与应对方法
    1. 穷举攻击 $\rightarrow $增大密钥量
    2. 统计分析攻击 $\rightarrow $使得明文与密文的统计特征不一样
    3. 解密变换攻击 $\rightarrow $选择足够复杂的加密算法
  4. 攻击的分类
    1. 自然攻击
      1. 自然灾害、电磁辐射、电磁干扰
    2. 人为攻击
      1. 外部攻击
        1. 被动攻击
        2. 内容信息获取(1)
        3. 数据业务流分析(2)
        4. 主动攻击
        5. 伪造(3)
        6. 篡改：内容修改(4)、顺序修改(5)、计时修改(6)
      2. 外部攻击
        1. 发送方否认(7)
        2. 接收方否认(8)
    3. 安全措施
      1. 数据保密:(1)(2)
      2. 消息认证:(3)(4)(5)(6)
      3. 数字签名:(7)(8)和部分的(3)(4)(5)(6)
  5. 安全攻击的形式
    1. 中断
    2. 截取
    3. 伪造
    4. 篡改
    5. 重放
  6. 密码分析分类
    1. 唯密文攻击：只知道一些密文
    2. 已知明文攻击：知道一些明文密文对
    3. 选择明文攻击：任意明文 $\rightarrow $密文
    4. 选择密文攻击：任意密文 $\rightarrow $明文
    5. 选择文本攻击：任意明文 $\leftrightarrow $任意密文
  7. 密码体制分类
    1. 单钥密码体制
      1. 流密码
      2. 分组密码
    2. 双钥密码体制
      1. 加密密钥和解密密钥不同，DF提出，公钥k1与私钥k2
      2. 用户A用自己的私钥 $k_{A2} $对消息m进行专用变换： $c=D{k_{A_2}} $，将c给用户B
      3. 用户B验证m使用: $$m=E{k{A1}}(c)=E{k_{A1}}(D{k_{A_2}}) $$
      4. 双钥保密和认证体制
        1. 为了同时实现保密性和准确性，可以采用双重加解密 
          
graph LR;
A(用户A)--m-->DkA2;
DkA2-->EkB1;
EkB1-->DkB2;
DkB2-->EkA1;
EkA1--m-->B(用户B);
DkA2--认证-->EkA1;
EkB1--保密-->DkB2;
SylverQG commented 1 year ago

二、流密码

  1. 基本概念
    1. 流密码将明文划分为字符（如单个字母），或其编码的基本单元（如0、1数字）
    2. 流密码强度完全依赖于密钥流生成器生成密钥流的随机性和不可预测性
    3. 同步流密码：密钥流产生算法与明文、密文无关
    4. 自同步流密码：密钥流产生算法与明文、密文相关
  2. n级反馈移位寄存器
    1. GF(2)上的一个n级反馈移位寄存器由n个二元存储器与一个反馈函数 $f(a_1,a_2,…,a_n)$

这个怎么这么丑

graph LR

   a3-->a2
   a2-->a1

   a3-->f
   a2---->f
   a1-->f

   f-->a3

   a1--输出-->e[*]
一个三级反馈移位寄存器的状态和输出 状态( $a_3,a_2,a_1$) 输出
1 0 1 1
1 1 0 0
1 1 1 1
0 1 1 1
1 0 1 1
1 1 0 0
  1. 线性反馈移位寄存器(LFSR)
    1. 性质：完全由其反馈函数决定
    2. n级LFSR的状态最多有 $2^n$个
    3. n级LFSR的状态周期 $\le 2^n -1$
    4. 输出序列的周期=状态周期 $\le 2^n -1$
    5. 选择合适的反馈函数可以使序列达到最大值 $2^n -1$
    6. 周期达到最大值的序列称为m序列
    7. LFSR的特征多项式 $p(x)=1+c_1 x+c2 x+…+c{n-1}x_{n-1}+c_n x_n$
  2. m序列
    1. 介绍在上
    2. 游程：连续的0或1的个数
    3. GF(2)上周期为T的序列 ${a_i}$的自相关函数
      1. 设 ${ai}$ 满足线性递推关系: $a{h+n}=c1a{h+n-1}\oplus c2a{h+n-2} \oplus … \oplus c_n a_h$
    4. m序列的破译
SylverQG commented 1 year ago
  1. 例：设敌手获得密文串：101101011110010， 和相应明文串：011001111111001， 相应密钥流：110100100001011，求对应递推关系。 假定敌手还知道密钥流是使用5级线性反馈移位寄存器 解：分别用密文串中前十个比特和明文串中前十个比特建立如下方程
(a_6,a_7,a_8,a_9,a_{10})=(c_5,c_4,c_3,c_2,c_1)
\begin{pmatrix}
a_1 & a_2 & a_3 & a_4 & a_5\\
a_2 & a_3 & a_4 & a_5 & a_6\\
a_3 & a_4 & a_5 & a_6 & a_7\\
a_4 & a_5 & a_6 & a_7 & a_8\\
a_5 & a_6 & a_7 & a_8 & a_9\\
\end{pmatrix}
\tag{1}

即：

(0, 1, 0, 0, 0)=(c_5,c_4,c_3,c_2,c_1)
\begin{pmatrix}
1 & 1 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 0\\
0 & 1 & 0 & 0 & 1\\
1 & 0 & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 0\\
\end{pmatrix}
\tag{2}

求矩阵的逆矩阵：

\begin{pmatrix}
1 & 1 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 0\\
0 & 1 & 0 & 0 & 1\\
1 & 0 & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 0\\
\end{pmatrix}^{-1}
=
\begin{pmatrix}
0 & 1 & 0 & 0 & 1\\
1 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 1\\
0 & 1 & 0 & 1 & 1\\
1 & 0 & 1 & 1 & 0\\
\end{pmatrix}
\tag{3}

从而

(c_5,c_4,c_3,c_2,c_1)=(0, 1, 0, 0, 0)
\begin{pmatrix}
0 & 1 & 0 & 0 & 1\\
1 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 1\\
0 & 1 & 0 & 1 & 1\\
1 & 0 & 1 & 1 & 0\\
\end{pmatrix}
\tag{4}
(c_5,c_4,c_3,c_2,c_1)=(1, 0, 0, 1, 0)\tag{5}

则密钥流的递推关系为

a_{i+5} = c_5 a_i\oplus c_2a_{i+3} =a_i\oplus a_{i+3}
SylverQG commented 1 year ago

三、置换密码

  1. 置换

    1. 置换密码又叫做换位密码，根据一定的规则重新排列明文，打破明文的结构特性。特点是保持明文所有的字符不变，仅仅打乱明文字符的位置和次序。

  2. 常见的置换密码有

    1. 列置换密码：明文遵照密钥的规则按照列换位并且按照列得到密文
    2. 周期置换密码：将明文按照固定的长度进行分组，然后对每组按照某种重新排列得到密文

  3. 例：设有限集 $X = { 1,2,3,4,5,6,7,8 }, \sigma$ 为 $X$上的一个置换，并且满足 $\sigma (1)=2, \sigma (2)=5, \sigma (3)=3, \sigma (4)=6, \sigma (5)=1, \sigma (6)=8, \sigma (7)=4, \sigma (8)=7,$ 因为置换可以对换表示，所以上述置换 $\sigma $可以形式化为:

    \sigma=\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\
2 & 5 & 3 & 6 & 1 & 8 & 4 & 7
\end{pmatrix}
=
(125)(3)(4687)
=
(125)(4687)

    则其逆置换 $\sigma ^{-1}$可表示为：

    \sigma ^{-1}=\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\
2 & 5 & 3 & 6 & 1 & 8 & 4 & 7
\end{pmatrix}^{-1} \\
=
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\
5 & 1 & 3 & 7 & 2 & 4 & 8 & 6
\end{pmatrix}
=(152)(3)(4786)=(152)(4786)

  4. 例：

    • 明文：cryptograph is an applied science
    • 密钥：encry
    • 求密文
\sigma=\begin{pmatrix}
2 & 3 & 1 & 4 & 5\\
c & r & y & p & t\\
o & g & r & a & p\\
h & y & i & s & a\\ 
n & a & p & p & l\\ 
i & e & d & s & c\\
i & e & n & c & e
\end{pmatrix}
=
\begin{pmatrix}
1 & 2 & 3 & 4 & 5\\
y & c & r & p & t\\
r & o & g & a & p\\
i & h & y & s & a\\ 
p & n & a & p & l\\ 
d & i & e & s & c\\
n & i & e & c & e
\end{pmatrix}

则 密文： ycrpt rogap ihysa pnapl diesc niece

  1. 周期置换密码
    1. 周期置换密码是将明文串P按固定长度m分组，然后对每组中的子串按1,2,…,m的某个置换重排位置从而得到密文C。其中密钥 $\sigma $包含分组长度信息。解密时同样对密文C按照长度m分组，并按照 $\sigma$ 的逆置 $\sigma ^{-1}$把每组子串冲核心排列位置从而得到明文P
    2. 例：
      1. 明文："State key Laboratory of Networking and Switching";加密密钥： $\sigma = (1\ 5\ 6\ 2\ 3)$
      2. 将明文分为7组：(Statek)(eyLabo)(ratory)(ofNetw)(orking)(andSwi)(tching)
      3. 加密变换：(aKttSe)(Loyaeb)(tyaorr)(Nwfeot)(kgrion)(dinSaw)(hgcitn)
      4. 最终密文：(aKttSeLoyaebtyaorrNwfeotkgriondinSawhgcitn)
      5. 由加密密钥易知解密密钥： $\sigma ^{-1}=(1\ 3\ 2\ 6\ 5)$
SylverQG commented 1 year ago
  1. 代换密码
    1. 代换，就是明文中的一个字母由其他字母、数字或者符号替代的一种方法
    2. 代换密码就是建立一个代换表，加密时将需要加密的明文依次通过查表，替换为相应的字符，明文字符被逐个替换后，生成无任何意义的字符串，即密文。这样的代换表被称之为密钥
    3. 代换密码的分类
      1. 依据：按照一个明文字母是否总是被一个固定的字符代换进行划分。
      2. 单表代换：(凯撒、仿射)：对明文消息中出现的同一个字母，在加密时都使用同一固定的字母来代换，不管他在什么地方。
      3. 多表代换：(维吉尼亚、Playfair、转轮)：明文消息中出现的同一个字母，在加密时不是完全被同一固定的字母代换，而是根据其出现的位置次序，用不同的字母代换。
    4. 例： 
      密钥=\begin{Bmatrix}
a & b & c & d & e & f & g & h & i & j & k & l & m & n & o & p & q & r & s & t & u & v & w & x & y & z\\
f & q & i & s & h & n & c & v & j & t & y & a & u & w & d & r & e & x & l & b & m & z & o & g & k & p
\end{Bmatrix}
      \begin{matrix}
& to  & be & or & not & to & be\\
加密 &\downarrow\downarrow & \downarrow\downarrow &\downarrow\downarrow &\downarrow\downarrow\downarrow &\downarrow\downarrow &\downarrow\downarrow\\
& bd & qh & dx & wdb & bd & qh\\
解密 &\downarrow\downarrow & \downarrow\downarrow &\downarrow\downarrow &\downarrow\downarrow\downarrow &\downarrow\downarrow &\downarrow\downarrow\\
& to  & be & or & not & to & be\\
\end{matrix}
    5. 仿射密码
      1. 加密： 
        e_k(x)=x+k(mod\ 26)=y\in C
      2. 解密： 
        x=d_k(y)=y-k(mod\ 26)
SylverQG commented 1 year ago
  1. DES
    1. 基本参数
      1. 分组加密算法：明文和密文为64位分组长度
      2. 对称算法：加密和解密除密钥编排不同外，使用同一算法
      3. 密钥长度：有效密钥56位，但每个第8位为奇偶校验位，可忽略
      4. 密钥可为任意的56位数，但存在弱密钥，容易避开
      5. 采用混淆和扩散的组合，每个组合先替代后置换，共16轮
      6. 设明文$m=(L_0 , R_0)$,则DES的加密过程可描述为： 
        \begin{cases}
L_i = R_{i-1}\\
R_i = L_{i-1}\oplus f(R_{i-1},K_i), i=1,2,…,16\\
\end{cases}

        DES的第 $i$ 圈加密结构图

\begin{matrix}
L_{i-1}(32位)& &  & & R_{i-1}(32位) & &\\
\downarrow & & & &\downarrow\\
\downarrow & & \downarrow &\leftarrow &\leftarrow &\leftarrow & K_i\\
\oplus & \longleftarrow & f & \leftarrow &\downarrow \\
(L->>R)&&&&(R->>L)\\
L_i(32位)&&&&R_i(32位)
\end{matrix}

  1. 分组密码的工作模式

    1. 分类
      1. 电码本(ECB)模式
      2. 密码分组链接(CBC)模式
      3. 密码反馈(CFB)模式
      4. 输出反馈(OFB)模式
      5. 计数器(CTR)
    2. 总评
      1. ECB模式简单、高速，但最弱，易受重发和替换攻击，一般不采用
      2. CBC，CFC，OFB模式的选用取决于实际的特殊需求
      3. 明文不易丢信号，对明文的格式没有特殊的要求的环境可选用CBC模式。需要完整性认证功能时也可以选用该模式
      4. 容易丢信号环境下，对明文格式有特殊要求的环境，可以选用CFB模式
      5. 信号特别容易错，但明文冗余特别多，可选用OFB模式

  2. AES

    1. 理论基础
      1. 字节运算：AES中一个字节三有限域GF(28)上的元素表示，通过倍成函数time()实现
      2. 字运算：AES中的32位字表示为系数在有限域GF(28)上的次数小于4的多项式，即$a(x)=a_3 x^3+ a_2 x^2 +a_1 x +a_0$
    2. AES加密
      1. AES密码是一种迭代式密码结构，但不是Feistel结构
      2. 对于AES算法，算法的轮数依赖于密钥长度： $将轮数表示N_r，当N_k=4, N_r=10, 当N_k=6, N_r=12 ; 当N_k=12,N_r=14。【其中：密钥的列数记为 N_k, N_k=密钥长度(bits)\div 32(bits)。 N_k 可以取为4、6和8，对应和密钥长度分别为128位、192位和256位】$
      3. 加密过程：（以128为例）
        1. AES需要迭代十轮，需要11个子密钥
        2. 前面9轮完全相同，每轮包括4个阶段，分别是字节代换(SubBytes)、行移位(ShiftRows)、列混淆(MixColumns)和轮密钥加(AddRoundKey)；最后一轮只3个阶段，减少列混淆。
        3. 例 
          graph TB
start[明文]-->a1(轮密钥加)
subgraph 第一轮
a1-->a2(字节代换)
a2-->a3(行移位)
a3-->a4(列混淆)
a4-->a5(轮密钥加)
end
a5--…-->c1(轮密钥加)
subgraph 第九轮
c1-->c2(字节代换)
c2-->c3(行移位)
c3-->c4(列混淆)
c4-->c5(轮密钥加)
end
c5-->d1(字节代换)
subgraph 第十轮
d1-->d2(字节代换)
d2-->d3(行移位)
d3-->d5(轮密钥加)
end
subgraph key
direction TB
b1("子密钥w[0,3]")-->a1
b2("子密钥w[4,7]")-->a5
b3("子密钥w[36,39]")-->c5
b4("子密钥w[40,43]")-->d5
end
d5-->密文

          mermaid-diagram-AES.svg

    3. AES解密:加密的逆过程
    4. AES安全性：
      1. 抵抗差分分析和线性分析（基于轨迹策略）
      2. 抵抗举密钥攻击
      3. 对密钥的选择没有任何限制，还没有发现弱密码和半弱密码的存在
SylverQG commented 1 year ago

四、公钥密码

4.1 数学基础

  1. 代数系统 代数系统是对要研究的现象或过程建立起的一种数学模型，模型中包括要处理的数学对象的集合以及集合上的关系或运算 运算可以三一元的也可以三多元的，可以有一个也可以有多个

  2. 封闭性 设 $\ast $是集合S上的运算，若对 $\forall a,b \in S $, $a\ast b \in S $, 则称S对运算 $\ast$是封闭的 若 $\ast$是一元运算，若对 $\forall a \in S $, $\ast b \in S $, 则称S对运算 $\ast $是封闭的

  3. 结合律 若对 $\ast a,b,c \in S,有 (a \ast b)\ast c = a\ast (b\ast c),$则称 $\ast $满足结合律

  4. 半群

    1. 设 $\lt G,\ast \gt $是一个代数系统， $\ast $满足：
      1. 封闭性
      2. 结合律
    2. 则称 $\lt G,\ast\gt $是半群

  5. 群 设 $\lt G,\ast\gt $是一个代数系统， $\ast $满足：

    1. 封闭性
    2. 结合律
    3. 存在元素e，对 $\forall a\in G,$有 $a \ast e = e\ast a = a$。 $[e称为\lt G,\ast\gt 的单位元]$
    4. 对 $\forall a\in G,\exists元素a^{-1} $使得 $a\ast a^{-1} = a^{-1} \ast a = e $。 $[称为a^{-1}为元素a的逆元]$

    则称 $\lt G,\ast\gt $是群

  6. 有限域&无限域 如果G是有限集合，则称 $\lt G,\ast\gt $是有限群，否则三无限群。有限群中， $G $的元素个数称为群的阶数

  7. Abel(交换群) 如果群 $\lt G, \ast>$中的运算 $\ast $还满足交换律，即对 $\forall a,b \in G, 有 a \ast b = b\ast a$,称 $\lt G, \ast\gt $为Abel群或交换群

  8. 群中运算 $\ast$一般为乘法，称该群为乘法群 若运算 $\ast $改为 +，则成为加法群。此时逆元 $a^{-1}写成-a$

  9. 循环群 设 $\lt G,\ast\gt $是一个群，I是整数集合。如果存在一个元素 $g\in G$,对于每一个元素 $a\in G$,都有一个相应的 $i\in I$, $能把a表示成g^i$,则称 $\lt G,\ast\gt $,是循环群，g称为循环群的生成元。

  10. 环 若代数系统 $\lt R,+,\ast>$的二元运算 $+和\ast$满足：

    1. $\lt R,+>$是Abel群
    2. $\lt R,\ast>$是半群

    3. 乘法 $\ast$在加法 $+$上可分配，即： 对 $\forall a,b,c \in R,有a\ast (b+c)=a\ast b + a\ast c 和(b+c)\ast a=b\ast a+c\ast a$

      则称 $\lt R,+,\ast\gt 是环$

  11. 域 若代数系统 $\lt F,+,\ast\gt $的二元运算 $+和\ast 满足$:

    1. $\lt F,+>$是Abel群
    2. $\lt F-{0},\ast\gt $是Abel群，其中0是+的单位元

    3. 乘法 $\ast $在加法+上分配，即： 对 $\forall a,b,c \in R,有a\ast (b+c)=a\ast b + a\ast c 和(b+c)\ast a=b\ast a+c\ast a$

      则称 $\lt F,+,\ast\gt $是域

  12. 有限域 有限域是指域中元素个数有限的域，元素个数成为域的阶

  13. Galois域 若q是素数的幂，即 $q=p^r$，其中p是素数，r是自然数，则阶为q的域称为Galois域，记为GF(q)或是Fq

  14. 同余，同余类 如果 $(a\ mod\ n)=(b\ mod\ n)$，则称两整数a和b模n同余，记为 $a\equiv b\ mod\ n$。称与a模n同余的数的全体为a的同余类，记为 $\lceil a\rceil$，称a为这个同余类的表示元素

  15. 费马定理[Fermat定理] 若P是素数，a是正整数且 $gcd(a,p)=1,则a^{p-1}\equiv 1\ mod\ p$ Fermat定理也可以写成如下形式： 设p是素数，a是任意正整数， $a^p\equiv a\ mod\ p$

  16. 欧拉函数 设n是一正整数，小于n且与n互素的正整数的个数成为n的欧拉函数，记为 $\phi (n)$若n是素数，则显然 $\phi (n)=n-1$

  17. 欧拉定理(Euler) 若a和n互素，则 $a^{\phi (n)}\equiv 1\ mod\ n$

  18. 欧几里德算法(Euclid)

    1. 求最大公因子：Euclid算法是基于下面的一个基本结论 
      对任意的非负整数a和正整数b，有gcd(a,b)=gcd(b,a\ mod\ b)
    2. 求乘法的逆元：如果gcd(a,b)=1,则b在moda下有乘法逆元(不妨设 $b< a$),即存在一个 $x(x< a)$,使得 $b x \equiv (1\ mod\ a) $，推广的Eucild算法先求出gcd(a,b),当gcd(a,b)=1时，则返回b的逆元
SylverQG commented 1 year ago

4.2 公钥密码体制

  1. 特点

    1. 公钥密码算法最大的特点就是采用两个相关的密钥将加解密分开，其中一个密钥是公开的，称为公钥，用于加密；另一个密钥是为用户专用，因而保密，称为密钥，用来解密。因此公钥密码体制也称之为双钥密码体制。
    2. 算法有以下特性：已知密码算法和加密密钥，求解密密钥在计算上的不可行的

  2. 公钥体制加密 PKc1

  3. 公钥密码体制认证 PKc2

  4. 公钥密码体制认证、保密 PKc3

  5. 公钥密码算法应该满足的要求

    1. 接收方B产生密钥对(公钥PKB和密钥SKB)在计算上是容易的
    2. 发送方A用接收方的公开密钥对消息m加密以产生密文c，即 $c=E_{PKB}(m)$，在计算上是容易的
    3. 接收方B用自己的密钥对c解密，即 $m=D_{SKB}(c)在计算上是容易的$
    4. 敌手由B的公钥PKB求解密钥SKB在计算上是不可行的
    5. 敌手由密文c和接收方B的公钥PKB恢复明文m，在计算上是不可行的
    6. 加密、解密次序可以调换，即 $E{PKB}[D{SKB}(m)]=D{SKB}[E{PKB}(m)]$
    7. 以上要求的本质在于要求一个单向陷门函数

  6. 对公钥密码体制的攻击

    1. 和单钥密码体制一样，如果密钥太短，公钥密码体制也容易受到穷举搜索攻击。因此密钥必须足够长才能抵抗穷举搜索攻击。然而又由于公钥密码体制所使用的可逆函数的计算复杂性与密钥长度常常不是线性关系，而是增大得更快。
    2. 公钥密码体制目前主要用于密钥管理和数字签名
    3. 对公钥密码算法的第二种攻击是寻找从公钥计算密钥的方法。目前为止，常用公钥算法还未能够证明这种攻击是不可行的
    4. 还有一种仅适用于对公钥密码的攻击方法，称为可能字攻击。因此不管公钥密码算法的密钥多长，这种攻击的本质是对56比特的DES密钥的穷举搜索攻击。抵抗方法是在欲发送的明文消息后添加一些随机比特。

4.3 RSA

  1. 公钥密码体制
    1. 为解决两个问题：密钥的分配，数字签名
    2. 对公钥密码体制的攻击
      1. 穷举法
      2. 根据公钥计算私钥
  2. RSA算法
    1. 原理
      1. 选取两个大素数p和q(保密)
      2. 计算 $n=p\ q(公开)，\phi (n)=(p-1)(q-1)（保密）$
      3. 随机选取正整数 $e,1\lt e\lt \phi (n)$, $满足gcd(e,\phi (n))=1,e$是公开加密的密钥
      4. 计算d，满足 $ed\equiv 1(mod\ \phi (n)), d$是保密的解密密钥
      5. 加密变换：对明文 $m \in Z_{n},密文为c= m^e \ mod\ n$
      6. 解密变换：对密文 $c \in Z_{n},明文为m= c^d \ mod\ n$
    2. $p和q$选择的限制
      1. $p和q$的长度应该差不多
      2. $p-1和q-1$ 都应该包含大的因素子
      3. $gcd(p-1, q-1)$应该很小
  3. 大素数生成
    1. 素数分布定理：
      1. 设 $x\gt 0,\pi (x)的素数的个数， 则\lim\limits_{x\rightarrow \infty } \frac{\pi (x)ln x}{x}=1$ 【注：素数的分布极不均匀，素数越大，分布越稀疏】
    2. Legendra符号
      1. 设 $p\gt 2$是一个素数，对任意整数 $a \ge 0$
      2. (\frac{a}{p})=
\begin{cases}
0,if\ a\equiv 0(mod p)\\
1, if\ a是模p的平方剩余\\
-1, if\ a是模p的非平方剩余\\
\end{cases}
    3. Jacobi
      1. 当m是奇素数时，jacobi符号就是Legedra符号
      2. 当m是奇素数，且 $(\frac{a}{m})=1$时，方程 $x^2 = a(mod\ m)$有解。当m不是奇素数时，结论不一定成立
    4. 模n的大数幂乘的快速算法
    5. Solovay-Strassen素性测试 测试的主要依据：设 $p\gt 2$是一个素数，则对于任意整数 $a\ge 0 ,(\frac{a}{p})\equiv a^{(p-1)/2}(mod\ p)$

五、密钥分类与密钥管理

5.1 加密体制的密钥分配

  1. 任何密码系统的强度都与密钥分配到方法有关

  2. 密钥分配方法：指将密钥发放给希望交换数据的双方而不让别人知道的方法

  3. A、B双方通信的密钥分配方法：

    1. 密钥由A选择，亲自交与B
    2. 第三方选择密钥后亲自交与A和B
    3. 一方用双方已有的密钥加密一个新密钥后发给另一方
    4. A和B与第三方C均有秘密通道，则C可以将密钥分别发送给A和B

  4. 对分配方法的分析

    1. 方法1和2需要人工传递密钥，对链路加密要求不过分，对端对端加密有些笨拙
    2. 方法3可用于链路加密和端到端加密。但攻击者若已成功获取一个密钥，随后密钥都会泄漏
    3. 对于端到端加密，方法4稍微变动即可应用，但需要一个密钥分配中心参与

  5. 密钥分类

    1. 会话密钥(Ks)：末端通信时使用的临时加密密钥
    2. 主密钥(Km)：加密Ks的密钥

  6. 密钥分发的具体步骤 KDCab1

  7. 会话密钥的生命周期

    1. 在安全性域通信时间之间折中考虑
    2. 对面向连接的协议，改变连接时，改用新的Ks
    3. 对非面向连接的协议，定期更改

  8. 会话密钥的类型

    1. 数据加密密钥，用于网络中的通用通信
    2. PIN加密密钥，用于电子资金转账和销售点应用的个人识别码
    3. 文件加密密钥，用于可公开访问的加密文件

  9. 密钥标志

    1. 标志含在密钥中，密钥分配时就被加密
    2. 一位表示主密钥或会话密钥
    3. 一位表示可否用于加密
    4. 一位表示可否用于解密
    5. 其余位未用
    6. 缺点：
      1. 位数少，限制了其灵活性和功能
      2. 标志不能以明文传输，解密后才能使用，限制对密钥的管理

  10. 会话密钥的类型保留私钥配发中心(KDC)

    1. 每个用会与KDC共享一个主密钥
    2. 用主密钥分配会话密钥
    3. 公钥用于分配主密钥
    4. 在大部分分散用户的情况下尤其有用
    5. 三层结构
      1. 公钥
      2. 主密钥
      3. 会话密钥

  11. 基本原理

    1. 性能：公钥加密慢，但仅用于偶尔更新用户和KDC之间的主密钥
    2. 向后兼容性：容易覆盖存在很小的破坏或者软件更新的KDC方案

  12. 可用的公钥分配方法

    1. 公开发布
    2. 公开可访问目录
    3. 公钥授权
    4. 公钥证书

  13. 通过更加严格地控制目录中的公钥分配，是公钥分配更加安全

    1. 具有目录特性
    2. 每一通信方必须知道目录管理员的公钥
    3. 用户和目录管理员进行交互以安全地获得所希望的公钥
      1. 当需要密钥时，确实需要能够实时访问目录
      2. 公钥目录管理员成为系统的瓶颈

  14. Diffie-Hellman密钥交换 DHkeyex

  15. 秘密分割

    1. 秘密分给多人掌管，必须有一定数目的掌管秘密的人同时到场才能恢复着一秘密
    2. (k,n)-秘密分割门陷方案，k称为方案的门陷值 设秘密s被分成n个部分信息，每一部分信息称为一个子密钥或影子，由一个参与者持有，使得
      1. 由k个或多于k个参与者所持有的部分信息可以重构s
      2. 由少于k个参与者所持有的部分信息则无法重构s
      3. 由少于k个参与者所持有的部分信息得不到秘密s的任何信息

  16. Shamir门陷方案 例： 设 $k=3,n=5,q=19,s=11$,随机选取 $a_1 = 2, a_2 = 7$,得多项式为 $$f(x)=(7x^2 +2x+11)\pmod{19}$$ 分别计算 $$f(1)=(7+2+11)\pmod{19}=20\pmod{19}=1$$ $$f(2)=(28+4+11)\pmod{19}=43\pmod{19}=5$$ $$f(3)=(63+6+11)\pmod{19}=80\pmod{19}=4$$ $$f(4)=(112+8+11)\pmod{19}=131\pmod{19}=17$$ $$f(5)=(175+10+11)\pmod{19}=196\pmod{19}=6$$ 如果知道其中的3个子密钥 $f(2)=5, f(3)=4, f(5)=6,$就可按照以下方式重构 $f(x):$

    \begin{aligned}
5\frac{(x-3)(x-5)}{(2-3)(2-5)}
&=5\frac{(x-3)(x-5)}{(-1)(-3)}=5\frac{(x-3)(x-5)}{3}\\
&=5\cdot (3^{-1}\pmod{19})\cdot (x-3)(x-5)\\
&=5\cdot 13\cdot (x-3)(x-5)=65(x-3)(x-5)\\
4\frac{(x-2)(x-5)}{(3-2)(3-5)}
&=4\frac{(x-2)(x-5)}{(1)(-2)}=5\frac{(x-2)(x-5)}{-2}\\
&=4\cdot ((-2)^{-1}\pmod{19})\cdot (x-2)(x-5)\\
&=4\cdot 9\cdot (x-2)(x-5)=36(x-2)(x-5)\\
4\frac{(x-2)(x-3)}{(5-2)(5-3)}
&=6\frac{(x-2)(x-3)}{(3)(2)}=6\frac{(x-2)(x-3)}{6}\\
&=6\cdot (6^{-1}\pmod{19})\cdot (x-2)(x-3)\\
&=6\cdot 16\cdot (x-2)(x-3)=36(x-2)(x-3)\\
\end{aligned}

    所以

    \begin{aligned}
f(x)&=[65(x-3)(x-5)+36(x-2)(x-5)+96(x-2)(x-3)]\pmod{19}\\
&=[8(x-3)(x-5)+17(x-2)(x-5)+(x-2)(x-3)]\pmod{19}\\
&=(26x^2 -188x+296)\pmod{19}\\
&=7x^2 +2x +11
\end{aligned}

    从而得秘密为 $s=11$

  17. 基于中国剩余定理的门限方案 例： 设 $k=3,n=5,m_1=97,m_2=98,m_3=99,m_4=101,m_5=103,$ 秘密数据 $s=671875, $满足 $10403=m_3 m_4 \lt s\lt m_1 m_2 m_3 = 941094$ 计算 $M=m_1 m_2 m_3 m_4 m_5=9790200882, s_i \equiv \pmod{m_i}(i=1,…,5)$ 得 $s_1 = 53,s_2 = 85, s_3 = 61, s_4 = 23, s_5 = 6$。5个子密钥 $(53,97,9790200882), (85, 98, 9790200882), (61, 99,9790200882), (23, 101, 9790200882), (6, 103, 9790200882)$ 现在假定 $i_1 、i_2 、i_3 联合起来计算s, 分别计算：$

    \begin{cases}
M_1 = \frac{M}{m_1}=100929906\\
N_1 \equiv M_{1}^{-1}\pmod{m_1}\equiv 95 
\end{cases}
\begin{cases}
M_2 = \frac{M}{m_2}=99900009\\
N_2 \equiv M_{2}^{-1}\pmod{m_2}\equiv 13 
\end{cases}
\begin{cases}
M_3 = \frac{M}{m_3}=98890918\\
N_3 \equiv M_{3}^{-1}\pmod{m_1}\equiv 31 
\end{cases}

    得到

    \begin{aligned}
s &\equiv s_1 M_1 N_1 + s_2 M_2 N_2 + s_3 M_3 N_3 \pmod{m_1 m_2 m_3}\\
&\equiv 53 \cdot 100929906 \cdot 95 + 85 \cdot 99900009 \cdot 13 + 61 \cdot 98890918 \cdot 31 \pmod{97\cdot 98\cdot 99}\\
&\equiv 805574312593 \pmod{941094}\\
&\equiv 671875
\end{aligned}

    假定 $i_1 、 i_4$联合起来计算 $ s$ ,分别计算：

    \begin{cases}
M_1 = \frac{M}{m_1}=100929906\\
N_1 \equiv M_{1}^{-1}\pmod{m_1}\equiv 95 
\end{cases}
\begin{cases}
M_4 = \frac{M}{m_4}=96932682\\
N_4 \equiv M_{4}^{-1}\pmod{m_4}\equiv 61 
\end{cases}
\begin{cases}
M_5 = \frac{M}{m_5}=95050494\\
N_5 \equiv M_{5}^{-1}\pmod{m_5}\equiv 100 
\end{cases}

    得到

\begin{aligned}
s &\equiv s_1 M_1 N_1 + s_4 M_4 N_4 + s_5 M_5 N_5 \pmod{m_1 m_4 m_5}\\
&\equiv 53 \cdot 100929906 \cdot 95 + 23 \cdot 96932682 \cdot 61 + 6 \cdot 95050494 \cdot 100 \pmod{97\cdot 101\cdot 103}\\
&\equiv 701208925956 \pmod{1009091}\\
&\equiv 671875\\
\end{aligned}

假定 $i_1 i_4$ 联合起来计算 $s$,则

\begin{aligned}
s &\equiv s_1 M_1 N_1 + s_4 M_4 N_4 \pmod{m_1 m_4}\\
&\equiv 53 \cdot 100929906 \cdot 95 + 23 \cdot 96932682 \cdot 61 \pmod{97\cdot 101}\\
&\equiv 644178629556 \pmod{9791}\\
&\equiv 5679
\end{aligned}

得到一个不正确结果

SylverQG commented 1 year ago

六、消息认证和哈希函数

  1. 作用：保证数据的完整性和认证性（主要用于鉴别）
  2. 定义：Hash 函数常用来构造数据的短“指纹”：消息的发送者使用所有的消息产生一个附件也就是短“指纹”，并将该短“短指纹”与消息一起传输给接收者。【即使在数据存储不安全的地方，接收者重新计算数据的指纹，并验证指纹是否改变，就能够监测数据的完整性。这是因为一旦数据在中途被破坏，或改变，短指纹就不在正确】
  3. Hash 函数的性质：
    1. 单向性：给定一个 Hash值 $y$，如果寻找一个消息 $x$，使得 $y=h(x)$是计算上不可行的，则称$h$是单向Hash 函数
    2. 弱抗碰撞性：给定一个消息 $x$，如果寻找另一个不同的消息 $x'$, 使得 $h(x)=h(x')$是计算上不可行的，则称 $h$ 是弱抗碰撞哈桑Hash函数
    3. 强抗碰撞性：如果寻找两个不同的消息 $x和x'$，使得 $h(x)=h(x')$是计算上不可行的,则称 $h$ 是强抗碰撞哈桑Hash函数
  4. Hash函数的攻击方法
    1. 穷举攻击：典型的生日攻击
    2. 利用散列函数的代数结构：攻击其函数的弱性质。通常的有中间相遇攻击、修正分组攻击和差分分析攻击
  5. 基于分组密码的Hash函数
    1. 基于分组密码的CBC工作模式： $y_i = E_k(xi \oplus y{i-1})$
    2. 基于分组密码的CFC工作模式： $y_i = x_i \oplus Ek ( y{i-1})$
  6. MD4
    1. 步骤：MD4算法的输入可以是任意长度消息x，对输入消息按512位的分组为单位进行处理，输出128位的散列值MD(x)。整个算法分为六个步骤：
      1. 消息的预处理。设x是一个消息，用二进制表示。首先由x生成一个数组 $M=M[0]M[1]…M[N-1]$。 $M[i]$是长度为32比特(bit)的(0,1)序列， $0 \le i \le N-1$, M 由 x 生成：
        1. $ d=(447-|x|)\pmod {512}$
        2. 另 $l为|x|\pmod 2^{64}$的二进制表示。l的长度为64比特(bit)。如果l的长度不足64比特(bit),则在l的左端添0补足
        3. $M=x||1||0^d||l$
      2. 增加填充位
      3. 附加消息长度值：填充方法是把64比特的长度分成两个32比特的字，低32比特字先填充，高32比特字后提提填充
      4. 初始化MD缓冲区
      5. 以512位的分组(16个字)为单位处理消息
      6. 输出
    2. 算法描述
      1. 设A，B，C，D是四个32的寄存器，其初值(用十六进制表示)分别为A=67452301，B=efcdab89，C=98badcfe，D=10325476：
      2. 对i=0至 N/16-1执行第3步至第8步
      3. 对j=0至15执行 $X[j]=M[16i+j]$
      4. 将寄存器A，B，C，D中的值存储到另外四个寄存器AA，BB，CC，DD中，AA=A，BB=B，CC=C，DD=D
      5. 执行第一步
      6. 执行第二步
      7. 执行第三步
      8. A=A+AA，B=B+BB，C=C+CC，D=D+DD
  7. MD5和SHA1的主要特点
    1. MD5的主要特点：
      1. 输入：最大长度为小于 $2^64$位（ $2^64 -1$位 ）的消息 $\longrightarrow$ 输出：128位消息摘要
      2. 处理：输入消息以512比特的分组为单位处理
    2. MD5的主要特点：
      1. 输入：最大长度为小于 $2^64$位（ $2^64 -1$位 ）的消息 $\longrightarrow$ 输出：160位消息摘要
      2. 处理：输入消息以512比特的分组为单位处理
  8. 消息认证的目的
    1. 验证消息的真实性（身份认证），验证消息的来源是真实的而不是冒充的
    2. 验证消息的完整性（消息认证），检查消息在传送或存储过程中是否被修改
  9. 认证函数的三种实现方法
    1. 基于消息加密的认证
    2. 基于消息认证码(MAC)的认证
    3. 基于哈希函数的认证
SylverQG commented 1 year ago

七、数字签名和认证协议

  1. 数字签名的特性：可信的、不可伪造的、不可复制的、不可改变的、不可抵赖的
  2. 基于公钥密码的数字签名，RSA数字签名描述如下：
    1. 秘密的选取两大素数p和q
    2. 计算 $n=pq, \phi (n)=(p-1)(q-1)$, n公开， $\phi(n)$保密
    3. 随机选取正整数 $1\lt e\lt \phi(n)$，满足 $gcd(e,\phi (n))=1，e$是公开的密钥
    4. 计算d, 满足 $ed \equiv1\pmod{\phi(n)}$,d是保密密钥
    5. 签名变换：对于消息 $m\in Z_n ，$则签名为 $Sig(m)=m^d \pmod{n}$
    6. 签名验证：对于m， $s\in Z_n , $如果 $m=s^e \pmod{n}$，则确认s为消息m的有效签名
  3. 认证类别
    1. 实体认证（entity Authentication）：验证信息的发送者是真的、而不是冒充的，包括信源、信宿等的认证和识别
    2. 数据源认证（DataoriginAuthentication）：也称之为消息认证(message authentication)，验证数据在传送或存储过程中未被窜改、重放或延迟等
  4. 数学签名要解决的问题 A发送消息给B：A(不可抵赖) $\longrightarrow$ B(不可伪造)(不可重用)
    1. 不可抵赖（假如：A可以否认发过该消息，B无法证明A确实发了该消息）
    2. 不可伪造（假如：B伪造一个不同的消息，但声称是从A收到的）
    3. 不可重用（假如：签名没有和消息绑定）
  5. 数字签名的安全模型、性质
  6. RSA签名算法以及存在的安全问题
    1. 签名
      1. 利用一个安全的hash函数h产生消息摘要 $h(m)$
      2. 计算签名 $s=sign_k(m)=h(m)^d \pmod{n}$
    2. 验证
      1. 接收者使用相同的hash函数h计算消息摘要h(m)
      2. 接收者验证 $h(m)\pmod{n} = s^e \pmod{n}$是否成立。若成立，则签名有效，否则签名无效
    3. RSA签名举例
      1. 初始化 假设A选取 $p=13, q=11, e=13, $ 则有 $n=pq=143, \phi (n)=(p-1)(q-1)=12\times 10 = 120。求解 ed=13d\equiv 1 \pmod{120} 得d = 37$
      2. 签名过程 假定消息 $m的Hash值h(m)=16，则计算m签名s\equiv h(m)^d \pmod{n}\equiv {16}^{37}\pmod{143}=3$
      3. 验证过程 接收者B收到签名后，计算 $s^e \pmod{n}\equiv 3^{13} \pmod{143}= 16，h(m)^d \pmod{n}\equiv 16 \pmod{143}=16$，等式 $h(m)\pmod{n}\equiv s^e \pmod{n}$成立，因此，B验证此签名有效
    4. 如果不使用Hash函数
      1. （存在性伪造）使用“已知消息攻击” 假设 $y_1 = sig_k (m_1)和y_2 = sig_k (m_2) $是签名者曾经签署的有效签名，那么 ${ver}_k (m_1 m_2 \pmod{n}), y_1 y_2 \pmod{n}= true$
      2. （选择性伪造）使用“选择消息攻击” 假设攻击者要对消息 $m$ 伪造一个签名， $m = m1 m2\pmod{n}$。假设攻击者能请求签名者为 m1 和 m2 签名（结果分别为 $y_1 和 y_2$ ），那么，y_1 y_2 mod n就是消息 m 的有效签名。对抗攻击的方法：使用Hash函数
    5. 使用Hash函数
      1. 去掉这类伪造的一个方法是使消息包含足够的多余度，使伪造的消息m只有很小的概率对应“有意义”的消息
      2. 因此，将签名方案和散列函数一起使用，可以排除这种伪造方法
SylverQG commented 1 year ago

八、密码协议 和 九、可证明安全

  1. 密码分配

    1. 定义：通信双方中的一方选取一个秘密密钥，然后传送给另一方
    2. Kerboros密钥分配协议：
      1. Kerboros密钥分配协议是一种在线式密钥分配协议(on-line key distribution protocol)。所谓在线(on-line)指的是，当两个用户U和V想要进行保密通信时，就根据协议产生一个新的钥匙，而不是实现确定一个密钥。 
        \begin{align}
TA \xrightarrow{E_{K_{U}}(K, ID(V), T, L)} U \\
TA \xrightarrow{E_{K_{V}}(K, ID(U), T, L)} U \xrightarrow{E_{K_{V}}(K, ID(U), T, L)}V \\
U \xrightarrow{E_{K}(ID(U), T)} V \\
V \xrightarrow{E_{K}(T+1)} U \\
\end{align}

  2. 密码协商

    1. 定义：通信双方可以在一个公开信道上通过相互传送一些消息来共同建立一个共享的秘密密钥。协商中，双方共同建立的秘密密钥通常双方输入消息的一个函数
    2. Diffie-Hellman
      1. 设p是一个大素数， $a\in Z_p$是一个本原元，p和a公开
      2. 用户U随机选取 $a_U, 1 \le a_U \le p-2$
      3. 用户U计算 $\alpha ^{a_U} \pmod{p}$,并将结果传送给用户V
      4. 用户V随机选取 $a_V, 1 \le a_V \le p-2$
      5. 用户V计算 $\alpha \pmod{p}$, 并将结果传送给用户U
      6. 用户U计算 $k={{\alpha}^{a_V}}^{a_U} \pmod{p}$
      7. 用户V计算 $k={{\alpha}^{a_U}}^{a_V} \pmod{p}$
    3. 此协议易受到中间人攻击
    4. 端对端协议 
      \begin{aligned}
(Alice) \xrightarrow{1.\ X=g^{X_A}\pmod{p}}(Bob)\\
(Bob) \xrightarrow{2.\ Y=g^{X_B}\pmod{p_i}E_k (S_B (g^{X_B}, g^{X_A}))} (Alice)\\
(Alice)\xrightarrow{E_k (S_A (g^{X_A}, g^{X_B})) } (Bob)\\
\\
(Alice)[k=Y^{X_A}\pmod{p}=g^{X_A X_B \pmod{p}}]\\
(Bob)[k=X^{X_B}\pmod{p}=g^{X_A X_B \pmod{p}}]
\end{aligned}

      可实现：

      • 相互实体认证
      • 显式密钥认证
      • 密钥协商

  3. 身份识别 Guillou-Quisquater身份识别方案

    sequenceDiagram
participant Alice
participant John

note left of Alice: s:Alice公钥,v:Alice私钥,r:随机数
note over Alice: 1. x=r^e mod n
Alice->>John: 2. 证据 x
John->>Alice: 3. 挑战 c
note over Alice : 4.y=r s^c mod n
Alice->>John: 4. 应答 y
opt 
  note over Jonh: 5. 判断 x 与y^x v^c是否相等-->是:有可能，否:不可能
end