模算法与半elgamal加密

Question

我正在实现一个已经在PVSS中使用的半ELGamal密码系统（来自一篇研究论文）函数。不幸的是，我无法解密，正如算法中所描述的那样。

以下是初始化阶段：

选择一个安全素数p使得p1=2q，其中q也是素数，然后做一个循环群G，设G是这个群的随机生成元。在组中选择一个随机的x（私钥），并设y=G^x（公钥）。我简单地初始化算法如下：

p = 233;
g = 131;
x = 139;
y = g ^ x mod 233; //y = 182

现在设s（秘密）为23，我们计算我们的es（加密秘密）：

s = 23
es = y ^ s mod 233// es = 231

为了解密es，我将es升为x（私钥）的逆，我应该返回g^s，假设ds是解密的值：

ds = es ^ 1/x mod 233 // 1/x = 57, ds = 116

这里有个问题,ds不等于g^s,但理论上应该是,因为：

回想一下，我们将%s加密为：

es = y ^ s mod 233

我们知道

y = g ^ x mod 233

所以,

es = g ^ x ^ s mod 233

有鉴于此,

ds = es ^ 1/x mod 233
// which means:
ds = g ^ x ^ s ^ 1/x mod 233

因此，我期望得到与G^S(131^23 mod 233）相同的结果，它必须是182，而我得到的ds结果是116。

我做的事情有什么不对吗？

Answer 1

当您有：

x * invX = 1 mod p 

下列等式一般不成立：

(g ^ x) ^ invX = g mod p

上面的表达式是将g*g*...*g乘以一定的次数，x*invx，根据第一模关系，也就是k*p+1。

假设生成器的大小为n<=P-1:

g ^ n = 1 mod p

这意味着x*invx必须是n的倍数...

在序言中，您断言q=(p-1)/2是素数，但在这里，情况并非如此，q=116...

在您的示例中，g=131生成长度为58=(p-1)/4的序列。
那么，只有那些x具有属性g^x^(1/x)=1 mod p:

58 116 132 154 174 203 229 231 232

注意，对于另一个生成器g=5，序列的最大长度为p-1，则满足(g^x)^invX=1 mod p的唯一x为x=p-1。

由于y^(p-1)=1 mod p对于任意y不是p的倍数，x=p-1总是按照您的预期工作...