
研究者探讨用线性同余生成器扫描全互联网地址时如何避免短循环
来源标题:Counting to 4B with linear congruential generators and Feistel networks
Hull 和 Dobell 1962 年证明的条件可用于选取线性同余生成器参数,使其在模 2^k 下具有满周期,从而避免陷入短循环。作者选用 Numerical Recipes 的乘数 1,664,525,并用 splitmix64 从种子派生出奇数的增量 c,以保证 IPv4 和 IPv6 地址空间都能完整遍历。该生成器输出的是索引而非地址本身。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
差的那些会进入一个短循环,永远到不了钟面的其余部分。作为扫描器,这会漏掉半个互联网,甚至几乎全部,而输出看起来仍然足够随机,让人察觉不出问题。
Hull 和 Dobell 在 1962 年精确证明了哪些取值可用。一个 LCG 具有满周期——即对模 m 的每个值恰好访问一次——当且仅当:
当 m 是 2 的幂时,它唯一的质因数是 2,三个条件缩减为两个:c 为奇数,且 a - 1 能被 4 整除。在四个时钟里,a = 5、c = 3 两个条件都满足。c = 2 是偶数。a = 3 给出 a - 1 = 2,a = 4 给出 3,都不能被 4 整除。
我选了 a = 1,664,525,即 Numerical Recipes 中的乘数。1,664,524 = 4 x 416,131,所以第二个条件对任何 2 的幂都成立。我不想让 c 是一个固定常数,所以它由种子经 splitmix64 导出,并强制其最低位为 1,这样它永远是奇数,对任何模 2k(IPv4 或 IPv6)都保证满周期。不同的 c 也意味着每个值的后继都不同,因为 a x v + c 随 c 变化,所以两个种子给出两种不同的顺序,而不是同一个循环从两个不同点开始。
生成器产生的是索引,不是地址。把排除之后剩下的目标地址从 0 编号到 N - 1,把时钟设为 2k,即大于等于 N 的最小 2 的幂,并跳过任何大于等于 N 的索引。由于 2k < 2N,被跳过的步数不到一半,而一个普通 CIDR 一步都不跳过。从 0.0.0.0/0 中排除私有和保留空间:
0.0.0.0/0 4,294,967,296 private & reserved - 592,708,864 ────────────────────────────────────────── N 3,702,258,432 skipped steps 13.8%
被排除的地址永远不会先生成再丢弃。它们根本不属于索引空间。一张有序的排除表把索引 i 映射到第 i 个未被排除的地址,所以 10.0.0.0/8 永远不会出现,唯一的浪费是超过 N 的那 13.8% 的步,每步花费一次生成器步进和一次混合。
一步是 x -> 5x + 3。两步就是该函数作用于自身:
one step: x -> 5x + 3 two steps: x -> 5(5x + 3) + 3 = 25x + 18 = 9x + 2 (mod 16)
LCG 的两步是另一个常数不同的单步 LCG。从 3 出发,两步应落在 13,而 9 x 3 + 2 = 29,29 mod 16 = 13。一般来说,先施加 (a1, c1) 再施加 (a2, c2) 得到:
(a2 x a1, a2 x c1 + c2)
把 2 步的常数与自身复合,得到 4 步,然后 8、16、32。任何步数都是这些 2 的幂之和,就像任何数都能写成二进制一样,所以跳 n 步对 n 的每一位做一次平方、对每个置位做一次复合。这就是平方求幂,与 RSA 中模幂所用的技巧相同。在 C 中:
/* Compose n steps of x -> a*x + c into one (a, c), modulo the power of 2 behind mask */ static void jump_params(u128 n, u128 c, u128 mask, u128 *ra, u128 *rc) { u128 a = 1, b = 0, sa = LCG_A & mask, sc = c & mask; while (n) { if (n & 1) { a = (sa * a) & mask; b = (sa * b + sc) & mask; sc = (sa * sc + sc) & mask; sa = (sa * sa) & mask; n >>= 1; *ra = a; *rc = b;
它用 128 位算术,所以同一份代码覆盖 IPv6。从 0 跳 109 步落在 2,621,190,656,与一步步走这 109 步得到的值相同。循环对步数的每一位运行一次,所以 IPv4 空间中的任何跳转最多 32 轮,而不是多达 4,294,967,295 步。
循环恰好包含每个索引一次,所以它可以像一副牌一样发出去。T 个分片中的第 i 个分片走第 i、i + T、i + 2T 步,依此类推。在 16 个位置的时钟上,4 台机器:
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。