一夜速成密码学

后天下午要考试了，或者说明天下午。所以开始学密码学。明日事今日毕。

言简意赅，点到为止，力求及格。

PS：笔记没写完，但及格问题不大。

1 密码学基础

了解即可。

推动近代密码学发展的重要理论著作：1949 香农 《The Communication Theory of Secret Systems》

推动现代密码学中公钥密码思想的重要论文：1976 Diffie & Hellman 《密码学的新方向》 非对称密码学。

2 古典密码学

代换密码都无法避免统计分析攻击。

• 单字母单表密码

  • 最简单的加密，普遍形式 $C_i=f(M_i),M_i=f^{-1}(C_i)$，$f$ 为固定一一映射。

  • Caesar：

    • $C_i=(M_i+k)\bmod 26, M_i=(C_i-k)\bmod 26$，约定密钥 $k$.

  • Affine Cipher：

    • $C_i=(aM_i+b)\bmod 26, M_i=a^{-1}(C_i-b)\bmod 26$，约定密钥 $a,b$

  • Mixed Alphabetic Cipher：

    • 给定字母一一映射，进行加密。

• 单字母多表密码

  • 让 $f$ 随着输入变动。即 $f_i=F(i,M_0,\cdots,M_{i-1})$，$C_i=f_i(M_i)$.

  • Vigenere

    • $C_i=(M_i + k_{i \bmod l})\bmod 26$，$M_i=(C_i - k_{i \bmod l})\bmod 26$
    • 将 Caesar 的 $k$ 改成了依赖于字母位置的 $k_{i\bmod l}$.

  • Rotor Machine 轮转密码机

    • 具体原理比较抽象，大概就是每输入一个字母就会改变若干转子状态，从而换一个表。需要输入初始状态和密文进行解密。

  • One Time Pad(OTP) 一次一密

    • 密钥和明文一样长，密钥不可重复使用，一次一密。

    • $C_i =M_i\oplus K_i, M_i=C_i \oplus K_i$

    • 可以提供 perfect security,但不实用。

      • 产生大规模的随机密钥是困难的。
      • 对于每一条发送的消息，需要提供发送方和接收方等长度的密钥，导致庞
        大的密钥分发(key distribution)问题。

    • 若密钥重复使用，若攻击者可发动选择明文攻击，则可获得密钥解密其他密文。

    • 若获取明文异或结果，可利用信息攻击。

      • ​​
      • ​​

• 多字母密码

  • Playfair

    • 挑选单词作为密钥。字母去重后依次填入矩阵。ij​ 当成一个字母。(因为 5*5=25<26)

    • 剩余格按顺序填入未出现字母，得密钥矩阵。

      • ​​

    • 加密：

      • 明文依次取两字符为一组。若一组字母相同，中间插入 x​

      • 在矩阵上：

        • 若两字符同行，取各自右侧字符 $c_{i,j+1 \bmod 5}$.
        • 若两字符同列，取各自下侧字符 $c_{i+1 \bmod 5,j}$.
        • 否则，取构成的子矩阵中，各自的对角字符。取第一个的行、第二个的列，及第二个的行、第一个的列。
        • ​​
        • 如：ra 变 mr，ab 变 bi，er 变 km.

    • 解密：

      • 两两分组解密。
      • 同行取各自左侧，同列取各自上侧。
      • 否则，子矩阵中，取第一个的行、第二个的列及第二个的行、第一个的列。
      • 删去 x. 判别 i/j.
      • 合并。

  • Hill 密码(矩阵加密)

    • $\mathbf{C}=\mathbf{KM}\bmod 26,\mathbf{M}=\mathbf{K}^{-1}\mathbf{C}\bmod 26$，$\mathbf{K}\in\mathbb{R}^{n\times n}$

• 置换密码

  • 打乱明文的顺序。

  • 栅栏密码

    • 原密码串 $M=M_0M_1\cdots M_{n-1}$.
    • 加密串 $C=M_0M_2\cdots M_1 M _3\cdots$
    • 例如：012345​ 变成 024135​

  • 列移位密码

    • 固定列宽 $m$，明文依次填入宽为 $m$ 的矩阵。
    • 给定长为 $m$ 的置换作为密钥，交换矩阵的列，读出交换后的矩阵。
    • ​​
    • ​​
    • 注意：加密按行写置换后按列读，解密按列写逆置换后按行读。

• 密码学攻击方法

  • 穷举攻击：增大密钥。
  • 统计分析攻击：减少明文与密文的统计相关性。
  • 解密变化攻击：算法复杂化。

• 密码攻击环境

  • 唯密文攻击(COA)：只知道密文。
  • 已知明文攻击(KPA)：只知道部分明文和对应密文。
  • 选择明文攻击(CPA)：选择一些明文得到对应密文。
  • 选择密文攻击(CCA)：选择一些密文得到对应明文。

• 密码学五大性质

  • 机密性：保密信息不泄露，加密算法保证。
  • 完整性：检测篡改。指纹校验。
  • 认证性：身份(来源和消息本身)确认(密钥和认证函数相结合)。
  • 不可否认性：无法否认信息生成、签名、接收行为。（数字签名）
  • 可用性：信息资源可以随时提供服务。

3 数据加密标准(DES)

对称密码分为分组密码和流密码。

分组密码：对明文消息分组，按分组加密。
流密码：对明文信息按比特或字节逐个加密。

• 分组密码设计准则

  • 目标：阻止分析出密钥和明文。
  • 混淆(confusion)：使密文和密钥的统计关系变得复杂。即使攻击者得到密文的统计关系，也无法得到密钥。
  • 扩散(diffusion)：将明文的统计特性散布到密文中，明文的每位影响密文多位，密文无法获得明文统计信息。

• 乘积密码思想：顺序执行多个密码变换(Substitution & Permutation)，产生的密码系统强度高于每个基本密码系统。

  • Substitution 对应 S-box，Permutation 对应 P-box.
  • S-box 起 confusion 效果，P-box 起 diffusion 效果。

• Feistel 网络

  • 每组明文分成左右两半 $\text{LE}_0,\text{RE}_0$.

  • 第 $i$ 轮输入为 $\text{LE}_i,\text{RE}_i$，则：

    • $\text{LE}_i=\text{RE}_{i-1}$，$\text{RE}_i = \text{LE}_{i-1}\oplus F(\text{RE}_{i-1},K_i)$
    • 其中 $K_i$ 为第 $i$ 轮子密钥。
    • $F$ 为轮函数(Round Function).

  • Substition: 每轮中，$\text{RE}_{i-1}$ 经过轮函数，再与 $\text{LE}_{i-1}$ 异或

  • Permutation: 代换完成后，交换左右两边。

  • 解密：

    • 基本一致，但使用子密钥的次序相反。先用 $K_n$，再用 $K_{n-1},\cdots$
    • $\text{LD}_1 = \text{RD}_0 = \text{LE}_n=\text{RE}_{n-1}$，$\text{RD}_1=\text{LD}_0\oplus F(\text{RD}_0,K_n) = \text{RE}_n \oplus F(\text{LE}_n,K_n)=\text{LE}_{n-1}$
    • 利用二次异或抵消。
    • 最终 $\text{LD}_n=\text{RE}_0,\text{RD}_n=\text{LE}_0$，交换即可得到原始明文。

  • 参数与特性关联：

    • 分组长度：越长越安全，但计算越慢。
    • 密钥长度：越长越安全，但越慢。
    • 迭代轮数
    • 子密钥生成算法
    • 轮函数

DES，极为流行的数据加密标准。分组密码算法。

• 加密

  • 64bits 明文。56bits key.

  • 初始置换重排序。

  • 进行 16 轮变换。

  • 结果左右交换，进行逆初始置换得到 64bits 密文。

  • 子密钥生成：

    • 初始时，密钥进入置换函数。
    • 每一轮，通过左循环移位。置换选择产生一个 subkey.
    • 左循环移位经过进入下一轮输入。
    • ​​

  • 每轮加密：输入 64bits 和 48bits subkey

    • $L_i=R_{i-1},R_i=L_{i-1}\oplus F(R_{i-1},K_i)$.
    • 根据拓展表，将 $R_{i-1}$ 重复某些 bits，扩展为 48bits. 与 subkey 异或，结果通过 S-box 产生 32bits，再通过 P-box 即为 $F(R_{i-1},K_i)$.
    • ​​
    • Substitution 有 8 个 S-box,输入 6bits,输出 4bits. 最高位最低为选行，其余选列。
    • ​​
    • P-box 就是一个 Permutation.

• 雪崩效应：明文或密钥的某一位变化，导致很多位发生变化。DES 具有雪崩效应。

对应的若干种攻击方式：

• 穷举攻击，密钥 $2^{56}$.

• 差分密码分析：攻击迭代分组密码的选择明文攻击。

  • 通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特。
  • 给定明文差分 $\Delta_P=P_1 \oplus P_2$，密文差分 $\Delta_C =C_1\oplus C_2$ 的概率分布可能泄露密钥比特信息。
  • DES 可以抵抗。

• 线性分析：已知明文攻击。

  • 寻找能够刻画分组密码整体变换的有效线性近似。
  • DES 可以抵抗。

• 穷举攻击仍是最直接有效的 DES 攻击方式。

DES 弱密钥：加密两次恢复原文的密钥。弱密钥使得 DES 中每一轮的子密钥相同。
四个弱密钥：

• 0000000 0000000
• 0000000 FFFFFFF
• FFFFFFF 0000000
• FFFFFFF FFFFFFF

多重 DES：多个密钥加密多次。解密时按逆序解密即可。

二重 DES：用两个密钥顺序加密两次，强度并不等价于 112bits,因为可以中途相遇攻击。类似于双向搜索。给定明文密文，一边枚举加密结果，存入表中。另一边枚举解密结果，寻找表中匹配项即可。

三重 DES 三次加密可使得明文攻击量级增加到 $2^{112}$. 但密钥长度变成了 168bits.
一种方法为：使用两个密钥，K1 加密-K2 解密-K3 加密。简记为 EDE.

4 高级加密标准(AES)

明文密文分组长度为 128bits.
无 Feistel 结构。
密钥长度可变，有 AES-128 AES-192 AES-256 等。不同长度有对应不同轮数。

AES 流程：

​​

代换和置换都将整个分组当成单一矩阵处理。
只在轮密钥加中使用密钥。算法以轮密钥加开始，以轮密钥加结束。
加密算法和解密算法不同。

将 16bytes 看作 $4\times 4$ 的状态矩阵。
密钥看作 $4\times4$ 或 $4\times6$ 或 $4\times 8$ 的状态矩阵。

​​

字节代换就是一个映射而已。不过 AES 的 S-box 有代数意义。
输入的 8bits 考虑为有限域 $GF(2^8)$ 的一个元素，求逆 $B_i'$ 后仿射变换得到 $B_i$.

​​

行移位很简单：第一行不变，第二行循环左移 1,第三行循环左移 2,第四行循环左移 3.

列混淆：状态矩阵左乘上一个固定的混淆矩阵。乘法在有限域 $GF(2^8)$ 上进行，使用的固定不可约多项式为 $x^8+x^4+x^3+x+1$.

轮密钥加则为：子密钥矩阵异或当前状态矩阵，得到更新的状态矩阵。

子密钥通过输入密钥扩展得来。若轮数为 $n$，则生成 $n+1$ 个子密钥！

AES 密钥拓展以 32bits 1word 为单位。
所有子密钥存储在一个密钥拓展数组 $W$ 中。对于 10 轮的 AES128,生成 44 个 words,$|W|=44$.

输入的密钥首先填充开头，随后：

函数 g:

• 输入 1word.
• RotWord：循环左移 1byte.
• SubWord：使用 S-box 对 byte 做代换。
• 将输出的第一个 byte 与轮常量 $RC_i$ 异或得到输出。

目的：增加密钥拓展过程的 non-linearity. 防止不同轮的轮密钥生成方式上的对称性或相似性。

​​

解密时，每层都是加密过程中的逆。

需要实现轮密钥加、列混淆、行移位、字节代换的逆变换。
轮密钥加和行移位是显然的。

列混淆：求相乘矩阵的逆矩阵即可。
字节代换：求解仿射变换的逆和有限域乘法逆。

​​

目前为止对完整版本的 AES 没有比穷举攻击复杂度更低的密码分析攻击。

5 分组密码操作模式

分组加密算法一次只加密一个分组。实际应用中，待加密消息数据量不固定。
如果使用相同密钥加密多个分组，会引发许多安全问题。
需要采用适当的操作模式。

明文信息填充：不为分组长度整数倍时，需要 padding.

PKCS5：设需要填充 $N$ bytes，加上 $N$ 个值为 $N$ 的 byte.
7字节：FD FD FD FD FD FD FD —
填充1字节后: FD FD FD FD FD FD FD 01
8字节： FD FD FD FD FD FD FD FD
填充8字节后: FD FD FD FD FD FD FD FD 08 08 08 08 08 08 08 08

OneAndZeroes Padding：填充一个 1bit,然后填充 0bits.

• 电子密码本，ECB

  • 在给定密钥下，对每个明文分组独立加密。

  • 优点：实现简单。可并行。

  • 缺点：相同明文对应相同密文，无法隐蔽明文分组统计规律。无法抵挡替换攻击。

    • ​​
    • ​​

  • 通常只用于短数据加密。

• 密码分组链接，CBC

  • 加密函数输入：当前明文分组和前一次密文分组的异或。

  • 相同明文分组产生不同密文分组。

  • 给定初始向量 IV. 每次消息加密应当使用新的 IV.

    • 使用中需要防止 IV 被篡改。
    • 攻击者伪造 IV，已知第一个分组明文时，可以让解密方的第一个分组解密结果为任意值，实现篡改。$P_1=D_K(C_1)\oplus IV$.

  • $C_1=E_K(IV\oplus P_1)$，$C_2=E_K(C_1\oplus P_2)$…

  • 解密时，$P_1=D_K(C_1)\oplus IV$，$P_2=D_K(C_2)\oplus C_1$，以此类推。

  • 优点：

    • 隐蔽明文数据模式。
    • 明文一组有错，后续无法解密。可用于数据完整性验证。

  • 缺点：

    • 加密顺序执行，无法并行。解密时若所有密文分组都已经收到，解密本身可以并行。
    • 错误传播导致一个分组出错会影响所有后续分组。

• 实现将分组密码作为流密码使用：

• 密文反馈，CFB

  • 传输数据最小单元 s bits，加密函数输入 b bits，是一个移位寄存器，给定初始值 IV.

  • 加密函数输入 b bits，输出的最高 s bis 和明文的第一个单元 $P_1$ xor 产生第一个密文单元 $C_1$ 传输出去。

  • 寄存器 lshift s bits，低位填充 $C_1$，再次加密…

  • 实际上是将加密算法作为一个密钥流产生器。

  • 解密时，使用的依然是分组算法的加密函数。

  • $C_1=P_1\oplus \text{MSB}_s(E(K,IV))$

  • $P_1=C_1\oplus \text{MSB}_s(E(K,IV))$​

  • $C_2=P_2\oplus \text{MSB}_s(E(K,IV\ll s \mid C_1))$

  • $P_2=C_2\oplus \text{MSB}_s(E(K,IV\ll s \mid C_1))$

  • 优点：

    • 可以按最小传输单元加密。
    • 相同明文产生不同密文。

  • 缺点：

    • 加密无法并行。解密可以并行。
    • 错误传播。一个地方出错影响后续所有。

• 输出反馈，OFB

  • CFB 将每个明文单元产生密文单元反馈到下一个加密函数的输入。

  • OFB 将加密函数的输出反馈到下一个加密函数的输入。

  • ​​

  • 实际上，整个密钥、加密算法输入输出都是独立的。只是生成若干的 $O_i$ 和明文异或而已。感觉和随机数生成器没区别。

  • 解密也一样生成 $O_i$ 然后异或即可。

  • 优点：

    • 无错误传播。
    • 可以预计算加密的密钥流。

  • 缺点：

    • 实时加解密无法并行计算。

• 计数器，CTR

  • ​​
  • 什么纯粹的随机数发生器。。。这样的好处是可以并行了。而且可以随机访问。
  • 但为什么我不直接用随机数生成器呢？

​​

感觉需要掌握几种图的画法。

​​

​​

​​

​​

​​

6 流密码

PRNG：伪随机数发生器，固定种子输入。

• 随机性

  • 分布独立性：位分布均匀，01 频率大约相等。
  • 独立性：任何子序列不能由其他子序列推导出。

• 不可预测性：

  • 给定部分序列，无法预测后续序列部分。

RC4：可变密钥长度、面向字节操作的流密码。以随机置换为基础，实现简单且快。

反馈移位寄存器：大多数新型流密码基于 Feedback Shift Register.

LFSR：

​​

初始为 $a_n,\cdots,a_1$，则输出顺序为 $a_1,\cdots,a_n,a_{n+1},\cdots$

对于整数 $t\ge 1$，$a_{n+t}=c_na_t \oplus c_{n-1}a_{t+1}\oplus \cdots \oplus c_1 a_{t+n-1}$.
特征多项式 $p(x)=1+c_1x^1+\cdots + c_nx^n$.

输出周期与状态周期相等。最大周期为 $N=2^n-1$.
最大周期条件：特征多项式不可约，为本原多项式。

7 有限域

群：$G$ 定义了二元运算 $\cdot$ 的集合，满足：

• 单位元：$\exists e\in G, \text{ s.t. }\forall g\in G, g\cdot e=e\cdot g$
• 逆元：$\forall g \in G, \exists g' \text{ s.t. } g \cdot g' = e = g' \cdot g$
• 封闭性：$\forall g,h\in G, g\cdot h \in G$
• 结合率：$\forall g_1,g_2,g_3\in G, (g_1\cdot g_2)\cdot g_3 = g_1\cdot (g_2\cdot g_3)$

环：$R$ 定义了两个二元运算 $+,\times$ 的集合，满足：

• $R$ 关于 $+$ 为交换群。对于该加法群，用 $0$ 表示单位元，$-a$ 表示 $a$ 的逆元。
• 乘法封闭性：$\forall a,b\in R,a\times b \in R$
• 乘法结合律：$\forall a,b,c\in R,(a\times b)\times c=a\times(b\times c)$
• 乘法交换律：$a\times b = b\times a$
• 乘法单位元1：存在元素 $1$ 使得 $\forall a\in R,a\times1=1\times a=a$
• 无零因子：$\forall a,b\in R,a\times b=0\implies a=0\vee b=0$
• 分配律：$a\times (b+c)=a\times b + a\times c$，$(a+b)\times c = a\times c + b\times c$

环没有规定每个元素有乘法逆元！

域：$F$ 定义了两个二元运算 $+,\times$，满足环的性质，此外存在乘法逆元：

• $\forall a \in F, a \neq 0 \implies (\exists a^{-1} \in F)(a\times a^{-1}=1)$

有限域的阶(元素个数)是素数幂，记为 $GF(p^n)$. 一般密码学中使用 $GF(2^n)$.
其运算为 $\bmod p^n$ 的整数运算。

$\mathbb{Z}_p$ 上的多项式集合 $S$ 包含 $f(x)=\sum \limits _{i=0}^{n-1}a_ix^i$，$a_i=0,1,\cdots,p-1$.
共 $p^n$ 个。

定义运算使得多项式集合 $S$ 构成有限域：

• 系数运算 $\bmod p$.
• 若乘法运算结果得到次数 $>n-1$ 的多项式，将其除以某个次数为 $n$ 的不可约多项式 $m(x)$ 并取余式。$r(x)=f(x)\bmod m(x)$.

​​

$GF(2^n)$ 中的多项式 $f(x)=\sum \limits _{i=0}^{n-1}a_ix^i$，$a_i=0/1$ 可以按位表示。

加法等效于位异或。乘法有一种巧妙的算法。

例如 $m(x)=x^8+x^4+x^3+x+1$，$x^8\bmod m(x) = x^4+x^3+x+1$.

考虑 $f(x) \cdot x = b_7x^8+\cdots + b_0x$，若 $b_7=0$ 结果为 $(b_6,b_5,\cdots,0)$.
否则，就要加上 $x^8\bmod m(x)$. 结果为 $(b_6,b_5,\cdots,0)\oplus (00011011)$.

递推可以得到 $f(x)\cdot x^k$.

8 数论基础

高中残存的记忆。

欧几里德算法：$\gcd(a,b)=\gcd(b,a\bmod b)$.

拓展欧几里德算法：求解 $ax+by=\gcd(a,b)$ 的方程。

这玩意手算怎么算呢？以 $a \times 6107 + b \times 8832 = 1$ 为例。

首先把 gcd 的计算全部写出来：

(8832, 6107)
(6107, 2725)
(2725, 657)
(657, 97)
(97, 75)
(75, 22)
(22, 9)
(9, 4)
(4, 1)
(1, 0)

然后加上末尾项：

(8832, 6107)
(6107, 2725)
(2725, 657)
(657, 97)
(97, 75)
(75, 22)
(22, 9)
(9, 4)
(4, 1)
(1, 0) 1, 0

然后每次：交换 $x,y$，随后 $y:=y-a/b \times x$.

(8832, 6107)
(6107, 2725)
(2725, 657)
(657, 97)
(97, 75) …
(75, 22) 5, -17
(22, 9) -2, 5
(9, 4) 1, -2
(4, 1) 0, 1
(1, 0) 1, 0

费马小定律：$p$ 素数，$a$ 正整数，$a^{p-1}\equiv 1\pmod p$.

欧拉函数：$\phi(n)$ 为小于 $n$ 中和 $n$ 互素的正整数个数。
欧拉函数满足积性，若 $n=pq$ 且 $\gcd(p,q)=1$，则 $\phi(n)=\phi(p)\phi(q)$.

欧拉定理：$\gcd(a,n)=1$则 $a^{\phi(n)}\equiv 1 \pmod n$.
另一种表述：任意 $a,n$，$a^{\phi(n)+1}\equiv a\pmod n$
拓展了费马小定律，应用于非素模数。

Miller-Rabin 素性测试。

Lemma1: $p$ 为奇素数，则 $x^2\equiv 1\pmod p$ 的解为 $x\equiv 1 \pmod p$ 或 $x\equiv p-1 \pmod p$.

Lemma2: $p$ 为奇素数，则 $p-1=2^kq,k > 0$，$q$ 为奇数。设 $a\in(1,p-1)$ 且为整数，下面两个条件之一成立：$a^q\equiv 1 \pmod p$，$\exists 1 \le j \le k , a^{2^{j-1}q}\equiv p-1\pmod p$.

测试 $n$ 是否为奇数，我们可以：

• 首先 $n-1=2^k q$，不断除以 $2$ 得出 $k,q$.
• 选取 $a\in(1,n-1) \cap \mathbb{N}$.
• 若 $a^q\bmod n \neq 1 \wedge a^q\bmod n \neq n-1$，断定为合数。
• 枚举 $j=1,2,\cdots$，若 $a^{2^j q} \bmod n \neq n-1$，断定为合数。
• 经过检测，断定为素数。

一般选取若干个基底，进行若干次检测。

中国剩余定理：模数两两互素 $m_1,\cdots,m_k$，同余方程组：

对模 $M=\prod m_i$ 有唯一解。即 $x \equiv \sum a_iM_i e_i \pmod M$.
其中 $M_i=M\div m_i$，$e_i$ 定义为 $e_i M_i\equiv 1 \pmod {m_i}$.

模数 $n$ 的本原根 $a$ 满足 $a^1,\cdots,a^{\varphi(n)}$ 互不相同且与 $n$ 互素。

对于素数 $p$，其本原根 $a$ 的幂能产生模 $p$ 下的非零整数集 $(1,2,\cdots,p-1)$.

不是所有整数都有本原根。

离散对数：对于素数 $p$ 的本原根 $a$，任意整数都有唯一幂次满足 $b \equiv a^i \pmod p, i \in[1,p-1]$.
称 $i=\operatorname{dlog}_{a,p}(b)$，为 $b$ 的离散对数。

给定 $a,i,p$ 容易求 $b$，但反过来求解幂次是很难的。BSGS 也只能做到根号级别。

9 公钥密码与 RSA

RSA 参见RSA.

10 其他公钥加密体制

DH 密钥交换：$p$ 为大素数，$g$ 为本原根，$p,g$ 公开。
用户 A 选择保密整数 $a$，发送 $Y_A=g^a\bmod p$.
用户 B 选择保密整数 $b$，发送 $Y_B=g^b\bmod p$.
双方使用自己的保密整数 $x$，和收到的 $Y$，计算 $K=Y^x=g^{ab}\bmod p$ 作为密钥。

只有 $p,g,Y_A,Y_B$ 公开，要想得到 $K$ 只能求离散对数。

DH 密钥交换容易受到中间人攻击。

ElGamal 密码体制，选定素数 $p$，本原根 $g$.
随机生成 $sk_A=a\in [2,\cdots,p-2)$，计算 $pk_A=g^A\bmod p$.
私钥为 $sk_A$，公钥为 $pk_A$.
用户向 A 发送消息 $M$ 时：随机选择整数 $k\in[2,p-2]$，计算 $C_1=g^k\bmod p$.
计算一次性密钥 $K=pk_A^k \bmod p = g^{ak}\bmod p$.
计算 $C_2= KM \bmod p$.
发送 $(C_1,C_2) = (g^k, M \cdot g^{ak})$ 给 A.

A 收到后，利用 $C_1=g^k$ 计算 $g^{ak}$，求逆乘上 $C_2$ 得 $M$.

若待加密数据分组后使用 ElGamal 加密，则每组需要使用不同的整数 $k$.
否则若泄露其中一个明文分组，可直接在不知道私钥的情况下破译其他明文分组。

​​

椭圆曲线密码体制：基于广义离散对数问题。

ECC 中，椭圆曲线方程为 $y^2=x^3+ax+b$.

由方程 $y^2=x^3+ax+b$ 确定的椭圆曲线记为 $E(a,b)$，包含满足该方程的所有点和无穷远点 $O$.
当 $4a^3+27b^2 \neq0$ 时，可以基于集合 $E(a,b)$ 定义二元运算，使其成为一个交换群。用加法 $+$ 表示。

• $O$ 为加法单位元，对于椭圆曲线上任一点，$P+O=P$.

• 对于一点 $P=(x_P,y_P)$，其加法逆元为 $-P=(x_P,-y_P)$，$P+(-P)=P-P=O$.

• 给定两点及坐标 $P=(x_P,y_P),Q(x_Q,y_Q)$，加法定义为：

  • 当 $P,Q$ 不同时，计算 $PQ$ 与椭圆曲线的交点关于 $x$ 轴的对称点 $R$，为 $P+Q=R$.
  • ​​
  • $P,Q$ 相同时，即为切线交点的对称点。
  • ​​

对于不互为逆元的两点 $P(x_P,y_P),Q(x_Q,y_Q)$，直线斜率为 $\Delta=(y_Q-y_P)\div (x_Q-x_P)$，计算得到 $x_R=\Delta^2 - x_P - x_Q$，$y_R=\Delta(x_P-x_R)-y_P$.

切线自己算吧。跟 $a$ 有关。

在有限域上定义椭圆曲线，$y^2\equiv x^3+ax+b\pmod p$.

​​

运算是类似的，除了除法要用逆元算。

​​

椭圆曲线上离散对数问题求解困难，即 $Q=kP$，给定 $k,P$ 算 $Q$ 是容易的，但给定 $P,Q$ 算 $k$ 是困难的。

求 $kP$ 可以用快速乘的思想。

11 哈希函数

高中写过了一些相关内容。哈希表 字符串哈希

• 哈希函数的要求

  • 单向性：已知 $x$，求 $h=H(x)$ 容易。已知 $h$ 求 $x$ 是不可行的。
  • 抗弱碰撞性：已知 $x$，求 $y \neq x$ 满足 $H(x)=H(y)$ 在计算上是不可行的。
  • 抗强碰撞性：找出任意两个不同的 $x \neq x'$ 满足 $H(x)=H(x')$ 在计算上是不可行的。

……后面的大概扫了一眼，不想详细写了。还有 MAC 啊数字签名之类的。