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

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

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

Answer 2

Используйте N-битный серийный номер R в сочетании с M-битным хешем H каскадной пары (R, S), где S - это некоторая секретная "соль" S, которую вы публикуете НЕ . Затем закодируйте пару (R, H) буквенно-цифровым способом любым обратимым способом. Если вам нравятся алгоритмы, такие как MD5 * или SHA, но число битов слишком велико, просто возьмите М младших значащих бит стандартного алгоритма хеширования.

Вы можете легко проверить: декодируйте буквенно-цифровую кодировку, чтобы вы могли видеть R и H. Затем вычислите H '= хэш (R + S) и убедитесь, что H = H'.

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

* Прежде чем кто-то скажет "MD5 сломан", позвольте мне напомнить вам, что известными слабостями для MD5 являются атаки столкновений, а не атаки прообразом . Кроме того, используя неопубликованное секретное солт-значение, вы лишаете злоумышленника возможности проверить ваш механизм безопасности, если только он не может угадать солт-значение. Если вы чувствуете себя параноиком, выберите два значения соли Sprefix и Ssuffix и вычислите хэш сцепленной тройки (Sprefix, R, Ssuffix).

Answer 3

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

Добавьте умный способ сопоставления цифр с символами, и вы получите свои коды.

Answer 4

Programming Pearls имеет несколько примеров алгоритмов для генерации наборов случайных чисел, вы должны прочитать его, если вас интересует проблема такого рода.

Книга показывает, что если вы генерируете m случайных чисел со значением меньше n, простой подход к генерации чисел и выбрасыванию дубликатов будет генерировать не более 2m случайных чисел, если m < n / 2. Вот он, в C ++:

void gensets(int m, int n)
{
    set<int> S;
    set<int>::iterator i;
    while (S.size() < m) {
        int t = bigrand() % n;
        S.insert(t);
    }
    for (i = S.begin(); i != S.end(); ++i)
        cout << *i << "\n";
}

Очевидно, что если вы беспокоитесь о том, что люди угадывают значения, вы захотите, чтобы m было намного меньше n / 2.

Существует даже алгоритм, основанный на множестве, для генерации m случайных чисел, меньших n, причем каждое значение одинаково вероятно, без дубликатов и гарантия не генерировать более m случайных чисел:

void genfloyd(int m, int n)
{
    set<int> S;
    set<int>::iterator i;
    for (int j = n-m; j < n; j++) {
        int t = bigrand() % (j+1);
        if (S.find(t) == S.end())
            S.insert(t); // t not in S
        else
            S.insert(j); // t in S
    }
    for (i = S.begin(); i != S.end(); ++i)
        cout << *i << "\n";
}

Порядок чисел не случайный, так что это, вероятно, не лучший выбор для вас.

Answer 5

Я бы сказал, чтобы использовать "идеальный хеш" - http://en.wikipedia.org/wiki/Perfect_hash_function в сочетании с 4-значным случайным числом ...

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

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

Answer 6

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

• Я выбрал префикс соли из 4 цифр
• и суффикс из 4 чисел
• тогда основной код 9 взаимозаменяемых цифр
• затем используя этот формат sprefix +random_numbers+ssuffix
• Я хеширую формат, сохраняющий его в базе данных немедленно
• запрос может помочь удалить похожие коды
• и суффикс и префикс должны быть изменены, как только вы напечатаете 9! (362880) раз.

Answer 7

Это сводка лучших битов всех остальных ответов. :)

Вам необходимо сгенерировать номера подарочной карты:

• уникальный
• неопределяемых

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

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

Answer 8

Я тоже ответил на другой вопрос: P

Лучший способ - генерировать по одному случайному буквенно-цифровому символу, пока у вас их не будет 8. Это будет ваш ваучер.

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

Например, с 8 символами у вас есть 1785793904896 возможных комбинаций, но если вы сгенерируете только 1573,415 ваучеров, у вас будет 50% шанс получить дубликат.

Итак, все зависит от того, сколько вы хотите сгенерировать, и максимальной длины кода, с которым вам удобно. Если вы генерируете много и хотите, чтобы оно было коротким, вам следует сохранить те, которые вы сгенерировали ранее, и проверить на наличие дубликатов в базе данных.

Answer 9

Что может работать эффективно, так это просто использовать время создания в ваших интересах. Скажем, две последние цифры года, месяц из двух цифр, день из двух цифр, час из двух цифр, минуты из двух цифр, секунды из двух цифр, затем перенесите секунды, скажем, в микросекунду. Если необходимо дальнейшее запутывание, сделайте предварительное кодирование (например, MYmdshhdMmYs вместо YYMMddhmmss). Затем измените основание (возможно, на пятиугольник), чтобы дальше отклонять любые попытки угадывания. Это дает два основных преимущества: 1-Использование даты, включая год, уничтожит любое дублирование, поскольку одно и то же время не пройдет дважды. Только через сто лет существует риск. Единственная проблема - потенциально создать два объекта в одну микросекунду, для чего было бы несложно запретить создание более одного за раз. Задержка в миллисекундах решит проблему.

2-угадать будет очень сложно. Мало того, что выяснение, какое основание и порядок чисел (и букв!) Будут трудной задачей, но выход в микросекунду делает последовательность в значительной степени неактуальной. Не говоря уже о том, как трудно клиенту понять, на какую микросекунду он покупал и как совпадают его часы с вашими.

Возражение может быть следующим: «Подождите! каждая возможность. Если прописные и строчные буквы не являются взаимозаменяемыми, данные можно сжать до цели 10 цифр с нулевыми проблемами.

Answer 10

Основываясь на ответе Джейсона Орендоффа , я собрал алгоритм для генерации кодов подарочных карт. По сути, он имеет два 40-разрядных числа: одно из них, чтобы гарантировать его уникальность, а другое, чтобы гарантировать, что его трудно угадать.

• 40-битной части случайного числа достаточно для 1 в 2 ^ 40 шансов угадывание;
• 40-битных последовательных чисел достаточно для 34,8 года уникальности (при условии, что мы генерируем одну подарочную карту за мс.)

Общая 80-битная последовательность затем преобразуется в 16-символьную строку, используя Base32 .

import java.security.SecureRandom;
import java.util.Random;
import java.util.concurrent.atomic.AtomicLong;

import org.apache.commons.codec.binary.Base32;

public class GiftCardUtil {

    private AtomicLong sequence;
    private Random random;

    public GiftCardUtil() {
        // 1325383200000L == 1 Jan 2012
        sequence = new AtomicLong(System.currentTimeMillis() - 1325383200000L);
        random = new SecureRandom();
    }

    public String generateCode() {
        System.out.println(sequence.get());
        byte[] id = new byte[10];
        longTo5ByteArray(sequence.incrementAndGet(), id);
        byte[] rnd = new byte[5];
        random.nextBytes(rnd);
        System.arraycopy(rnd, 0, id, 5, 5);
        return new Base32().encodeAsString(id);
    }

    private void longTo5ByteArray(long l, byte[] b) {
        b[0] = (byte) (l >>> 32);
        b[1] = (byte) (l >>> 24);
        b[2] = (byte) (l >>> 16);
        b[3] = (byte) (l >>> 8);
        b[4] = (byte) (l >>> 0);
    }
}