Привет, %username%!
Бывает необходимо генерировать ID не подряд, причем чтобы они гарантированно не повторялись. На youtube это используется для того, чтобы вы не могли брутфорсом получить все новые и старые видосики, так же это не редкость на разных файлообменниках и вообще везде где нужно предотвратить или хотя бы затруднить возможность прямого перебора значений.
К примеру, в системе moodle, которая использовалась у нас в универе для тестирования студентов, ID ответов были инкрементными и сквозными на всю базу. Логично предположить, что правильным ответом был тот, что с наименьшим ID в пределах вопроса. В общем, проблем с тестами у нас не было. Потом они перешли на GUID, но я к тому моменту уже выпустился, хехе.
Давайте рассмотрим несколько способов генерации таких ограниченных по длине последовательностей от самых простых до криптографически стойких.
Способ номер 0. Random
Самый тру подход в плане криптостойкости (даже теоретически ничего не предсказать), но неудобен в хозяйстве. Каждую ID мы генерим абсолютно случайно какой-нибудь железкой и проверяем в базе, что такой еще нет и тогда пишем. Но это надо лезть в базу каждый раз, чтобы проверить, со временем генерация будет всё медленней и прочие проблемы. Я поставил этот способ на первое место, потому что тут 0 математики.
Кольцо вычетов
Точнее, мультипликативная группа кольца вычетов. На деле проще, чем звучит. Поясню картинкой
Видите, степени тройки тут идут по порядку
1, 2, 3, 4, 5, 6, а результат остатка от деления — нет
3, 2, 6, 4, 5, 1. Но всё равно в итоге все числа от 1 до 6 присутствуют.
7 называется модулем, а 3 — первообразным корнем (генератором). Чтобы это работало, модуль должен быть вида
где p — простое число больше двух.
Модули для нас — максимальные значения ID, которые мы можем сгенерить с их помощью.
Чем не подход для генерации псевдослучайных айдишек? Берем ID по порядку, возводим генератор в степень этой ID и берем остаток по модулю. Для достаточно больших модулей получится вполне себе.
Это, кстати, почти что Диффи Хэллман, только в масштабах поменьше. Кстати, те кто генерил ручками параметры DH для веб серверов, знают, что процесс это небыстрый. Именно потому, что искать первообразный корень для больших чисел непросто
Линейный конгруэнтный метод
Популярная штука в качестве дефолтных генераторов случайных чисел во многих языках программирования, но абсолютно не криптостойкая. Вот её формула:
А если в качестве m выбрать простое число, то даже c можно выкинуть при определенных условиях, период будет максимальным или близким к нему.
Недостатки очевидны — нужно искать спец числа, да и не факт что они будут кратны размеру байта. Ну и предсказать следующий член последовательности, зная предыдущие, можно, это доказали математики.
Линейные регистры сдвига с обратной связью
Абсолютно замечательные конструкции, которые позволяют генерировать псевдослучайные последовательности путём перексоривания всего нескольких бит. Какие биты ксорить определяет многочлен, лежащий в основе LFSR. Если он примитивный, то последовательность получится максимальной.
Эти примитивные многочлены не так-то просто генерить, примерно как искать простые числа. Но нашлась таки отличная программка primpoly, которая умеет находить примитивные многочлены заданной степени. Даже может выводить списком все возможные примитивные многочлены если передать параметр -a, например, Primpoly.exe -a 2 64
Если нам нужна ID размером в 8 байт, примерно как на Youtube, то вот самый минимальный полином
x ^ 64 + x ^ 4 + x ^ 3 + x + 1
Как им пользоваться:
У нас есть любое 64битное число кроме нуля. Мы ксорим между собой биты 64, 4, 3 и 1. Единица в полиноме означает, что число сдвигается вправо на 1 бит, а результат ксора помещается в старший бит.
Пример реализации на C:
bit = ((lfsr >> 0) ^ (lfsr >> 60) ^ (lfsr >> 61) ^ (lfsr >> 63) ) & 1;
lfsr = (lfsr >> 1) | (bit << 63);
Сдвиг на 0 дает нам бит 64, сдвиг на 1 бит 63 и т. д.
Если этот код выполнять в бесконечном цикле, то мы в итоге придем к тому значению, с которого начинали.
А если прогнать число через несколько регистров с разными полиномами, то предсказать такую последовательность будет довольно сложно даже математически подкованным товарищам. Кстати, на принципе комбинации LFSR построены алгоритмы шифрования GSM трафика A5/1 и A5/2, правда их уже поломали, но тем не менее.
Минус такого подхода в том, что мы можем получать ID только последовательно, не зная заранее, какая будет «через одну». Поэтому переходим к следующему способу
Обратимые функции
Или еще назовем их изоморфные.
Вот тут вообще бесконечное количество вариантов, всё ограничивается вашей фантазией и желанием накрутить сложность процесса, результатом которого является ваша айдишечка.
К примеру, возьмем функции σ0 и σ1 из SHA-256, которые одному 32битному числу сопоставляют другое 32битное (f1 и f2 они называются в описании потокового шифра HC-128)
>>> это циклический сдвиг, >> это просто сдвиг вправо.
Вот цитата от товарищей, которые исследовали эти функции:
The σ0 and σ1 GF(2)- linear mappings are one to one (in order to check this property, we computed the 32x32 GF(2) matrices representing σ0 and σ1, and checked that the kernel of this matrix was restricted to the null vector).
Из неё понятно, что они изоморфны (one to one), можно самим не проверять
Мы даже можем обратную функцию не строить, просто все числа в цикле прогоняем через одну или другую, или обе, или пару раз одну, потом пару раз другую, ну вы поняли. И получаем все ID в диапазоне 32 бит в псевдослучайном порядке, о котором знаем только мы.
Таких функций напридумывать, как вы понимаете, можно базилион и комбинировать как угодно. Но пока что, это тоже не криптостойкий способ. Да и получить обратно, если нужно, оригинальную ID по-простому не получится
Криптостойкая генерация последовательностей ID любого размера
Вы не поверите, но всё уже придумано за нас, я даже статью про это писал
Только тут у нас не номера кредиток, а числа размером сколько нам нужно. От 16 до 192 бит с шагом в 1 бит для одного раунда алгоритма BPS.
Мы берем основание системы такое какое нам нужно, не обязательно кратное 8. В алгоритме лимит на максимальное основание 65536, но ничто не мешает сделать больше, технически там в одну половинку сети фейстеля помещается 96 бит. Или вообще не извращаться, сделать основание 256 и просто шифровать столько байт сколько их в вашей айдишке.
Итак, настраиваем BPS на это основание, ключ для AES, IV(Tweak) и прогоняем все оригинальные ID от 1 до «основание системы — 1» через этот BPS. Потом то, что получилось оборачиваем в какой-нибудь base58 и вот вам готовая красивая айдишечка
Нам даже хранить её не надо, мы можем её расшифровать и сопоставить оригинальной нормальной айдишке, бекенд вообще может не знать о том, что мы с ID извращаемся.
Такие дела
Автор: Virgil Security, Inc.
