密码学题目 - ElGamal签名方案

在ElGamal签名方案中，设P=19，g=2，私钥x=9，则公钥y=2^9 mod 19=18。若消息m的Hash值为152，试给出选取随机数k=5时的签名和验证过程。

ElGamal签名方案重新生成

给定参数

• $$P = 19$$
• $$g = 2$$
• 私钥 $x = 9$
• 公钥 $y = g^x \mod P = 2^9 \mod 19 = 18$
• 消息的 Hash 值 $h(m) = 152$
• 随机数 $k = 5$

签名过程

1. 计算 $r$

   $$r = g^k \mod P$$

   代入已知值：

   $$r = 2^5 \mod 19$$

   计算 $2^5 = 32$，然后取模：

   $$r = 32 \mod 19 = 13$$

2. 计算 $s$

   $$s = k^{-1} (h(m) - xr) \mod (P-1)$$

   这里，$k^{-1}$ 是 $k$ 的模逆元，满足 $k \times k^{-1} \equiv 1 \mod (P-1)$。

   计算 $k^{-1} \mod 18$（因为 $P-1 = 18$）：

   $$k = 5 \Rightarrow 5 \times k^{-1} \equiv 1 \pmod{18}$$

   用扩展欧几里得算法求解，得到 $k^{-1} = 11$，因为 $5 \times 11 \equiv 1 \mod 18$。

   然后计算 $s$：

   $$s = 11 \times (152 - 9 \times 13) \mod 18$$

   先计算括号内的值：

   $$152 - 9 \times 13 = 152 - 117 = 35$$

   再计算 $s$：

   $$s = 11 \times 35 \mod 18$$

   计算 $11 \times 35 = 385$，然后取模：

   $$385 \mod 18 = 7$$

   所以签名 $(r, s)$ 为 $(13, 7)$。

验证过程

验证签名需要验证以下等式：

$$g^{h(m)} \equiv y^r \cdot r^s \mod P$$

1. 计算左侧 $g^{h(m)} \mod P$

   $$g^{h(m)} \equiv 2^{152} \mod 19$$

   快速幂算法计算 $2^{152} \mod 19$

   快速幂算法是通过将指数分解为二进制形式，然后逐步计算幂并取模，以减少计算量。具体步骤如下：

   1. 将 152 转换为二进制：

      $$152 = 10011000_2$$

   2. 计算过程中每一步的幂取模：

      $$\begin{aligned} 2^1 & \equiv 2 \mod 19 \\ 2^2 & \equiv 2^2 = 4 \mod 19 \\ 2^4 & \equiv 4^2 = 16 \mod 19 \\ 2^8 & \equiv 16^2 = 256 \equiv 256 \mod 19 = 9 \\ 2^{16} & \equiv 9^2 = 81 \equiv 81 \mod 19 = 5 \\ 2^{32} & \equiv 5^2 = 25 \equiv 25 \mod 19 = 6 \\ 2^{64} & \equiv 6^2 = 36 \equiv 36 \mod 19 = 17 \\ 2^{128} & \equiv 17^2 = 289 \equiv 289 \mod 19 = 4 \\ \end{aligned}$$

   3. 根据二进制位求出 $2^{152} \mod 19$：

      $$2^{152} = 2^{128} \cdot 2^{16} \cdot 2^8$$

      从上面的计算，我们知道：

      $$2^{128} \equiv 4 \mod 19$$ $$2^{16} \equiv 5 \mod 19$$ $$2^8 \equiv 9 \mod 19$$

      所以：

      $$2^{152} \equiv 4 \cdot 5 \cdot 9 \mod 19$$

   4. 计算 $4 \cdot 5 \cdot 9 \mod 19$：

      $$4 \cdot 5 = 20 \equiv 1 \mod 19$$ $$1 \cdot 9 = 9 \equiv 9 \mod 19$$

   因此，正确的结果是：

   $$2^{152} \equiv 9 \mod 19$$

1. 计算右侧 $y^r \cdot r^s \mod P$

   $$y^r \equiv 18^{13} \mod 19$$

   由于 $18 \equiv -1 \mod 19$，所以：

   $$(-1)^{13} \equiv -1 \mod 19$$

   计算 $r^s \equiv 13^7 \mod 19$：
   使用快速幂计算 $13^7 \mod 19$:

   $$13^2 \equiv 169 \equiv 17 \mod 19$$ $$13^4 \equiv 17^2 \equiv 289 \equiv 4 \mod 19$$ $$13^7 \equiv 13 \cdot 13^2 \cdot 13^4 \equiv 13 \cdot 17 \cdot 4 \mod 19$$ $$13 \cdot 17 = 221 \equiv 12 \mod 19$$ $$12 \cdot 4 = 48 \equiv 10 \mod 19$$

   所以：

   $$y^r \cdot r^s \equiv (-1) \cdot 10 \equiv -10 \equiv 9 \mod 19$$

由于两侧相等，验证通过。

结果

• 签名 $(r, s) = (13, 7)$
• 验证通过，签名有效。

ElGamal签名方案原理和公式

ElGamal签名方案原理

ElGamal签名方案是基于离散对数问题的公钥密码算法，用于数字签名。它包括生成密钥对、签名和验证三个主要步骤。

生成密钥对

1. 选择一个大素数 $P$ 和一个生成元 $g$，其中 $g$ 是 $P$ 的一个原根。
2. 随机选择一个私钥 $x$ ，满足 $1 \leq x \leq P-2$。
3. 计算公钥 $y$： $$y = g^x \mod P$$

签名过程

给定消息的哈希值 $h(m)$ 和私钥 $x$，选择一个随机数 $k$ ，满足 $1 \leq k \leq P-2$ 并且 $k$ 与 $P-1$ 互素，签名过程如下：

1. 计算 $r$： $$r = g^k \mod P$$
2. 计算 $k$ 的模逆元 $k^{-1} \mod (P-1)$，满足： $$k \times k^{-1} \equiv 1 \pmod{P-1}$$
3. 计算 $s$： $$s = k^{-1} (h(m) - xr) \mod (P-1)$$

签名结果是 $(r, s)$。

验证过程

给定签名 $(r, s)$ 和消息的哈希值 $h(m)$，验证过程如下：

1. 检查 $0 < r < P$ 和 $0 < s < P-1$。如果不满足条件，则签名无效。
2. 计算： $$v_1 = g^{h(m)} \mod P$$
3. 计算： $$v_2 = y^r \cdot r^s \mod P$$
4. 验证： $$v_1 \equiv v_2 \mod P$$ 如果相等，则签名有效，否则无效。

公式总结

1. 生成密钥对：

   $$y = g^x \mod P$$

2. 签名：

   $$r = g^k \mod P$$ $$s = k^{-1} (h(m) - xr) \mod (P-1)$$

3. 验证：

   $$v_1 = g^{h(m)} \mod P$$ $$v_2 = y^r \cdot r^s \mod P$$ $$v_1 \equiv v_2 \mod P$$

快速幂求模和模重复平方方法（也称为指数模运算）实际上是同一种方法，用来高效地计算大整数的幂次模运算。这个方法的主要思想是通过将指数分解为二进制形式，并利用幂的性质（如乘方的结合性）来减少计算量。

快速幂求模（模重复平方）方法

原理

快速幂求模方法通过将指数的幂次分解为二进制形式，利用二进制位上的计算简化大整数的幂次运算。具体来说，它使用了以下性质：

$$a^{b+c} \equiv (a^b \cdot a^c) \mod m$$ $$(a \cdot b) \mod m = [(a \mod m) \cdot (b \mod m)] \mod m$$

步骤

1. 将指数 $e$ 表示为二进制形式。
2. 初始化结果 $result = 1$。
3. 从最低位到最高位处理二进制指数的每一位：
   • 如果当前位是 1，则 $result \equiv (result \cdot base) \mod m$。
   • 将 $base$ 更新为 $base^2 \mod m$。
4. 返回最终的 $result$。

伪代码

def modular_exponentiation(base, exponent, modulus):
    result = 1
    base = base % modulus  # 保证 base 初始值小于 modulus
    
    while exponent > 0:
        if exponent % 2 == 1:  # 如果当前位是 1
            result = (result * base) % modulus
        exponent = exponent >> 1  # 右移一位
        base = (base * base) % modulus  # base 平方
        
    return result

示例

计算 $3^{13} \mod 17$：

1. 将 13 表示为二进制形式：1101
2. 初始化 $result = 1$
3. 从最低位到最高位处理每一位：
   • 位 1（最低位）：$result = (1 \cdot 3) \mod 17 = 3$
   • $base = (3 \cdot 3) \mod 17 = 9$，指数右移一位
   • 位 0：跳过
   • $base = (9 \cdot 9) \mod 17 = 13$，指数右移一位
   • 位 1：$result = (3 \cdot 13) \mod 17 = 5$
   • $base = (13 \cdot 13) \mod 17 = 16$，指数右移一位
   • 位 1（最高位）：$result = (5 \cdot 16) \mod 17 = 12$
   • $$base = (16 \cdot 16) \mod 17 = 1$$

最后，得到 $3^{13} \mod 17 = 12$。

结论

快速幂求模方法和模重复平方方法本质上是同一种方法。它们都是利用指数的二进制表示，通过重复平方和乘法来高效计算大整数的幂次模运算。这个方法在计算机科学和密码学中被广泛应用，特别是在公钥加密算法（如RSA和Diffie-Hellman）中。