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

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

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

• уникальными
• недоступными

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

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

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

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

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

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

Можно использовать \@ backslashchar . Для меня работает следующее:

\documentclass{article}
\begin{document}
\newwrite\file
\immediate\openout\file=myfile.out
\makeatletter
\immediate\write\file{\@backslashchar}
\makeatother
\closeout\file
\end{document}

Обычно я делаю это следующим образом:

1. Подключите кабель USB к компьютеру и установите карту SD на компьютере
2. Получите файл APK где-нибудь на карте SD на телефоне
3. Отключите карту SD на компьютере, позволяет телефону снова увидеть содержимое SD-карты
4. Используйте Astro File Manager или какое-либо подобное приложение, чтобы перейти к этому файлу на SD-карте и выбрать его, , который предложит установить приложение на телефон.

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

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

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

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

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

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

В книге показано, что при генерации m случайных чисел со значением менее n, простой подход генерации чисел и выбрасывания дубликатов будет генерировать не более 2m случайных чисел if 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";
}

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

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

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

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

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

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

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

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

Вы хотите «жестко-трещин» последовательность. Генератор для последовательности достаточно жесткой трещины называется PseudOrandom Generator (конечно, вам, вероятно, не нуждается в , что To-To-Track). Примером является последняя цифра элементов в r выше, предусмотрено P Секрет (я правильно?). Но ответ Andreas уже использует источник (псевдо-) случайные числа, поэтому нельзя назвать Pseudorandom Generator.

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

Вот только:

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

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

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

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

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

Осредоточение особняка Хамиказына

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

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