记输出为[G`, G, p, q, g]，其中p为大素数，G`为模p的有限循环整数群，阶为p-1；q为大素数，为G的阶，G为G`的子群（模亦是p），生成元为g（G`的一个元素），另外满足如下条件：

1. 1<q的位长<p的位长，p、q随机选取，p同余于1 mod q，即p-1整除q，q为p-1的素因子

2. 1<g<=p-1，随机选取，测试它的q次幂是否等于1 mod p，若不等于则重新选取，直到等于

3. 上面选定的g，遍历1到q的幂模p，就得到G的各元素

数学基础：一个有限群，对每个元素它的阶整除群的阶，它的群阶幂次方等于单位元；一个有限循环群，它的生成元个数为群阶的欧拉数，若群阶是素数，则所有非1的元素都是生成元

结论：这种计算子群的方法由于保证阶为素数且只要超过160位长，就可避免针对阶为合数的质因子分解并利用中国剩余定理求离散对数的已知最好攻击，具有中长期安全强度

春秋十二月 2023-09-06 22:28 发表评论