Алгоритм кодов подарочных карт

Question

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

Давайте предположим, что я использую некоторый формат кода - скажем, 10 символов от A до Z для простоты, и я начинаю генерировать ваучеры. Какой правильный алгоритм для этого?!

Мой первый подход состоит в том, чтобы пронумеровать все возможные коды от 0 до 308 915 776, а затем начать генерировать случайные числа в этом диапазоне. Это, очевидно, имеет большую проблему - я должен проверить свое случайное число по всем ранее сгенерированным кодам ваучеров, и если оно столкнется с существующим, мне придется отказаться от кода и попробовать другое. Поскольку система накапливает больше данных, она замедляется. В крайнем случае, когда остается только один код, система почти не сможет угадать его правильно.

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

Так что мне остается использовать коды последовательно. Я не хочу предположительных кодов ваучера все же. У пользователя, который покупает ваучер "AAAAAAAAAY", не должно быть шансов получить другой действительный код, если он введет "AAAAAAAAAZ".

Я могу перетасовать свой алфавит и свои позиции так, чтобы вместо

'ABCDEFGHIJKLMNOPQRSTUVWXYZ' я использую

LYFZTGKBNDRAPWEOXQHVJSUMIC '

и так, чтобы вместо позиций

9 8 7 6 5 4 3 2 1 0 позиции

1 8 0 7 5 4 3 9 2 6

Используя эту логику, учитывая код

LNWHDTECMA

следующий код будет

LNEHDTECMA

Это, безусловно, менее вероятно. Но они все еще находятся на расстоянии одного символа друг от друга, и, имея всего два таких ваучера, вы будете знать, какая позиция увеличивается, и у вас будет 90% шанс получить следующий код за 24 или менее догадки.

Мой "аварийный люк" - это бросить все это и использовать GUID. В них больше символов, чем я хотел, чтобы мои пользователи вводили, и они содержат похожие символы, такие как I / 1 и O / 0, но они волшебным образом устраняют все вышеуказанные головные боли. Тем не менее, мне весело думать об этом, может быть, вы тоже. Я хотел бы услышать некоторые альтернативные предложения. Что у тебя есть?

Спасибо!

Answer 1

Я думаю, что лучший способ - это предложить Андреас. Но мой ответ об интересной связанной дискуссии.

Вы хотите сгенерировать последовательность чисел, которые вместе образуют перестановку S = {1, ..., MAX}. Один из способов сделать это - взять элементы циклической группы над S. Например, числа R = {x modulo p, x^2 modulo p, x^3 modulo p, ..., x^(p-1) modulo p} образуют циклическую группу над {1, ..., p-1}, при условии, что p является простым числом, а x взаимно простым с * 1007. *. Поэтому, если вы выбираете MAX в качестве простого числа, вы используете эту последовательность.

Вы хотите "сложную последовательность". Генератор для последовательности, достаточно жесткой для взлома, называется псевдослучайным генератором (конечно, вам не нужно , что трудно взломать). Пример - последняя цифра элементов в R выше, при условии, что p держится в секрете (я прав?). Но в ответе Андреаса уже используется источник (псевдо-) случайных чисел, поэтому его нельзя назвать генератором псевдослучайных чисел.

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

Answer 2

Во-вторых, я использую криптографический хеш - брать биты из MD5 очень просто.Чтобы сделать вещи читабельными, я натолкнулся на следующую идею: взять список слов и использовать биты ключа для индексации списка слов.Мой список слов составляет около 100 000 слов, то есть около 16 бит на слово, что для четырех слов дает 64-битное пространство ключей.Результаты, как правило, вполне читабельны.

Например, криптографическая подпись предыдущего абзаца -

отхаркивающий особняк камикадзе

(Мой список словнаклонен в сторону большего пространства клавиш; если вам нужны более короткие фразы, у вас будет меньше слов.)

Если у вас есть удобная библиотека MD5, эту стратегию очень легко реализовать - я делаю это примерно в 40 строках Lua.

Answer 3

Вот что:

• ID = каждый ваучер имеет уникальный (с автоматическим увеличением?) ID
• CHECKSUM = применить N итераций Verhoeff или алгоритм Luhn для идентификатора
• VOUCHER = base преобразовать сгенерированный CHECKSUM из базы 10 в базу 36

См. также этот связанный вопрос SO: Идеи создания небольшого (<10 цифр), не очень (очень) безопасного хэша </a>.

---

Один простой способ сделать этот метод более безопасным - этоиспользовать неинкрементное значение идентификатора, один из вариантов может заключаться в использовании идентификатора в качестве последних 6 или 7 цифр временной метки UNIX и вычисления контрольной суммы.