Центральный Дом Знаний - Сидельников В.М. Криптография и теория кодирования

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Я учусь (закончил(-а) в
Всего ответов: 2653

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

Сидельников В.М. Криптография и теория кодирования

Сидельников В.М. 

Современная криптография является наукой и одновременно искусством защиты информации. Наиболее известные математической общественности результаты современной криптографии относятся к теории чисел и теории сложности. Менее известно, что теория кодирования так же или даже более необходима для решения широкого круга криптографических задач.
Настоящий доклад призван рассказать о достижениях криптографии, которые получены с помощью теории кодирования, и указать на их значимость.
Теория кодирования в первую очередь связана с традиционной криптографией, а именно с ее главным разделом, в котором изучается так называемое симметрическое шифрование.
Симметрическое шифрование — это современное название пропедуры шифрования и расшифрования, которые реализуются на обоих концах линии связи с помощью одинаковых или почти одинаковых шифровальных устройств (шифраторов). Между прочим, еще 25 лет назад других шифрований, одно из которых сейчас называется асимметрическим, не было известно, — все системы шифрования были симметрическими. Симметрическое шифрование является наиболее распространенным в современном мире, хотя усилия известных математиков в последние годы по ряду причин почти полностью были направлены на исследования проблем, связанных с асимметрическим шифрованием и открытым распределением ключей.
Особым видом симметрического шифрования является, так называемый, шифр Вернама, который представляет из себя наложение на открытую информапию «белой» гаммы. Это один из немногих видов шифрования, для которого можно строго доказать (см. [1]) его абсолютную нераскрываемость. Шифры, подобные шифру, Вернама обычно изучают в рамках теории информации, которая и возникла в трудах К. Шеннона под сильным влиянием его занятий криптографией. Подобные шифры и связанные с ними теоретико-информационные проблемы мы в настоящей работе рассматривать не будем. В работе под симметрическим шифрованием понимается автоматное шифрование с относительно небольшим ключом.
При симметрическом шифровании нападающая сторона (противник) не может прочитать зашифрованное сообщение из-за того, что он не знает алгоритма шифрования, который в значительной мере определяется секретным ключом.
Асимметрическое шифрование принципиально отличается от симметрического тем, что его алгоритм шифрования, который представляет собой отображение некоторого множества в себя, общеизвестен. Стойкость этого шифрования основывается на том, что противник (нелегитимный пользователь) не в состоянии доступными ему средствами вычислить обратное отображение. Вместе с тем вычисление обратного отображения для легитимного пользователя вычислительно доступно из-за того, что он знает некоторый секрет, который был использован при построении прямого отображения.
Асимметрическое шифрование принпипиально отличается от симметрического еще также тем, что для него не нужен абсолютно надежный канал для рассылки секретных ключей. Это свойство в некоторых случаях дает асимметрическим системам шифрования значительные практические преимущества перед традиционным симметрическим. Вместе с тем необходимо отметить, что, во-первых, сложность вычисления значений «одностороннего отображения» и его обратного, т.е. сложность асимметрического зашифрования и расшифрования, обычно значительно выше, чем сложность этих процедур при традиционных симметрических автоматных методах шифрования, и, во-вторых, — в настоящее время неизвестны практически реализуемые системы асимметрического шифрования, для которых достаточно убедительно доказана невозможность их раскалывания квалифицированным незаконным пользователем.
Следует сказать, что всегда (это справедливо и в данном случае) высокую стойкость криптографической системы криптографу удается обосновать лишь в рамках рассматриваемых им же методов анализа этой системы.
Стойкость всех асимметрических систем шифрования, подвергнувшихся серьезному криптографическому анализу, всегда существенно ниже, чем мощность пространства ключей, и имеет явную тенденцию к постоянному снижению.
Настоящая работа включает в себя несколько этюдов по отдельным разделам криптографии, которые так или иначе связаны с теорией кодирования. Автор на полноту охвата предмета не претендует.
Особенно существенным и интересным автору представляется последний раздел работы (часть II), где конкретно и подробно рассматривается один метод определения ключей асимметрической системы шифрования. Как может увидеть читатель, для того чтобы «расколоть» даже относительно несложную систему необходимо использовать нетривиальные и глубокие математические результаты. По мнению автора, стойкость криптографической системы существенно зависит от квалификации и способностей того, кто анализирует эту систему.
2   Теоретико-кодовые асимметрические системы шифрования
В настоящее время известно только 3-4 типа асимметрических систем с предположительно высокой стойкостью шифрования. Одним из них являются системы открытого шифрования МакЭлиса и Пидеррайтера, в основе которых лежат коды, корректирующие ошибки. Их стойкость основана на том, что декодирование кодов «общего положения» является NP-трудной задачей [20], в то время как сложность декодирования некоторых алгебраических кодов является относительно простой вычислительной задачей. Поэтому основная идея, которая используется при построении этих систем, состоит в «маскировке» алгебраических кодов под коды обшего положения. Стойкость этих систем в основном зависит от того, насколько хорошо выполнена такая маскировка.
Теоретико-кодовые системы отличаются от других систем тем, что у них, с одной стороны, скорость зашифрования и расшифрования заметно выше, а с другой стороны — объем их открытого ключа значительно больше, чем у остальных систем открытого шифрования. Первое является значительным преимуществом, а второе — недостатком.
Теория кодирования доставляет несколько примеров стойких систем открытого шифрования. Остановимся на одном из них.
Пусть С — линейный код с параметрами {n,k.d) над конечным полем Yq. который имеет простое декодирование, и М — его порождающая к х n-матрипа. Пусть 77 — невырожденная к х fr-матрипа и Г — перестановочная п х п-матрица.
Открытой информацией, подлежащей шифрованию, в теоретико-кодовой асимметрической системе шифрования является fc-мерный вектор to (Е F^, а шифрованной информацией — п-мерный вектор ш = и)П • М • Г + е, где е — случайный вектор веса wt(e) ^ [^у^]- Секретный ключ образуют матрицы 77 и Г, а общедоступным ключом является матрипа М' = 77-М-Г. Случайный элемент е генерирует отправитель. Матрицы II и Г «маскируют» порождающую матрицу М с простым алгоритмом декодирования.
Получив ш, легитимный абонент А', который знает секретный ключ, вычисляет следующие элементы: ш' = шГ-1, декодирует ш', т.е. представляет его в виде ш' = а -Не', о (Е C,wt(e') ^ где о = и;77 • М, и, наконец, с помощью последнего соотношения находит со = all-1.
Проделать последнюю цепочку вычислений злоумышленнику трудно из-за того, что он не знает Г. Поэтому ему трудно декодировать код С с порождающей матрипей М', который для него является кодом «общего положения».
Известно, что сложность N декодирования таких кодов общего положения имеет вид Лг = 2стт{к.п-к) [22, 23]. Поэтому даже при относительно небольших к и п — к вычислительная сложность декодирования для таких кодов является неприемлемо большой.
Если в качестве С взять Боуза — Чоудхури — Хоквингема код [18] или Рида — Маллера код [12], то при подходящем к и п мы получим предположительно стойкую систему асимметрического шифрования. Если же в качестве С взять Рида — Соломона код, то получим заведомо слабую систему [И].
3 О стойкости симметрических систем шифрования
Возвратимся снова к симметрическим системам шифрования. По-видимому, наиболее значительным полем применения теоретико-кодовых конструкпий, но в то же время наименее известным математической общественности, является анализ стойкости и синтез шифраторов. Традиционно стойкость шифратора определяется как число операций, необходимых для определения его ключа при некоторых предположениях. В первом приближении предполагается, что нападаюшая сторона, называемая также противником или злоумышленником, знает устройство шифратора, но не его ключ. Противник знает и некоторое число знаков, которые выработал шифратор на данном ключе.
Многие проблемы теоретической криптографии, относящиеся к анализу стойкости симметрических систем шифрования, изучаются в рамках давно сложившихся направлений математики: теории вероятностей и статистики, теории чисел, алгебры, теории кодирования, комбинаторики, теории сложности вычислений. В качестве примера укажем на методы построения рекуррентных последовательностей с определенными свойствами, методы выявления статистических закономерностей в массивах дискретной информапии, поиск эффективных способов разложения на множители больших пелых чисел, свойства булевых функций и преобразований, методы дискретной оптимизапии и многие другие.
Особенно большое значение для криптографии имеют результаты, связанные с построением эффективных алгоритмов решения тех или иных конкретных задач. Например, решение системы линейных уравнений, умножение матриц, вычисление значений некоторых булевых функций и преобразований, а также и многие другие, являются массовыми задачами для многих методов определения ключа. Поэтому знание эффективных оценок сложности их решения (как верхних, так и нижних) позволяют делать относительно обоснованные выводы о стойкости систем шифрования.
Ввиду того, что задача определения ключа может быть представлена как задача решения некоторой системы нелинейных уравнений в конечном поле, для криптографии представляют значительный интерес методы решения систем того или иного вида и опенки их сложности. С примерами криптографических исследований можно познакомиться по многочисленным работам, связанным с изучением свойств преобразования DES, которые опубликованы в последние 20 лет в Procedings of Crypto, Pro-cedings of Eurocrypt, Journal of Cryptology и в [6, 4].
Если говорить обобщенно, как правило при анализе и синтезе необходимо решить многие задачи, которые похожи или совпадают с традиционными задачами теории кодирования. При этом не следует умалять роль и многих других математических дисциплин, задачи которых также возникают при анализе криптосхем. Вместе с тем задачи теории кодирования играет здесь наиболее заметную роль. Это связано с тем, что теория кодирования и криптография, без сомнения, имеют родственные генетические основы: первая борется с атаками природы (ошибками), а вторая — с атаками злоумышленников. Методология защиты от этих атак во многом совпадают. Недаром основоположник научной криптографии К.Шеннон одновременно является и основоположником научных основ как криптографии, так и теории кодирования.
4 Аппроксимация булевыми функциями
Одним из примеров криптографической задачи, в решении которой значительную роль играют идеи и методы теории кодирования, является задача приближения одной сложной и не до конца известной булевой функции другой простой, которая принадлежит некоторому узкому классу булевых функпий.
Loading

Календарь

«  Июнь 2019  »
ПнВтСрЧтПтСбВс
     12
3456789
10111213141516
17181920212223
24252627282930

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24