Crypto

古典密码

古典密码工具箱, 里面有个人收集的一些古典密码的脚本

凯撒密码/加法密码

就是明文字母对应的ASCII数字加 3, 加 3 就是凯撒密码, 这玩意代码网上遍地都是, 有兴趣自己去找找吧

乘法密码

乘法密码百度百科

栅栏密码

栅栏密码

仿射密码

仿射密码百度百科

密钥短语密码

密钥短语密码

维吉尼亚密码

周围的字母行和列被称为密钥字母行和密钥字母列

我们通过例子来说明维吉尼亚密码的加密流程

例如, 明文 P : I LOVE YOU

密钥 K : KISS

我们把明文和密钥对应起来就是

K I S S K I S S

I L O V E Y O U

我们对第一个字母 "I" 的加密过程如下 :

1. 找到最左侧密钥字母列, K 所在的地方, 和最上面密钥字母行 I 所在的地方

2. 然后 K 的那一行和 I 的那一列, 找到它们的相交字母为 S

这样 I 就被加密成了 S

以此类推, 我们加密结果如下 :

密钥 K : K I S S K I S S

明文 P : I L O V E Y O U

密文 C : S T G N O G G M

希尔密码

加密过程:

1. 先定义一个矩阵k(必须存在逆矩阵)作为加密密钥

2. 将我们需要加密的明文字母转换成数字序列

3. 将数字序列按照矩阵k的阶数进行分组

4. 每组数字序列和密钥矩阵k进行乘法运算, 结果即为密文数字序列

5. 把密文数字序列转换成字符串 mod 26 之后转换成字符串

解密过程

1. 先算 k 的逆矩阵 k^{-1} (见初等变换求逆矩阵) 初等变换求逆矩阵

2. 明文 M = (密文 C) * (k 的逆矩阵 k^{-1}), 最后 mod 26 转换成字符串

playfair 密码

首先将密钥的单词(去掉重复字母)从左到右、从上到下填在 5x5 的矩阵格子中, 再将剩余的字母按照字母表顺序 (abcdefg这种顺序就叫字母表顺序)从左到右、从上到下填在矩阵剩下的格子里. 字母 I 和 J 暂且当成一个字母.

例如密钥单词 : monarchy

现代密码

对称密码

DES

DES 为分组加密算法, 明文和密文为 64 位分组长度

对称加密算法的意思是, 加解密算法相同, 但是密钥编排不同

DES 基于 Feistell 结构

DES 的有效密钥长度是 56 位, 因为 64 位密钥中, 每个第 8 位是奇偶校验位, 可以忽略

DES 密钥可以为任意 56 位数, 但是存在若密钥

DES 总的加密流程图如下 :

DES 与 Feistell 结构的区别在于多了 IP 置换和 IP^{-1} 逆置换

Feistell 结构定义

加密 : L_i = R_{i-1}; R_i = L_{i-1} \bigoplus F(R_{i-1}, K_i)

解密 : R_{i-1} = L_i

L_{i-1} = R_i \bigoplus F(R_{i-1}, K_i) = R_i \bigoplus F(L_i, K_i)

DES 算法细节

子密钥的产生

64 位的密钥经过

1. 置换 1 (PC-1, 也称压缩变换)
   去掉 8 个奇偶校验位, 并把剩下的 56 位打乱重排, 前 28 位作为 C_0, 后 28 位作为 D_0

2. C_0 和 D_0 分别循环左移一位或两位, 由迭代次数 (圈数、轮数决定)

3. 置换选择 2 (PC-2), 再从 56 位中选出 48 位, 形成密钥 K_1

4. 重复上面的步骤 2 和步骤 3, 产生 16 个子密钥
   K_1 ~ K_{16}, 16 个子密钥

置换选择就是把原来的数字, 按照编号填在表里

置换 IP 与逆置换 IP^{-1}

加密函数

这个是 DES 的核心部分, 作用是在第 i 次加密迭代中用子密钥 K_i 对 R_{i-1} 进行加密, 包括扩展运算 E、 代替函数 (也称为选择压缩运算、S-box) 和置换运算 P 组成

DES 的一轮迭代

扩展置换 E-box 32 为扩展到 48 位

代替函数组 S-box 48 位压缩到 32 位

每一组把 6bit 转换成 4bit

具体的 S_1-box \cdots S_8-box 不要求掌握

用例子告诉你怎么把 6bit 转换成 4bit

假设 6bit 数据为 110011

第 1 位和最后 1 位作为行 11_{(2)} = 3_{10}, 二进制 11 转换为十进制 3

中间的作为列 1001_{(2)} = 9_{(10)}, 二进制 1001 转换成十进制 9

所以得到第 3 行第 9 列, 然后查表得出结果

• 注意 : 以上运算的行数和列数都是从 0 开始数

• S 盒的构造
  DES 其它算法都是线性的, 而 S-box 是非线性的

  它的密码强度决定了整个算法的安全强度

置换运算 P

其构造准则 :

• P 置换的目的是提供雪崩效应

• 明文或密钥的一点小变动都引起密文的较大变化

DES 的解密过程

解密算法与加密过程是完全一样的, 只是各个子密钥的顺序相反, 即 K_{16} K_{15} \cdots K_1

DES 的安全弱点

1. 密钥较短

2. 存在若密钥
   4 个弱密钥 + 12 个半弱密钥 + 48 个半半弱密钥 = 64

3. 存在互补对称性

2 DES 与 3 DES

DES 的密钥 K 为 56 位

2 DES : K \times 2 = 112 位, 也就是 K_1 K_2

3 DES : K \times 3 = 163 位, 也就是 K_1 K_2 K_3

2 DES 流程图 :

AES

AES 采用 Square 结构

AES 轮数不固定, 有 10/12/14 轮迭代

其根据密钥长度来迭代

密钥长度 (bit)	迭代轮数
128	10
192	12
256	14

Square 结构的基本运算有字节代换 (SubBytes)、行移位 (ShiftRows)、列混淆 (MixColumns)、轮密钥加 (AddRoundKey)

DES 是按比特加密, AES 是按字节加密

AES 总的加密流程图如下 (以 128bit 密钥为例):

字节代替 SubBytes

首先需要说明的是, 16 字节的名文块在每一个处理步骤中都被排列成 4 \times 4 的二维数组

所谓字节代替, 就是把明文块的每一个字节都代替成另一个字节, 替代的依据是一个被称为 S 盒 (Subtitution Box) 的 16 \times 16 大小的二维常量数组

假设明文块中 a[2, 2] = 5B (一个字节是 2 位 16 进制), 那么输出值 b[2,2] = S[5][11]

行移位 ShiftRows

注意下标, 这里是从 0 开始数

第一行不变

第二行循环左移1个字节

第三行循环左移2个字节

第四行循环左移3个字节

列混淆 MixColumns

这一步, 输入数组的每一列要和一个名为修补矩阵（fixed matrix）的二维常量数组做矩阵相乘, 得到对应的输出列

这个修补矩阵就是

正向列混淆就是 S 左乘 上面的矩阵得到 S'

逆向列混淆则是 S' 左乘 下面的矩阵得到 S

此处的乘法和加法都是定义在 GF(2^8) 上面的, 需要注意以下几点 :

1. 将某个字节对应值乘以 2, 其结果就是将该值的二进制位左移一位 (右边补 0), 如果原始值的最高位为 1, 则还需要将移位后的结果与 0001 1001 异或

2. x \times 03, 结果为 (x \times 02) \bigoplus x

GF(2^8) 上的加法都是异或运算

轮密钥加 AddRoundKey

这一步是唯一利用到密钥的一步, 128bit 的密钥也同样被排列成 4 \times 4 的矩阵

让输入数组的每一个字节 a[i,j] 与密钥对应位置的字节 k[i,j] 异或一次, 就生成了输出值 b[i,j]

需要补充一点, 加密的每一轮所用到的密钥并不是相同的. 这里涉及到一个概念：扩展密钥(KeyExpansions)

扩展密钥 KeyExpansions

AES 源代码中用长度 4 \times 4 \times (10 + 1) 字节的数组 w 来存储所有轮的密钥. w{0 - 15} 的值等同于原始密钥的值, 用于为初始轮做处理

后续每一个元素 w[i] 都是由 w[i - 4] 和 w[i - 1] 计算而来, 直到数组 w 的所有元素都赋值完成

w 数组当中, w{0 - 15} 用于初始轮的处理, w{16 - 31} 用于第 1 轮的处理, w{32 - 47} 用于第 2 轮的处理, 一直到 w{160 - 175} 用于最终轮 (第 10 轮) 的处理

解密就是把加密流程倒置过来, 顺序变为最终轮 \rightarrow 普通轮 \rightarrow 初始轮, 扩展密钥的使用顺序也和加密相反

---

接下来我们来详细解释这个密钥扩展算法

AES 首先将初始密钥输入到一个 4 \times 4 状态矩阵中

第一列就是 W[0], 第二列就是 W[1], 第三列就是 W[2], 第四列就是 W[3]

这个 4 \times 4 矩阵的每一列的 4 个字节组成一个字, 矩阵 4 列的 4 个字依次命名为 W[0] W[1] W[2] W[3], 它们构成一个以字为单位的数组 W_0

我们举例说明, 设密钥 k 为 "abcdefghijklmnop"

接着, 对 W 数组扩充 40 个新列, 构成总共 44 列的扩展密钥数组. 新的列以如下方式递归产生 :

1. 如果 i 不是 4 的倍数, 那么第 i 列由如下等式确定
   W[i] = W[i - 4] \bigoplus W[i - 1]

2. 如果 i 是 4 的倍数, 那么第 i 列由如下等式确定
   W[i] = W[I - 4] \bigoplus T(W[I - 1])

我们来看这里面的函数 T, 函数 T 由 3 个部分组成 :

• 字循环 : 将 1 个字中的 4 字节循环左移 1 个字节

• 字节代换 : 对字循环的结果使用 S 盒进行字节代换

• 轮常量异或 : 将前两步的结果同轮常量 Rcon[j] 进行异或, 其中 j 表示轮数

Rcon[j] 是一个字, 其值见下表 (j 为轮数) :

j	1	2	3	4	5
Rcon[j]	01 00 00 00	02 00 00 00	04 00 00 00	08 00 00 00	10 00 00 00

j	6	7	8	9	10
Rcon[i]	20 00 00 00	40 00 00 00	80 00 00 00	1B 00 00 00	36 00 00 00

还是举个例子, 设初始 128 位密钥为 : 3C A1 0B 21 57 F0 19 16 90 2E 13 80 AC CA 07 BD

那么 4 个初始值为:

W[0] = 3C A1 0B 21

W[1] = 57 F0 19 16

W[2] = 90 2E 13 80

W[3] = AC C1 07 BD

接下来求扩展的第 1 轮的子密钥 (W[4], W[5], W[6], W[7])

由于 4 为 4 的倍数, 所以 W[4] = W[0] \bigoplus T(W[3])

T(W[3]) 的计算如下 :

1. 循环地将 W[3] 的元素移位 : AC C1 07 BD \Rightarrow C1 07BD AC

2. 将 C1 07 BD AC 作为 S 盒输入, 输出 78 C5 7A 91

3. 将 78 C5 7A 91 与第一轮轮常量 Rcon[1] 进行异或运算, 得到 79 C5 7A 91

T(W[3]) = 79 C5 7A 91

故 W[4] = 3C A1 0B 21 \bigoplus 79 C5 7A 91 = 45 64 71 B0

同理, W[5] = 12 94 68 A6

W[6] = 82 BA 7B 26

W[7] = 2E 7B 7C 9B

\Rightarrow 第一轮密钥为 45 64 71 B0 12 94 68 A6 82 BA 7B 26 2E 7B 7C 9B

RC4

RC4 加密算法分两部分, 初始化 KSA 和伪随机子密钥生成器 PRGA

RC4 初始化

1. 初始化 S-Box (用 n 个数据填充 S-Box, 0 < n < 257, n 为整数) 1~256
   00 01 02 ... n-1

2. 初始化 K-Box (用密钥比如 : 123456 的 Ascii 码填充 n 个 K-Box 空位)
   31 32 33 ... 31 32 33 ...

3. 生成置换 S-Box
   通过将 S-Box 中每个元素与 K_Box 中另一个元素交换的方式, 打乱 S-Box 排列顺序

下面用伪代码来描述

i = k = j = 0;              // 取 S 盒中第一个元素 00
s[i] = i;                   // 取 k 盒中第一个元素 31
i = (j + s[i] + k[i]) % n;  // 与 S 盒中第一个元素交换 S 盒元素序号
swap(s[i], s[j]);           // i = (0 + 00 + 31) % n, 设 n 为 8 则 j = 7, 将 S 盒第 1 个元素与第 7 个元素交换

RC4 伪随机密钥生成

RC4 加密过程中, 为每一个待加密的字节生成一个伪随机数, 将生成的伪随机数与明文对应字节进行异或运算生成密文

伪代码描述

i = j = k =0;
i = (i + 1) % n;
j = (j + s[i]) % n;
swap(s[i], s[j])

随机值在 S-Box 中的序号 k = (s[i] + s[j]) % n

迭代值 R = s[k]

最后明文与迭代值进行异或即可得到密文

举例演示

明文 : security

密钥 : 12345

S-Box 元素个数 n = 8

初始 S-Box : 00 01 02 03 04 05 06

初始 K-Box : 31 32 33 34 35 31 32 33

置换 S-Box : 06 00 01 04 03 07 05 02

迭代值 05 02 07 07 04 01 05 04

将明文异或迭代值得到密文 : 76 67 64 72 76 68 71 7D

公钥密码

非对称加密就是, 公钥用来加密, 私钥用来解密

DH 密钥交换算法

流程

小明加密的时候, 首先选一个素数和一个底数 (本原根).

例如, 素数 p = 23, 底数 g = 5 (底数可以任选), 再选择一个秘密整数私钥 d_a = 6, 计算公钥 K_A = g^a mod p = 8

然后就可以把 p = 23, g = 5, K_A = 8 传给女神

女神收到之后, 也选一个秘密整数私钥 d_b = 15, 然后计算公钥 K_B = g^b mod p = 2

小明自己计算出密码 (也就是共同密钥) s = B^a mod p = 2, 女神也自己计算出密码 s = A^b mod p = 2, 于是, 小明和女神最终协商的密码 s 为 2.

本原根的求法

有些题目要求单独计算本原根, 我们再来看看本原根, 也就是底数的求法.

1. 生成一个大素数 q, 直接 p 是素数, 其中 p = 2q + 1

2. 生成一个随机数 g, 1 < g < p - 1, 直到 g^2 mod p \neq 1 并且 g^q mod p \neq 1

3. 得到 g 是 p 的本原根

RSA

RSA 算法, 我们请来 Alice 和 Balbo 来帮我们说明加密流程

乘法逆元

RSA 常用的是 1024bit 密钥

因为这里加密解密数字比较大, 这里就涉及到了快速幂指数运算 快速幂

椭圆曲线 ECC

椭圆曲线的定义

椭圆曲线并不是椭圆, 它名字叫椭圆曲线是因为它的方程和椭圆的面积公式很相似, 真正的椭圆是叫圆锥曲线

椭圆曲线是两个变元 x, y 满足形如三次方程 y^2 +a \cdot xy + by = x^3 + c \cdot x^2 + d \cdot x + e 的所有点的集合, 外加一个零点或者无穷远点 O. (这个方程也叫维尔斯特拉斯方程, Weierstrass)

其中 a, b 是实数, x 和 y 在实数域上取值. 上述方程可以通过坐标变换转化为 y^2 = x^3 + ax + b

它整个方程完全依赖于 a 和 b 的取值, 由该方程确定的椭圆曲线常记为 E(a, b), 简记为 E

当 4a^3 + 27b^2 \neq 0 时, 称 E(a, b) 是一条非奇异椭圆曲线. 对于非奇异椭圆曲线, 可以基于集合 E(a, b) 定义一个群

这是一个阿贝尔群 (Abel), 具有重要的 "加法规则" 属性. 下面首先给出加法规则的几何描述, 然后给出加法规则的代数描述

如果你学过 C++ 的话, 可以把这个加法规则理解为对 + 加号的运算符重载

• 加法的几何描述

如果椭圆曲线上的 3 个点位于同一直线上, 那么它们的和为 0 (无穷远点或者说零点)

于是我们可以得到椭圆曲线所有的加法规则 :

1. 假设 O 为加法的单位元, 对于椭圆曲线上的任何一点 P, 有 P + O = P

2. 对于椭圆曲线上的一点 P = (x, y), 它的逆元为 -P = (x, -y) 也就是关于 x 轴对称的点
   注意 P + (-P) = P - P = 0

3. 设 P, Q 是椭圆曲线上 x 坐标不同的两点, P + Q 定义如下 :
   作一条通过 P 和 Q 的直线 l 与椭圆曲线相交于 R (这个 R 点是唯一的除非这条直线在 P 点或者 Q 点与椭圆曲线相切, 此时分别取 R = P 或者 R = Q), 然后过 R 点作 y 轴的平行线 l', l' 与椭圆曲线相交的另一个点 S 就是 P + Q, 如下图所示

   

   如果我们想算 P + Q, 我们直接把 P Q 两点连接起来形成一条直线, 该直线一定会与椭圆曲线相交于一点 R, 然后通过 R 作一条 y 轴的平行线 l', l' 与椭圆曲线相交于另一点 S, S 就可以被定义为 P + Q 的取值

4. 上述几何描述也适用于具有相同 x 坐标的两个点 P 和 -P 的情况, 用一条垂直的线连接这两个点, 可以看作是在无穷远点与椭圆曲线相交, 因此有 P + (-P) = 0

5. 为了计算点 Q 的两倍, 在 Q 点作一条切线并找到与椭圆曲线的另一个交点 T, 则 Q + Q = 2Q = -T

以上定义的加法满足加法运算的一般性质, 比如交换律结合律等

• 加法的代数描述

几何描述用于理解, 代数描述用于计算

对于椭圆曲线上不互为逆元的两点 P = (x, y) 和 Q = (x_2, y_2), P 和 Q 不关于 x 轴对称.

S = P + Q = (x_3, y_3) 由以下规则确定 :

x_3 = \lambda^2 - x_1 - x_2 y_3 = \lambda (x_1 - x_3) - y_1

其中

\lambda = \frac {y_2 - y_1} {x_2 - x1}, P \neq Q \lambda = \frac {3x^2_1 + a} {2y_1}, P = Q

有限域上的椭圆曲线

为啥我们不用实数域上面的椭圆曲线来搞密码 ? 因为机器没法实现这个事情.

椭圆曲线密码体制使用的是在有限域上面的椭圆曲线, 即变量和系数均为有限域中的元素. 有限域 GF(P) 上的椭圆曲线是指满足方程 y^3 \equiv x^3 + ax +b (mod P) 的所有点 (x, y) 再加上一个无穷远点 O 构成的集合, 其中 a b x 和 y 均在有限域 GF(P) 上取值, P 是素数. 这里把该椭圆曲线记为 E_P(a, b) 该椭圆曲线只有有限个点, 其个数 N 由 Hasse 定理确定.

\equiv 表示同余, 就是同时除以 P 的时候, y^3 和 x^3 + ax + b 有相同余数, 这个也可以称为 y^3 在 mod P 情况下与 x^3 + ax +b 同余

Hasse 定理 : 设 E 是有限域 GF(P) 上的椭圆曲线, N 是 E 上点的个数, 则 P + 1 - 2\sqrt{P} \leq N \leq P + 1 + 2\sqrt{P}

当 4a^3 + 27b^2(mod P) \neq 0 时, 基于集合 E_P(a, b) 可以定义一个 Abel 群, 其加法规则与实数域上描述的代数方法一致. 设 P, Q \in E_P(a, b) 则

1. P + O = P

2. 如果 P = (x, y), 那么 (x, y) + (x, -y) = 0 即点 (x, -y) 是 P 的加法逆元, 表示为 -P

3. 设 P = (x_1, y_1) 和 Q = (x_2, y_2), P \neq Q, 则 S = P + Q = (x_3, y_3) 由以下规则确定 :

   x_3 \equiv \lambda^2 - x_1 - x_2 (mod P) y_3 \equiv \lambda(x_1 - x_3) - y_1(modP)

   其中

   \lambda \equiv \frac{y_2 - y_1} {x_2 - x_1}(mod P), P neq Q \lambda \equiv \frac{3x_1^2 + a} {2y_1}(mod P), P = Q

4. 倍点运算定义为重复加法, 比如 4P = P + P + P + P

例 : 设 P = 11, a = 1, b = 6, 即椭圆曲线方程为 y^2 \equiv x^3 + x + 6(mod 11)

要确定椭圆曲线上的点, 对每个 x \in GF(11), 首先计算 z \equiv x^3 + x + 6 (mod 11)

然后再判定 z 是否是模 11 的平方剩余 (也就是方程 y^2 \equiv z mod 11 是否有解), 若不是 (也就是方程无解), 则椭圆曲线上没有与这一 x 相对应的点; 若是, 则求出 z 的两个平方根. 该椭圆曲线上的点如下表所示 :

x	0	1	2	3	4	5	6	7	8	9	10
x^3 + x + 6 (mod 11)	6	8	5	3	8	4	8	4	9	7	4
是否为模 11 的平方剩余	否	否	是	是	否	是	否	是	是	否	是
y			4	5		2		2	3		2
y			7	6		9		9	8		9

只有 x = 2, 3, 5, 7, 8, 10 时才有点再椭圆曲线上, E_{11}(1, 6) 是由表中的点再加上一个无穷远点 O 构成, 即 E_{11}(1, 6) = {O, (2, 4), (2, 7), (3, 5), (3, 6), (5, 2), (5, 9), (7, 2), (7, 9), (8, 3), (8, 8), (10, 2), (10, 9)}

设 P = (2, 7), 计算 2P = P + P, 首先计算

\lambda \equiv \frac{3 \times 2^2 + 1}{2 \times 7} (mod 11) = \frac{2}{3}(mod 11) \equiv 8

于是

x_3 \equiv 8^2 - 2 - 2 (mod 11) \equiv 5 y_3 \equiv 8 \times (2 - 5) - 7 (mod 11) \equiv 2

所以 2P = (5, 2), 2P 这个点其实也在我们的点集中

同样我们可以算出 3P = (8, 3) 4P = (10, 2) 5P = (3, 6) 6P = (7, 9) 7P = (7, 2) 8P = (3, 5) 9P = (10, 9) 10P = (8, 8) 11P = (5, 9) 12P = (2, 4) 13P = O

由此可以看出, E_{11}(1, 6) 是一个循环群, 其生成元是 P = (2, 7)

椭圆曲线密码学

为了使用椭圆曲线来构造密码体制, 我们需要找到类似大整数因子分解或者离散对数这样的问题来保证密码的安全性.

定义 1 : 椭圆曲线 E_P(1, b) 上的点 P 的阶是指满足 nP = P + P + \cdots + P (n 个 P)= O 的最小正整数, 记为 ord(P), 其中 O 是无穷远点

定义 2 : 设 G 是椭圆曲线 E_P(a, b) 上的一个循环子群, P 是 G 的一个生成元, Q \in G. 已知 P 和 Q, 求满足 mP = Q 的整数 m, 0 \leq m \leq ord(P) - 1

这个就称为椭圆曲线上的离散对数问题 (elliptic curve discrete logarithm problem, ECDLP), 计算 mP 的过程称为点乘运算 (Point multi-plication)

在使用一个椭圆曲线密码体制时, 首先需要将发送的明文 m 编码为椭圆曲线上面的点 P_m = (x_m, y_m), 然后再对 点 P_m 做加密变换, 在解密后还得将点 P_m 逆向译码才能获得明文.

下面对椭圆曲线上的 ElGamal 密码体制做一个介绍

1. 密钥生成 (KeyGen)
   在椭圆曲线 E_p(a , b) 上选取一个阶为 n (n 为一个大整数) 的生成元 P. 随机选取整数 x (1 < x < n), 计算 Q = xP. 公钥为 Q, 私钥为 x. (Q 也是该群上的一个点)

2. 加密 (Encrypt)
   为了加密 P_m, 随机选取一个整数 k, 1 < k < n, 计算 C_1 = kP, C_2 = P_m + kQ, 则密文 c = (C_1, C_2)

   C_1 为 k 个 P 点相加, C_1 也在这个群上

   C_2, P_m 是编码后的点, kQ 同上

   所以 C_1 和 C_2 都是椭圆曲线上的点

3. 解密 (Decrypt)
   为了解密一个密文 c = (C_1, C_2), 计算 C_2 - xC_1 即可, 因为 C_2 - xC_1= P_m + kQ - xkP = P_m + kxP - xkP = P_m, 我们的 k 被消去了

攻击者要想从 c = (C_1, C_2) 计算出 P_m, 就必须知道 k, 而要从 P 和 kP 中计算出 k, 攻击者将要面临求解椭圆曲线上的离散对数问题

• 下面说明如何将明文消息编码到椭圆曲线上 :

设明文消息为 m, k 是一个足够大的整数, 使得将明文消息嵌入到椭圆曲线上时, 错误概率是 2^{-k}. 如果 k = 30, 对明文 m, 如下计算一系列 x:

x = {mk + j, j = 0, 1 ,2, 3, \cdots} = {30m, 30m + 1, 30m + 2, cdots}

直到 x^3 + ax + b (mod P) 有平方根, 则得到点 (x, \sqrt{x^3 + ax + b})

反过来, 从椭圆曲线点 (x, y) 得到明文消息 m, 只需求出 m = \frac{x}{30}

密码学中的数据完整性算法

Hash 函数

Hash 函数的定义

将任意长的消息 M 映射为较短的、固定长度的一个值 H(M)

Hash 函数也称为哈希函数、散列函数、压缩函数、杂凑函数、指纹函数等. 其函数值 H(M) 为哈希值、散列值、杂凑码、指纹、消息摘要等

Hash 函数 H 一般是公开的

由 Hash 函数定义我们知道, Hash 函数是多对一的映射, 也就是说同一个 Hash 值, 有多个消息与之对应

我们用一个例子介绍简单的 Hash 函数

M 是一个长消息, 设 M =(M_1, M_2, \cdots, M_k,其中 M_i 为 l 长的比特串, 定义函数 H 如下 :

H(m) = M_1 \bigoplus M_2 \bigoplus \cdots \bigoplus M_k

显然函数 H 可以接收任意长度 M, 输出固定长度, 所以 H 是一个 Hash 函数

该函数提供一种错误检测能力, 也就是改变消息中任何一个比特或者几个比特, 都可能使得 Hash 值发生变化

但是这个函数是否真的能够提供这种错误检测能力呢 ? 下面我们看看 Hash 函数安全性定义

Hash 函数满足条件以及安全性定义

Hash 函数的目的是为需要认证的数据产生一个 "指纹", Hash 函数应该满足以下几个条件 :

1. Hash 函数的输入可以是任意长

2. Hash 函数的输出是固定长

3. 易于在软件和硬件上实现

但是 Hash 函数是多对一的, 就是不同的消息会有相同的指纹, 因此我们需要一些其它的安全条件来保障和实现它的安全认证功能. 我们给出下面几种安全性的定义 :

1. 单向性 : 已知 x, 求 H(x) 较为容易; 但是, 已知 H(x) 去求使得 H(x) = h 的 x 在计算上是不可行的, 就是求不出来 x.

2. 抗弱碰撞性 : 已知 x, 找出 y (y \neq x) 使得 H(y) = H(x) 在计算上是不可行的

3. 抗强碰撞性 : 找出任意两个不同的输入 x, y, 使得 H(y) = H(x) 在计算上是不可行的

我们回到上面那个例子 :

M 是一个长消息, 设 M =(M_1, M_2, \cdots, M_k),其中 M_i 为 l 长的比特串, 定义函数 H 如下 :

H(m) = M_1 \bigoplus M_2 \bigoplus \cdots \bigoplus M_k

我们看看它满足哪些安全性定义

• 单向性

• 不满足强抗碰撞性

• 不满足抗弱碰撞性

我们下面来考虑三个安全性定义的关系

任何一个 Hash 函数, 如果满足抗强碰撞性, 其一定满足抗弱碰撞性, 也一定满足单向性

Hash 函数迭代构造

我们首先把消息进行分组, 分为固定长度的 b 比特, 最后一个分组不足 b 比特的时候需要填充到 b 比特, 最后一个分组还包括输入长度

Hash 函数反复使用压缩函数 M, 它的输入是前一步 n 比特输入和 b 比特分组. 我们把前一步的 n 比特输入称为连接变量, 连接变量的初始值是由算法开始时指定, 最终值 CH_L 为哈希值, 该算法广泛使用于各种哈希算法中

如果压缩函数具有抗碰撞能力, 那么迭代型哈希函数就具有抗碰撞能力, 因此哈希函数常使用这种迭代结构

生日攻击

生日攻击的相关问题

• 问题 1 : 第 1 类生日攻击问题
  • 已知一杂凑函数 H 有 n 个可能的输出, H(x) 是一个特定的输出, 如果对 H 随机取 k 个输入, 则至少有一个输入 y 使得 H(y) = H(x) 的概率为 0.5 时, k 有多大 ?

MD5

SHA-1

消息认证

中国商用密码

SM4 对称加密算法

其它

初等变换求逆矩阵

乘法逆元

• 定义 : 若在 mod P 意义下, 对于一个整数 a, 有 a \times x \equiv 1 (mod P), 那么这个整数 x 即为 a 的乘法逆元, 同时 a 也为 x 的乘法逆元

• a 存在模 P 的乘法逆元的充要条件是 gcd(a, P) = 1, 也就是 a 与 P 互质

有了乘法逆元之后, 求 (a/b) % P 等同于求 (a \times b的逆元) % P

设 b 的乘法逆元为 x

则 b \times x \equiv 1 (mod P) \Rightarrow (b \times x) mod P = 1 mod P

从而解决了 (a/b) % P 除法掉精度以及没有分配率的问题 (转换成乘法就不会掉精度并且有分配率)

• 那么新的问题来了, 怎么求这个 b 的乘法逆元 ?

• 求解逆元的方法有费马小定理 (P 为质数)、扩展欧几里得算法、线性递推......

• 费马小定理 : 假如 a 是一个整数, P 是一个质数, 那么

1. 如果 a 是 P 的倍数, a^P \equiv a (mod P)

2. 如果 a 不是 P 的倍数, a^{(P-1)} \equiv 1 (mod P)

\because a 存在模 P 的乘法逆元的充要条件是 a 与 P 互质, gcd(a, P) = 1

\therefore a 不是 P 的倍数 \Rightarrow a^{(P-1)} \equiv (mod P)

\Rightarrow a \times a^{(P-2)} \equiv 1 (mod P) \Rightarrow 根据定义, a^{(P-2)} 即为 a 的乘法逆元

\Rightarrow (a mod P) \times (a^{(P-2)} mod P) = 1 mod P

一般 P 为一个大质数, 所以我们求 a^{(P-2)} 一般用快速幂 快速幂

快速幂

a, m 为正整数

我们把 m 表示为二进制 : b_kb_{k-1} \cdots b_0 也就是

m = b_k \cdot 2^k + b_{k-1} \cdot 2^{k-1} + \cdots + b_1 \cdot 2 + b_0 \Rightarrow a^m = (\cdots(((a^{b_k})^2a^{b_{k-1}})^2 \cdots a^{b_1})^2 \cdot a^{b_0}

举个例子, 比如说我们要求 3^{596}

首先得到 596 =1 \times 2^9 + 0 \times 2^8 + 0 \times 2^7 + 1 \times 2^6 + 0 \times 2^5 + 1 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 0 \times 2^0

\Rightarrow 3^{596} = (((((((((3^1)^2 \cdot 3^0)^2 \cdot 3^0)^2 \cdot 3^1)^2 \cdot 3^0)^2 \cdot 3^1)^2 \cdot 3^0)^2 \cdot 3^1)^2 \cdot 3^0)^2 \cdot 3^0

扩展欧几里得算法

求逆元的代码 :

int mod_inverse(int a, int m)
{
    int x, int y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}

把代码转换成流程图

避免出现指针, 方便画流程图, 所以这里选了一个 python 代码

#-*-coding:utf-8-*-
# 扩展欧几里得算法
# 输入m n
# 输出 m n的最大公约数 还有s,t
#
# 默认 m > n

import sys

def exgcd(m, n, x, y):
  if n == 0:
    x = 1
    y = 0
    return (m, x, y)
  a1 = b = 1
  a = b1 = 0
  c = m
  d = n
  q = int(c / d)
  r = c % d
  while r:
    c = d
    d = r
    t = a1
    a1 = a
    a = t - q * a
    t = b1
    b1 = b
    b = t - q * b
    q = int(c / d)
    r = c % d
  x = a
  y = b
  # d 为 m n 的最大公约数, x, y 为方程的解
  return (d, x, y)

# 从命令行读取 m n 的值
m = int(sys.argv[1])
n = int(sys.argv[2])
ans = exgcd(m, n, 0, 0)

print("gcd(%d, %d) = %d" % (m, n, ans[0]))
print("x = %d, y = %d" % (ans[1], ans[2]))