security - 什么是Android点密码系统的熵？

Question

android点登录系统可以进行多少种排列？我知道事实的解决方案在于离散数学，特别是Permutations Without Repetition，如果您的答案不使用排列或组合，那么您是错误的。

密码的长度在4到9个点之间，但是总共有9个点需要置换。所以我的初始方程式是:

9P4+9P5+9P6+9P7+9P8+9P9

但是，我知道这个方程式是不完整的，因为它没有考虑所有规则。每个点由于位置而不同，因此，如果您按如下方式为每个点分配一个数字，则:

123
456
789

密码“1397”是不可能的，如果您尝试使用该密码，实际上您已经输入了“1236987”，因为它们之间的数字是自动选择的。需要创建另一个方程式来解决这些限制，然后从上面的我的nPr方程中减去。

这个link的视频非常棒，有人在使用android登录名。在规则中也有更详细的说明。该页面上的数学运算完全不正确，他甚至没有一个真正的解决方案。

Answer 1

这只是部分答案。唯一相关的起始点是1、2和5。对于点1和2，您可以通过简单的旋转变换来生成等效于从任何其他点(5以外的点)开始的图案。这意味着，如果您可以枚举从1和2开始的所有模式，则可以通过乘以4来计数从5以外的任何数字开始的所有模式。

从5开始的路径是不同的情况。您可以通过计算以5-> 1和5-> 2开头的所有路径并乘以4来计算所有这些路径，因为您可以通过简单的旋转变换再次生成所有其他可能的路径。

因此，枚举路径的方法是...

(从1开始的所有路径+从2开始的所有路径+以5-> 1开头的所有路径+以5-> 2开头的所有路径)* 4

再次，编号系统，以方便引用:

1  2  3
4  5  6
7  8  9

对于此第一步:

从1-> 2、4、5、6和8可访问。

从2-> 1、3、4、5、6、7和9可访问(基本上不是8或本身)。

从5-> 1、2、3、4、6、7、8和9可访问。

此后的 Action 变得非常有趣。

例如，1537是有效密码。 1539不是。

简而言之，是规则:

没有点可能两次成为路径的一部分。如果点不是路径的一部分，并且通过过渡恰好与之交叉，则它将成为源点和目标点之间路径的一部分。

以下是一些示例路径:

允许

2-> 3-> 1-> 8。

1-> 3-> 2-> 5是不允许的，因为当1-> 3刚好超过2时，2并不是路径的一部分，因此无论您想要的路径是1-> 2-> 3-> 5去还是不去。

1-> 2-> 3-> 7是不允许的，因为3-> 7跨越5并且5尚未成为路径的一部分。

允许

1-> 5-> 3-> 7。在3-> 7中忽略5，因为它已经是路径的一部分。

该程序:

class LockPattern(object):
    def __init__(self, *args):
        if (len(args) == 1) and hasattr(args[0], '__iter__'):
            args = tuple(args[0])
        if len(args) > 9:
            raise TypeError("A LockPattern may have at most 9 elements.")
        self._pattern = ()
        for move in args:
            if not self.isValidNextStep(move):
                raise TypeError("%r is not a valid lock sequence." % (args,))
            else:
                self._pattern = self._pattern + (move,)
    def __len__(self):
        return len(self._pattern)
    def __iter__(self):
        return iter(self._pattern)
    def isValidNextStep(self, nextdot):
        nextdot = int(nextdot)
        if (nextdot < 1) or (nextdot > 9):
            raise ValueError("A lock sequence may only contain values from 1 "
                             "to 9 and %d isn't." % (nextdot,))
        if len(self._pattern) <= 0:
            return True # Any dot is valid for the first dot
        if len(self._pattern) >= 9:
            return False
        if nextdot in self._pattern:
            return False # No dot may be visited twice
        prevdot = self._pattern[-1]
        dotpair = tuple(sorted((prevdot, nextdot)))
        if dotpair == (1,3):
            return 2 in self._pattern
        if dotpair == (1,7):
            return 4 in self._pattern
        if dotpair in ((1,9),(2,8),(3,7),(4,6)):
            return 5 in self._pattern
        if dotpair == (3,9):
            return 6 in self._pattern
        if dotpair == (7,9):
            return 8 in self._pattern
        return True
    def isValidLockSequence(self):
        return 4 <= len(self)
    def newSequenceAddDot(self, nextdot):
        if not self.isValidNextStep(nextdot):
            raise ValueError("%d is not a valid next dot for the sequence." % (nextdot,))
        newseq = LockPattern()
        newseq._pattern = self._pattern + (nextdot,)
        return newseq

def genAllPatterns(starting = LockPattern()):
    if starting.isValidLockSequence():
        yield starting
    for dot in xrange(1,10):
        if starting.isValidNextStep(dot):
            for result in genAllPatterns(starting.newSequenceAddDot(dot)):
                yield result

print reduce(lambda x, p: x+1, genAllPatterns(), 0)

生成389112的答案。

这也验证了我以前的直觉:

lsts = tuple(((p, list(genAllPatterns(LockPattern(p)))) for p in ((1,), (2,), (5,1), (5,2))))
[(x[0], len(x[1])) for x in lsts]
-> [((1,), 38042), ((2,), 43176), ((5, 1), 7352), ((5, 2), 8708)]
sum((len(x[1]) for x in lsts)
-> 97278
97278 * 4
-> 389112