Самый надежный пароль

У меня есть приложение, защищенное четырехзначным PIN-кодом, и пользователь получил пять попыток войти в систему, прежде чем учетная запись заблокирована.

Теперь один из моих клиентов хочет «усилить» безопасность и отстаивать другое решение:

• шесть-значный PIN-
• НЕТ "одной цифры рядом друг с другом": например, 11 3945 или 39 55 94
• НЕТ «трехзначных чисел»: например: 123 654 или 53 789 3

Теперь вопрос: какое решение самое сильное?

Я могу легко вычислить четырехзначную цифру, но как рассчитать другую?

Благодаря!

Обновить

Вы получаете то, что просите - особенно при работе с математикой :)

Итак, что я просил, так это количество комбинаций для обеих числовых последовательностей.

Прочитав ответы и комментарии, я понял, что это не имеет значения. Если у вас есть 5 предположений, то не имеет значения, есть ли у вас 10.000 или ~ 800.000 на выбор. Более важным является исключение 1234 и день рождения. В моей ситуации у меня фактически есть день рождения пользователя, поэтому у меня есть что проверить.

Спасибо за отличную дискуссию!

Вы обратились за помощью по этому вопросу на форум статистиков, поэтому я предоставлю статистический ответ. Таким образом, разумно предположить, что вас интересует вероятность угадывания PIN-кода случайным образом (для некоторого определения случайного числа), но это больше понимает вопрос, чем предусмотрено.

Мой подход будет состоять в том, чтобы перечислить все возможные варианты без ограничения, а затем вычесть пустые варианты. Это имеет острый угол, хотя и называется принципом включения-исключения, что соответствует интуитивной идее, что вы не хотите вычитать одно и то же из набора дважды!

В шестизначном ПИН-коде без ограничений и десятичной системе счисления существует возможных комбинаций от до каждая цифра имеет 10 вариантов.$10^6$$000 000$$999 999:$

Рассмотрим, как выглядят «две соседние, одинаковые» цифры: , где позиции, помеченные , одинаковы, а может быть любой десятичной цифрой. Теперь рассмотрим, сколько еще строк можно расположить в шесть цифр: , , и . Таким образом, для любого конкретного порядка (одного из этих вариантов) существует не менее комбинаций, поскольку есть цифры без ограничений. Теперь, сколько выбора из есть? Мы работаем с десятичными цифрами, поэтому должно быть 10. Таким образом, есть$AAXXXX$$A$$X$$AA$$XAAXXX$$XXAAXX$$XXXAAX$$XXXXAA$$10^4$$10^4$$A$$10^5$выбор для конкретного заказа. Существует пять таких порядков, поэтому есть соглашений, которые удовлетворяют этому определению. (То, что это означает с точки зрения безопасности, может быть измерено с точки зрения теоретико-информационной меры того, насколько это уменьшает энтропию пространства ПИН.)$5\times10^5$

Теперь рассмотрим, как выглядят последовательные числа. В строке , если мы знаем A, мы также знаем B и C *: если A равно 5, то B равно 6, а C равно 7. Таким образом, мы можем перечислить следующие параметры:$ABCXXX$

• 012XXX
• 123XXX
• 234XXX
• 456XXX
• 789XXX

и на данный момент неясно, есть ли «обтекание». Если есть, мы также включаем

• 890XXX
• 901XXX

Каждое решение имеет связанных комбинаций, по той же причине, что и выше. Так что просто подсчитайте, сколько решений должно быть. Имейте в виду, чтобы подсчитать альтернативные заказы, такие как$10^3$$XABCXX.$

Теперь мы подошли к острому углу, который является принципом включения-исключения. Мы сделали набор из всех шестизначных ПИН-кодов в трех наборах:

A. Допустимые PIN-коды B. Отмена PIN-кодов из-за «соседних цифр» C. Отмена PIN-кодов из-за «последовательных цифр»

Но есть дополнительная тонкость, которая является то , что есть некоторые 6-значные числа , которые могут быть выделены как и . Поэтому, если мы вычисляем мы вычитаем эти числа дважды, и наш ответ неверен. Правильное вычисление где есть множество элементов как и . Таким образом , мы должны определить , сколько способов может число падения как и .C | S | = | A | - | Б | - | C | , | S | = | A | - | Б | - | C | + | B ∩ C | , B ∩ C B C B $B$$C$$|S|=|A|-|B|-|C|,$$|S|=|A|-|B|-|C|+|B\cap C|,$$B\cap C$$B$$C$$B$$C$

Это может произойти несколькими способами:

• $AABCXX$
• $ABCXDD$ и так далее. Таким образом, вы должны выработать системный подход к этому, а также способ отслеживать альтернативные заказы. Используя ту же логику, которую я применил выше, это должно быть очень гибким, хотя и немного утомительным. Просто имейте в виду, сколько может быть альтернативных способов удовлетворить как B, так и C.

Немного более продвинутые подходы воспользуются преимуществами основных комбинаторных результатов и фундаментальной теоремы подсчета, но я выбрал этот путь, поскольку он ложится наименьшим техническим бременем для читателя.

Теперь, чтобы это был правильно сформированный вопрос вероятности, мы должны иметь некоторую меру вероятности для каждого соглашения. В предположении наивной атаки можно предположить, что все комбинации цифр имеют равную вероятность. В этом сценарии вероятность случайно выбранной комбинации равна Однако, если вы заинтересованы в такой атаке, то предложенный набор критериев, очевидно, ослабляет систему, потому что некоторые комбинации запрещены, так что их может попробовать только тупой атакующий. Я оставляю остальное упражнение читателю.$\frac{1}{|S|}$

Складка «пять до блокировки» определенно лучше защищает от несанкционированного доступа, так как в четырехзначной или шестизначной схеме существует очень большое количество вариантов, и даже пять различных случайных догадок имеют низкое значение. вероятность успеха. Для правильно поставленного вопроса о вероятности можно рассчитать вероятность успеха такой атаки.

Но другие факторы, кроме вероятности последовательностей чисел, могут влиять на безопасность механизма ПИН. В основном люди не выбирают ПИН-код наугад! Например, некоторые люди используют свою дату рождения, или DOB детей, или какой-либо аналогично личный номер в качестве PIN-кода. Если злоумышленник знает DOB пользователя, он, вероятно, будет одним из первых, что он попробует. Таким образом, для конкретного пользователя некоторые комбинации могут быть более вероятными, чем другие.

* Последовательность, которую вы перечисляете, строго увеличивается, и неясно, будет ли она увеличиваться и уменьшаться, когда вы говорите «трехзначное число».

Получение закрытой формулы кажется сложным. Однако их довольно легко перечислить. Есть 568 916возможные коды для второго решения. Что больше, чем количество решений с четырехзначным PIN-кодом. Код для их перечисления ниже. Хотя и не оптимизировано, для запуска требуется всего несколько секунд.

Запись. Я предположил, что последовательность должна быть в порядке возрастания (который можно легко изменить в three_running)

N = 999999

candidates = range(N)

def same_consecutive_digits(x):
    x_string = str(x).zfill(6)
    for i in range(1,len(x_string)):
        if x_string[i] == x_string[i-1]:
            return True
    return False

def three_running(x):
    x_string = str(x).zfill(6)
    for i in range(2,len(x_string)):
        if int(x_string[i]) == int(x_string[i-1]) + 1 and int(x_string[i-1]) == int(x_string[i-2]) + 1:
            return True
    return False

def valid(x):
    return not same_consecutive_digits(x) and not three_running(x)

assert(same_consecutive_digits(88555))
assert(same_consecutive_digits(123))
assert(not same_consecutive_digits(852123))
assert(three_running(123456))
assert(not three_running(4587))
assert(valid(134679))
assert(not valid(123894))
assert(not valid(111111))
assert(not valid(151178))
assert(valid("031278"))

accepted = [i for i in range(N) if valid(i)]
print(len(accepted))