Задание на лабораторную работу

САНКТ-ПЕТЕРБУРГСКИЙ КОЛЛЕДЖ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

ЛАБОРАТОРНАЯ РАБОТА № 8 ПО ДИСЦИПЛИНЕ

“ Информационная безопасность ”

Тема: «Щифры гаммирования»

Специальность: 230115

Программирование в компьютерных системах

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

2013

ЛАБОРАТОРНАЯ РАБОТА ШИФРЫ ГАММИРОВАНИЯ

6.1. Основы шифрования.

6.2. Генерация гаммы.

Вопросы для самопроверки.

6.1. Основы шифрования

В аддитивных шифрах используется сложение по модулю (mod) исходного сообщения с гаммой, представленных в числовом виде. Напомним, что результатом сложения двух целых чисел по модулю является остаток от деления (например, 5+10 mod 4 = 15 mod 4 = 3).

В литературе шифры этого класса часто называют потоковыми. Стойкость закрытия этими шифрами определяется, главным образом, качеством гаммы, которое зависит от длины периода и случайности распределения по периоду [8].

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

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

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

C_i = (P_i + K_i) mod N, (6.1)

P_i = (C_i + N - K_i) mod N, (6.2)

где P_i, C_i - i-ый символ открытого и шифрованного сообщения;

N - количество символов в алфавите;

К_i - i-ый символ гаммы (ключа). Если длина гаммы меньше, чем длина сообщения, то она используется повторно.

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

Рис.6.1. Таблица кодирования символов

Например, для шифрования используется русский алфавит (N = 33), открытое сообщение – «АБРАМОВ», гамма – «ЖУРИХИН». При замене символов на числа буква А будет представлена как 0, Б – 1, …, Я – 32. Результат шифрования показан в следующей таблице.

Таблица 6.1. Пример аддитивного шифрования по модулю N

Сложение по модулю 2. Значительный успех в криптографии связан с именем американца Гильберто Вернамом [15]. В 1917 г. он, будучи сотрудником телеграфной компании AT&T, совместно с Мейджором Джозефом Моборном предложил идею автоматического шифрования телеграфных сообщений. Речь шла о своеобразном наложении гаммы на знаки алфавита, представленные в соответствии с телетайпным кодом Бодо пятизначными «импульсными комбинациями». Например, буква а представлялась комбинацией («– + – – –»), а комбинация («+ + – + +») представляла символ перехода от букв к цифрам. На бумажной ленте, используемой при работе телетайпа, знаку «+» отвечало наличие отверстия, а знаку «–» - его отсутствие. При считывании с ленты металлические щупы проходили через от-верстия, замыкали электрическую цепь и, тем самым, посылали в линию импульс тока.

Вернам предложил электромеханически покоординатно складывать «импульсы» знаков открытого текста с «импульсами» гаммы, предварительно нанесенными на ленту. Сложение проводилось «по модулю 2». Имеется в виду, что если «+» отождествить с 1, а «–» с 0, то сложение определяется двоичной арифметикой:

	0	1
0	0	1
1	1	0

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

C_i = P_i K_i, (6.3)

P_i = C_i K_i. (6.4)

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

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

Шифры гаммирования стали использоваться немцами в своих дипломатических представительствах в начале 20-х гг., англичанами и американцами – во время Второй мировой войны. Разведчики-нелегалы ряда государств использовали шифрблокноты¹. Шифр Вернама (сложение по модулю 2) применялся на правительственной «горячей линии» между Вашингтоном и Москвой, где ключевые материалы представляли собой перфорированные бумажные ленты, производившиеся в двух экземплярах [23].

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

Таблица 6.2. Коды символов Windows 1251 и их двоичное представление

Примечание. Dec-код – десятичный код символа, Bin-код – двоичный код символа.

Пример шифрования сообщения «ВОВА» с помощью гаммы «ЮЛЯ» показан в следующей таблице.

Таблица 6.3. Пример аддитивного шифрования по модулю 2

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

Таблица 6.4. Пример использования ложной гаммы

В 2013 г. ученые Корнельского университета предложили использовать для генерации ключей (шифроблокнотов) куски полупрозрачного стекла [42]. Кратко принцип нового метода шифрования заключается в том, что отправитель и получатель (Алиса и Боб) во время встречи формируют общий ключ, облучая кусочки стекла изображением-паттерном с ID_i (внешне он напоминает QR-код). В результате отражения и преломления, характер которого индивидуален для каждого куска стекла, у Алисы и Боба получаются собственные случайные изображения, которые затем оцифровываются (получаются ключи keyA_i и keyB_i). Из этих изображений и составляется общий ключ (keyAB_i = keyA_i keyB_i).

Схема генерации одного общего ключа показана на следующем рисунке.

Рис.6.2. Схема генерации одного общего ключа

Как и в классической системе Вернама, каждый случайный паттерн (ключи keyA_i, keyВ_i и keyAВ_i) можно использовать лишь однажды. В связи с этим Алиса и Боб должны сформировать достаточное количество ключей, облучая свои куски стекла разными паттернами. После генерации общие ключи keyAВ_i помещаются в общедоступное хранилище.

Процедура обмена шифрограммами выглядит следующим образом (рис.6.3).

1) Алиса выбирает паттерн с ID_i, облучает свой кусочек стекла и оцифровывает полученное изображение, получая ключ keyA_i.

2) Исходное сообщение P_i Алиса складывает по модулю 2 с ключом keyA_i (C_i = P_i keyA_i) и отсылает шифрограмму C_i с идентификатором паттерна ID_i Бобу.

3) Боб по полученному идентификатору ID_i из общедоступного хранилища считывает общий ключ keyAB_i и, облучая паттерн с ID_i и свой кусочек стекла, генерирует собственный ключ keyB_i.

4) Складывая по модулю 2 ключи keyAB_i и keyB_i, Боб получает ключ keyA_i (keyA_i = keyAB_i keyB_i).

5) Для прочтения исходного сообщения P_i Боб складывает по модулю 2 шифрогамму C_i и ключ keyA_i (P_i = C_i keyA_i).

Рис.6.3. Схема зашифрования и дешифрования сообщения

По утверждению авторов схемы, взломать шифр Вернама можно только украв сами кусочки полупрозрачного стекла. Однако даже в этом случае у Алисы и Боба будет около 24 часов на определение факта кражи, поскольку злоумышленнику потребуется определить структуру стеклянного образца.

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

6.2. Генерация гаммы

В 1949 году Клод Шеннон опубликовал работу, в которой доказал абсолютную стойкость шифра Вернама. При этом гамма (ключ) должна обладать тремя свойствами:

- быть истинно случайной;

- совпадать по размеру или быть больше заданного открытого текста;

- применяться только один раз.

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

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

2)Применение детерминированного алгоритма генерации псевдослучайных чисел с помощью функции Random, хеш-функций или рекуррентных формул. При этом следует помнить, что никакой детерминированный алгоритм не может генерировать полностью случайные числа. Как сказал Джон фон Нейман, «всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений». Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается - начинает повторять одну и ту же последовательность чисел [17].

Примером такого алгоритма является печально известный алгоритм RANDU (один из вариантов линейного конгруэнтного генератора псевдослучайных чисел), десятилетиями использовавшийся на мейнфреймах. Он определяется рекуррентным соотношением:

V_i+1 = (65539 V_i) mod 2³¹, (6.5)

где V₀ нечётное.

Псевдослучайные числа вычисляются следующим образом:

X_i = V_i / 2³¹. (6.6)

Пример псевдослучайной последовательности, порождаемой алгоритмом RANDU при начальном значении V₀ = 1:

65539

393225

1769499

7077969

26542323

...

388843697

238606867

79531577

477211307

В общем случае линейный конгруэнтный генератор псевдослучайных чисел задается выражением

X_i+1 = (a X_i + b) mod m, (6.6)

где a, b и m – некоторые коэффициенты.

К сожалению, линейные конгруэнтные генераторы нельзя использовать в криптографии, так как они предсказуемы. Впервые линейные конгруэнтные генераторы были взломаны Джимом Ридсом (Jim Reeds), а затем Джоан Бояр (Joan Boyar) [8]. Ей удалось также вскрыть квадратичные генераторы

X_i+1 = (a X_i² + b X_i + с) mod m (6.7)

и кубические генераторы

X_i+1 = (a X_i³ + b X_i² + c X_i + d) mod m. (6.8)

Криптографически стойким ГПСЧ является алгоритм Блюм - Блюм - Шуба (англ. Algorithm Blum - Blum - Shub, BBS), предложенный в 1986 году Ленор Блюмом, Мануэлем Блюмом и Майклом Шубом.

Рекуррентная формула BBS выглядит следующим образом:

X_i+1 = X_i² mod m, (6.9)

где m = p * q – является произведением двух больших простых p и q, сравнимых с 3 по модулю 4.

На каждом шаге алгоритма выходные данные получаются из X_i путём взятия либо бита чётности³, либо одного или больше наименее значимых бит X_i.

Пример с использованием двух малых простых чисел.

p = 7 (7 mod 4 = 3) и q = 19 (19 mod 4 = 3).

m = 7 * 19 = 133.

X₀ = 53.

Рис.6.4. Пример генерации гаммы по алгоритму BBS

Особенностью этого алгоритма является то, что для получения X_n необязательно вычислять все n - 1 предыдущих чисел, если известно начальное состояние генератора X₀ и числа p и q, то n-ное значение может быть вычислено «напрямую» по формуле:

. (6.10)

Другие алгоритмы ГПСЧ:

- алгоритм Ярроу;

- алгоритм Fortuna;

- метод Фибоначчи с запаздываниями;

- /dev/random в UNIX/Linux;

- Microsoft CryptoAPI;

- Java SecureRandom;

- вихрь Мерсенна и т.д.

Некоторые из перечисленных ГПСЧ для повышения энтропии⁴ применяют хеш-функции⁵ (SHA-1 и MD5).

По схеме использования аддитивные потоковые шифры делятся на синхронные и самосинхронизирующиеся [8, 23] .

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

Рис.6.5. Схема шифрования с использованием синхронного потокового шифра

При этом генератор гаммы, как правило, состоит из трех основных блоков.

Рис.6.6. Устройство генератора гаммы с внутренней обратной связью

Внутреннее состояние описывает текущее состояние генератора гаммы. Начальное внутреннее состояние, как правило, определяется ключом K. Два генератора, с одинаковым ключом и одинаковым внутренним состоянием, создают одинаковые гаммы. Выходная функция считывает внутреннее состояние и генерирует бит гаммы K_i. Функция переходов считывает текущее внутреннее состояние и генерирует новое внутреннее состояние.

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

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

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

Достоинство СПШ. Отсутствие распространения ошибок. Если во время передачи бит C_i изменит свое значение, что намного вероятнее его потери, то некорректно расшифровывается только один измененный бит.

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

Рис.6.7. Схема шифрования с использованием самосинхронизирующихся генераторов гаммы

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

Недостатки ССПШ.

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

2. При потере бита C_i необходимо заново передать часть сообщения, но в отличие от СПШ, синхронизация генераторов намного проще.

Достоинство ССПШ. Генераторы могут работать не постоянно, а только на момент передачи сообщений.

²Белый шум - стационарный шум, спектральные составляющие которого равномерно распределены по всему диапазону задействованных частот. Примерами белого шума являются шум близкого водопада (отдаленный шум водопада - розовый, так как высокочастотные составляющие звука затухают в воздухе сильнее низкочастотных), или шум Шоттки на клеммах большого сопротивления. Название получил от белого света, содержащего электромагнитные волны частот всего видимого диапазона электромагнитного излучения.

³Бит чётности (англ. parity bit) – контрольный бит, служащий для проверки чётности количества единичных битов в числе. Если количество единиц в числе нечетно, то контрольный бит равен 1, иначе 0.

⁴Информационная энтропия - мера неопределённости или непредсказуемости информации, неопределённость появления какого-либо символа первичного алфавита.

⁵Хеш-функция - легко вычислимая функция, преобразующая исходное сообщения произвольной длины (прообраз) в сообщение фиксированное длины (хеш-образ).

Задание на лабораторную работу

В лабораторной работе необходимо зашифровать свою фамилию с помощью шифров гаммирования по модулю N и модулю 2.

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

Дата добавления: 2019-07-15; просмотров: 1687; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!