李卫海PPT学习笔记

其他概念

Needham-Schroeder协议：

利用对称密码技术分发密钥。A，B分别与T有静态密钥。借助信任权威T，分发对称密钥Kab

多项式GCD算法

重点：模重复平方算法

1
2
3
4
5
6
c=1
for i =k-1 to 0:
    c=(c^2)mod n
    if ei==1:
        c=c*m mod n
     return

难点：AES列混合矩阵计算，有限域上的多项式模运算。

对合算法

对合运算:f =f‘ ，模 2加运算是对合运算。
密码算法是对和运算，则加密算法=解密算法，工程实现工
作量减半。

同态加密（英语：Homomorphic encryption）是一种加密形式，它允许人们对密文进行特定形式的代数运算得到仍然是加密的结果，将其解密所得到的结果与对明文进行同样的运算结果一样。换言之，这项技术令人们可以在加密的数据中进行诸如检索、比较等操作，得出正确的结果，而在整个处理过程中无需对数据进行解密。其意义在于，真正从根本上解决将数据及其操作委托给第三方时的保密问题，例如对于各种云计算的应用。

零知识证明是一种特殊的交互式证明，其中证明者知道问题的答案，他需要向验证者证明“他知道答案”这一事实，但是要求验证者不能获得答案的任何信息。

可以参考这样一个简单的例子。证明者和验证者都拿到了一个数独的题目，证明者知道一个解法，他可以采取如下这种零知识证明方法：他找出81张纸片，每一张纸片上写上1到9的一个数字，使得正好有9份写有从1到9的纸片。然后因为他知道答案，他可以把所有的纸片按照解法放在一个9乘9的方格内，使得满足数独的题目要求（每列、每行、每个九宫格都正好有1到9）。放好之后他把所有的纸片翻转，让没有字的一面朝上。这样验证者没办法看到纸片上的数字。接下来，验证者就验证数独的条件是否满足。比如他选一列，这时证明者就把这一列的纸片收集起来，把顺序任意打乱，然后把纸片翻过来，让验证者看到1到9的纸片都出现了。整个过程中验证者都无法得知每张纸片的位置，但是却能验证确实是1到9都出现了。

字频统计攻击

对凯撒密码，通过识别a-e-i或r-s-t三元组的峰，或jk和xyz的特征，可以获得密钥

对单表替换密码，破译步骤：

  • 统计密文字母出现频率
  • 将统计结果与自然语言频率表对比，确定部分密钥
  • 结合连接特征和重复特征，确定部分密钥
  • 双、三字母的频率统计表往往很有帮助
  • 从语义上，猜测其它密钥

已知明文攻击（Known plaintext attack）是一种攻击模式，指攻击者掌握了某段明文 x 和对应密文 y。

在所有密码分析中，均假设攻击者知道正在使用的密码体制，该假设称为科克霍夫假设。而已知明文攻击也假设攻击者能够获取部分明文和相应密文，如截取信息前段，通过该类型攻击获取加密方式，从而便于破解后段密文。

希尔密码依赖唯密文攻击较难破解，而通过已知明文攻击则容易攻破。

**选择明文攻击 **在这种攻击模式中，攻击者可以事先任意选择一定数量的明文，让被攻击的加密算法加密，并得到相应的密文。攻击者的目标是通过这一过程获得关于加密算法的一些信息，以利于攻击者在将来更有效的破解由同样加密算法（以及相关密钥）加密的信息。在最坏情况下，攻击者可以直接获得解密用的钥匙。

这种攻击模式初看起来并不现实，因为很难想像攻击者可以选择任意的信息并要求加密系统进行加密。不过，在公钥密码学中，这就是一个很现实的模式。这是因为公钥密码方案中，加密用的钥匙是公开的，这样攻击者就可以直接用它来加密任意的信息。

选择密文攻击 在密码分析中，选择密文攻击指的是一种攻击方式。攻击者掌握对解密机的访问权限，可构造任意密文所对应的明文x。在此种攻击模型中，密码分析者事先任意搜集一定数量的密文，让这些密文透过被攻击的加密算法解密，透过未知的密钥获得解密后的明文。

唯密文攻击指的是在仅知已加密文字（即密文）的情况下进行攻击。此方案可同时用于攻击对称密码体制和非对称密码体制。
唯密文攻击所希望达到的目的包括几种，依照成功的程度排列：

取得原始明文中的部分资讯。
取得原始明文。
得知解密用的钥匙。
穷举法是属于一种唯密文攻击，但一般在设计算法时都会考虑到穷举法。

一次性密码本（英语：one-time pad，缩写为OTP）是古典密码学中的一种加密算法。是以随机的密钥（key）组成明文，且只使用一次。

在理论上，此种密码具有完善保密性，是牢不可破的。它的安全性已由·香农所证明。

虽然它在理论上的安全性无庸置疑，但在实际操作上却有着以下的问题：

用以加密的文本，也就是一次性密码本，必须确实是随机产生的。
它至少必须和被加密的文件等长。
用以加密的文本只能用一次，且必须对非关系人小心保密，不再使用时，用以加密的文本应当要销毁，以防重复使用。

生日攻击 生日攻击是一种密码学攻击手段，所利用的是概率论中生日问题的数学原理。这种攻击手段可用于滥用两个或多个集团之间的通信。此攻击依赖于在随机攻击中的高碰撞概率和固定置换次数（鸽巢原理）。攻击者可在

image-20210713213656807

中找到散列函数碰撞，2^n 为原像抗性安全性。

重合指数法：所有字母出现概率的平方的和接近0.065，这个值称为重合指数。

数据扩散：改变明文的任何一位，密文通常有一半的位数发生变化。

数据混淆：改变密钥的任何一位，密文通常有一半的位数发生变化。

所谓扩散就是让明文中的每一位影响密文中的许多位，或者说让密文中的每一位受明文中的许多位的影响．这样可以隐蔽明文的统计特性．当然，理想的情况是让明文中的每一位影响密文中的所有位，或者说让密文中的每一位受明文中所有位的影响．
所谓混淆就是将密文与密钥之间的统计关系变得尽可能复杂，使得对手即使获取了关于密文的一些统计特性，也无法推测密钥．使用复杂的非线性代替变换可以达到比较好的混淆效果，而简单的线性代替变换得到的混淆效果则不理想．

仿射密码

image-20210919212715548

代换密码要先建立一个替换表（即密钥），加密时将需要加密的明文依次通过查表，替换为相应的字符，明文字符被逐个替换后，生成无任何意义的字符串，即密文。
置换密码是对明文字符按某种规律进行位置的置换。

中间人攻击

SP网络（代换-置换网络）

Substitution-Permutation Network，缩写作SP-network或SPN

S一般被称为混淆层，主要起混淆作用
P一般被称为扩散层，主要起扩散作用

代换起混淆作用，置换起扩散作用

DES

面向二进制数据的密码算法
因而能够加解密任何形式的计算机数据。

S盒起混淆作用

改变S盒的任一输入比特，其输出至少有两比特发生改变

置换运算P起扩散作用

image-20211110215431361 image-20211110215415819

弱点

image-20211110215618739

AES

面向二进制的密码算法
能够加解密任何形式的计算机数据。
不是对合运算，加解密使用不同的算法

最后一轮的轮变换中没有列混合变换。

image-20211114232150250

密钥备份和恢复只能针对加解密密钥，无法对签名密钥进行备份。

第一章-绪论

密码体制的基本要素：

  • 密码算法
  • 密钥

密码系统的数学描述：

S={P,C,K,E,D} 其中，明文空间P也常用消息空间M

image-20210713213509244

现代密码学基本原则：

  • 柯克霍夫原则（Kerckhoff’s principle）
    除了密钥之外，即使密码系统的一切均被公开，它仍然应当是安全的。
  • 香农箴言（Shannon’s maxim）
    敌人了解系统。
  • 密码系统的安全性不在于算法的保密，而在于当对手获知了算法和密文后，分析出密钥或明文的难度。

密码提之的安全性：

  • 无条件安全
  • 可证明安全
  • 计算上安全
  • 实际安全

通信信道加密方式：

  • 链路加密–点到点加密
  • 高层链接加密–端到端加密

存储数据的加密：

  • 硬盘级加密
  • 文件级加密

攻击方法

攻击类型 密码分析员的资源
唯密文攻击 Ciphtext-only 密码算法 待分析密文
已知明文攻击 Known-plaintext 密码算法 待分析密文 用同一密钥加密的一个或多个明文－密文对
选择密文攻击 Chosen-ciphertext 密码算法 待分析密文 可选择特定密文，并获得对应的明文
选择明文攻击 Chosen-plaintext 密码算法 待分析密文 可选择特定明文，并获得对应的密文
选择文本攻击 Chosen-text 密码算法 待分析密文 可选择特定密文/明文，并获得对应的明文/密文
相关密钥攻击 Related-key 密码算法 待分析密文 有确定关系的两个密钥对应的明文-密文对

序列密码体制 / 流密码体制（Stream Cipher）

  • 以比特（有时也用字节）为单位进行加密/解密运算
  • 同一明文对应的密文一般不同

分组密码体制（Block Cipher）

  • 以若干比特（通常大于64比特）的数据块为处理单元
  • 同一明文块对应的密文块相同

根据密文的唯一性分类：

  • 确定型密码体制
  • 概率型密码体制

明文：Plaintext,Message

密文：Ciphertext

目前，衡量一个密码系统是否安全的一个通用的做法是：公开接受来自全世界的研究和攻击。

第二章-经典密码学

代换（Substitution）
明文内容的表示形式改变，内容元素之间相对位置不变
明文字母用密文中对应字母代替

置换（Transposition or Permutation）
明文内容元素的相对位置改变，内容的表示形式不变

乘积密码（Product Ciphers）
多个加密技术的叠加

算术密码

1.移位密码

凯撒密码

将每个字母用字母表中它之后的第k个字母替代
C = E(k, p) = (p+k) mod 26， p = D(k, C) = (C-k) mod 26
一些文献中认为Caesar固定使用k=3

2.仿射密码

密钥：a,b
加密：C = E([a,b], p) = (ap+b) mod 26
解密：p = D([a,b], C) = ((C-b)/a) mod 26

a=1时，蜕化为凯撒密码。这里不考虑。
a≠0时，b无限制。
相当于b=0的仿射加密后，再叠加一次凯撒加密。
a的取值有限制：gcd(a,26)=1
a=3,5,7,9,11,15,17,19,21,23,25
否则不能保证一一映射
例：a=2, b=1时，p=3->C=7; p=16->C=7
不同的明文对应同一密文，无法解密
密钥空间大小为11*26=286

3.HILL密码

密钥：m*m个密钥

加密：每次加密m个明文字母

image-20210721220734130 image-20210721220911593

解密（要求K可逆）

image-20210721220926003

安全性：掩盖频率信息

抵抗唯密文攻击

易受已知明文攻击

代换密码

1.单表代换密码

经典密码破译：

  • 频率特征（单字母，双字母，三字母）
  • 连接特征
  • 重复特征

2.Playfair密码——二维单表代换

image-20210721223610875

加密方法：

每次加密或解密两个字母

加密规则：

  • 如果两字母是重复的，则在其中插入字母x。
    例如balloon划分为ba lx lo on
  • 如果两字母位于同一行，则各自用右侧字母代换。
    例如ar->RM
  • 如果两字母位于同一列，则各自用下侧字母代换。
    例如mu->CM
  • 否则各自用同行异列字母代换。
    例如hs->BP；ea->IM或JM

3.多表代换加密（抵抗字频统计攻击）

4.维吉尼亚密码

加密算法：Ci = E(k, pi) = (pi+ki mod d) mod 26
解密算法：pi = D(k, Ci) = (Ci-ki mod d) mod 26

攻击方法：

若获得了替换表的个数（密钥长）d，则可以逐个分析

分析位于i,i+d,i+2d,…的密文，获得密钥ki

  • 密钥：deceptive，d=9明文
  • 密文：ZICVTWQNGRZGVTWAVZHCQYGLMGJ
  • 重排列，在每一列上进行字频攻击

寻找密钥长度d

vKasiski方法

  • 在密文中寻找重复字段
  • 计算重复字段的间距
  • 密钥长度d应是这些间距的公约数

5.Autokey密码

加解密密钥＝ ”密钥” + ”明文”

置换技术

重新排序隐藏信息

乘积密码

两次代换可以构造更复杂的代换，等效为一次规则复杂的代换
两次置换可以构造更复杂的置换，等效为一次规则复杂的置换
交替使用代换和置换，可以大大提高安全性

第三章-密码学基础理论（8.4）

密码系统运算

  • 构建复杂密码
  • 分析合成密码系统

1.先验概率，后验概率

2.闭合系统，非闭合系统

同构：定义：若密码系统T的消息空间与密文空间相同，则称它是自同构的。
若密码系统T是自同构的，则可定义指数运算：

幂等：定义：若密码系统T满足TT=T，则称它是幂等的。
维吉尼亚密码是幂等的

单纯密码，混合密码

相似密码系统

信息量：H(x)

冗余，冗余度

完美安全：完美安全一般用于加密最重要的信息，或者消息集很小的场合。

消息模糊度

密钥模糊度

唯一解距离

内容：数论基础

第一节 有限域

群，环，域

有限群的阶等于群中元素的个数

有限群，交换群（阿贝尔群），

循环群：如果群中的每一个元素都是一个固定的元素a(a∈G)的幂ak(k为整数)，则称群G为循环群。
元素a生成了群G，或者说a是群G的生成元。

关系图

image-20210805204923411

模运算

a=qn + r 0≤r<n; q=⌊a/n⌋

image-20210807230847616

image-20210913223741755

image-20210917200006538

同余

整数a, b及n≠0, 当且仅当a-b=kn时，a与b是模n同余，记为 a≡b mod n

a≡b mod n当且仅当 a mod n = b mod n

如果a=mb, 其中 a,b,m 为整数，则当b≠0时，称b能整除a, b是a的一个因子，或a除以b余数为0，记为b|a

如果n|(a-b), 则a≡b mod n

加法逆元，乘法逆元

  • 加法表
  • 乘法表
  • 逆元表

模n的完全剩余类集

有限域

多项式计算

有限域GF(2n)上的多项式计算

素多项式

任何多项式可以写为：f(x)=q(x)g(x)+r(x)
r(x)称为余式
r(x)=f(x) mod g(x)

若不存在余式，则称g(x)整除f(x)，g(x)|f(x)

若f(x)除了它本身和1外，不存在其它因式，则称f(x)是不可约多项式，或既约多项式、素多项式

系数在GF(p)中，以素多项式取模的多项式构成一个域

欧几里得算法

1
2
3
4
5
6
7
a可以表示成a = kb + r（a，b，k，r皆为正整数，且r<b），则r = a mod b
假设d是a,b的一个公约数，记作d|a,d|b，即a和b都可以被d整除。
而r = a - kb，两边同时除以d，r/d=a/d-kb/d=m，由等式右边可知m为整数，因此d|r
因此d也是b,a mod b的公约数
假设d是b,a mod b的公约数, 则d|b,d|(a-k*b),k是一个整数,
进而d|a.因此d也是a,b的公约数
因此（a,b）和（b,a mod b）的公约数是一样的，其最大公约数也必然相等，得证。
1
2
3
4
5
对于任何可以整除a和b的整数，那么它也一定能整除a-b（和b)，因此我们选择该整数（前面提到的任何整数）为gcd(a,b)，它一定比a-b和b的最大公约数小：gcd(a,b)<=gcd(a-b,b)
同理，任何可以整除a-b和b的整数，一定可以整除a和b，因此我们选择该整数为gcd(a-b,b)，它一定比a和b的最大公约数小：gcd(a-b,b)<=gcd(a,b)
由此可知：gcd(a,b)=gcd(a-b,b)
因为总有整数n，使得 a - n*b = a mod b，
所以迭代可知：gcd(a-b,b)=gcd(a-2b,b)=...=gcd(a-n*b,b)=gcd(a mod b,b)

gcd(a,b)=gcd(a mod b, b)

若a和b只有唯一的正公因子1，则称整数a和b是互素的，即gcd(a, b)=1

扩展欧几里得

求d=gcd(a,b)，并解ax+by=d

第二节 素数

素数有无限多个

费马数

梅森素数

完全数

素因子分解

任一正整数可通过列出所有素因子的非零指数分量来表示
例：12可以表示为{a2=2, a3=1}
例：18可以表示为{a2=1, a3=2}

两个数的乘法等同于对应指数分量的加法：
K = mn → kp = mp + np 对所有p
例：216=12×18=(22×31)×(21×32)=23×33

最大公约数：k=gcd(a,b) <=> 所有kp=min(ap,bp)
例：300=22×31×52, 18=21×32 gcd(18,300)=21×31×50=6

费马定理

image-20210807223557784

欧拉定理

image-20210808111928181

image-20210808122519540

image-20210808115027528

中国剩余定理

image-20210808122417972

阶

image-20210808205302384

原根

image-20210808205601708

原根的模数不一定是素数：5是模6的一个原根

原根未必唯一

所有的奇数都是模2的原根

image-20210808210709152

image-20210808211446013

算术基本定理

image-20210808214234027

DH算法

image-20210902223744193 image-20210913221636557

扩展欧几里得

求乘法逆元

第四章-分组密码

第一节 DES

Feistel密码结构

DES 64位密钥

实际只使用56位

其它用作奇偶校验等

雪崩效应就是一种不稳定的平衡状态也是加密算法的一种特征，它指明文或密钥的少量变化会引起密文的很大变化，就像雪崩前，山上看上去很平静，但是只要有一点问题，就会造成一片大崩溃。 可以用在很多场合对于Hash码，雪崩效应是指少量消息位的变化会引起信息摘要的许多位变化。指加密算法（尤其是块密码和加密散列函数）的一种理想属性。雪崩效应是指当输入发生最微小的改变（例如，反转一个二进制位）时，也会导致输出的不可区分性改变（输出中每个二进制位有50%的概率发生反转）。合格块密码中，无论密钥或明文的任何细微变化都必须引起密文的不可区分性改变。

构造一个具备良好雪崩效应的密码或散列是至关重要的设计目标之一。

计时攻击

能量攻击

DES能够很好地抵抗计时攻击

DES不能抵御差分分析、线性分析

差分密码攻击

  • 分析明文对的差异和密文对的差异之间的关系
  • 确定轮运算的子密钥，从而恢复某些密钥比特

线性密码分析

DES的设计标准

第二节有限域计算
第三节 AES

密钥长度：128，192，256

不是Feistel结构

字节代换、行移位、列混淆三个阶段一起提供了混淆、扩散和非线性功能。这些阶段不涉及密钥，其本身并不提供安全性

image-20210917224400452
第四节 分组密码工作模式

image-20210917233643054

不同分组模式的优缺点。

第五节 其他密码
image-20210922095840573

第五章-流密码

分类：

  • 同步流密钥
  • 自同步流密钥

第六章-公钥密码

第七章-消息认证

1.消息认证
2.散列算法
3.MAC算法

hash是无密钥的

MAC是有密钥的

生日悖论

image-20210926214703360

对输出n比特的hash函数，生日攻击的代价为$2^{n/2}$

第八章-数字签名

第九章-密钥管理

1.加密

  • 链路加密
  • 端到端加密

2.密码系统的安全性取决于算法强度和密钥长度