Сидельников В. - Криптография и теория кодирования
Современная криптография является наукой и одновременно искусством защиты информации. Наиболее известные математической общественности результаты современной криптографии относятся к теории чисел и теории сложности.
Менее известно, что теория кодирования так же или даже более необходима для решения широкого круга криптографических задач.
Настоящий доклад призван рассказать о достижениях криптографии, которые получены с помощью теории кодирования, и указать на их значимость.
Теория кодирования в первую очередь связана с традиционной криптографией, а именно с ее главным разделом, в котором изучается так называемое симметрическое шифрование.
Симметрическое шифрование это современное название процедуры шифрования и расшифрования, которые реализуются на обоих концах линии связи с помощью одинаковых или почти одинаковых шифровальных устройств (шифраторов). Между прочим, еще 25 лет назад других шифрований, одно из которых сейчас называется асимметрическим, не было известно, все системы шифрования были симметрическими.
Симметрическое шифрование является наиболее распространенным в современном мире, хотя усилия известных математиков в последние годы по ряду причин почти полностью были направлены на исследования проблем, связанных с асимметрическим шифрованием и открытым распределением ключей.
Особым видом симметрического шифрования является, так называемый, шифр Вернама, который представляет из себя наложение на открытую информацию белой гаммы. Это один из немногих видов шифрования, для которого можно строго доказать (см. [1]) его абсолютную нераскрываемость.
Шифры, подобные шифру, Вернама обычно изучают в рамках теории информации, которая и возникла в трудах К. Шеннона под сильным влиянием его занятий криптографией. Подобные шифры и связанные с ними теоретико-информационные проблемы мы в настоящей работе рассматривать не будем.
В работе под симметрическим шифрованием понимается автоматное шифрование с относительно небольшим ключом.
При симметрическом шифровании нападающая сторона (противник) не может прочитать зашифрованное сообщение из-за того, что он не знает алгоритма шифрования, который в значительной мере определяется секретным ключом.
Асимметрическое шифрование принципиально отличается от симметрического тем, что его алгоритм шифрования, который представляет собой отображение некоторого множества в себя, общеизвестен. Стойкость этого шифрования основывается на том, что противник (нелегитимный пользователь) не в состоянии доступными ему средствами вычислить обратное отображение.
Вместе с тем вычисление обратного отображения для легитимного пользователя вычислительно доступно из-за того, что он знает некоторый секрет, который был использован при построении прямого отображения.
Из материалов конференции Московский университет и развитие криптографии в России (МГУ, 17-18 октября 2002 г.).
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (код проекта 0201-00687).
Асимметрическое шифрование принципиально отличается от симметрического еще также тем, что для него не нужен абсолютно надежный канал для рассылки секретных ключей. Это свойство в некоторых случаях дает асимметрическим системам шифрования значительные практические преимущества перед традиционным симметрическим.
Вместе с тем необходимо отметить, что, во-первых, сложность вычисления значений одностороннего отображения и его обратного, т.е. сложность асимметрического зашифрования и расшифрования, обычно значительно выше, чем сложность этих процедур при традиционных симметрических автоматных методах шифрования, и, во-вторых, в настоящее время неизвестны практически реализуемые системы асимметрического шифрования, для которых достаточно убедительно доказана невозможность их раскалывания квалифицированным незаконным пользователем.
Следует сказать, что всегда (это справедливо и в данном случае) высокую стойкость криптографической системы криптографу удается обосновать лишь в рамках рассматриваемых им же методов анализа этой системы.
Стойкость всех асимметрических систем шифрования, подвергнувшихся серьезному криптографическому анализу, всегда существенно ниже, чем мощность пространства ключей, и имеет явную тенденцию к постоянному снижению.
Настоящая работа включает в себя несколько этюдов по отдельным разделам криптографии, которые так или иначе связаны с теорией кодирования. Автор на полноту охвата предмета не претендует.
Особенно существенным и интересным автору представляется последний раздел работы (часть II), где конкретно и подробно рассматривается один метод определения ключей асимметрической системы шифрования. Как может увидеть читатель, для того чтобы расколоть даже относительно несложную систему необходимо использовать нетривиальные и глубокие математические результаты.
По мнению автора, стойкость криптографической системы существенно зависит от квалификации и способностей того, кто анализирует эту систему.
Теоретико-кодовые асимметрические системы шифрования
В настоящее время известно только 3-4 типа асимметрических систем с предположительно высокой стойкостью шифрования. Одним из них являются системы открытого шифрования МакЭлиса и Нидеррайтера, в основе которых лежат коды, корректирующие ошибки. Их стойкость основана на том, что декодирование кодов общего положения является NP-трудной задачей [20], в то время как сложность декодирования некоторых алгебраических кодов является относительно простой вычислительной задачей. Поэтому основная идея, которая используется при построении этих систем, состоит в маскировке алгебраических кодов под коды общего положения.
Стойкость этих систем в основном зависит от того, насколько хорошо выполнена такая маскировка.
Теоретико-кодовые системы отличаются от других систем тем, что у них, с одной стороны, скорость зашифрования и расшифрования заметно выше, а с другой стороны объем их открытого ключа значительно больше, чем у остальных систем открытого шифрования. Первое является значительным преимуществом, а второе недостатком.
Теория кодирования доставляет несколько примеров стойких систем открытого шифрования. Остановимся на одном из них.
Пусть С линейный код с параметрами (n,k,d) над конечным полем Fg, который имеет простое декодирование, и М его порождающая к х п-матрица. Пусть Л невырожденная к х ^-матрица и Г перестановочная п х п-матрица.
Открытой информацией, подлежащей шифрованию, в теоретико-кодовой асимметрической системе шифрования является к-мерный вектор ш G Fg, а шифрованной информацией п-мерный вектор ш = шН ¦ М ¦ Г + е, где е случайный вектор веса wt(e) ^ [рр]. Секретный ключ образуют матрицы Л и Г, а общедоступным ключом является матрица М' = Н-М-Т. Случайный элемент е генерирует отправитель.
Матрицы Л и Г маскируют порождающую матрицу М с простым алгоритмом декодирования.
Получив ш, легитимный абонент X, который знает секретный ключ, вычисляет следующие элементы: ш' = иіГ '. декодирует га', т.е. представляет его в виде ш' = а + е', а € С. wt(e') ^ [рр], где а = шН ¦ М, и, наконец, с помощью последнего соотношения находит ш = all 1.
Проделать последнюю цепочку вычислений злоумышленнику трудно из-за того, что он не знает Г. Поэтому ему трудно декодировать код С с порождающей матрицей М', который для него является кодом общего положения.
Известно, что сложность N декодирования таких кодов общего положения имеет вид N = 2cmm(i,n-t) [22, 23]. Поэтому даже при относительно небольших кшп к вычислительная сложность декодирования для таких кодов является неприемлемо большой.
Если в качестве С взять Боуза Чоудхури Хок?ингема код [18] или Рида Маллера код [12], то при подходящем k ж п мы получим предположительно стойкую систему асимметрического шифрования. Если же в качестве С взять Рида Соломона код, то получим заведомо слабую систему [И].
О стойкости симметрических систем шифрования
Возвратимся снова к симметрическим системам шифрования. По-видимому, наиболее значительным полем применения теоретико-кодовых конструкций, но в то же время наименее известным математической общественности, является анализ стойкости и синтез шифраторов. Традиционно стойкость шифратора определяется как число операций, необходимых для определения его ключа при некоторых предположениях.
В первом приближении предполагается, что нападающая сторона, называемая также противником или злоумышленником, знает устройство шифратора, но не его ключ. Противник знает и некоторое число знаков, которые выработал шифратор на данном ключе.
Многие проблемы теоретической криптографии, относящиеся к анализу стойкости симметрических систем шифрования, изучаются в рамках давно сложившихся направлений математики: теории вероятностей и статистики, теории чисел, алгебры, теории кодирования, комбинаторики, теории сложности вычислений. В качестве примера укажем на методы построения рекуррентных последовательностей с определенными свойствами, методы выявления статистических закономерностей в массивах дискретной информации, поиск эффективных способов разложения на множители больших целых чисел, свойства булевых функций и преобразований, методы дискретной оптимизации и многие другие.
Особенно большое значение для криптографии имеют результаты, связанные с построением эффективных алгоритмов решения тех или иных конкретных задач. Например, решение системы линейных уравнений, умножение матриц, вычисление значений некоторых булевых функций и преобразований, а также и многие другие, являются массовыми задачами для многих методов определения ключа.
Поэтому знание эффективных оценок сложности их решения (как верхних, так и нижних) позволяют делать относительно обоснованные выводы о стойкости систем шифрования.
Ввиду того, что задача определения ключа может быть представлена как задача решения некоторой системы нелинейных уравнений в конечном поле, для криптографии представляют значительный интерес методы решения систем того или иного вида и оценки их сложности. С примерами криптографических исследований можно познакомиться по многочисленным работам, связанным с изучением свойств преобразования DES, которые опубликованы в последние 20 лет в Procedings of Crypto, Pro-cedings of Eurocrypt, Journal of Cryptology и в [6, 4].
Если говорить обобщенно, как правило при анализе и синтезе необходимо решить многие задачи, которые похожи или совпадают с традиционными задачами теории кодирования. При этом не следует умалять роль и многих других математических дисциплин, задачи которых также возникают при анализе криптосхем. Вместе с тем задачи теории кодирования играет здесь наиболее заметную роль. Это связано с тем, что теория кодирования и криптография, без сомнения, имеют родственные генетические основы: первая борется с атаками природы (ошибками), а вторая с атаками злоумышленников.
Методология защиты от этих атак во многом совпадают. Недаром основоположник научной криптографии К.Шеннон одновременно является и основоположником научных основ как криптографии, так и теории кодирования.
Аппроксимация булевыми функциями
Одним из примеров криптографической задачи, в решении которой значительную роль играют идеи и методы теории кодирования, является задача приближения одной сложной и не до конца известной булевой функции другой простой, которая принадлежит некоторому узкому классу булевых функций.
Более подробно: пусть нам известна двоичная последовательность
(1)
7 = (f(a,i),f(a2),...,f(aN)),aj G F™,
где / неизвестная булева функция, связанная некоторым образом с неизвестным ключом шифратора. Координаты последовательности 7 определяются известными нам входами а,-. Мы хотим приблизить в метрике Хемминга последовательность 7 последовательностью
Th = (h(ai),h(a2),...,h(aN)), (2)
где h, например, является аффинной функцией. Ближайшая функция h, как правило, дает некоторую информацию об устройстве функции /. Эта информация может быть полезна при определении ключа шифратора.
На самом деле в этой задаче заложено две подзадачи. Во-первых, надо выбрать схему шифратора так, чтобы последовательность 7 плохо приближалась последовательностями сг/,. определяемыми функциями h, которые принадлежат узкому классу L. Во-вторых, надо иметь эффективные алгоритмы, которые позволяют находить ближайшую к 7 последовательность т/, и, следовательно, функцию Ь.
Последний алгоритм естественно рассматривать как алгоритм декодирования искаженной последовательности 7 кода К длины N, который образован всевозможными последовательностями 07,. h G L. Подробно подобная задача рассматривалась в работе [13].
В теории кодирования известно не так много кодов, которые имеют эффективные алгоритмы декодирования. Одним из таких кодов является код Рида Маллера первого порядка.
Для него и некоторых его модификаций известно [21] , [25] несколько различных алгоритмов быстрого декодирования. Все они так или иначе используют быстрый алгоритм умножения вектора на матрицу Адамара Уолша.
Последний алгоритм весьма широко используется в современной криптографии.
Криптографические протоколы
Переходим теперь к обсуждению некоторых криптографических протоколов. Упомянем из них только те, в которых по существу используются теоретико-кодовые конструкции.
В симметрических системах шифрования все пользователи должны быть тем или иным способом снабжены ключами. Обычно это осуществляется с помощью дополнительных секретных каналов связи, которые в свою очередь подвержены атакам противника. Безопасное хранение и использование таких секретных ключей является также весьма нетривиальной проблемой.
Задачи безопасной пересылки и сохранения ключей в секрете решаются как с помощью физических методов, так и в последнее время с помощью методов теории кодов, корректирующих ошибки. В частности, рассматривались теоретико-кодовые методы разделения секретов и методы, защищающие секретные ключи от компрометации при их пересылке и хранении.
Некоторые из этих весьма нетривиальных и практически полезных методов защиты ключей были разработаны в России.
Одной из важнейших задач криптографии является разработка методов, защищающих информацию, например, финансовую или командную, от неконтролируемого ее изменения при передаче ее по общедоступным каналам связи, при хранении и при некоторых других видах ее использования. В этому же кругу задач относятся и механизмы доказательства принадлежности.
При этом скрытие информации не всегда является необходимым.
К криптографическим протоколам, решающих подобные задачи, относится цифровая подпись и имитозащита информации. Цифровая подпись является общеизвестным криптографическим протоколом, в котором широко используются теоретико-числовые конструкции.
Вместе с тем известны подходы по созданию цифровой подписи на базе кодов, корректирующих ошибки.
С другой стороны, методы имитозащиты информации полностью базируются на очень изящных конструкциях, которые родственны или совпадают с конструкциями, которые разработаны в теории кодирования. Так, одна из основных таких конструкций называется кодами, обнаруживающими обман.
Пусть необходимо передать элемент а из конечного множества А. В качестве а часто выступает значение хеш-функции. Будем предполагать, что на обоих концах канала связи имеется секретный элемент Ъ (ключ) из множества В. Пусть функция р(х,у) : А х В -^4- (' инъективна при каждом фиксированном у и обладает тем свойством, что для каждого а и с множество S(a,c),S(a,c) С В, решений уравнения ір(а, у) = с имеет достаточно много элементов.
В рассматриваемой системе имитозащиты по общедоступному каналу связи вместо элемента а из А передается элемент с = ір{а,Ъ). Законный пользователь знает ключ Ъ, поэтому он, получив элемент с, решает уравнение с = ір(х, Ь) и определяет элемент а.
Представим, что элемент а известен незаконному пользователю (злоумышленнику), который предполагает заменить его на другой элемент а' (навязать фиксированный элемент а'). Для этого злоумышленник вместо с должен послать с' такое, что уравнение с' = ір(х,Ь) имело решение х = а'; только в этом случае законный пользователь не заметит подмены и произойдет неконтролируемое изменение информации.
Стратегия поведения злоумышленника в этом случае может состоять только в переборе элементов множества ip(a',S(a, с)) с надеждой напасть на подходящий элемент с'. Если это множество имеет достаточно много элементов, то эта стратегия становится неэффективной.
Рассмотренная выше идея может быть реализована, например, с помощью множеств А = Fq, В = {b = (bi,b2)\bi 6 Fq,bi Ф 0}, С = Fq и аффинной функции ір(а,Ь) вида с = а ¦ Ъ\ + Ьг, где Fq конечное поле с q элементами. Отметим, что при каждом Ъ из В функция ір(х, Ь) является перестановкой элементов поля а функции {Г?(.г.
Ь);Ъ € В} дважды транзитивной группой перестановок на Fq. Несколько более сложная конструкция позволяет построить систему имитозащиты, которая практически исключает возможность навязывания не только фиксированного элемента а', но и какого-либо а', отличного от а. Отметим, что в рассмотренном примере одновременно с имитозащитой осуществляется и шифрование сообщения а.
Часть II
Как раскалывается одна асимметрическая система шифрования
Основной целью данного раздела работы является рассказ со всеми подробностями о том, как можно расколоть за полиномиальное время систему открытого шифрования Нидеррайтера или МакЛиса, построенную на основе кодов Рида Соломона. Основные результаты этой статьи впервые изложены в работе Шестакова С. О. и автора [11].
Как полагает автор, статья будет полезной молодым исследователям.
Не надо думать, что все системы открытого шифрования, основанные на кодах, корректирующих ошибки, являются не стойкими. Данная работа является единственным известным примером кодовой системы открытого шифрования, которая раскалывается за полиномиальное время.
Даже эту относительно простую систему расколоть, как будет видно ниже, весьма нетривиально. Для этого используются многие замечательные алгебраические конструкции: группы, матрицы, конечные поля и т.п.
Как представляет себе автор, доказательство нестойкости даже отдельной системы шифрования, которая только деталями отличается от подобных стойких систем, имеет существенное как педагогическое, так и научное значение не всё предлагаемое в открытой криптографии является качественным. Автор попытался сделать изложение замкнутым, но, по-видимому, полностью осуществить это ему не удалось.
7 Коды Рида Соломона
Основные понятия теории кодирования.
В настоящем разделе будут даны только начальные сведения о теории кодирования, необходимые для определения систем открытого шифрования, предложенных Маклисом [10] и Нидеррайтером [14]. Для простоты, мы рассматриваем только частные случаи кодов, которые имеют наибольшее значение для криптографии.
Значительно более полное изложение теории кодирования имеется в книгах [17] и [35].
Мы рассматриваем конечное поле Fg, ц = р1, где р простое число и I положительное целое, содержащее q элементов. Множество FJ = (ж = (жі,... ,xn)\xj G Fg}, мы обычным образом рассматриваем как линейное пространство размерности п.
На пространстве Fg! задана метрика Хемминга, которая определяется следующим образом. Расстояние і(х,у) между двумя векторами ж и у из F равно числу координат, в которых эти векторы различаются.
Например, расстояние между векторами (0,1,2) и (2,1,0) из F| (трехмерное пространство над полем F3 = {0,1,2} из трех элементов) равно 2, так как эти векторы различаются только в первой и последней координате. Метрическое пространстве FJ с метрикой Хемминга будем называть пространством Хемминга. На пространстве Хемминга рассматривают еще одну функцию wt^) вес вектора ж, равный числу его ненулевых координат.
Функции d(ж, у) и wt^) связаны соотношениями d(x,y) = wt(x - у), d(0,ж) = wt^).
Кодом называется произвольное подмножество JC пространства F. Кодовое расстояние іЦк'А кода К, определяется как минимальное расстояние между двумя различными элементами К,, т.е. іІ(к'А = пипц-.у.;.?:ш /yd(x. у). Всюду далее мы в качестве кодов К, будем рассматривать только линейные подпространства L пространства F. Размерность L всегда будем обозначать буквой к. Такие коды называются g-значными линейными кодами.
Их параметры коротко записываются в виде [и. к. d\,r где п длина кода К, к его размерность и d = il(k'A его кодовое расстояние. Число г = п к обычно называют избыточностью кода.
Следует заметить, что кодовое расстояние линейного кода может представлено и несколько иным, во многих случаях более удобным способом. А именно, d(K.) = минимальному весу ненулевого элемента кода к'..
Определенные выше коды используются для коррекции ошибок при передачи информации в канале связи. Схема такого использования состоит в следующем.
Под одиночной ошибкой типа замещения мы понимаем замену одного из символов в векторе ж G F на другой символ. Если в векторе ж произошло t ошибок, то t координат изменило свое значение.
То, что пространство F является метрическим, позволяет утверждать, что і-кратная ошибка превращает кодовый вектор ж в вектор ж', отстоящий от ж на расстояние t, т.е. d(ж, ж') = t. Таким образом, если в канале связи происходит не более, чем t ошибок, то искаженный кодовый вектор ж' находится в шаре (в метрике Хемминга) радиуса t с центром в точке ж € К..
Геометрическая интерпретация кода.
Если все шары радиуса t с центрами в кодовых точках кода К, не пересекаются, то из очевидных геометрических соображений следует, что код может исправить любые t или меньше ошибок, которые поразили кодовый вектор ж в канале связи. Для этого необходимо использовать процедуру декодирования, которая находит тот центр шара ж (кодовый вектор), к которому принадлежит искаженный вектор ж'. Из сказанного выше вытекает, что если код имеет кодовое расстояние d(k'A ^ 2t + 1, то он может корректировать все ошибки кратности t.
Вектору и = (I...../.- )- aj е Fg, который переносит информацию, поставим в соответствие
кодовый вектор х(а) G к'-. Для передачи информационного вектора а по каналу связи с шумами в канал вместо а посылают кодовый вектор ж (а). На выходе канала после декодирования определяется вектор ж (а), а затем и информационный вектор а.
Рассмотренную геометрическую модель коррекции ошибок можно построить из-за того, что F является метрическим пространством, метрика которого в согласована с видом искажений, которые возникают в канале связи. Можно сказать, что с геометрической точки зрения теория кодов, исправляющих ошибки, представляет собой науку, которая занимается упаковками шаров в метрических пространствах, в частности, в пространстве Хемминга, а также задачами декодирования кодов того или иного вида.
Таким образом, такое весьма абстрактное математическое понятие, как метрическое пространство, оказывается весьма полезным для содержательных и наглядных представлений кодов К,, корректирующих ошибки, и в конечном итоге для их построения и использования.
Одной из основных задач теории кодирования является задача построения кода длины п с кодовым расстоянием d с возможно большим числом элементов, т.е. в случае линейного кода с возможно большой размерностью к. За многие годы развития теории кодирования создано большое число разнообразных кодов. Мы остановимся только на относительно узком классе: классических и давно известных кодах Рида Соломона и кодах Боуза Чоудхури Хоквингема (БЧХ-код).
Код Рида Соломона является частным случаем БЧХ-кода.
Проверочная и порождающая матрицы линейного кода и их свойства.
Будем пользоваться без объяснений стандартными понятиями теории конечных полей и линейной алгебры.
Подпространство К, (линейный код над конечным полем Fg) пространства F может быть определено (задано) двумя способами: как своим базисом, так и базисом пространства К .
