math - 生成一系列随机 6 位数字，避免潜在的因一位或换位错误

Question

我有一个应用程序，其中将分配 6 位数字用于物理访问控制。我遇到的困难是找到一种方法来避免单位数字或换位错误，从而产生有效的 PIN(来自该位置的一系列 PIN)。我们希望每个位置不再需要 1000 个 PIN。

无法在访问控制点执行校验和，因为它只会根据批准的 PIN 列表查找 PIN。

有人有什么建议吗？

Answer 1

1000 个数字很少。只要有一种算法，一次生成一个六位随机数即可。对于生成的每个号码，它会检查该号码是否已被使用，如果没有，则将其添加到 PIN 列表中，并将该号码本身及其所有单位数字和换位错误标记为已使用。对于 6 位十进制数，可能存在 6×9=54 个单位错误，6C2=15 个换位错误(如果只关心相邻换位，则只有 5 个错误)，因此该数字本身加上所有附近的数字总计为 70 个数字生成的号码，或您需要跟踪的一组 70,000 个号码。

这种方法的巨大好处除了非常简单之外，还在于它几乎保持了完全随机生成 6 位数字的全部熵。对任何单个 PIN 没有额外限制，仅对 PIN 总数设置限制。因此，只有当您拥有大量已知的 PIN 码时，理论上您才可以使用它们来稍微减少您尚不知道的 PIN 码的搜索空间。我想说，效果太小，没有实际意义。即使您知道 1000 个 PIN 中的 999 个，您也可以从 10⁶=1,000,000 个可能的 PIN 中排除最多 999×70=69,930 个，即少于 7%。

任何仅生成 5 位数字然后添加校验和的方法都将具有比这更少的熵，即可以更轻松地通过在较小的域上进行强力试验来找到 PIN。

一条评论提出了这样一个问题:这整件事是否值得付出努力。一方面，发生碰撞的实际可能性是多少？有 (10⁶)¹⁰⁰⁰=10⁶⁰⁰⁰ 种可能的方法来独立选择 PIN(甚至允许重复)。大约有 1,000,000×999,930×…=product(10⁶−70k for k from 0 to 999)≈2.8×10⁵⁹⁸⁴ 种方法可以做到这一点，而不会出现您所描述的冲突。这是一个小得多的数字。这 1000 个数字中的任意两个(类似于 birthday paradox )之间发生冲突的几率为 (10⁶⁰⁰⁰ − 2.8×10⁵⁹⁸⁴)/10⁶⁰⁰⁰ = 1−2.8×10⁻¹⁶ ≈ 1 因此，使用完全随机选择的这种几乎冲突的可能性非常(尽管在 almost certain 中并非如此)数学意义)。但这并不意味着任何一个 PIN 码的任何一个错误都有很大机会与另一个 PIN 码匹配。

另一方面，您要防范的场景是什么？无论如何，任意数字成为有效 PIN 码的几率均为 1000:10⁶ = 1:1000。因此，如果您认为可能性为 0.1%，那么陌生人猜出有效 PIN 码的可能性已经相当大了。你要防范的是两件事之一。知道 PIN 码的人可以作为其他人进行身份验证。如果您考虑到在某些设置中由普通用户输入且输错的 PIN 可能比陌生人随机输入的 PIN 更有可能，那么这是有道理的。但是，除非 PIN 码的身份相关，即您根据 PIN 码授予不同的访问权限，或者您保留使用过的 PIN 码的日志，否则这并不重要:如果已经使用一个 PIN 码获得访问权限的人使用另一PIN不同，那又怎样？还有一种情况是，观察者可能正在观察密码键盘，因此可能会了解到几乎正确的 PIN，而您希望避免它意外地变为实际正确的情况。如果这是一个严重的问题，您应该考虑设置密码键盘，或者要求用户在输入 PIN 码时隐藏键盘。