[Техпоп] Обфускация инкрементальных идентификаторов с помощью модульного умножения

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

В одном из прошлых постов я написал про инкрементальные и строковые идентификаторы и как я преобразовал одно в другое в нашей игре.

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

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

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

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

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

Это умножение:

По английски умножение — это multiplication, поэтому явления, связанные с умножением, часто называются мультипликативными.

Это вычисление остатка от деления:

По английски это называется modulo, поэтому явления, связанные с этой операцией, называются модульными.

Это определение мультипликативной инверсии:

Например, 5 * 0.2 = 1. 0.2 — это мультипликативная инверсия для 5.

Теперь переходим от школьной математики к не школьной.

Это модульное умножение (modular multiplication):

Оно как обычное умножение, только потом берем остаток от деления на m.

Это определение модульной мультипликативной инверсии (modular multiplicative inverse, MMI):

И тут уже не все так просто.

Во-первых, не для любых x и m можно найти такое число y. Чтобы модульная мультипликативная инверсия гарантировано существовала, x и m должны быть больше нуля и взаимно простыми, т.е. их наибольший общий делитель (НОД) должен быть равен 1. Например, числа 10 и 15 не взаимно простые — оба делятся на 5. А числа 5 и 16 — да.

Во-вторых, таких инверсий может быть несколько (или даже бесконечное число). Так как мы имеем дело с остатком от деления, у нас по сути циклический результат. 5%10=5, 15%10=5, 25%10=5… Например, для чисел 5 и 16 модульная мультипликативная инверсия — это 13, 29, 45 и так далее.

Подробнее об этой инверсии можно почитать тут (на английском).

Нахрена нам вообще сдались эти модульное умножение и модульная мультипликативная инверсия? У модульного умножения есть одно важное и очень полезное свойство: если x и m взаимно простые (а нас только такие случаи и интересуют), то для любого числа y от 1 до m-1 модульное умножение даст нам уникальный результат, который меньше m. Возьмем, например, все те же 5 и 16. Тогда выражение для модульного умножения будет таким:

Если мы будем перебирать y от 1 до m-1, то получим такую последовательность:

Самое важное — это то, что здесь нет повторов. Т.е. мы преобразовали последовательность от 1 до 15 в последовательность из тех же чисел, но в другом порядке и без повторов. Другими словами, мы обфусцировали инкрементальный идентификатор!

Модульная мультипликативная инверсия нужна, чтобы деобфусцировать идентификаторы, т.е. вернуть как было. Для 5 и 16 инверсия равна 13. Получаем такое выражение:

Если на место x подставим числа из обфусцированной последовательности (5, 10, 15, 4, 9…), то получим это:

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

В реальных задачах у нас числа больше, чем 15, поэтому вот вам алгоритм подготовки обфускатора:

Подробнее об этом можно почитать тут и тут (на английском).

Обфусцируем мой ID на DTF (который равен 354):

Проверим, что деобфускация работает:

Мы получили операцию, которая преобразовывает целочисленные инкрементальные идентификаторы в те же самые целочисленные идентификаторы, но не зависящие от порядка.

Если говорить математическим языком, то:

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

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

#техпоп #математика #приходько_техпоп