Основы защиты информации в телекоммуникационных системах


ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ

им. проф. М.А. БОНЧ-БРУЕВИЧА

ФАКУЛЬТЕТ ВЕЧЕРНЕГО И ЗАОЧНОГО ОБУЧЕНИЯ











Реферат

по курсу

Основы защиты информации в телекоммуникационных системах

Тема: Аддитивные потоковые шифры







Факультет ВиЗО

Группа Р-21з

№ зач. кн. ****21








г. Санкт-Петербург

2007 г.


Содержание:

Содержание: 1

Аддитивные потоковые шифры. 3

Применение линейных рекуррентных регистров для потокового шифрования. 5

Список использованной литературы: 8



Аддитивные потоковые шифры.

По способам формирования криптограммы из сообщения различают:

  • Блоковое шифрование;

  • Потоковое шифрование.

Для образования блокового шифра последовательность M, состоящая из символов сообщения, разбивается на блоки M1, M2, …., Mi,.. одинаковой длинны n. Если число символов в последовательности M не кратно n, она дополняется необходимым числом нулей. После разбиения каждый такой блок преобразуется в блок криптограммы по одному и тому же правилу, зависящему от ключа шифрования Кш. Блоки криптограммы E1, E2, …., Ei обычно имеют ту же длину n, что и блоки сообщения.

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

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

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

Ei=MiOГi(K),

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

Mi=EiOГi(K).

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

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

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


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

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

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

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

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

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

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

Потоковые шифры имеют следующие преимущества перед блоковыми:

  • Проще и дешевле аппаратная реализация;

  • Высокая скорость шифрования;

  • Отсутствие размножения ошибок, возникающих в каналах связи.

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

Датчики гаммы разнообразны. Во многих потоковых шифрах в качестве датчиков гаммы применяется рекуррентный метод формирования псевдослучайных последовательностей с помощью так называемого линейного рекуррентного регистра сдвига с обратными связями (ЛРР).

Применение линейных рекуррентных регистров для потокового шифрования.

Индивидуальные свойства линейного рекуррентного регистра сдвига с обратными связями определяет двоичная последовательность множителей h0,h1,...,hn, где h0=hn=1.


Поскольку среди элементов последовательности некоторые имеют нулевые значения, отводы оказываются подключенными не ко всем сумматорам, а только к тем, которые соответствуют hi=1. Текущее состояние ЛЛР определяется конкретным заполнением всех ячеек памяти а0, а1, …. аn-1.

Перед пуском производится заполнение ячеет ЛЛР элементами начальной двоичной последовательности IV.

Под действием каждого поступающего тактового импульса вычисляется по модулю 2 сумма: a0 + h1a1 + h2a2 +…+ hn-1an-1, и происходит сдвиг содержимого всех ячеек в сторону выхода. Шаг сдвиг – одна ячейка. Освободившаяся ячейка с номером n-1 заполняется найденной суммой, а содержимое ячейки a0 с нулевым номером покидает регистр и становится очередным символом bj выходной последовательности. По окончанию следующего такта на выходе появится содержимое предыдущей ячейки а1 в качестве символа bj+1 и тд.

Каждому ЛЛР можно составить полином обратной связи

h(x) = xn + hn-1xn-1 + hn-2xn-2 +….+ h1x +1

с двоичными коэффициентами hi, где h0=hn=1. Верно и обратное: по заданному степенному полиному h(x) всегда можно построить ЛРР. Например, полиному h(n)=x4+x+1 соответствует линейный рекуррентный регистр сдвига из 4х ячеек памяти (n=4).


Линейный рекуррентный регистр сдвига длинной n имеет следующие основные свойства:

  • Период Т выходной последовательности из символов bj при любом начальном заполнении ячеек ограничен неравенством T≤2n-1.

  • Период Т выходной последовательности максимален, т.е. определяется равенством Т=2n-1, при любом начальном заполнении тогда и только тогда, когда полином обратной связи h(x) является примитивным полиномом.

Полином h(x) степени n с двоичными коэффициентами называется примитивным, если он:

  • Является неприводимым, т.е. не представим в виде произведения двух или более многочленов с двоичными коэффициентами (при этом все действия выполняются по модулю 2).

  • Делит полином x2n-1+1 без остатка, но не делит без остатка ни один полином вида xn`+1 при любом n`<2n-1.

При больших значениях степени n число примитивных полиномов весьма велико. В настоящее время имеются подробные таблицы примитивных полиномов, в том числе и больших степеней. Имеются также алгоритмы, которые позволяют проверить, является ли случайно сгенерированный полином, даже высокой степени примитивным. Таким образом, не существует проблемы выбора примитивного полинома обратной связи h(x) для ЛРР достаточно большой длинны n, т.е. такого полинома, который обеспечит достаточно большой период выходной последовательности Т=2n-1 при любом начальном заполнении. Отметим также, что для сокращения числа отводов в конструкции ЛРР среди примитивных полиномов данной степени используют полиномы с наименьшим числом ненулевых коэффициентов.

Выходная последовательность линейного рекуррентного регистра сдвига, реализованного на примитивном полиноме, обладает свойствами «баланса» и «окна». Свойство «баланса» состоит в том, что число нулей на периоде Т=2n-1 точно равно 2n-1-1, а число единиц равно 2n-1. Свойство «окна» гарантирует, что во всех 2n-1 «окнах» из n символов, расположенных друг за другом на периоде, все возможные 2n-1 нулевые двоичные последовательности появятся только по одному разу.

Перечисленные свойства ЛРР, а также некоторые другие, приводят к тому, что последовательность символов на выходе ЛРР может быть принята за чисто случайную. Она практически не отличается от последовательностей, получаемых при бросании симметричной монеты. Однако в действительности выходная последовательность ЛРР является строго детерминированной. Она однозначно задана начальным заполнением aj€{0,1},j=0,1,…,n-1, и полиномом обратной связи h(x), в силу чего ее называют псевдослучайной последовательностью (ПСП).

Использовать ЛРР непосредственно в качестве датчика гаммы Г в потоком шифраторе нельзя.


ЛРР обладает следующим свойством: если известна выходная последовательность ЛРР длинной все лишь 2n, можно вычислить как начальное заполнение, так и полином обратной связи однозначно, причем сложность решения данной задачи имеет порядок O(n3), т.е. требует примерно n3 операций. Данное свойство является непосредственным следствием линейности ЛРР. Оно позволяет свести решение задачи криптоанализа к решению системы линейных уравнений.

Чтобы избежать описанного выше нападения, нужно нарушить линейность датчика гаммы, например, используя два линейных рекуррентных регистра, из которых первый ЛРР служит для второго генератором тактовых импульсов, или применяя нелинейные узлы усложнения.

Список использованной литературы:

  1. Коржик В.И., Кушнир Д.В. Теоретические основы информационной безопасности телекоммуникационных систем: учебное пособие / СПбГУТ. – СПБ, 2000

  2. Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. –М.: Радио и Связь, 1999

Comments