Как сгенерировать проверочный код / ​​номер?

Question

Я работаю над приложением, в котором пользователи должны позвонить и ввести проверочный номер с клавиатуры своего телефона.

Я бы хотел определить, является ли число, которое они вводят, правильным или нет. Телефонная система не имеет доступа к списку действительных номеров, но вместо этого проверяет номер по алгоритму (например, по номеру кредитной карты).

Вот некоторые требования:

• Должно быть трудно ввести правильный случайный код
• Должно быть сложно иметь действительный код, если я произвожу опечатку (перестановка цифр, неправильная цифра)
• У меня должно быть разумное количество возможных комбинаций (скажем, 1M)
• Код должен быть максимально коротким, чтобы избежать ошибок со стороны пользователя

Учитывая эти требования, как бы вы сгенерировали такое число?

РЕДАКТИРОВАТЬ:

@ Haaked: код должен быть числовым, потому что пользователь набирает его на своем телефоне.

@ matt b: на первом шаге код отображается на веб-странице, второй шаг - вызвать и ввести код. Я не знаю номер телефона пользователя.

Продолжение: я нашел несколько алгоритмов для проверки достоверности чисел (см. Этот интересный проект Google Code: checkDigits ).

Answer 1

После некоторых исследований, я думаю, я пойду с формулой ISO 7064 Mod 97,10 . Кажется, это довольно солидно, поскольку используется для проверки IBAN (Международный номер банковского счета).

Формула очень проста:

1. Взять номер: 123456
2. Примените следующую формулу, чтобы получить контрольную сумму из 2 цифр: mod(98 - mod(number * 100, 97), 97) => 76
3. Конкат номер и контрольная сумма для получения кода => 12345676
4. Чтобы подтвердить код, убедитесь, что mod(code, 97) == 1

Тест:

• mod(12345676, 97) = 1 => ХОРОШО
• mod(21345676, 97) = 50 => ПЛОХО!
• mod(12345678, 97) = 10 => ПЛОХО!

По-видимому, этот алгоритм отлавливает большинство ошибок.

Еще одним интересным вариантом был алгоритм Верхоффа . Он имеет только одну проверочную цифру и его сложнее реализовать (по сравнению с простой формулой выше).

Answer 2

Для 1М комбинаций вам понадобится 6 цифр. Чтобы убедиться, что нет случайно действительных кодов, я предлагаю 9 цифр с вероятностью 1/1000, что случайный код работает. Я бы также предложил использовать другую цифру (всего 10) для проверки целостности . Что касается шаблонов распределения, то будет достаточно случайного выбора, а контрольная цифра обеспечит, что одна ошибка не приведет к правильному коду.

Редактировать: Видимо, я не полностью прочитал ваш запрос. Используя номер кредитной карты, вы можете выполнить хэш (MD5 или SHA1 или что-то подобное). Затем вы обрезаете в соответствующем месте (например, 9 символов) и конвертируете в основание 10. Затем добавляете контрольную цифру (и), и это должно более или менее работать для ваших целей.

Answer 3

Вы хотите сегментировать свой код. Часть этого должна быть 16-битной CRC остальной части кода.

Если вам нужен только проверочный номер, просто используйте порядковый номер (при условии, что у вас есть единственная точка генерации). Таким образом, вы знаете, что вы не получаете дубликаты.

Затем вы префикс последовательности с CRC-16 этого порядкового номера И некоторый закрытый ключ. Вы можете использовать все что угодно для закрытого ключа, если вы храните его в секрете. Сделайте что-то большое, по крайней мере, GUID , но это может быть текст Война и мир из проекта Гутенберг . Просто нужно быть тайным и постоянным. Наличие закрытого ключа не позволяет людям подделать ключ, но использование 16-битного CR облегчает его взлом.

Чтобы проверить, просто разделите номер на две части, а затем возьмите CRC-16 из порядкового номера и секретного ключа.

Если вы хотите больше скрыть последовательную часть, разделите CRC на две части. Поместите 3 цифры впереди и 2 сзади последовательности (нулевой блок, чтобы длина CRC была одинаковой).

Этот метод также позволяет начинать с более мелких клавиш. Первые 10 клавиш будут состоять из 6 цифр.

Answer 4

Должны ли быть только цифры? Вы можете создать случайное число от 1 до 1М (хотя я бы предложил еще больше), а затем Base32 закодировать его . Следующее, что вам нужно сделать, это хэшировать это значение (используя секретное солт-значение) и base32 кодировать хеш. Затем добавьте две строки вместе, возможно, разделенные чертой.

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

Answer 5

Вы связались с проектом check digits , и использование функции "кодирования" кажется хорошим решением. Там написано:

Кодирование может выдать исключение, если ему передаются «плохие» данные (например, не числовые), а при проверке возвращается только истина или ложь. Идея заключается в том, что кодирование обычно получает данные из «доверенных» внутренних источников (например, ключ базы данных), поэтому на самом деле должно быть довольно обычным, на самом деле, исключительным случаем передачи плохих данных.

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

Answer 6

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

Есть несколько способов, которыми люди делали это в прошлом.

1. Сделать открытый ключ и закрытый ключ. Закодируйте числа 0-999,999, используя закрытый ключ, и раздайте результаты. Вам нужно будет добавить несколько случайных чисел, чтобы результат вышел на более длинную версию, и вам придется преобразовать результат из базы 64 в базу 10. Когда вы получите введенное число, преобразуйте его обратно в base64, примените закрытый ключ и посмотрите, не превышают ли целые числа менее 1 000 000 (отбросьте случайные числа).
2. Использовать обратимую хеш-функцию
3. Используйте первый миллион номеров из PRN, отобранных по определенному значению. Функция проверки может получить начальное значение и знать, что следующий миллион значений хорош. Он может генерировать их каждый раз и проверять одну за другой при получении кода, или при запуске программы сохранять их все в таблице, сортировать, а затем использовать бинарный поиск (максимум сравнений), поскольку миллион целых чисел - это не много пространства.

Существует множество других опций, но они распространены и просты в реализации.

-Adam

Answer 7

Если вы уже знаете, как определить, какая клавиша нажата пользователем, это должно быть достаточно легко выполнимо. В мире безопасности существует понятие «одноразового» пароля. Это иногда называют «одноразовым паролем». Обычно они ограничены (легко вводимыми) значениями ASCII. Итак, [a-zA-z0-9] и куча легко набираемых символов. как запятая, точка, точка с запятой и скобки. Однако в вашем случае вы, вероятно, захотите ограничить диапазон до [0-9] и, возможно, включить * и #.

Я не могу объяснить все технические детали того, как эти одноразовые коды генерируются (или работают) надлежащим образом. За этим стоит какая-то промежуточная математика, которую я убил бы, не просмотрев сначала сам. Достаточно сказать, что вы используете алгоритм для генерации потока одноразовых паролей. Независимо от того, как много предыдущих кодов вы знаете, последующий не может быть угадан! В вашем случае вы просто будете использовать каждый пароль в списке в качестве случайного кода пользователя.

Вместо того, чтобы объяснять детали реализации самостоятельно, я направлю вас к 9-страничной статье, где вы можете прочитать ее самостоятельно:

Answer 8

Когда вы создаете код подтверждения, у вас есть доступ к номеру телефона звонящего?

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

Насчет хеширования, я не уверен, возможно ли взять 10-значное число и получить результат хеширования, который будет <10 цифр (я думаю, вам придется жить с определенным количеством коллизий) но я думаю, что это поможет гарантировать, что пользователь - это тот, о ком говорят. </p>

Конечно, это не будет работать, если номер телефона, использованный на шаге 1, отличается от того, с которого они звонят на шаге 2.

Answer 9

• У меня должно быть разумное количество возможных комбинаций (скажем, 1M)
• Код должен быть максимально коротким, чтобы избежать ошибок со стороны пользователя

Ну, если вы хотите, чтобы в нем было как минимум миллион комбинаций, тогда вам нужно как минимум шесть цифр. Это достаточно коротко?