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

Ответ 1

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

Ответ 2

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

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

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

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

Ответ 3

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

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

Ответ 4

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

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

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

Ответ 5

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

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

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";
}

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

Ответ 6

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

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

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

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

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

Ответ 7

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

Вам нужно создать номера подарочных карт, которые:

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

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

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

Ответ 8

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

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

Ответ 9

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

Вы хотите сгенерировать последовательность чисел, которые вместе образуют перестановку 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 является взаимно просты до p. Поэтому, если вы выберете MAX как простое число, вы используете эту последовательность.

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

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

Ответ 10

На основе Jason Orendoff answer, я собрал алгоритм для создания подарочных кодов. В принципе, у него есть два 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);
    }
}

Ответ 11

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

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

Возражение может быть "Подождите! Это 17 цифр (YYMMDDhhmmss.sssss), но впоследствии выйдет на большую базу, уменьшится. Переход на базу 36 с использованием 10 чисел и 26 букв означает, что 11-значный код будет охватывать любая возможность. Если в верхнем и нижнем регистре не взаимозаменяемы, данные могут быть сжаты до 10 цифр с нулевыми проблемами.

Ответ 12

Вот, хотя:

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

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

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

Ответ 13

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

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

Камикадзский особняк из отбросов

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

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