1.密钥生成
- 选择 $k+1$ 个较小的奇素数 $u, v_1, \ldots, v_i, \ldots, v_k$，其中 $u$ 相对较小。
- 选择两个合适的大素数 $v_p$ 和 $v_q$，使得素数 $p$ 和 $q$ 的比特长度相同，其中 $p$ 和 $q$ 通过如下计算得到：$p = 2uv_1v_2 \ldots v_i \ldots v_k v_p + 1$，$q = 2uv_1v_2 \ldots v_i \ldots v_k v_q + 1$。
- 计算大整数 $N = pq$ 和 $\lambda = \text{lcm}(p - 1, q - 1)$，其中 $\lambda$ 是以 $N$ 为参数的Carmichael函数的值。
- 从集合 $\{v_1, v_2, \ldots, v_i, \ldots, v_k\}$ 中选择一个数或多个数的乘积作为 $t$，则自然存在 $t|\lambda$ 。
- 选择一个满足 $g^{utN} = 1 \mod N^2$ 的随机整数 $g \in \mathbb{Z}_{N^2}^*$，其自然满足 $\text{gcd}(L(g^\lambda \mod N^2), N) = 1$，其中函数 $L$ 定义为 $L(x) = \frac{x - 1}{N}$。
- 计算 $h = g^{\frac {N \lambda}{t}} \mod N^2$，并将 $pk = (N, g, u, h)$ 作为公钥。
- 令 $wsk = t$ 为弱私钥，$ssk = \lambda$ 为强私钥。
$\mathbb{Z}_{N^2}^*$ 表示模 $N^2$ 乘法群，即所有与 $N^2$ 互素的整数集合。