Об одном методе маскировки программ


"Перемешивание" программ - часть 2


Поэтому использование булевских тождеств в нашем случае обнаруживается значительно сложнее.

Комбинаторные тождества. Все рассматриваемые далее тождества, как комбинаторные, так и теоретико-числовые взяты, в основном, из [3]. Рассмотрим в качестве примера следующее биномиальное тождество

.

Тождество может использоваться следующим образом: в качестве n берётся несущественная переменная, принимающая целые значения в небольшом интервале (например, от 0 до 5). Генерируются инструкции, вычисляющие сумму биномиальных коэффициентов и помещающие результат во временную переменную, для определённости @1. Генерируется инструкция сдвига, вычисляющая 2n и помещающая результат в другую временную переменную, например @2. Далее в исходной функции выбирается аддитивное целое выражение, результат которого сохраняется в некоторой временной переменной, например, @3, и строится новое выражение @1 + @3 - @2. Это выражение всегда будет равно выражению @3, но содержит зависимость по данным от переменной n.

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

Теоретико-числовые тождества. В качестве примера рассмотрим известную малую теорему Ферма.

ap-1

1 (mod p)

для любого целого

и простого p. При маскировке генерируется случайное простое число p. Далее генерируются инструкции для вычисления ap-1 mod p, причём возведение в степень вычисляется с помощью разложения p-1 в двоичную систему. Эти инструкции образуют достаточно длинную линейную последовательность, которая может быть распределена по базовым блокам маскируемой функции. Результат вычисления выражения добавляется как множитель в какое-либо мультипликативное выражение исходной программы, либо как множитель к переменной.

Другие теоретико-числовые тождества, которые также могут использоваться для внесения зависимостей по данным, приведены ниже. Обобщением малой теоремы Ферма является теорема Эйлера:

где n и x произвольные целые числа,

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




Начало  Назад  Вперед