p = 17, α = 3, xA= 2, xB= 5, m = 11, k = 5, 求elgamal签名及验证

ElGamal签名的步骤如下：

1.选择一个大素数p和一个原根α

2.选择私钥 xA 和公钥 yA

3.计算 yA = α ^ xA mod p

4.签名：计算 r = α ^ k mod p , s = (m - xA * r) * k^-1 mod (p-1)

5.验证：计算 v1 = yA^r * r^s mod p, v2 = α^m mod p, 如果 v1 = v2，则验证通过

根据题目给出的参数，我们可以得到：

p = 17, α = 3, xA= 2, xB= 5, m = 11, k = 5

1. 选择大素数p和原根α

已知p=17是素数，α=3是17的原根。

2. 选择私钥 xA 和公钥 yA

私钥 xA=2，公钥 yA=α^xA mod p=3^2 mod 17=13

3. 签名：计算 r 和 s

r=α^k mod p=3^5 mod 17=6

s=(m-xA*r)*k^-1 mod (p-1)=(11-2*6)*5^-1 mod 16=5

因为p=17是奇素数，所以p-1=16是偶数，k^-1 mod (p-1)需要用扩展欧几里得算法求解。

4. 验证

计算 v1 和 v2

v1=yA^r * r^s mod p=13^6 * 6^5 mod 17=5

v2=α^m mod p=3^11 mod 17=5

因为v1=v2，所以验证通过。

因此，ElGamal签名为(6,5)，验证通过。

相关问题

3. 在ElGamal系统中, α=7, p=13, xa=5, xb=3. a) 假定A加密传送m=3给B，随机选择k=8，密文是什么?

在ElGamal密码系统中，加密过程如下：

1. A选择一个随机数k，并且计算出C1 = α^k mod p
2. A计算出C2 = m * xb^k mod p
3. A将密文发送给B，密文包括C1和C2

根据题目中给出的参数，我们可以按照上述步骤来加密明文m=3：

1. A选择一个随机数k=8，并且计算出C1 = α^k mod p = 7^8 mod 13 = 2
2. A计算出C2 = m * xb^k mod p = 3 * 3^8 mod 13 = 9
3. A将密文发送给B，密文为(2, 9)

因此，当A使用随机数k=8对明文m=3进行加密时，密文为(2, 9)。

在ElGamal系统中, α=7, p=13, xa=5, xb=3. a) 假定A加密传送m=3给B，随机选择k=8，密文是什么?

在 ElGamal 系统中，公钥为 $(p, \alpha, \beta)$，私钥为 $x$。其中，$p$ 是一个大素数，$\alpha$ 是模 $p$ 的原根，$\beta = \alpha^x \bmod p$ 是公钥。在这个系统中，如果 A 想要向 B 发送一条消息 $m$，则可以执行以下步骤：

1. A 选择一个随机数 $k$，$1 \leq k \leq p-2$。
2. A 计算 $C_1 = \alpha^k \bmod p$ 和 $C_2 = m \cdot \beta^k \bmod p$。
3. A 将密文 $(C_1, C_2)$ 发送给 B。

B 收到密文 $(C_1, C_2)$ 后，可以执行以下步骤来解密：

1. B 计算 $M = C_2 \cdot (C_1^x)^{-1} \bmod p$。
2. 解密后的明文为 $m = M$。

现在，根据题目中的参数，我们可以计算出：

- 公钥：$(p, \alpha, \beta) = (13, 7, 11)$。
- 私钥：$x = 3$。

现在，A 想要向 B 发送 $m = 3$。A 选择一个随机数 $k = 8$，然后计算：

$$
\begin{aligned}
C_1 &= \alpha^k \bmod p = 7^8 \bmod 13 = 3 \\
C_2 &= m \cdot \beta^k \bmod p = 3 \cdot 11^8 \bmod 13 = 9
\end{aligned}
$$

因此，密文为 $(C_1, C_2) = (3, 9)$。A 将密文发送给 B，B 收到密文后，计算：

$$
\begin{aligned}
M &= C_2 \cdot (C_1^x)^{-1} \bmod p \\
&= 9 \cdot (3^3)^{-1} \bmod 13 \\
&= 9 \cdot 5 \bmod 13 \\
&= 11
\end{aligned}
$$

因此，解密后的明文为 $m = 11$。