Датчики М-последовательностей

Лабораторная работа № 12

Шифрование, дешифрование информации с применением криптографических алгоритмов гаммирования

Цель работы

Криптоанализ и программная реализация алгоритмов гаммирования для шифрования и дешифрования исходного текста.

 

Краткие теоретические сведения

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

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

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

Процесс дешифрования данных сводится к повторной генерации гаммы шифра при известном ключе и наложении такой гаммы на зашифрованные данные.

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

Метод гаммирования становится бессильным, если злоумышленнику становится известен фрагмент исходного текста и соответствующая ему шифрограмма. Простым вычитанием по модулю получается отрезок псевдослучайной последовательности (ПСП) и по нему восстанавливается вся последовательность. Однако, если большинство посылаемых сообщений начинается со слов “СОВ.СЕКРЕТНО”, то криптоанализ всего текста значительно облегчается. Это следует учитывать при создании реальных систем информационной безопасности.

Ниже рассматриваются наиболее распространенные методы генерации гамм, которые могут быть использованы на практике.

Датчики псевдослучайных чисел (ПСЧ).

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

Конгруэнтные датчики

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

Одним из хороших конгруэнтных генераторов является линейный конгруэнтный датчик ПСЧ. Он вырабатывает последовательности псевдослучайных чисел T(i), описываемые соотношением

T(i+1) = (A*T(i)+C) mod m,

где А и С - константы, Т(0) - исходная величина, выбранная в качестве порождающего числа. Очевидно, что эти три величины и образуют ключ.

Такой датчик ПСЧ генерирует псевдослучайные числа с определенным периодом повторения, зависящим от выбранных значений А и С. Значение m обычно устанавливается равным 2n, где n - длина машинного слова в битах. Датчик имеет максимальный период М до того, как генерируемая последовательность начнет повторяться. По причине, отмеченной ранее, необходимо выбирать числа А и С такие, чтобы период М был максимальным. Как показано Д. Кнутом, линейный конгруэнтный датчик ПСЧ имеет максимальную длину М тогда и только тогда, когда С - нечетное, и А mod 4 = 1.

Для шифрования данных с помощью датчика ПСЧ может быть выбран ключ любого размера. Например, пусть ключ состоит из набора чисел x(j) размерностью b, где j=1, 2,..., n. Тогда создаваемую гамму шифра G можно представить как объединение непересекающихся множеств H(j).

Датчики М-последовательностей

М -последовательности также популярны, благодаря относительной легкости их реализации.

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

Строго это можно представить в виде следующих отношений:

r₁:=r₀ r₂:=r_1... r_k-1:=r_k-2

r₀:=a₀ r₁ Å a₁ r₂ Å... Å a_k-2 r_k-1

Г_i:= r_k-1-

Здесь r₀ r_1... r_k-1 - k однобитных регистров, a₀ a_1... a_k-1 - коэффициенты неприводимого двоичного полинома степени k-1. Г_i - i-е значение выходной гаммы.

Период М -последовательности исходя из ее свойств равен 2 ^k -1.

Другим важным свойством М -последовательности является объем ансамбля, т.е. количество различных М -последовательностей для заданного k. Эта характеристика приведена в таблице 3.1.

Таблица 3.1

k	Объем ансамбля

Очевидно, что такие объемы ансамблей последовательности неприемлемы.

Поэтому на практике часто используют последовательности Голда, образующиеся суммированием нескольких М -последовательностей. Объемы ансамблей этих последовательностей на несколько порядков превосходят объемы ансамблей порождающих М -последовательностей. Так при k=10 ансамбль увеличивается от 1023 (М -последовательности) до 388000.

Также перспективными представляются нелинейные датчики ПСП (например сдвиговые регистры с элементом “И” в цепи обратной связи), однако их свойства еще недостаточно изучены.

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

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

Шифр Вернама – шифр, в котором открытый текст записан в двоичном виде (последовательность 0;1), ключ - случайная равновероятная двоичная последовательность той же длины, что и открытый ключ, шифрованный текст получается суммированием по модулю 2 (т.е. 0+0=1+1=0, 0+1=1+0=1). Процедура расшифрования совпадает с процедурой шифрования.

Внешняя простота этого шифра немедленно привлекла внимание специалистов, которые предприняли немало попыток его дешифрования, ни одна из которых не увенчалась успехом. Теоретическую невозможность дешифрования этого шифра, при условии однократного использования случайной равновероятной гаммы-двоичной последовательности, используемой для шифрования путем суммирования с открытым текстом, доказал в своих работах К. Шеннон в середине 30-ых годов. С этого момента шифр приобрел еще одно название - «Совершенно стойкий шифр».

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

При наличии на руках шифрованного текста

ШИФР = 10011000100010001001010010010000

используя для расшифрования ключ

00010010000000110000101000000111

мы получим открытый текст

КЛЮЧ = 1000 1010 1000 1011 1001 1110 1001 0111

используя для расшифрования ключ

00010111000011010001100100001100

мы получим открытый текст

ПЕНЬ = 10001111100001011000110110011100

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

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

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

Наиболее близкими по своим качествам к шифру Вернамаявляются шифры гаммирования с псевдослучайной гаммой. Для определения шифра гаммирования в общем виде нам потребуется определение операции модульного сложения и вычитания. Определим ее следующим образом для чисел A и B меньших C и больших или равных нулю.

A + B, если (A+B) меньше C

A + B по модулю C =

A + B -C, если (А+ B) больше или равно С,

 

A - B, если (A-B) больше или равно нулю

A - B по модулю C =

A - B + C, если (А- B) меньше нуля

Например для С=3 эти операции определяются следующим образом

0+0=0 1+0=1 2+0=2

0+1=1 1+1=2 2+1=0

0+2=2 1+2=0 2+2=1

0-0=0 1-0=1 2-0=2

0-1=2 1-1=0 2-1=1

0-2=1 1-2=2 2-2=0

Пусть каждый знак открытого сообщения может принимать С значений (например для русского алфавита без учетов знаков препинания С=33). Занумеруем их от 0 до (С-1).

Шифр гаммирования -шифр, в котором открытый текст, представленный последовательностью чисел, каждое из которых принимает значение от 0 до С-1, преобразуется в шифрованный, представленный аналогичной последовательностью той же длины, путем позначного сложения по модулю C с гаммой - последовательностью чисел, каждое из которых принимает значение от 0 до С-1 длины, равной длине открытого текста и полученной из ключа по какому либо закону.

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

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

1. Максимальную близость гаммы по статистическим свойствам к случайной равновероятной последовательности независимых величин (далее по аналогии с термином «белый шум», известным из физики, такую последовательность будем называть «белой гаммой»).

2. Отсутствие возможности практического восстановления неизвестных отрезков гаммы (в том числе и ключа) по известным.

 

Лабораторное задание

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

4. Содержание отчета:

· название и цель лабораторной работы;

· описание алгоритма и блок-схемы программы;

· результаты выполнения программы: исходный, зашифрованный и дешифрованный текст;

· вывод, отражающий достоинства и недостатки исследуемого метода.

Контрольные вопросы

1. В чем заключается принцип шифрования гаммированием?

2. Поясните, как происходит построение гаммы.

3. В чем слабость шифра гаммирования с неравновероятной гаммой?

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

5. Объясните выражение – «совершенно стойкий шифр».

6. Почему недопустимо использовать дважды одну и ту же гамму для защиты открытых текстов?

7. Назовите преимущества и недостатки шифра Вернама?

8. Какие условия необходимы для обеспечения криптостойкости шифра гаммирования?