问子组上的ElGamal加密

EN

乘法群\mathbb{Z_{67}}^*有66个元素。通过拉格朗日定理拉格朗日定理，我们可以说，任何子群G of \mathbb{Z_{67}}^*的顺序都必须除以该群的次序，66。定理的逆不需要保持，因此必须检查有2,3和11阶子群及其乘积。

使用下面的SageMath，您可以列出生成器及其顺序；

def findOrder(a,G):
    temp = a
    for i in range (G.order()):
        if temp == G(1):
            return i+1
        temp = temp*a
        
R = Zmod(67)
grouplist = R.multiplicative_subgroups()
print(grouplist)
for x in grouplist:
    print(x, "order = ", findOrder(R(x[0]),R))

不要为大型组尝试这段代码！下面的代码输出空子集的错误！

( 2,) order =  66
( 4,) order =  33
( 8,) order =  22
(64,) order =  11
(38,) order =  6
(37,) order =  3
(66,) order =  2

因此，我们有所有可能的子群，没有逆拉格朗日定理的反例。

唯一的质数顺序是2,3和11。为了简单的安全性，您需要选择11。实际上，素数是不必要的，因为ElGamal加密可以在任何循环组G上定义。另一方面，安全性依赖于离散对数问题，当群不处于素数阶时，Pohlig进入博弈，而我们并不比最大素数阶更安全。

好的，让我们继续使用p=11，它有一个生成器作为g=64。

• 从\alpha中选择一个随机整数\{1,\ldots, 10\}
• 现在，计算\beta = g^{\alpha}
• 公钥(G,q,g,\beta)和私钥是\alpha