模运算和半算法加密

Question

我正在实现已在 PVSS 中使用的半 ELGamal 密码系统（来自 research paper）函数。不幸的是，我无法解密，因为它已在算法中进行了描述。

这是初始化阶段：

Select 一个安全素数 p 使得 p-1=2q 其中 q 也是一个素数，然后创建一个循环群 G 并让 g 成为这个群的随机生成器。在组中随机选择一个 x（私钥）并令 y = g^x（public 密钥）。我简单地初始化算法如下：

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（私钥）的倒数，我应该return 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 对于任何非 p 的倍数的 y，x=p-1 总是按你预期的方式工作...

Modular arithmetic and semi elgamal encryption