Тезаурус: Математика в криптографии

Цифровая безопасность в современном мире во многом обеспечивается благодаря математическим приложениям криптологии. В проекте «Банк знаний», созданном совместно с Корпоративным университетом Сбербанка, мы выделили главные математические термины и понятия, напрямую связанные с криптографией

Булева функция

Функция, отображающая множество наборов из нулей и единиц длины n во множество {0,1}, где n — натуральное число, называемое числом переменных или числом входов булевой функции.

Отрицание булевой функции

Функция, принимающая на всех наборах противоположное значение. На всех наборах, где функция f принимает значение 0, отрицание функции f принимает значение 1, и, наоборот, на всех наборах, где функция f принимает значение 1, отрицание функции f принимает значение 0.

Уравновешенная булева функция

Булева функция, принимающая значения 0 и 1 на одинаковом количестве наборов. Если у булевой функции n переменных, то она является уравновешенной в том и только том случае, если принимает значения 0 и 1 в точности на 2{n-1} наборах каждое. Уравновешенные булевы функции полезны для генерации псевдослучайных последовательностей в поточных шифрах.

Полином функции

Представление функции в виде суммы мономов. Для булевой функции наиболее часто используется полином Жегалкина (называемый в англоязычной литературе алгебраической нормальной формой), представляющий собой сумму по модулю 2 произведений переменных. Представление булевой функции полиномом Жегалкина единственно.

Степень булевой функции

Длина самого длинного монома в ее полиноме Жегалкина.

Аффинная булева функция

Булева функция, степень которой не превосходит 1, или функция, в полиноме Жегалкина которой нет мономов длины больше 1 (такие мономы называются нелинейными слагаемыми).

Линейная булева функция

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

Нелинейная булева функция

Булева функция, степень которой не меньше двух, то есть содержащая нелинейные слагаемые в полиноме.

Оператор

Так иногда называют совокупность из нескольких булевых функций, — например, m функций от n переменных каждая. При m=n такие операторы часто используются в блочных шифрах.

Корреляционная иммунность

Свойство булевой функции, при которой выход функции статистически не зависит от совокупности любых m ее входов. В этом случае функция называется корреляционно-иммунной порядка m.

Псевдослучайная последовательность

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

Ортогональный массив

Матрица размера N x n, в клетках которой записаны символы алфавита мощности v, — такая, что при ограничении на любые t столбцов любая из возможных v t строк длины t встречается в массиве одинаковое число раз. Параметр t называется силой ортогонального массива. Простой (то есть без повторяющихся строк) двоичный (v=2) ортогональный массив силы t эквивалентен корреляционно-иммунной булевой функции порядка t.

Кодовое расстояние

Минимальное расстояние между наборами кодового множества. Чем больше кодовое расстояние, тем большее количество ошибок можно гарантированно исправить.

Ортогональный код

Код, являющийся ортогональным подпространством к исходному коду, представляющему собой линейное подпространство.

Поточный шифр

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

Блочный (или блоковый) шифр

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

Алгебраическая атака

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

Алгебраическая иммунность

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

Функция голосования

Функция, принимающая то значение, которое принимают большинство ее аргументов.

Конечное поле

Поле с конечным числом элементов, то есть алгебраическая структура с конечным числом элементов, для которых определены двуместные операции, называемые сложением и умножением, удовлетворяющие ряду аксиом, напоминающих свойства сложения и умножения обычных чисел. Конечное поле с q элементами существует тогда и только тогда, когда q — степень простого. Если q простое, то поле с q элементами эквивалентно кольцу вычетов по модулю q, то есть множеству из чисел 0, 1, q-1, на котором сложение и умножение определены как сложение и умножение чисел по модулю q.