这篇文章上次修改于 228 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
ElGamal 同态加密
初始化：素数群 $G$ 的阶为 $q$，生成元为 $g$
密钥生成：私钥 $sk=\alpha$，公钥 $PK=h=g^{\alpha}$
加密：消息为 $m \in Z_q$，选择随机数 $r \in Z_q$，计算 $C_1=g^r, C_2=g^m \cdot h^r$，密文为 $C=(C_1, C_2)$
解密：输入私钥 $sk=\alpha$ 和密文 $(C_1, C_2)$，计算 $g^m=C_2/C_1^{\alpha}$
对 $g^m$ 暴力搜索获得明文消息 $m$，需要指数计算复杂度
推导：$g^m=C_2/C_1^{\alpha} = (g^m \cdot h^r)/g^{r\alpha}=g^{m} \cdot g^{\alpha r} / g^{r\alpha} = g^m$
门罗币金额：32bit
ECDSA 中的份额转换协议，保密份额 32bit，经不住暴力搜索。
msg 太大，自己无法解密，太小，禁不住对方暴力搜，所以 ECDSA 中的份额转换协议通常使用 Paillier 同态加密
同态性：对于两个密文 $C, C'$，定义加法同态为 $C \bigoplus C'=C \cdot C'=(g^{r+r'},g^{m+m'}\cdot h^{r+r'})$
1 预备知识
1.1 费马小定理
若 $p$ 为素数，$a$ 是正整数且不能被 $p$ 整除，互素，则 $a^{p-1}=1$ mod $p$
证明：正整数 $a$ 与素数 $p$ 互素，则集合 $S=\left\{a, 2a, ...,(p-1)a\right\}$ 中均不可能模 $p$ 同余。因此集合 $S$ 模 $p$ 结果恰好就是集合 $T=\left\{1, 2, 3,... p-1\right\}$ 中的元素。因此以下等式成立
$$ \begin{align} &a \cdot 2a \cdot ... (p-1)a = 1 \times 2 \times ... (p-1) (mod \space p) \\ &(p-1)! \cdot a^{p-1} = (p-1)! (mod \space p) \end{align} $$
由于 $gcd((p-1)!,p)=1$，所以两边消去 $(p-1)!$，得到 $a^{p-1}=1$ mod $p$
1.2 欧拉函数
小于 $n$ 且与 $n$ 互素的正整数个数称为欧拉函数 $\psi(n) $。习惯上 $\psi(1)=1$
- 如果 $n$ 是素数，则 $\psi(n)=n-1$
- 如果有两个素数 $p, q$，且 $p \ne q$，则对于 $n=pq$，有 $\psi(n)=\psi(p)\cdot\psi(q)$
- 素数幂 $p^r$，欧拉函数为 $\psi(p^r)=p^{r-1}(p-1)$
欧拉定理：对于任意互素的 $a$ 和 $n$，有 $a^{\psi(n)}=1$ mod $n$
因此，欧拉定理是费马小定理的一般化。欧拉定理中，$n$ 可以是合数，$a$ 是素数且与 $n$ 互素。
欧拉定理扩展：$a^{k \cdot \psi(n) + 1} = a \space mod \space n$
1.3 Carmichael 函数
剩余类（同余类）：设模为 $n$ ，根据余数可将所有的整数分为 $n$ 类，分别为 [0], [1], ..., [ $n - 1$] 。所有与整数 $a$ 模 $n$ 同余的整数构成的集合叫做模 $n$ 的一个剩余类，记作 [$a$] 。 $a$ 称为剩余类 [$a$] 的一个代表元。
Carmichael 函数：函数 $\lambda=\lambda(n)$，对于一个剩余类 $a \in Z_n^*, a^{\lambda(n)}=1$ mod $n$ 均成立，且 $\lambda(n)$ 是满足该等式的最小数。
Carmichael 定理：
$\lambda(p_1^a...p_2^a)=lcm(\lambda(p_1^a), ..., \lambda(p_k^a))$
$if (a|b), then (\lambda(a) | \lambda(b))$
$\lambda(lcm(a, b))=lcm(\lambda(a), \lambda(b))$
设 $p , q$ 为长度相等的大素数，计算 $n = pq$ ，欧拉函数 $ \psi( n ) = ( p - 1)(q - 1)$ ，Carmichael 函
数 $\psi ( n ) = lcm ( p - 1)( q - 1)$ 。
欧拉函数性质 $ \psi ( n^2 ) = n \psi ( n )$
Paillier 会用到的关键结论：对于随机数 $r \in Z_{n^2}^*$，以下两个等式成立：
(1) $r^{\lambda} = 1$ mod $n$
(2) $r^{n\lambda}=1$ mod $n^2$
证明 (1)：
$$ \begin{align} &\lambda=\lambda(n) = lcm(p-1, q-1) \\ &p-1 | \lambda, q-1 | \lambda\\ &\lambda=k_1(p-1)=k_2(q-1) \end{align} $$
根据费马小定理
- $r^{\lambda}=r^{k_1(p-1)}=(r^{(p-1)})^{k_1}=1$ mod $p$，所以 $r^{\lambda}-1 = 0$ mod $p$
- $r^{\lambda}=r^{k_2(q-1)}=(r^{(q-1)})^{k_2}=1$ mod $q$，所以 $r^{\lambda}-1 = 0$ mod $q$
所以
$$ \begin{align} &r^{\lambda} - 1 = 0 \space mod \space pq \\ &r^{\lambda} - 1 = 0 \space mod \space n \end{align} $$
所以 $r^{\lambda}=1$ mod $n$ 成立
证明 (2)：
证明：$n=pq, n^2=p^2q^2$，根据 Carmichael 定理
$$ \begin{align} \lambda(n^2)&=lcm(\lambda(q^2), \lambda(p^2))\\&=lcm(\psi(q^2), \psi(p^2))\\&=lcm(q\psi(q), p\psi(p))\\&=lcm(q(q-1), p(p-1))\\&=pq(lcm(p-1, q-1))\\&=n\lambda(n) \end{align} $$
$$ \begin{align} &r^{\lambda} = r^{\lambda(n)} = 1 \space mod \space n\\ &r^{\lambda(n^2)} = 1 \space mod \space n^2 \\ &r^{n\lambda(n)} = 1 \space mod \space n^2 \end{align} $$
所以 $r^{n\lambda}=1$ mod $n^2$ 成立
二项式泰勒展开为
$$ (1+n)^x=\sum^x_{k=0}C^k_xn^k=1+nx+\frac{x(x-1)}{2!}n^2+...+\frac{x(x-1)...(x-n_1)}{n!}n^n+... $$
根据二项式泰勒展开，得到 $(1+n)^x$ mod $n^2$ = $1 + nx$ mod $n^2$
1.4 模反元素存在性
如果大素数 a 和大合数 n 互素，则一定可以找到整数 b，使得 ab = 1 mod n，则称 b 是 a 的模反元素。
证明：使用欧拉定理 $a^{\psi(n)} = 1$ mod $n$，则 $a^{1+\psi(n)-1}$ mod $n$，则 $a \cdot a ^{\psi(n)-1}=1$ mod $n$，则 $b=a^{\psi(n)-1}$
2 Paillier 同态加密
2.1 困难假设
困难假设 1：因子分解困难问题
对于两个长度相等的大素数 $p, q$，$p \ne q$，计算 $N = p \cdot q$。公开 $N$，求 $p, q$ 是困难的。需要指数时间暴力搜索，在多项式时间内不可行。
困难假设 2：叛决复合冗余 Decisional Composite Residuosity（DCR）困难问题
不存在概率多项式时间攻击者 $A$ 能够以不可忽略的优势概率区分以下两个分步
$$ \left\{[N,c], c=r^N \space mod \space N^2 \right\}, \space \left\{[N,c], c=g^m \cdot r^N \space mod \space N^2 \right\} $$
其中，$m, r \in Z_N, \space N=p \cdot q, \space g = N+1$
2.2 同态加密
密钥生成：生成两个长度相同的大素数 $p, q$，且 $p \ne q$，满足 gcd$(pq, (p-1)(q-1))=1$，该性质确保两个素数的长度相同；计算 $n=pq$，最小公倍数 $\lambda=lcm(p-1, q-1)$；分式除法函数 $L(y)=(y-1)/n$；选择正整数 $g=1+n \in Z_{n^2}^*$，使得 $u=(L(g^{\lambda} mod n^2))^{-1}$ mod $n$ 存在。公钥为 $n$，私钥为 $p, q$ 或 $\lambda$（$p,q$ 可以算出 $\lambda$，解密的时候实际使用的是 $\lambda$）
如果 $p , q$ 长度相等，则密钥生成步骤能够化简为： $g = n + 1, \lambda = \psi( n ), u=\psi( n )^{-1} $ mod $n$
其中 $\psi(n)=(p-1)(q-1)$，如果 $p, q$ 足够大，则 $u$ 计算时间较长，推荐使用该方法
加密：消息 $m \in Z_n$，选择随机数 $r \in Z_n^*$，计算密文 $c = g^m \cdot r^n$ mod $n^2$，用到了公钥 $n$
解密：输入密文 $c \in Z_{n^2}$，计算解密 $m = L(c^{\lambda} \space mod \space n^2)\cdot u \space mod \space n$，用到了私钥 $\lambda$
证明：
$$ \begin{align} & c^{\lambda} \space mod \space n^2 = g^{\lambda m} \cdot r^{\lambda n} \space mod \space n^2 = g^{\lambda m} \cdot 1 \space mod \space n^2 = (1+n)^{m\lambda} \space mod \space n^2 = 1 + nm\lambda \space mod \space n^2 \\ & g^{\lambda} \space mod \space n^2 = = 1 + n\lambda \space mod \space n^2 \\ & L(c^{\lambda} \space mod \space n^2) = \frac{c^{\lambda} \space mod \space n^2 - 1}{n} = m\lambda \space mod \space n^2 \\ & L(g^{\lambda} \space mod \space n^2) = \frac{g^{\lambda} \space mod \space n^2 - 1}{n} = \lambda \space mod \space n^2 \\ & m = \frac{L(c^{\lambda} \space mod \space n^2)}{L(g^{\lambda} \space mod \space n^2)} \space mod \space n \end{align} $$
同态性：给定两个密文 $c_1, c_2 \in Z_{n^2}$，其中 $c_1 = Enc_{pk}(m_1), c_2=Enc_{pk}(m_2)$
密文之间的同态加 $\bigoplus$
$c_1 \bigoplus c_2 = c_1c_2 \space mod \space n^2 = (g^{m_1}r_1^{n} \space mod \space n^2)(g^{m_2}r_2^{n} \space mod \space n^2) = (g^{m_1+m_2}(r_1r_2)^{n} \space mod \space n^2)$
因此，$c_1 \bigoplus c_2 = Enc_{pk}(m_1 + m_2) \space mod \space n$
给定 $a \in Z_n$ , c = Enc{pk} ( m ) 定义随机数 $a$ 与密文 $c$ 的乘法运算 $\bigotimes$
$a \bigotimes c = c^a \space mod \space n^2 = g^{am}(r^a)^n \space mod \space n^2 = Enc_{pk}(am \space mod \space n)$
因此，$a \bigotimes c = Enc_{pk}(am \space mod \space n)$
3 Paillier 算法优化
预计算优化
密钥生成：对于大素数 $p, q$，额外要求 $p=q=3$ mod 4，且 $gcd(p-1, q-1)=2$，可确保 $p, q$ 不等。因为如果 $p=q$，则 $gcd(p-1,q-1)=p-1=q-1 \ne 2$。这样的素数称为 Blum 整数。
Blum 整数生成方法：随机选择两个长度为 k-bit 的大数 $k_1,k_2$，计算 $p=4k_1+3, q=4k_2+3$，(a) 检测 $p,q$ 是否为素数，如果是，则计算 $p-1=2(2k_1+1),q-1=2(2k_2+1)$，(b) 检测 $gcd(p-1,q-1)=2$
用户端：寻找 Blum 整数 $p,q$ 通常约 6s，但密钥生成只需要允许一次
服务端：可以预计算 $p,q$
预计算：选择随机数 $x \in Z_n^*$，计算 $h=-x^2$ mod $n$，雅可比符号为 -1 确保存在二次剩余（雅可比符合是勒让德符号的累积，勒让德符号 $\begin{pmatrix}\frac{a}{p} \end{pmatrix}=a^{\frac{p-1}{2}}$ mod $p$ ，$\begin{pmatrix}\frac{a}{p} \end{pmatrix}$ =1，说明存在整数 $x$，满足 $x^2=a$ mod $p$，则 $a$ 是模 $p$ 的二次剩余， $\begin{pmatrix}\frac{a}{p} \end{pmatrix}$ =-1，则 $a$ 是模 $p$ 的二次非剩余）
预计算 $f=h^n$ mod $n$
对于 $c=g^mr^n$ mod $n^2$
原来：选择随机数 $r \in Z_n^*$，计算 $r^n$ mod $n^2$
改为：基于预计算 $f$（新增的公钥），在折半空间选择随机数 $a \in Z_{2^{[n/2]}}$，计算 $f^a$ mod $n^2$（随机数的长度减半，计算更快；如果因子分解是困难的，则计算不可区分，所以安全性一样）
$f^a$ mod $n^2$ = $h^{na}$ mod $n^2$ = $(h^a)^n=(-x^{2a})^n$ mod $n^2$ 与 $r^n$ mod $n^2$ 分布不可区分
所以 Paillier 加密可以优化为：
$c=g^mr^n$ mod $n^2$ = $g^mf^a$ mod $n^2$ = $g^m$ mod $n^2 \cdot f^a$ mod $n^2$（有 2 个模指数运算）
通过中国剩余对模指数运算加速
$c=g^mf^a$ mod $n^2$ $c=g^m$ mod $n^2 \cdot f^a$ mod $n^2$ 中有 2 个模指数运算
中国剩余定理
作用：n 个小空间聚合映射回大空间（线性组合）
线性同余方程组 S 表达如下
$$ \left\{ \begin{array}{c} x=a_1 \space mod \space m_1 \\ x=a_2 \space mod \space m_2 \\ ...\\ x=a_n \space mod \space m_n \\ \end{array} \right. $$
其中，$m_1, ...m_n$ 两两互素，$a_1, ..a_n$ 为任意整数，求 $x$。该线性同余方程组有解。
设 $M=\prod^n_{i=1}m_i$，且 $M_i=M/m_i=\prod^n_{j=1,j \ne i}m_i, j=1, ...,n$，所以 $M_i$ 与 $m_i$ 互素（条件1）。
由于模反元素存在，所以存在 $t_i$ 满足 $M_i \cdot t_i = 1 \space mod \space m_i$（条件2）.
则解为 $x=kM + \sum^n_{i=1}a_it_iM_i, k \in Z$
模 $M$ 后的唯一解为 $x=\sum^n_{i=1}a_it_iM_i$ mod $M$
证明：$x$ mod $m_i = a_it_iM_i + \sum^n_{j \ne i}a_jt_jM_j$ mod $M = a_it_iM_i + 0 = a_i $ mod $m_i$
裴蜀定理/贝祖定理
对任何整数 a、b，且 gcd(a,b)=d，关于未知数 x 和 y 的线性不定方程（称为裴蜀等式）： 若 a,b 是整数，且 gcd(a,b)=d，则
（1）对于任意整数 x, y, 则 ax+by 一定是 d 的倍数；
（2）特别地，一定存在整数 x, y，使 ax+by=d 成立；
（3）重要推论：a,b 互素的充分必要条件是存在整数 x,y 使 ax+by=1.
模指数运算加速
使用中国剩余定理的条件：知道私钥 $n=pq$，$p, q$ 互素，才能构造子空间 $Z_p \times Z_q$
计算 $a^b$ mod $n$
大空间映射到 2 个小空间，2 个小空间并行模指数运算
$a^b$ mod $n$ 映射到空间 $p$ 得到 $a_1 = a$ mod $p$，根据欧拉定理 $b_1 = b $ mod $\psi(p)$
在小空间 $Z_p$ 上进行模指数运算 $x_1=a_1^{b_1}$
同理，$a_2=a$ mod $q$，$b_2 = b$ mod $\psi(q)$
在小空间 $Z_q$ 上进行模指数运算 $x_2=a_2^{b_2}$
2 个小空间聚合映射回大空间
根据中国剩余定理通项公式 $x=\sum^n_{i=1}a_it_iM_i$ mod $M$，有
$$ x = x_1 \cdot q^{-1}(\space mod \space p) \cdot q + x_2 \cdot p^{-1} (\space mod \space q) \cdot p $$
裴蜀定理： $p$ 与 $q$ 互素，则 $ q^{-1}(\space mod \space p) \cdot q + p^{-1} (\space mod \space q) \cdot p = 1$
带入裴蜀定理进一步优化：$x=x_1 + (x_2 - x_1)p^{-1} (\space mod \space q) \cdot p$
4 素性测试
一个 2048bit 的大整数是否为素数？
n 是奇数，则 n - 1 是偶数。将 n - 1 进行 k 次除以 2，直到结果为奇数 q。因此任意 n >= 3 的奇整数可以表达为 $n-1=2^kq$
素数 p 有两个性质：
- 若 p 为素数，a 是小于 p 的正整数，则 $a^2 \space mod \space p = 1$ 当且仅当 $a \space$ mod $p = 1$ 或 $a$ mod $p = -1 = p-1$
若 p 为大于 2 的素数，则 $p-1=2^kq$，a 是小于 p - 1 的正整数，则以下 2 个条件之一成立
- (a) $a^q=1$ mod p
- (b) 整数集合 $\left\{a^q, q^{2q}, ...a^{2^{k-1}q}\right\}$ 中存在某个数 $a^{2^iq}$，满足 $a^{2^iq}=-1$ mod $p$
分析：根据费马小定理，p 为素数，a 是小于 p 的正整数，则 $a^{p-1}=1$ mod $p$，则 $a^{p-1}=a^{2^k}q=1$ mod $p$。因此扩展整数集合 $\left\{a^q, q^{2q}, ...a^{2^{k-1}q},a^{2^kq}\right\}$ 中最后一个为 1。
则 $(a^{2^{k-1}q})^2$ mod $p=a^{2^kq}$ mod $p=1$。根据性质 1，则 $a^{2^{k-1}q}$ mod $p=\pm 1$
- 如果性质 (a) 成立，则集合 $\left\{a^q, q^{2q}, ...a^{2^{k-1}q}\right\}$ 中每个元素值为 1，所以性质 (b) 不成立
- 如果性质 (a) 不成立，则 $a^{2^{k-1}q}$ mod $p=-1$，则 (b) 成立
素性测试算法
输入整数 n，计算 $n-1=2^kq$
选择随机数 $a \in (1,n-1)$
如果 $q^q$ mod $n=1$，则返回可能是素数
否则，循环 k 次，如果 $a^{2^iq}=-1$ mod $n, i=0,..,k-1$，则返回可能是素数
返回一定是合数
重复测试 t 次
没有评论