计算机安全学实验:如何生成素数阶群

密码学 计算机安全学作业

在实现公钥密码学协议的过程中，常常需要用到一个素数阶的群。本文讲述如何高效快速生成一个素数阶群。(不需要穷巨遍历寻找生成元)

以Elgamal加密为例子：要保证ELGamal加密的可证明安全性,必须要求其在素数阶群上运行。因此在实现ELGamal协议的时候，需要生成一个素数阶的群。

生成素数阶群的时候，我们常常需要用到$Z^{*}_p$，其中$p$为素数。注意,$Z^{*}_p$的阶并不是$p$，而是$\phi(p)=p-1$。我们可以从某些特殊的$Z^*_p$中提取出素数阶的子群。先看以下定理:

定理1：拉格朗日定理
设$G,S$为两个群，若$S$是$G$的子群，则$|G|$可被$|S|$整除。

上面的定理给了我们一个提示:由于$|Z^*_p|=p-1$(必然是个偶数),那么$Z^*_p$中的子群的阶必然会是$p-1$的某个因子。我们可以使$p-1$有一定的结构使得它有个素数子群，以下定理阐述了这种“结构”：

定理2:
设$p = rq+1$,其中$p,q$为素数.$r$为某个整数(使$p,q$满足前面的条件)那么:
$G:=\{ [h^r \ mod \ p] | h \in Z^*_p\}$
是一个$Z^*_p$的子群并且它的阶为$q$.

引理
$p$是一个素数,则$Z^*_p$有生成元.

定理2证明 :
显然$G$是一个$Z^*_p$的子群。设$g$为$Z^*_p$的生成元，显然$g^r \in G$(定义)
构造无穷序列$\{g^0,g^r,g^{2r},...,g^{qr}=g^{p-1},...\}。$(显然该序列所构成的集合就是$G$)

假设$g^r$的order是$q$，则$G$的阶为$q$.(why?因为上面的无穷序列构成的集合即$G$，再由order的定义，可知该序列的周期为$q$，即只有q个不同的元素)。同时，这也说明$g^r$是$G$的生成元.

现证明$g^r$的order确实是$q$。先设$k$为$g^r$的order。
已知$g^{rk} \equiv 1 \equiv g^{p-1} \equiv g^{rq} (mod \ p)$，由阶的最小性，有$k | q$。
由于$q$是素数，$k$等于$1$或$q$。显然$k\ne 1$，因为如果$k=1$，那么$r$就是$g$的order，即$r = p-1$，与题设矛盾。

以上定理阐述了,如果我们令$p,q$为满足$p=2q+1$的素数。那么上述的群$G$是一个$q$阶群。

如何找出这个子群$G$的生成元呢？只要取一个$h \in Z^*_p(h \neq 1)$，然后计算$g' = h^r (mod \ p)$。只要$g' \neq 1$，那么$g'$必然是$G$的生成元(因为$G$是素数阶群)。

总结步骤: 如何生成一个素数阶群？
1. 给定输入参数$n$，生成两个n比特的素数$p,q$。要求$p,q$满足$p=2q+1$.(对应定理2的$r=2$)
2. 取$h \in Z^*_p$且$h \neq 1$
3. 计算$g = h^2 \mod p$.
4. 如果$g$等于$1$，返回步骤2；否则输出$G = (g,q,p)$

小思考题：
0: 如何从该群中随机抽取一个元素？
1: 该群的乘法如何做？给定$a \in G,b \in G$，$a$和$b$的乘法运算应该是$(a \cdot b) \mod p$，还是$(a \cdot b) \mod q$？为什么？
2: 论证：当$p,q$是奇数时，$h$取2即可。