多少位字符串能够遍历六位密码？

zihubu · 发表于 2024-4-9 19:59

智能门锁有虚位密码功能，即不管输入多少位，只要输入数据中包含连续六位正确密码，就可以开启。那么设想这样一个暴力破解场景，对于任意一组六位密码，最少输入多长的字符串能开启这道门？我一开始是想可能十万位多一点就能遍历这十万种组合，但觉得也不太可能。

shamisen · 发表于 2024-4-9 20:03

字符串是什么意思，你的锁6位密码每位有256种可能吗

Freewolf · 发表于 2024-4-9 20:05

本帖最后由 Freewolf 于 2024-4-9 20:14 编辑

德布鲁因序列？
编辑：查到了，这种序列叫超排列，有个著名的超排列下界问题就是凉宫春日问题
https://groups.google.com/g/superpermutators/c/0k_z5srgXbg?pli=1
这个链接似乎就是n=6时超排列的证明，序列长度872

https://www.gregegan.net/SCIENCE ... erpermutations.html
这里有更详尽的解释

Hieda · 发表于 2024-4-9 20:06

少刷点OJ吧

2474089352 · 发表于 2024-4-9 20:08

全排列按序数拼一起成串，然后从前往后滑动窗口计算当前窗口内容的序数并从串中移除。应该不是最优。

论坛助手,iPhone

長友彩海 · 发表于 2024-4-9 20:10

6位的话，下界是组合数量加5，上界是组合数量的6倍？

日日夜夜 · 发表于 2024-4-9 20:24

Freewolf 发表于 2024-4-9 20:05
德布鲁因序列？
编辑：查到了，这种序列叫超排列，有个著名的超排列下界问题就是凉宫春日问题
https://grou ...

超排列问题是n个元素的排列，n=6时只有6个元素，lz的问题则是0-9共10个元素的6个的组合

aki1ostt · 发表于 2024-4-9 20:25

这个问题实际上是一个排列组合问题。我们需要找出一个字符串，使其包含所有可能的6位数字组合。每个数字可以是0-9中的任何一个，所以总共有$10^6$（即1,000,000）种可能的6位数字组合。

假设我们有一个字符串，每次我们只移动一位来获取一个新的6位数字组合。这就像是一个滑动窗口，窗口大小为6，每次移动一位。为了包含所有可能的6位数字组合，我们需要的字符串长度至少为$10^6 + 6 - 1 = 1,000,005。这是因为我们的滑动窗口需要移动\10^6 - 1$次来获取所有可能的组合，而初始窗口就占用了6位。

所以，一个由数字组成的字符串，长度至少需要达到1,000,005，才能包含所有可能的6位数字组合。

Freewolf · 发表于 2024-4-9 20:25

日日夜夜发表于 2024-4-9 20:24
超排列问题是n个元素的排列，n=6时只有6个元素，lz的问题则是0-9共10个元素的6个的组合 ...

原来如此，是我理解错了

Ny · 发表于 2024-4-9 20:32

https://www2.zhihu.com/question/333880103

mqm · 发表于 2024-4-11 14:14

本帖最后由 mqm 于 2024-4-11 14:16 编辑

后知后觉，编辑

qqdragon · 发表于 2024-4-11 14:16

支付宝sb 刚被强制改了六位数字密码

GMJ · 发表于 2024-4-11 14:32

aki1ostt 发表于 2024-4-9 20:25
这个问题实际上是一个排列组合问题。我们需要找出一个字符串，使其包含所有可能的6位数字组合。每个数字可 ...

要不了那么多，中间有很多可以重复利用的

小野賢章 · 发表于 2024-4-11 14:32

考虑简化的二进制密码，只有字符 0 和 1，密码长度为 4，可以构造一个有向图：图的每个顶点是长度为 3 的密码的组合情况，然后每个顶点发出两条边，分别表示在尾部加 0 或 1，然后去掉第一位，然后找到这个图的欧拉回路，也就是解决一笔画问题。构造的这个有向图的入度和出度相等，一定可以一笔画。记录下一笔画遍历的每个顶点的，就是一个德布鲁因序列。

		自动登录	找回密码
密码			立即注册

[科技] 多少位字符串能够遍历六位密码？

本帖子中包含更多资源

评分