密码学复习

大四开了两门课，《信息安全数学基础》、《密码学》，临近期末考试，复习一下学过的知识

关于《密码学》老师说没有足够的课时，只能给我们讲一下常用的算法，在学习时可以看到密码学依赖于信息安全数学基础的学习，不过信安数学有点不太容易理解.

着重复习几个章节，首先是第三章的传统加密：

对称加密五部分：
明文
加密算法
密钥
密文
解密算法

密码编码学三特性：
1.转换明文为密文的运算类型
所有加密算法基于：代替和置换
2.所用的密钥数
用同一个：对称密码
用不同的：非对称密码，公钥密码
3.处理明文方式
分组密码：每次处理输入的一组数据，每次输出一组
流密码：连续处理输入的数据，每次输出一个

对加密信息的攻击类型
攻击类型 已知
唯密文攻击 加密算法；密文
已知明文攻击 加密算法；密文；用同一个密钥加密的一个或者多个名密文对
选择明文攻击 加密算法；密文；分析者选择的明文，对应的密文
选择密文攻击 加密算法；密文；分析者选择的密文，对应的明文
选择文本攻击 加密算法；密文；分析者选用的明文以及对应的密文；分析者 选择的密文以及对应的明文

——–代替技术————–

Caesar凯撒密码

C=E(N,P)=(P+N)mod (26) //每个后移n位

P=D(N,C)=(C-N)mod (26) //解密

playfair密码

playfair密码是多字母代替密码。基于一个5×5的字母表，其中i/j看作是同一个如下图

playfair算法一次加密两个字母，规则如下

hill密码

vigenere维吉尼亚密码

这是多表替换密码

Vernam密码

———–置换技术—————–

栅栏密码

轮转机

第四章：分组密码和数据加密标准

会涉及DES、AES算法

现在使用大多数对称分组加密算法都是基于Feistel分组密码结构

DES加密

两个输入：明文、密钥
DES明文长64位，密钥长56位

以课本例题讲解
如下面图1，题目给出明文和密钥，我们先把他们的二进制格式写出来，然后从1开始标号方便后续查表。

1.现在要求出第一轮子密钥c0，d0，通过查下面图2的信息，找到密钥二进制位数对应的数字

原本64位的密钥通过置换变成56位的子密钥，如下图3

然后c0和d0同时左移一位，见下图4

然后我们把c1,d1合并成一个56位的数据集，通过另一个表，见下图5来置换数据得到48位的子密钥K1

得到了48位的子密钥K1，如图6

2.现在我们来对明文进行处理，根据下图7的表，对64位的明文进行置换

然后把置换好的明文拆分成位数一样的两个部分，记作L0和R0，既左半边和右半边，如图8

3.根据DES算法步骤，现在要对R0进行E扩展，此时L0不做改动，记为E(R0)，目的是把32位R0扩充为48位，方法是把每四位的前、后一个数据加到头尾，如下图9，以1111为例，扩充后为01110，0000扩充后是100001

4.接下来要用E(R0)和子密钥K1进行异或，注意到此时两者都是48位，结果如图10

5.随后我们要根据S盒来进行置换，因为分为了8组，因此有8个s盒子，记为S1-S8，置换的方法是，根据刚才扩充好的数据，以 0 1110 0 为例子，原数据是 1110 以左右两边 0 0 进行扩充，我们把扩充的 00看作是S盒的行号，原数据 1110 看作是S盒的列号，以此来进行置换（注意每次用的S盒不同），方法也可用下图11来计算

5.把S1到S8置换后的数据拼接在一起，组成32位的数据，记为B，结果如下图12

6.接下来要根据另一个表来对上面的拼好的32位数据进行P盒置换，记为P(B)，P盒见下图13，置换后的结果见下图14

7.然后我们将P(B)跟L0（到目前为止L0一直未处理）进行异或得到新的R1，结果如下图15

8.最后求L1，L1就是R0，如下图16

这样完成了一轮DES加密

AES加密

AES使用有限域GF（2⁸）内的算数，其中不可约多项式为：M(X)=x⁸+x⁴+x³+x+1，也就是二进制数00011011看a0到a7，尤其是分析a7情况
a7=0时，正常结果

a7=1时，结果需要异或00011011
注意，指的是左移之前的a7，如02·87=0000 0010 ·1000 0111=0000 1110(87左移一位)，因为87的二进制a7为“1”，所以结果要异或 0001 1011 即 0000 1110 xor 0001 1011=0001 0101

AES的四个阶段：
1.字节替代：用s盒完成分组的字节到字节的代替
2.行位移：简单置换
3,列混淆：利用域上特性进行代替
4.轮密钥加：当前分组和扩展密钥的一部分进行按位异或

1.字节替代：根据给的s盒，从行列找出对应的值，注意x是行，y是列喔
2.行位移：第一行不动，第二行左移一位，第三行左移两位，第四行左移三位
3.列混淆：试图构造出带有02的，因为×02相当于左移一位，当移位前的最左边是1，也就是a7是1的时候，如上文所说要异或00011011
在列混淆中需要用到一个矩阵：
02 03 01 01
01 02 03 01
01 01 02 03
03 01 01 02
该矩阵是左边的，跟经过行位移后的矩阵进行乘法，即左边矩阵第一行乘右边矩阵第一列，再异或得到对应的数字，注意01乘啥是啥，02乘啥，啥就二进制左移一位。
4.轮密钥加变换

—-公钥密码—-

第九章：公钥密码学和RSA

RSA算法

C=M^e mod n //加密
M=C^d mod n=(M^e)^d mod n=M^ed mod n //解密

RSA找到以下内容计算：
1.互素的两个整数 p、q //保密的，选定的
2.n=p×q //公开的，计算得出的
3.e 满足gcd(Ф(n),e)=1 //公开的选定的
4.d≡e^-1 （mod Ф(n) ） //保密的，计算得出的
私钥{d,n},公钥{e,n}, Ф(n) =(p-1)(q-1)

第十章：密钥管理、其他密钥体制

Diffie-Hellman密钥交换

要定义离散对数，定义素数p的本原根a（就是信安数学的原根概念）

对于任意整数b和素数p的原根a，有：

---

算法：
素数q,他的原根α这两个整数是公开的。
当用户A与B要用该算法交换密钥，那么A要选择一个随机的整数Xa<q,计算Ya=α^Xa mod q，
B也要选择一个随机的整数Xb<q,计算Yb=α^Xb mod q。对于A要保护好自己的Xa，B要保护好Xb，通信的时候A和B可以交换Ya和Yb，接下来验证：
A计算K=（Yb）^Xa mod q
B计算K=（Ya）^Xb mod q
这两个算出来的K是一样的

EIGamal密码体制

同上一个算法一样，要选一个素数q，以及它的原根α（素根），用户A生成密钥对：
1.随机生成整数Xa，1<Xa<q-1
2.计算Ya=α^Xa mod q
3.A的私钥为Xa，公开的为{q，α，Ya}

用户B用用户A的公开信息对明文加密：
1.信息表示为一个整数M，使得1<=k<=q-1
2.随机选一个整数k，1<=k<=q-1
3.计算一次密钥K=(Ya)^k mod q
4.把M加密成明文对（C1,C2）,其中
C1=α^k mod q C2=KM mod q

用户A解密：
1.计算K=(C1)^Xa mod q //恢复密钥
2.计算M=(C2^K-1) mod q //解密

第十一章：密码学hash函数

SHA-512

1.附加填充位
2.附加长度
3.初始化hash缓冲区
4.以1024位的分组（128字节）为单位处理信息
5.输出

示例：
对“abc”构成的消息块进行hash处理，可根据他们的ascii码写成二进制形式：
a:97(₁₀) 0110 0001
b:98(₁₀) 0110 0010
c:99(₁₀) 0110 0011

所以“abc”一共有 24 位，二24对应的二进制为：1 1000

根据SHA算法，消息被填充后要跟1024模896同余，所以要填充长度为896-24=872位

填充的内容是 ： 1个 “1” 和 871个 “0”

然后，把128位的长度信息附在填充消息的后面,表示保存的被填充之前的消息长度，在这里是24位，也就是1 1000（₂）=18（₁₆）

因此，abc被扩充之后应该是如下：
0110 0001 0110 0010 0110 0011 | 1 0(*871) | 0(*123) 1 1000

前24位是abc的ascii码对应二进制，之后872位是1和871个0，最后的128位是若干个0（取决与原始长度）以及24对应的ascii码。一共1024位。