8.1 历史 ADR：Base62 位数保持混淆方案与正确性复核

2 months ago
5a2e80a

历史 ADR：Base62 位数保持混淆方案与正确性复核

状态：历史记录，非当前算法正确性保证。本文保留原问题和方案意图，并修正原记录中“必然保持位数”“整体为双射”的过强结论。

背景

短码自动生成流程以域名级递增 ID 为输入，可选执行 XOR 混淆，再进行 Base62 编码，并按域名配置追加随机后缀和校验位。历史问题是：期望进入四位 Base62 区间的 ID 在混淆后可能落回三位区间。

Base62 的 N 位数值范围是：

[62^(N-1), 62^N - 1]

部分边界：

位数 起始值 结束值
1 0 61
2 62 3,843
3 3,844 238,327
4 238,328 14,776,335
5 14,776,336 916,132,831

当时的设计意图

历史调整不再直接在 ID 的二进制位宽内旋转，而是：

  1. 计算 ID 的 Base62 位数；
  2. 取该位数对应的 minVal、maxVal 和 rangeSize；
  3. 归一化为 id - minVal；
  4. 在 rangeSize 内做加法旋转；
  5. 与 secret % rangeSize 做 XOR；
  6. 加回 minVal。

当前 local 和 Redis 发号器都保留了相同形式：

normalized = (normalized + rotAmount) % rangeSize
obfuscated := normalized ^ (secret % rangeSize)
return obfuscated + minVal

正确性复核

加法旋转 x → (x + r) mod rangeSize 在有限环上是双射，并保持 0 <= x < rangeSize。问题在随后的 XOR：当 rangeSize 不是 2 的幂时，即使两个操作数都小于 rangeSize，XOR 结果也可能大于或等于 rangeSize。

二位 Base62 区间的 rangeSize = 3782。存在简单反例：

normalized = 2
secret % rangeSize = 3780
2 XOR 3780 = 3782

结果已经越过合法归一化上界 3781；加回 minVal=62 后得到 3844，进入三位 Base62 区间。因此仅凭当前公式不能证明位数必然保持。

同样，“XOR 自身可逆”不足以证明整个限定区间上的映射是双射：若输出允许越界，或者后续为了回区间简单取模，都需要重新证明无碰撞。

当前使用建议

  • 不把 enable_xor_obfuscation 当作密码学加密或安全边界。
  • 对短码长度有严格外部契约时，优先关闭 XOR，并通过 default_start_number、随机后缀和校验位配置长度。
  • 域名的生成参数创建后由更新接口保护，避免运行中改变历史规则。
  • 在修改算法前固定历史测试向量，验证 local 与 Redis 实现一致。

后续算法要求

若未来重新实现真正的位数保持置换，应满足：

  1. 对每个 Base62 位数区间，输入和输出集合完全相同；
  2. 映射是可证明的双射，不通过有碰撞的取模修补；
  3. 对边界 62^(N-1) 与 62^N-1 做性质测试；
  4. local/Redis 使用同一共享实现，避免复制漂移；
  5. 升级不改变既有短码解析，且给出兼容/迁移策略；
  6. 明确混淆只降低可预测性，不替代授权、限速和安全策略。

可考虑在固定有限域上的 Feistel 置换或 cycle-walking，但选型前必须评估性能、证明、密钥轮换和向后兼容。

关联章节