大步小步算法

在群论中，大步小步算法（）是发明的一种中途相遇算法，用于计算离散对数或者有限阿贝尔群的阶。其中离散对数问题在公钥加密领域有着非常重要的地位。

许多常用的加密系统都基于离散对数极难计算这一假设——计算越困难，这些系统提供的数据传输就越安全。增加离散对数计算难度的一种方法，是把密码系统建立在更大的群上。

理论
这是一种空间换时间的算法，实质上是求解离散对数的朴素算法（枚举并试乘）的一个相当简单的改进。

给出一个 n 阶循环群 G 、该群的一个生成元 \alpha 和一个元素 \beta 。试找到一个整数 x 满足
: \alpha^x = \beta\,.

大步小步算法把 x 代换成：
:x = im + j
:m = \left\lceil \sqrt{n} \right\rceil
:0 \leq i
:0 \leq j

于是有：
: \alpha^x = \beta\,
: \alpha^{im + j} = \beta\,
: \alpha^j = \beta\left(\alpha^{-m}\right)^i\,

该算法先对 j 的不同取值计算出 \alpha^j 的值，然后固定一个 m ，并对 i 尝试不同的取值,带入上面同余式的右边，看是否与某个（已经预先算出的）同余式左边的值相匹配。

算法
给出C++17版本的代码：

#include
#include
#include

std::uint32_t pow_m(std::uint32_t base, std::uint32_t exp, std::uint32_t mod) {
// 这里需要实现快速幂算法
}

///计算满足 g^x % mod == h 的x
std::optional babystep_giantstep(std::uint32_t g, std::uint32_t h, std::uint32_t mod) {
const auto m = static_cast(std::ceil(std::sqrt(mod)));
auto table = std::unordered_map{};
auto e = std::uint64_t{1}; // 临时值可能大于32位整数的范围
for (auto i = std::uint32_t{0}; i (e)] = i;
e = (e * g) % mod;
}
const auto factor = pow_m(g, mod-m-1, mod);
e = h;
for (auto i = std::uint32_t{}; i (e)); it != table.end()) {
return {i*m + it->second};
}
e = (e * factor) % mod;
}
return std::nullopt;
}

實務應用
加速大步小步算法的最佳方式，是使用高效的表格查找機制。在此情況下，最適合的是使用雜湊表（hash table）。雜湊是針對第二個元件（即元素對的第二個值）進行，並且在主迴圈的第 1 步中，會對 γ 做雜湊，然後檢查對應的記憶體位置。由於雜湊表可以在 O(1)（常數時間）內進行新增與查詢操作，因此這個過程不會拖慢整體的大步小步算法。

此演算法的空間複雜度為 O(\sqrt{n})，而時間複雜度則為 O(\sqrt{n})。這樣的執行時間比起暴力的 O(n) 執行時間來得更優。

當模數是一個不是太大的質數時，竊聽者可以使用大步小步算法來推導在Diffie–Hellman金鑰交換中產生的私鑰。如果模數不是質數，則可以使用Pohlig–Hellman演算法，其演算法複雜度更低，也有可能解出相同的問題。

评论 (0)