Самокорректирующиеся коды и их применения в криптографии

Юрий Валерьевич Таранников

Серия: Классический учебник МГУ

Книга написана на основе специальных курсов лекций «Теория кодирования и ее применения в криптографии» и «Теория кодирования и ее приложения к криптографии (дополнительные главы)», читавшихся автором более десяти лет на механико-математическом факультете МГУ, начиная с 2008 года.
Книга дает необходимые общие сведения из теории самокорректирующихся кодов, уделяя при этом особое внимание приложениям в криптографии и смежных областях. Большая глава посвящена матрицам Адамара, подробно обсуждаются коды Рида—Маллера, строящиеся с помощью булевых функций и имеющие связь с нелинейностью булевых функций, — важным свойством, требующимся от булевых функций при их использовании в качестве узла криптосистем. Дается необходимый аппарат работы с коэффициентами Уолша.

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