- 如果 2³ = 8
- 那么 log₂(8) = 3
这很容易计算:
- 正向:
2³ = 2 × 2 × 2 = 8
- 反向:log₂(8) = 3 也不难
在模运算下的对数问题:
-
比如在 mod 11 下:
-
2³ ≡ 8 (mod 11)
-
问题:已知
2ˣ ≡ 8 (mod 11)
,求 x -
这就是离散对数问题!
已知:
- 基点 G
- 点 P = kG(k次点加运算)
- 求 k
- (k 一般是个大随机数, 私钥) 就像:
- 知道 G 和 3G
- 要反推那个 3
- 因为结果是离散的值(不连续)
- 在模运算中,只有
有限个可能的值
(群) - 没有连续的中间状态
- 普通对数可以用计算器
- 离散对数没有类似工具
- 只能一个个试:
- kG, 2G, 3G, 4G...
- 直到找到匹配的点
在实际应用中:
- k 是 256 位的数
- 可能的值有 2²⁵⁶ 种
- 暴力破解需要太长时间
-
容易的方向:
-
私钥(k) → 公钥(kG)
-
困难的方向:
-
公钥(kG) → 私钥(k)
- 生成公钥很容易(正向计算)
- 从公钥推导私钥几乎不可能(需要解离散对数)