现代密码学

概论

计算机安全的最核心三个关键目标（指标）/为：保密性 Confidentiality、完整性 Integrity、可用性 Availability ，三者称为 CIA三元组
- 数据保密性：确保隐私或是秘密信息不向非授权者泄漏，也不被非授权者使用（获取到明文）
OSI安全架构关注安全攻击、安全服务和安全机制。
- 安全攻击：任何危及信息系统安全的活动
  - 被动攻击试图获取或利用系统的信息，但不影响系统资源。如信息内容的泄漏和流量分析
    - 被动攻击不涉及对数据的修改，因此很难检测。通常采用加密的方式来阻止被动攻击。即重点是预防而非检测。
  - 主动攻击则试图改变系统资源或影响系统运行。主动攻击分为：伪装、重放、消息修改和拒绝服务。
    - 伪装：指某实体假装为其他实体。伪装攻击还包含其他形式的主动攻击。例如，截获认证信息，在认证信息完成合法验证以后进行重放。无权限的实体就可以通过冒充有权限的实体获得额外的权限。
    - 重放：指攻击者未经授权将截获的信息再次重放。
    - 消息修改：指未经授权地修改合法消息的一部分，或延时消息的传输，或改变消息的顺序。
    - 拒绝服务
- 安全服务：加强信息安全性的一种处理过程或通信服务。其目的是使用安全机制进行反攻击。
- 安全机制：用来检测、阻止攻击，或者从攻击状态恢复到正常状态的机制
攻击面是由系统中一系列可访问且可利用的漏洞组成。主要分为：
- 网络攻击面：指的是企业网络、广域网或是互联网。包含协议的漏洞及拒绝服务供给、终端通信链路等。
- 软件攻击面：设计应用程序、工具包或操作系统漏洞。
- 人类攻击面：主要是系统人员或是外部人员造成的漏洞。
攻击树是采分支化、层次化表示利用安全漏洞的可能技术集合的一种数据结构。
- 根节点：攻击目的。第二层是攻击的目标，再往下则是攻击的方式等。
- 深度越深则越具体。因此叶节点是具体的攻击方式。

网络安全模型需要考虑

设计安全的相关变换算法
产生算法所需的秘密信息（密钥）
设计分发、共享秘密信息的方案
指定协议，该协议利用安全变换和秘密信息实现安全服务

传统加密技术

密码编码学

密码编码学具备以下三个独立特征：

转换明文为密文的运算类型:代换和置换
- 代换是将明文中的元素映射成另个元素；置换是将明文中的元素重新排列。这些运算都要求不能信息丢失、即所有运算是可逆的。
密钥：发送方和接收方使用相同密钥，称为对称密码否则，称为非对称密码。
处理明文的方法：分组处理或流式处理

密码分析：密码分析的目标是获取密钥，而非恢复出单个密文对应的明文。

穷举法

Shannon：一个好的密码系统应具备抵抗统计分析的两个特性:

扩散性(diffusion)：在同一密钥下
- 相似的明文，密文差别较大；
- 相似的密文，明文差别较大。
- 扩散性可以隐藏明文和密文之间的关系，阻止对手通过统计密文找到明文
混淆性(confusion)：在同一明文下：
- 相似的密钥，密文差别较大；
- 相似的密文，密钥差别较大。
- 混淆性隐藏密文和密钥之间的关系，阻止对手通过统计密文来找到密钥

Substitution 代换技术 Caesar

思路：

元素表：以 26个字母为元素表，做循环排列，形如：abcd…xy zabcdef…
密码表：与明文表相对而言。所有明文经过变换得到的密文的合集，就是密码表。
间隔：可以自定义间隔，间隔指示应当向向后找多少位的字母代替当前字母。间隔不同，密码表就不同。

例如，假设间隔为 3，则 A B C 应分别代换为 D E F
在这里插入图片描述
完整的代换表为：

Caesar密码的三个重要特征使我们可以采用穷举攻击分析方法:

已知加密和解密算法
需测试的密钥只有25个
明文所用的语言是已知的，且其意义易于识别

DEMO

解密以下 caesar密码：
EHVWWLPHRIRIWKHKHBHBDULVLVVVSUSULQJZKHQIQRORZHUHVUVEOEORRRP

对这个密文尝试所有位移值，直到看到可理解的文本。为节省时间，我可以快速编写代码来完成这个过程。

通过暴力破解密文，我们发现位移值为 3 时（向前），密文解密后的结果为：
BEST TIME OF THE YEAR IS SPRING WHEN FLOWERS BLOOM.

代换技术之单表代换

首先必须区分单表代换与 caesar密码的区别。

caesar密码中，所有明文–>密文必须遵循相同的间隔。即，若 A 对应 D，则能推断出 B 一定对应 E。这样，密码表只有 26张。

单表代换中，所有明文 --> 密文不遵循相同的间隔。即，若 A 对应 D，B 可能对应 A/B/C/E/F…任意一个，只有确保一一对应的关系，明文与密文可以以一种杂乱的关系确定下来。这样，密码表有 26！张。大大增加了复杂性。

但代换技术的弱点没有解决：

因为单字母替代不会改变字母的频率，所以原始文字的统计特征几乎被完整保留下来。
有两种主要方法可以减少代换密码里明文结构在密文中的残留度：
- 对明文中的多个字母一起加密；
- 采用多表代换

Playfair

Playfair密码将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文的双字母组合。

编制密码表（矩阵）

PlayFair 中，密码表即按照指定密钥字母串构造出来的矩阵。

准备一个密钥字母串，一个 5X5 的矩阵。
将密钥字母串去重，得到顺序集合 A；
将 26字母表去重集合 A，得到顺序集合 B；
I 和 J 被算为一个字母;
从左到右，从上到下，将顺序集合 A 填充到该矩阵，然后再将顺序集合B 填充到该矩阵。

整理明文表

将明文表字母两两分组，一组即为一对。
分割后，任一对明文字母如果是重复的，则在这对明文字母之间插入一个填充字符，如 X。
分割且填充后，任一对明文字母若在矩阵的同一行中出现(不需要相邻），那么分别用矩阵中其右侧的字母代替，行的最后一个字母由行的第一个字母代替。例如：ar 加密为 RM，ek 加密为 FE
分割且填充后，任一对明文字母若在矩阵的同一列中出现(不需要相邻），那么分别用矩阵中其下方的字母代替，列的最后一个字母由行的第一个字母代替。例如：hs 加密为 BP，ea 加密为 IM/JM
否则，任一对明文字母中的每一个字母将由与其同行，且与另一个字母同列的字母代替。例如：hs 加密为 BP，ea 加密为 IM/JM。（即按照矩形规则替换为隔壁角）

DEMO

使用的密钥词是 monarchy，将 ballon 加密。

去重得到的顺序集合A 为【m，o，n，a，r，c，h，y】
将 26字母表去重集合 A，得到顺序集合 B【b，d，e，f，g，i，j，k，l，p，q，s，t，u，v，w，x，z】
将 I 和 J 视为一个字母，并将顺序集合A、B 填充，可得：
欲加密的明文是 balloon。则两两分组为：balloon --> ba ll oo n --> ba lx lo on
ba 在同一列中出现，替换成 ib；lx 不同行不同列，按照矩形规则，替换为 su；lo 不同行不同列，按照矩形规则替换为 pm；on 在同一行中出现，替换为 na。
最终得到密文 ibsupmna。

代换技术之多表代换（Vigennere）

多表代换的代换表有多个。加密时交替使用不同的代换表。但注意，加密和解密要同步，也就是，加密和解密所用的代换表顺序要一致，不然解密会出错。
多表代换跟单表代换相比，其主要优点是，多表代换增大了密钥空间，更彻底地打破整体上的统计特性。
Vigenere 实质上就是扩展的 Caesar加密。Vigenere 的代换表有多张，且每张使用不同的间隔k，在加密时，交替使用不同的代换表进行代换。

多表代换 DEMO

假设明文表为{1，2，3，4}
代换表1 为{1：2，2：4，3：3，4：1}；
代换表2 为{1：4，2：1，3：2，4：3}。
代换表1 和代换表2 交替使用。
现在加密明文 123112：
在这里插入图片描述

Vigenere DEMO

Vigenere 中，密码表也是按照指定密钥字母串构造出来的矩阵。

构造一个 26X26 矩阵，第一行内容为【a，b…z】，第二行内容为第一行内容循环右移一位即【b，c…a】，以此类推。
选定任意密钥字母串
将欲加密明文与密钥字母串比对，当密钥比明文短时，重复密钥至与明文等长；
加密过程基于明文字符和密钥字符在密码表中的位置关系。明文字符决定行：在密码表中找到以明文字符开头的行；密钥字符决定列：在密码表中找到以密钥字符为列头的列。交点字符即为密文字母。

取密钥为：deceptive
欲加密明文为：wearediscoveredsaveyourself
扩展密钥成为：deceptivedeceptivedeceptive

则明文字符 w 对应的密文为：Z（坐标为 (w,d)）

整体密文为：ZICVTWONGRZGVTWAVZHCOYGLMGI

多表代换之轮转机（Enigma）

发信人首先要调节三个转子的方向，使它们处于 17576个方向中的一个(事实上转子的初始方向就是密匙，这是收发双方必须预先约定好的)，然后依次键入明文，并把闪亮的字母依次记下来，然后就可以把加密后的消息用电报的方式发送出去。

单表代换之仿射加密 Affine Cipher

仿射加密的字母系統中所有字母都藉一簡單數學方程加密，對應至數值，或轉回字母。所有字母皆藉由方程 （ax + b）mod m加密。其中：

对于加密

每个字母都被映射到一个数字上（通常是 A = 0, B = 1, …, Z = 25），然后通过仿射变换函数 （ax + b）mod m进行加密得到数字串后，再转回字母即可。
- a 和 b 为密钥；
- x 为明文字符对应的数字
- m 为字母个数，一般为 26；
- a 和 m 必须互质，由于 m 一般为 26，则 a 可选值为 1、3、5、7、9、11、15、17、19、21、23、25。（a > 26 会导致重复计算，没有意义)
- 当 a 为 1 时，仿射变换实质就是 Caesar密码。

对于解密

每个字母都被映射到一个数字上（通常是 A = 0, B = 1, …, Z = 25），然后通过仿射变换解密函数
进行解密得到数字串后，再转回字母即可。
- 其中，a^（-1）是 a 的乘法逆元，将其设为 x，则

例如，对于 3 的乘法逆元，即求一个数 x，使得 3x mod 26 = 1 成立，可知 x = 9。

其本质就是穷举，但是更具体来说，可以有一种思路：既然要求 mod 的结果为 1。则等式左边结果恒比等式右边的可能倍数大 1。

等式右边可能的取值为 26，52，78，104，130…
则等式右边只能从 27，53，105，131… 中取得，进而可以快速匹配

DEMO

在这里插入图片描述

明文为：HELLO
参数：a = 5, b = 8, m = 26，则仿射变换函数为（5x + 8）mod 26

对于加密过程

对于 H，加密过程为（5 X 7 + 8）mod 26 = 43 mod 26 = 17 -> R
以此类推，得到密文为 RCLLA。

对于解密过程

5 的乘法逆元满足 5x mod 26 = 1，则 5 的乘法逆元为 21。则解密的变换函数为 21·(x - 8)mod 26
对于密文字符 R，解密过程为：21·(17 - 8)mod 26 = 189 mod 26 = 7 ->H
以此类推，得到明文为HELLO

证明加密函数等于解密函数

在这里插入图片描述

代换之 Hill密码

Hill密码是一种基于矩阵运算的多字母替换密码，它是第一个用到代数方法的加密算法，主要用矩阵和向量的乘法来实现加解密。
Hill密码能抵抗唯密文攻击，但不能抵抗已知明文攻击，事实上，只要知道 n块相互独立的明文串及相对的密文，就可以确定密钥 K。
加密公式为C = (K·P) mod m，其中：
- P：明文的向量形式，即一组字母转化为数字的形式（如 A = 0, B = 1, …, Z = 25，则[a,b,c,d] 转化为[0,1,2,3]）。
  • K：密钥，是一个 n x n 方阵（必须可逆）。
  • C：密文向量，计算得到的加密结果。
  • m：字母表大小（通常 m = 26）。

加密过程为：

选定方阵的行列均为 n，然后将明文串每 n个分一组，最后一组不足 n个则补 X，这样就得到了若干组 n x 1向量。
将分组中的字母映射为数字；
将每组明文向量 P 与密钥矩阵 K 相乘得到：C = (K·P) mod 26 ，每次运算得到一个 n x 1的密文向量Q，将其转化回字母即可得到密文。

解密过程为：

将密文串每 n个分一组，最后一组不足 n个则补 X，这样就得到了若干组 n x 1向量。
将分组中的字母映射为数字；
根据已知的密钥矩阵K，求其逆矩阵设为 K‘
将每组密文向量Q 与密钥矩阵K‘ 相乘得到：C = (K’·Q) mod 26 ，每次运算得到一个 n x 1的明文向量P，将其转化回字母即可得到明文。

在这里插入图片描述

求逆矩阵

Hill加密的逆矩阵是在模运算基础上的逆矩阵，因此求其逆矩阵时，需时刻计算模
在这里插入图片描述

DEMO 之求加解密过程

DEMO 之已知明密对、n，求加密矩阵

给定一下信息，求解 Hill加密矩阵

•	分组长度 n = 2
•	明文（明文对）：“howareyoutoday”
•	密文（密文对）：“zwseniuspljveu”

将明文和密文按照分组长度 n = 2 分成对应的列向量，就得到了明文和密文的矩阵。
在这里插入图片描述

代换之一次一密

使用与消息一样长且无重复的随机密钥来加密消息
每个密钥都是一次性的，加密后就不再使用。
在理论上它是不可攻破的。它产生的随机输出与明文没有任何统计关系。因为密文不包含明文的任何信息。

代换技术之破解方法

最常用的是统计方法。

在英语中，用的最多的单个字母依次是 e，t，o，a，h，I；最少的是 z，j。
最常用的双字母组依次是 th，in，er，re，an；
最常用的三字母组是 the，ing，and，ion。

分组密码

在分组密码中，大小为 n 的一组明文符号被一起进行加密，创建出相同大小的一组密文。
在分组密码中，即使密钥是由多个值构成的，但仍看成单密钥，整个分组都由它进行加密。
playfair密码是分组密码，组的大小是n=2两个字符一起加密。
Hill密码是分组密码，用单密钥(一个矩阵)进行整体加密。虽然密钥由 n x n 个值组成，还是要看作一个单密钥。

置换 Permutation

置换是通过变动明文块内部的字符排列次序来达到加密信息的目的。

第一种置换方法

 - 明文设为字符集合A
 - 密钥即为置换和逆置换。置换为【2，7，4，6，1，3，51】(2 表示当前位置用第 2个字母置换】。逆置换为【5，1，6，3，7，4，2】
 - 密文即为用密钥（置换）改变字符集合A 顺序得到的字符串B

第二种置换方法

明文设为字符串集合A，将 A 按行优先依次填入空矩阵中。
密钥为顺序数字集合。
按密钥中数字的顺序，排布矩阵中的列

隐写术

隐写术不是严格意义上的加密，其实现方式是将秘密消息隐藏在其他消息中。
- 字符标记:选择一些印刷字母或打字机打出的文本，用铅笔在其上书写一遍。这些标记需要做得在一般场合下辨认不出，除非将纸张按某个角度对着亮光看。
- 不可见墨水:有些物质用来书写后不留下可见痕迹，除非加热或加之以某种化学物质
- 针刺:在某些字母上刺上小的针孔，这一般是分辨不出来的，除非对着光线。
- 打字机的色带校正:用黑色的色带在行之间打印。用这种色带打印后的东西只在强光下可见。
- 加水印

数论基础

整除性

在这里插入图片描述
注意： a != 0，但 b 可以为 0 ，且当 b 为 0 时，对于任何的 a ，a｜b恒成立。如 1｜0、2｜0…

在这里插入图片描述

例：证明若3｜n且7｜ n，则21｜ n

由3｜n，可知存在整数m 使得 n = 3m，进而代换可得 7｜3m

此外，对于任何的m，1｜m 恒成立，因此 7｜7m 恒成立

运用线性运算法则，对于任意的 x、y：7｜{x（3m）+y（7m）}恒成立

令 x = -2，y = 1，则有 7 ｜（ -6m + 7m）= 7｜m = 21 ｜3m = 21 ｜n

欧几里得算法求最大公因数（最大公约数）

最大公因数就最大公约数
在这里插入图片描述

欧几里得算法的时间复杂度：O（log n）

扩展欧几里得算法求两个数的最大公约数的线性表示

求 198 和 252 的最大公约数，并把它表为 198 和 252 的整系数线性组合
在这里插入图片描述

扩展欧几里得算法求乘法逆元

a mod b，在 a < b 时，求乘法逆元

欧几里得算法也叫辗转相除法，这个方法可以找到两个非负整数的最大公约数，
只要知道：扩展欧几里得的形式为余数 = 被除数 - 系数x除数，即每一步都为减法
辗转相除直到余数为 1；
通过将前步等式代换得到 a，p 关系，a 的乘数即为所求。

此外还必须注意的细节有：

除法系数必须写右边，方便合并
与第一条同理，任何乘法必须注意次序，并且任何一项始终保持两两相乘
最终得到的 x 若为负数，则令 |x| + z = p，z 即为所求。

a mod b，在 a > b 时，求乘法逆元

在这里插入图片描述

模运算

同余

在这里插入图片描述

模算术运算（快速幂）

将幂转化为二进制。
设 ans = 1，cur = 底数，开始迭代；
轮数等于二进制幂的长度。从后往前看二进制幂：若为 1 ，则 ans = ans ✖️ cur （mod 模数），cur = cur ✖️ cur （mod 模数）；若为 0 ，则 ans 不变，cur = cur ✖️ cur （mod 模数）。
最后结束 ans 即为整体的结果。

在这里插入图片描述

中国剩余定理

用于加速模运算
某一范围内的整数可通过它对两两互素的整数取模所得的余数来重构
使得非常大的数对M 的模运算转化到更小的数上来进行运算

DEMO

计算 Mi 和 M。其中 M1 = 除了一式以外所有式子的模；相乘；M为所有式子的模数相乘
计算 Mi 的乘法逆元；
使用公式

在这里插入图片描述

欧拉定理、费马小定理

欧拉函数：设 n 是正整数，小于 n 且与 n 互素的正整数个数称为 n 的欧拉函数，记为 φ（n）例如： φ（6）= 2 ；φ（7）=
6。
- 若 n 是素数，则 φ（n）= n - 1；
- 若 n = pq，且 p、q 均为素数，则 φ（n）= （p - 1）（q - 1）

欧拉定理求大整数的后几位

计算模数n 的欧拉函数值 φ（n）
将幂拆解为含有欧拉函数值 φ（n）欧拉函数值 φ（n）的多因子的乘积

费马小定理指数取模

在 a、p 互素的情况下：
在这里插入图片描述

用费马小定理将指数化为小于模数的形式
将指数继续分拆，模出来的结果相乘最后再模即可

在这里插入图片描述

离散对数

本原根

多项式计算

对称密码体制

分组密码

分组密码将输入的明文分组当做一个整体处理，输出一个等长的密文分组。
Feistel密码结构是分组密码中的一种对称结构。由于它是对称的密码结构，所以对信息的加密和解密的过程就极为相似，甚至完全一样。这就使得在实施的过程中，对编码量和线路传输的要求就减少了几乎一半。
Feistel 建议使用乘积密码来增强密码的强度
Feistel建议交替使用代换和置换，增强密码的扩散和淆性能
- 扩散 Diffusion：让每个明文数字尽可能地影响多个密文数字，使明文和密文的统计特性不相关。
- 混淆 Confusion：使密文和密钥之间的关系变得复杂
- 乘积密码 Product Cipher：在单个加密机制中依次使用两个或两个以上不同类型的基本密码(如代换和置换)，所得结果的密码强度将强于每个单个密码的强度
DES 等传统分组加密算法都采用了 Feistel结构。

分组密码之 DES

DES具有很好的雪崩效应：明文或密钥某一位发生变化(微小的变化)将对密文产生很大的影响
DES 采用 P置换来达到扩散性
DES 采用 S盒置换来达到混淆性

其中，IP扩展、E扩展、P置换都为查表置换。

DEMO

已知 S盒如下，若输入为 101101，求输出。

首尾二数为 11，十进制为 3，则第三行；
中间数字为 1001，十进制为9，则第九列；
查表三行九列为 14，十进制为 1100，即输出值。
在这里插入图片描述

分组密码之 AES

AES 分组长度只能是 128bit
密钥长度 128/192/256bit，分别对应着 10/12/14 轮的迭代。
处理单位是字节；作为对比，DES 处理单位为 bit。
AES 的基本运算，可以记为“三代替、一换位”
- 字节代替SubBytes
- 列混淆MixColumns
- 行移位ShiftRows
- 轮密钥加AddRoundKey
AES 解密的基本运算为：
- 逆向行移位
- 逆向字节代替
- 轮密加
- 逆向列混淆。

分组密码运行模式

当消息长度大于分组长度时，需要分成几个分组分别进行处理，分组的方式/顺序就称为分组密码的工作模式或分组密码算法的运行模式。
- 电子编码本模式。优点：简单且有利于并行计算，误差不会被传送。缺点：不能隐藏明文的模式，一旦有一个块被破解，使用相同的方法可以解密所有的明文数据，安全性比较差；可能对明文进行主动攻击这种方法
- 密码分组链接模式。优点：不易被主动攻击，是 SSL、IPSec 的标准。缺点：不利于并行计算，误差传递。
- 输出反馈模式。跟密码分组链接差不多。
- 密码反馈模式。

公钥密码

公钥密码解决的基本问题
- 解决传统密码中的密钥分配和数字签名
公钥密码的特点：
- 仅根据密码算法和密钥来确定解密密钥在计算上不可行；两个密钥中的任何一个都可用来加密，另一个用来解密。
公钥密码的六个组成部分:
- 明文、密文；公钥、私钥；加密、解密算法
公钥密码的三个作用
- 加解密：发送者用接收者的公钥加密消息，
- 数字签名：发送者用自己的私钥签名消息
- 密钥交换：通信双方用公钥密码交换会话密钥，此后便可用会话密钥进行对称加密，节省资源。
单向函数 one-way function
- 陷单问函数(Trapdoor one-way function) 是单向函数，在不知陷门信息下，由f（x）求 x 极为困难；当知道陷门信息后，由 f（x）求 x 是易于实现的。