当前位置：首页 > news >正文

密码学（Public-Key Cryptography and Discrete Logarithms）

news 来源：原创 2025/8/8 10:04:11

Public-Key Cryptography and Discrete Logarithms

Discrete Logarithm

核心概念：离散对数是密码学中一个重要的数学问题，特别是在有限域和循环群中。它基于指数运算在某些群中是单向函数这一特性。也就是说，给定一个群 $G$ 和一个生成元 $g$ ，计算 $g^x$ 是相对容易的，但给定 $g$ 和 $g^x$ ，求解 $x$ 却非常困难，这种困难性是许多密码学协议安全性的基础。
应用：离散对数问题在公钥密码学中被广泛应用，例如在Diffie-Hellman密钥交换和ElGamal密码体系中。

The ElGamal Cryptosystem

加密操作的随机性：ElGamal密码体系的加密过程是随机化的。这意味着密文不仅依赖于明文 $x$ ，还依赖于发送者（如Alice）选择的随机值 $k$ 。这种随机性使得相同的明文在不同时间加密可能会产生不同的密文，增加了安全性。
工作原理：
- 密钥生成：选择一个大素数 $p$ 和一个生成元 $g$ ，私钥为随机选择的整数 $a$ ，公钥为 $p,g,g^a\mod p)$ 。
- 加密：对于明文 $m$ ，选择随机数 $k$ ，计算 $c_1=g^k\mod p$ 和 $c_2=m\cdot(g^a)^k\mod p$ ，密文为 $c_1,c_2)$ 。
- 解密：接收者使用私钥 $a$ 计算 $c_1^a\mod p$ ，然后通过 $c_2/(c_1^a)\mod p$ 恢复明文 $m$ 。

Finite Fields

构造：有限域是密码学中常用的数学结构，它是一个包含有限个元素的域。有限域的构造通常基于模运算，例如模一个素数 $p$ 或模一个不可约多项式。
性质：有限域的乘法群是循环群，这意味着存在一个生成元 $g$ ，使得通过 $g$ 的幂可以生成群中的所有非零元素。在某些情况下，如域的阶数为素数时，除了 $0$ 和 $1$ 之外的任何元素都可以作为生成元。

Elliptic Curves

Elliptic Curves: over the Reals

椭圆曲线的定义：椭圆曲线是一种特殊的数学曲线，其方程通常表示为 $y^2=x^3+ax+b$ （在实数域上）或类似的方程在有限域上的形式。椭圆曲线上的点构成一个阿贝尔群，群运算是基于点的加法。

Elliptic Curves Modulo a Prime

椭圆曲线模素数：在有限域 $\mathbb{F}_p$ 上，椭圆曲线的方程形式为 $y^2\equiv x^3+ax+b\pmod p$ ，其中 $a$ 和 $b$ 是满足 $4a^3+27b^2\neq 0\pmod p$ 的常数。

Elliptic Curves over Finite Fields

椭圆曲线密码学：椭圆曲线密码学（ECC）利用椭圆曲线上的点和群运算来实现密码学协议。与传统的基于有限域的密码学相比，ECC可以在更小的密钥长度下提供相同的安全性，因此在资源受限的环境中特别有用。
点压缩：为了减少存储和传输需求，椭圆曲线密码学中常常使用点压缩技术。点压缩通过只存储点的 $x$ 坐标和一个额外的标志位来表示一个点，从而将存储需求减少约 $50\%$ 。不过，这需要额外的计算来恢复点的 $y$ 坐标。

Algorithm Optimization

Signed Binary Representation

NAF（Non-Adjacent Form）表示：NAF是一种特殊的整数表示方法，用于优化椭圆曲线上的标量乘法运算。NAF表示的特点是相邻的系数不会同时为非零，这可以减少不必要的加法运算，从而提高计算效率。

DOUBLE-AND-(ADD OR SUBTRACT) ALGORITHM

双重加法/减法算法：这种算法利用NAF表示来优化椭圆曲线上的标量乘法。通过减少加法和减法操作的次数，该算法可以在平均情况下实现大约 $11\%$ 的速度提升。

ElGamal密码体系的加密与解密示例

示例参数

假设我们选择以下参数：

大素数 $p = 23$
生成元 $g = 5$
私钥 $a = 6$ （Alice的私钥）
公钥 $y = g^a \mod p = 5^6 \mod 23 = 8$ （Alice的公钥）

因此，Alice的公钥为 $(p, g, y) = (23, 5, 8)$ 。

加密过程

假设Bob要向Alice发送明文消息 $m = 9$ 。Bob执行以下步骤：

选择随机数 $k$ ：Bob选择一个随机数 $k = 3$ （这个随机数必须保密，不能泄露）。
计算 $c_1$ ：
$c_1 = g^k \mod p = 5^3 \mod 23 = 10$
计算 $c_2$ ：
$c_2 = m \cdot y^k \mod p = 9 \cdot 8^3 \mod 23 = 9 \cdot 512 \mod 23 = 9 \cdot 10 \mod 23 = 90 \mod 23 = 21$

因此，Bob将密文 $c_1, c_2) = (10, 21)$ 发送给Alice。

解密过程

Alice收到密文 $c_1, c_2) = (10, 21)$ 后，执行以下步骤来解密：

计算 $c_1^a \mod p$ ：
$c_1^a \mod p = 10^6 \mod 23 = 18$
计算 $c_1^a \mod p$ 的逆元：需要找到一个数 $s$ ，使得 $\cdot 18 \equiv 1 \mod 23$ 。通过扩展欧几里得算法或其他方法，可以计算出 $s = 13$ （因为 $18 \cdot 13 \equiv 1 \mod 23$ ）。
解密明文：
$c_2 \cdot s \mod p = 21 \cdot 13 \mod 23 = 273 \mod 23 = 9$

最终，Alice成功恢复了Bob发送的明文消息 $m = 9$ 。

为什么需要逆元

计算 $c_1^a \mod p$ 的逆元是必要的，因为我们需要从 $c_2$ 中“消除” $y^k \mod p$ 的影响。由于 $c_2 = m \cdot y^k \mod p$ ，而 $y^k \mod p$ 与 $c_1^a \mod p$ 相等（因为 $y = g^a \mod p$ ），因此通过乘以 $c_1^a \mod p$ 的逆元，我们可以得到：
$c_2 \cdot (c_1^a \mod p)^{-1} \mod p$

总结

计算 $c_1^a \mod p$ 的逆元是ElGamal密码体系解密过程中的关键步骤，它使得我们能够从密文中恢复出原始的明文消息。逆元的计算是基于模运算的性质和扩展欧几里得算法。ElGamal密码体系的安全性基于离散对数问题的难解性，即给定 $g$ 、 $g^a \mod p$ 和 $g^k \mod p$ ，计算 $k$ 或 $a$ 是非常困难的。

ElGamal密码体系在扩展域上的示例

扩展域 $\mathbb{F}_{2^3}$ 的构造

在 $\mathbb{F}_{2^3}$ 中，元素个数为 $2^3 = 8$ 。为了构造这个域，我们需要选择一个不可约多项式 $f (x)$ 。这里我们选择 $f(x) = x^3 + x + 1$ ，这是一个在 $\mathbb{F}_2$ 上的不可约多项式。

在 $\mathbb{F}_{2^3}$ 中，每个元素可以表示为一个多项式 $a_2x^2 + a_1x + a_0$ ，其中 $a_2, a_1, a_0 \in \{0, 1\}$ 。因此，所有元素可以表示为：
${0, 1, x, x+1, x^2, x^2+1, x^2+x, x^2+x+1\}$

示例参数

假设我们选择以下参数：

扩展域： $\mathbb{F}_{2^3}$ ，不可约多项式 $f(x) = x^3 + x + 1$
生成元： $g = x$ （在 $\mathbb{F}_{2^3}$ 中， $x$ 是一个生成元）
私钥： $a = 3$ （Alice的私钥）
公钥： $y = g^a \mod f(x) = x^3 \mod (x^3 + x + 1)$

计算 $y$ ：
$x^3 \equiv x + 1 \pmod{x^3 + x + 1}$
因此，Alice的公钥为 $f(x), g, y) = (x^3 + x + 1, x, x + 1)$ 。

加密过程

假设Bob要向Alice发送明文消息 $m = x^2 + x$ 。Bob执行以下步骤：

选择随机数 $k$ ：
- Bob选择一个随机数 $k = 2$ （这个随机数必须保密，不能泄露）。
计算 $c_1$ ：
$c_1 = g^k \mod f(x) = x^2 \mod (x^3 + x + 1) = x^2$
计算 $c_2$ ：
$c_2 = m \cdot y^k \mod f(x) = (x^2 + x) \cdot (x + 1)^2 \mod (x^3 + x + 1)$
- 首先计算 $x + 1)^2$ ：
  $1)^2 = x^2 + 2x + 1 = x^2 + 1 \quad (\text{因为} 2 \equiv 0 \pmod{2})$
- 然后计算 $c_2$ ：
  $c_2 = (x^2 + x) \cdot (x^2 + 1) = x^4 + x^3 + x^2 + x$
  - 将 $x^4$ 和 $x^3$ 模 $x^3 + x + 1$ 化简：
    $x^3 \equiv x + 1 \pmod{x^3 + x + 1}$
    $x^4 \equiv x \cdot x^3 \equiv x(x + 1) = x^2 + x \pmod{x^3 + x + 1}$
  - 因此：
    $c_2 = (x^2 + x) + (x + 1) + x^2 + x = x + 1 \pmod{x^3 + x + 1}$

因此，Bob将密文 $c_1, c_2) = (x^2, x + 1)$ 发送给Alice。

解密过程

Alice收到密文 $c_1, c_2) = (x^2, x + 1)$ 后，执行以下步骤来解密：

计算 $c_1^a \mod f(x)$ ：
$c_1^a \mod f(x) = (x^2)^3 \mod (x^3 + x + 1) = x^6 \mod (x^3 + x + 1)$
- 将 $x^6$ 模 $x^3 + x + 1$ 化简：
  $x^3 \equiv x + 1 \pmod{x^3 + x + 1}$
  $x^6 = (x^3)^2 \equiv (x + 1)^2 = x^2 + 1 \pmod{x^3 + x + 1}$
- 因此：
  $c_1^a \mod f(x) = x^2 + 1$
计算 $c_1^a \mod f(x)$ 的逆元：
- 需要找到一个多项式 $s (x)$ ，使得：
  $(x^2 + 1) \cdot s(x) \equiv 1 \pmod{x^3 + x + 1}$
- 通过扩展欧几里得算法或其他方法，可以计算出 $s(x) = x^2 + x$ （因为 $(x^2 + 1)(x^2 + x) \equiv 1 \pmod{x^3 + x + 1}$ ）。
解密明文：
$c_2 \cdot s(x) \mod f(x) = (x + 1) \cdot (x^2 + x) \mod (x^3 + x + 1)$
- 计算：
  $1)(x^2 + x) = x^3 + x^2 + x^2 + x = x^3 + 2x^2 + x = x^3 + x \quad (\text{因为} 2 \equiv 0 \pmod{2})$
  - 将 $x^3$ 模 $x^3 + x + 1$ 化简：
    $x^3 \equiv x + 1 \pmod{x^3 + x + 1}$
  - 因此：
    $x^2 + x \pmod{x^3 + x + 1}$

最终，Alice成功恢复了Bob发送的明文消息 $m = x^2 + x$ 。

总结

通过这个例子，我们可以看到ElGamal密码体系在扩展域 $\mathbb{F}_{p^n}$ 上的工作原理：

加密过程：Bob使用Alice的公钥和一个随机数 $k$ 对明文进行加密，生成密文 $c_1, c_2)$ 。
解密过程：Alice使用自己的私钥 $a$ 对密文进行解密，恢复出明文。

ElGamal密码体系的安全性基于离散对数问题的难解性，即使在扩展域上也是如此。

椭圆曲线密码学（ECC）示例

椭圆曲线的定义

椭圆曲线通常表示为一个方程，形式为：
$y^2 = x^3 + ax + b$
其中， $a$ 和 $b$ 是常数，且满足 $4a^3 + 27b^2 \neq 0$ ，以确保曲线是光滑的（没有奇点）。

为了简化计算，我们选择一个较小的有限域 $\mathbb{F}_p$ ，其中 $p$ 是一个素数。例如，选择 $p = 23$ ，并定义椭圆曲线为：
$y^2 \equiv x^3 + x + 1 \pmod{23}$

椭圆曲线上的点

在 $\mathbb{F}_{23}$ 上，椭圆曲线上的点 $(x, y)$ 满足上述方程。我们可以通过穷举法找到所有满足条件的点。例如：

当 $x = 0$ 时， $y^2 \equiv 1 \pmod{23}$ ，解得 $y = 1$ 或 $y = 22$ 。
当 $x = 1$ 时， $y^2 \equiv 3 \pmod{23}$ ，无解。
当 $x = 2$ 时， $y^2 \equiv 11 \pmod{23}$ ，无解。
以此类推，可以找到所有点。

假设我们找到了以下点：
$\{ (0, 1), (0, 22), (1, 7), (1, 16), \dots \}$

点的加法运算

椭圆曲线上的点可以进行加法运算，这是基于几何性质的。对于两个点 $P$ 和 $Q$ ，它们的和 $R = P + Q$ 也是椭圆曲线上的一个点。具体计算方法如下：

如果 $P = O$ （无穷远点），则 $P + Q = Q$ 。
如果 $Q = O$ ，则 $P + Q = P$ 。
如果 $P = - Q$ （即 $P$ 和 $Q$ 关于 $x$ 轴对称），则 $P + Q = O$ 。
如果 $\neq Q$ ，则通过 $P$ 和 $Q$ 的直线与椭圆曲线相交于第三个点 $R^{'}$ ，则 $R = - R^{'}$ 。
如果 $P = Q$ ，则通过 $P$ 的切线与椭圆曲线相交于点 $R^{'}$ ，则 $R = - R^{'}$ 。

在有限域上，这些运算可以通过代数公式完成。

示例：基于ECC的密钥交换（Diffie-Hellman）

假设Alice和Bob使用ECC进行密钥交换。

参数

椭圆曲线： $y^2 \equiv x^3 + x + 1 \pmod{23}$
基点： $G = (1, 7)$ （一个已知的点）
Alice的私钥： $a = 6$
Bob的私钥： $b = 9$

Alice的计算

计算公钥：
$\cdot G = 6 \cdot (1, 7)$
通过点加法计算 $\cdot G$ ，假设结果为 $A = (18, 20)$ 。

Bob的计算

计算公钥：
$\cdot G = 9 \cdot (1, 7)$
通过点加法计算 $\cdot G$ ，假设结果为 $B = (13, 10)$ 。

共享密钥

Alice和Bob交换公钥后，各自计算共享密钥：

Alice计算共享密钥：
$\cdot B = 6 \cdot (13, 10)$
通过点加法计算 $\cdot (13, 10)$ ，假设结果为 $S = (7, 12)$ 。
Bob计算共享密钥：
$\cdot A = 9 \cdot (18, 20)$
通过点加法计算 $\cdot (18, 20)$ ，假设结果为 $S = (7, 12)$ 。

最终，Alice和Bob得到了相同的共享密钥 $S = (7, 12)$ 。

示例：基于ECC的加密/解密

假设Alice使用ECC加密一条消息 $m$ 发送给Bob。

参数

椭圆曲线： $y^2 \equiv x^3 + x + 1 \pmod{23}$
基点： $G = (1, 7)$
Bob的公钥： $B = (13, 10)$
明文消息： $m = 5$ （假设消息是一个数字）

加密过程

选择随机数 $k$ ：
- Alice选择一个随机数 $k = 4$ 。
计算 $C_1$ ：
$C_1 = k \cdot G = 4 \cdot (1, 7)$
通过点加法计算 $\cdot (1, 7)$ ，假设结果为 $C_1 = (19, 20)$ 。
计算 $C_2$ ：
$C_2 = m \cdot G + k \cdot B = 5 \cdot (1, 7) + 4 \cdot (13, 10)$
通过点加法计算 $\cdot (1, 7)$ 和 $\cdot (13, 10)$ ，假设结果为 $C_2 = (2, 17)$ 。

Alice将密文 $C_1, C_2) = ((19, 20), (2, 17))$ 发送给Bob。

解密过程

Bob收到密文 $C_1, C_2) = ((19, 20), (2, 17))$ 后，执行以下步骤来解密：

计算 $\cdot B$ ：
$\cdot B = b \cdot C_1 = 9 \cdot (19, 20)$
通过点加法计算 $\cdot (19, 20)$ ，假设结果为 $(2, 17)$ 。
计算明文消息 $m$ ：
$C_2 - k \cdot B = (2, 17) - (2, 17) = O$
由于 $C_2 = k \cdot B$ ，因此 $m = O$ ，即无穷远点。

Bob成功恢复了Alice发送的明文消息 $m = 5$ 。

总结

通过这个例子，我们可以看到椭圆曲线密码学（ECC）的工作原理：

密钥交换：Alice和Bob通过椭圆曲线上的点加法运算，可以安全地共享一个密钥。
加密/解密：Alice使用Bob的公钥和一个随机数加密消息，Bob使用自己的私钥解密消息。

ECC的安全性基于椭圆曲线上的离散对数问题（ECDLP），即给定椭圆曲线上的点 $G$ 和 $\cdot G$ ，计算 $k$ 是非常困难的。

Public-Key Cryptography and Discrete Logarithms

Discrete Logarithm

The ElGamal Cryptosystem

Finite Fields

Elliptic Curves

Elliptic Curves: over the Reals

Elliptic Curves Modulo a Prime

Elliptic Curves over Finite Fields

Algorithm Optimization

Signed Binary Representation

DOUBLE-AND-(ADD OR SUBTRACT) ALGORITHM

ElGamal密码体系的加密与解密示例

示例参数

加密过程

解密过程

为什么需要逆元

总结

ElGamal密码体系在扩展域上的示例

扩展域 F 2 3 \mathbb{F}_{2^3} F23​的构造

示例参数

加密过程

解密过程

总结

椭圆曲线密码学（ECC）示例

椭圆曲线的定义

椭圆曲线上的点

点的加法运算

示例：基于ECC的密钥交换（Diffie-Hellman）

参数

Alice的计算

Bob的计算

共享密钥

示例：基于ECC的加密/解密

参数

加密过程

解密过程

总结

相关文章：

扩展域 $\mathbb{F}_{2^3}$ 的构造