密码学笔记

This is a placeholder for the excerpt.

数学基础¶

贝祖恒等式¶

贝祖恒等式：\(ax + by = gcd(a, b)\)，其中 \(x, y\) 为整数（可以为负数）。当 \(a, b\) 互质时，\(x, y\) 为 \(a, b\) 的模逆元。

模逆元¶

加法逆元：古典密码学，例如凯撒密码、仿射密码会用到。古典密码学不能够抗频率分析。

乘法逆元：使用扩展欧几里得算法求解。例如求解 \(x, y\) 使得 \(13x = 1 \mod 35\)：

欧几里得算法将每一个没有出现的数用已知的数表示，然后逐步替换，直到得到最终的结果。

35 = 2 * 13 + 9
         13 = 1 * 9 + 4
                  9 = 2 * 4 + 1

=> 1 = 9 - 2 * 4 
     = (35 - 2 * 13) - 2 * (13 - 1 * 9)
     = 35 * 1 - 2 * 13 - 2 * 13 + 2 * 9
     = 35 * 1 - 4 * 13 + 2 * (35 - 2 * 13)
     = 35 * 3 - 8 * 13

欧拉函数¶

欧拉函数：小于 \(n\) 且与 \(n\) 互质的数的个数。\(\displaystyle \phi(n) = n \prod_{p|n} (1 - \frac{1}{p})\)。

欧拉定理：\(a^{\phi(n)} = 1 \mod n\)，其中 \(a, n\) 互质。

费马小定理：\(a^{p-1} = 1 \mod p\)，其中 \(p\) 为素数。

从而，如果 \(p, q\) 互质，那么 \(\phi(pq) = (p - 1)(q - 1)\)。

经典的密码学算法¶

哈希函数¶

哈希函数：摘要，单向不可逆函数，用于在不告知具体内容的情况下仍然能够验证内容的完整性。破解方法：空间换时间、彩虹表。

彩虹表：对随机起点，多次哈希（每次哈希之前需要取余数），得到一个链表。只存储链表的头尾，节省空间。破解时，只在末端寻找泄露的哈希值，如果没找到，对原有的起点多次哈希（但总哈希次数减少 1 次），在新的到的链表尾部寻找，直到找到或者哈希次数为 0。彩虹表的初始值：由于无法保证上面的过程生成完整的明文空间，因此，彩虹表不保证一定能够找到，但是可以保证找到的是正确的。

对称加密算法¶

分组密码与流密码：分组密码是将明文分组加密（并且每一组会影响后续的组），流密码是将明文流加密。

DES、AES：对称加密算法，使用相同的密钥进行加密和解密。混淆、扩散。微小的改变会导致密文的巨大变化。

AES：SubBytes、ShiftRows、MixColumns、AddRoundKey。

非对称加密算法¶

RSA：非对称加密算法，使用公钥加密、私钥解密。基于大素数的乘法取模运算。RSA 的安全性基于大整数分解的困难性。

ECC：椭圆曲线加密算法，使用椭圆曲线上的点进行加密。ECC 的安全性基于椭圆曲线上的离散对数问题的困难性。抗量子计算攻击、侧信道攻击。

选择合适的椭圆曲线E和基点G，接收方选择私钥d，计算公钥Q=dG，发送方选择随机数k，计算点C1=kG，C2=kQ，发送C1和C2给接收方，接收方计算C2-dC1，得到明文。

椭圆曲线上的点构成一个群，提供加法运算。

同态加密算法¶

ElGamal：非对称、部分同态性质的加密算法。可以实现对乘法的同态性质，即 \(E(m_1) \cdot E(m_2) = E(m_1 \cdot m_2)\)。

密码学协议¶

数字签名¶

数字签名的原理：Alice 发送报文 M 给 Bob，Alice 拥有自己的私钥 priv 和公钥 pub。

Alice 使用自己的私钥对 Hash(M) 进行加密，得到 Enc(priv, Hash(M))，然后将 M 和 Enc(priv, Hash(M)) 发送给 Bob。

数字签名能够保证报文的完整性和真实性，但是不能保证报文的机密性。

不经意间传输¶

不经意间传输：允许 Alice 向 Bob 传输一组消息，Bob 选择获取其中一个。并且满足：Alice 不能知道 Bob 选择的是哪一个，Bob 不能知道 Alice 传输的其它消息。

1-out-of-2 OT（RSA）：假设 Alice 有消息 \(m_0\) 和 \(m_1\) ，Bob想要获取 \(m_b\) (\(b \in \{0,1\}\))。

Alice 生成 RSA 密钥对，公钥为 \(n, e\)，私钥为 \(d\)。
Alice 生成随机数 \(x_0, x_1\)。
Alice 将公钥 \(n, e\) 和 \(x_0, x_1\) 发送给 Bob。
Bob 选择 \(b\)，生成随机数 \(k\)。
Bob 使用 Alice 的公钥加密 \(k\)，然后使用 \(x_b\) 混淆，并将得到的 \(v\) 发送给 Alice。
- \(v = (x_b + k^e) \mod n\)
Alice 使用私钥解密得到 \(k_0\) 和 \(k_1\)，其中一个等于 \(k\)，但此时 Alice 不知道是哪一个：
- \(k_0 = (v - x_0)^d \mod n\)
- \(k_1 = (v - x_1)^d \mod n\)
Alice 使用一次性密码本加密 \(m_0\) 和 \(m_1\)，并将结果发送给 Bob：
- \(m_0' = m_0 \oplus k_0\)
- \(m_1' = m_1 \oplus k_1\)
Bob 使用选择的 \(b\) 和 \(k\) 解密得到 \(m_b\)：
- \(m_b = m_b' \oplus k\)

秘密共享¶

秘密共享：将一个秘密 \(S\) 分割成 \(n\) 个份额，并分发给 \(n\) 个参与者，使得只有当足够数量 (门限值 \(t\)) 的参与者协作时，才能重构出原始秘密。

基于多项式插值的秘密共享：假设有秘密 \(S\)，门限值 \(t\)，参与者数量 \(n\)：

秘密持有者构建多项式 \(f(x) = S + a_1x + a_2x^2 + \cdots + a_{t-1}x^{t-1}\)，其中 \(a_1, a_2, \cdots, a_{t-1}\) 是随机数。
- \(f(0) = S\)
- 每个参与者 \(i\) 都会得到一个份额 \(f(i)\)。
门限值 \(t\) 个参与者协作，使用拉格朗日插值法重构出原始秘密 \(S\)。
- 解密的过程就是解出多项式 \(f(x)\) 的系数的过程，这是一个线性方程组。

安全多方计算¶

安全多方计算：Alice 和 Bob 合作计算，例如计算 \(f(x, y) = x + y\)，但是不希望对方知道自己的输入。

Yao 的混淆电路方法：

Alice 负责将待计算的函数转换为等价的布尔电路。
对每一个逻辑门，Alice 将它的两个输入端口 a,b 的可能输入值替换为随机的标签 \(X_0^a, X_1^a\) 和 \(X_0^b, X_1^b\)；将它的输出端口 c 的可能输出值替换为随机的标签 \(X_0^c, X_1^c\)。使用这些标签替换逻辑门的原始真值表。
对于每一个真值表项，Alice 使用输入项作为密钥加密输出项，得到乱码表。这将确保只有拥有正确输入的参与者才能解密输出项。
- 例如，对于与门，0 & 1 = 0 对应的乱码表项为 \(Enc_{X_0^a, X_1^b}(X_0^c)\)
Alice 将电路中所有门的计算后的混淆表发送给 Bob，并将与她的输入相对应的标签发送给 Bob。
对于 Bob 的每一个输入位，他使用 1-out-of-2 OT 协议向 Alice 请求对应的标签。
Bob 使用 Alice 发送的标签解密混淆表，得到输出标签。Bob 向 Alice 发送输出标签，Alice 解密得到输出。

零知识证明¶

零知识证明：证明者向验证者证明某个断言是真的，但是不泄需任何关于这个断言的信息。

Schnorr 协议：Peggy 向 Victor 证明她知道 \(x\) 的值。

Peggy 和 Victor 选择一个素数 \(p\) 和域 \(\mathbb{Z}_p\) 的乘法群的生成元 \(g\)。
Peggy 计算 \(y = g^x \mod p\)，发送给 Victor。
重复以下过程：
1. Peggy 选择随机数 \(r \in [0, p-2]\)，计算 \(C = g^r \mod p\)，发送给 Victor。
2. Victor 在以下两个选项中选择一个：
  - 要求 Peggy 提供 \(r\)，然后验证 \(C \equiv g^r \mod p\)。
  - 要求 Peggy 提供 \((x + r) \mod (p-1)\)，然后验证 \(C \cdot y \equiv g^{(x + r) \mod (p-1)} \mod p\)。
    - 由于 \(g\) 是 \(\mathbb{Z}_p\) 的生成元，其阶数为 \(p-1\)，因此 \(g^{p-1} \equiv 1 \mod p\)（费马小定理）。
    - 因此，对于任何指数 \(k\)，\(g^{k \mod (p-1)} \equiv g^k \mod p\)（展开 \(k\) 为 \(k = q \cdot (p-1) + r\)）。
  - 两个选项随机选择，确保了 Peggy 无法通过预测 Victor 的选择，以事先发送准备好的 \(C\)。

密钥交换¶

Diffie-Hellman 密钥交换：Alice 和 Bob 通过公开的通道交换信息，生成一个共享的密钥。

威胁模型¶

攻击者的目标是窃取密钥，根据攻击者能够获得的信息，分为：

选择明文攻击（可以选择明文并获得其加密后的密文）、选择密文攻击（可以选择密文并获得其解密后的明文）、已知明文攻击。