Зачем в криптографии используется кодирование?

ПостНаука продолжает рассказывать о современных технологиях в проекте «Банк знаний», подготовленном совместно с Корпоративным университетом Сбербанка.

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

Помехи рассматриваются разные. Например, какие-то символы вставились, какие-то символы выпали или заменились. Классические случаи связаны как раз с заменой символов, потому что при добавлении или выпадении символов используется более специфическая теория. И поэтому самый классический раздел — это коды, исправляющие ошибки типа замены. Как вообще возможно исправить ошибку? Ведь если даже хотя бы один символ испортился, откуда мы знаем, испортился он или нет?

Идея заключается в том, что передавать по каналу связи нужно не все сообщения, а только сообщения из некоторого множества. Это множество обладает таким свойством, что любые два набора из него достаточно сильно различаются. Так что если произошло, как на практике бывает, небольшое число ошибок, то мы от того сообщения, которое мы передавали, не сильно далеко уедем и к другому не подъедем ближе, чем-то, от которого уехали.

Но как эти ошибки можно исправить? Первый способ — иметь список всех передаваемых сообщений. Тогда мы получаем сообщение на выходе, сравниваем с теми сообщениями, которые могли бы в принципе передаваться, ищем, какое ближе. Такой способ очень надежный, но, если объемы передаваемых слов очень большие, искать соответствия в таблицах долго. Но очень важно делать это быстро, поэтому ученые нашли специальные способы, как это делать быстро (например, с помощью линейных кодов).

Любое сообщение — это последовательность в некотором алфавите. В качестве такого алфавита часто используется двоичный код. Все сообщения кодируются словами из множества слов, которые друг от друга достаточно сильно отличаются. Такие множества составляют специальные классы кодов, свойства которых изучает высшая алгебра. Например, код Рида — Соломона, или код БЧХ (Боуза — Чоудхури — Хоквингема — по имени авторов), основан на свойствах конечных полей.

Конечные поля — это множество элементов с операциями сложения и умножения. Точнее, в теории конечных полей действуют аксиомы, похожие на законы сложения и умножения для обычных чисел, например закон дистрибутивности или коммутативности. Но число этих элементов конечно. Если порядок поля — простое число, например семь, то конечное поле с операциями сложения и умножения будет состоять из семи элементов и совпадать с кольцом вычетов целых чисел от 0 до 6 по модулю 7.

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

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

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

Например, один из полиномиальных алгоритмов декодирования кода БЧХ имеет еще большее упрощение, называется алгоритм Берлекэмпа — Месси. Он связан с регистром сдвига с линейной обратной связью. Регистр сдвига с линейной обратной связью — это один из популярных примитивов в криптографии, который порождает псевдослучайные последовательности, используемые для шифрования.

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

Один способ связан с задачей, когда мы перехватили последовательность и надо восстановить по ней весь регистр. Естественно, это задача простая в том смысле, что нужно не узнать регистр, а предугадать, как он будет себя вести дальше. Но поскольку мы не знаем всю длину регистра, нужно надеяться, что мы перехватили достаточно длинный кусок, и тогда нужно восстановить регистр наименьшей длины, который порождает эту последовательность. И эта задача — общая задача декодирования кода БЧХ.

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