Laby_MiSZI / Лабораторная работа 3

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

Цель работы: освоить шифрования поточными методами.

Описание методов поточного шифрования

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

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

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

Рис.1. Кодирование в автоключевой системе Виженера

Для того чтобы дешифровать сообщение, приёмник должен знать ключевое слово или символ (в примере, показанном на рис.1, это один символ— "Р"), что по­зволяет расшифровать первый символ сообщения. Это дает ключ для следую­щего символа, и т. д. Шифрованию и расшифровке помогает таблица Виженера (рис.2).

Рис.2. Таблица Виженера для русского языка

Одноразовое заполнение (шифр Вернама)

В 1949 году американский криптограф Клод Шеннон опубликовал работу, в которой доказал абсолютную стойкость шифра Вернама, который также известен, как одноразовый блокнот (one-time pad).

Рис.3. Система одноразового шифрования

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

Шифр Вернама был изобретен в 1917 году Мейджором Джозефом Моборном (Major Joseph Mauborn) и Гильбертом Вернамом (Gilbert Vernam) из AT&T (American Telephone & Telegraph). Суть шифрования одноразовым заполнением заключается в следующем: открытый текст представляется в виде пятизначных "импульсных комбинаций"(код Бодо). В этом коде, например, буква "А" имеет вид (+ + — — —). На бумажной ленте эта буква получала следующий вид:

Знак "+" означал отверстие, а знак "—" - его отсутствие. При считывании с ленты пятерка металлических щупов "опознавала" отверстия (при наличии отверстия щуп замыкал электрическую цепь). В линию связи посылались импульсы тока:

Вернам предложил электромеханически покоординатно складировать импульсы знаков секретного текста с импульсами гаммы (гамма - это секретный ключ, представляющий из себя хаотический набор букв того же самого алфавита). Сложение, по современной терминологии, осуществлялось "по модулю 2"(логика XOR или ИЛИ-НЕ):

(здесь "0" означает знак "—" "кода Бодо", а 1 - "+"). Пусть, например, знак гаммы имеет вид:

,

тогда буква "А" при шифровании переходит в двоичную комбинацию:

,

при расшифровывании ту же операцию необходимо повторить (покоординатно):

Для шифрования булевой строки длины N используется секретный ключ - полностью случайная булева строка длины N. Отправитель и Получатель имеют этот секретный ключ, и больше никто его не знает. Чтобы послать Получателю сообщение (булеву строку длины N), Отправитель побитно складывает текст сообщения с секретным ключом по модулю 2 и пересылает результат Получателю. Получатель, имея точно такой же ключ, сможет восстановить исходное сообщение, побитно сложив полученную от Отправителя строку с ключом. Шенноном было доказано, что такой шифр будет абсолютно стойким при условии полной случайности ключа и однократности его использования.

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

Регистры сдвига с обратной связью

Большинство реальных поточных шифров основано на регистрах сдвига с обратной связью. Регистр сдвига применяют для генерации ключевой последовательности. Регистр сдвига с обратной связью состоит из двух частей: регистра сдвига и функции обратной связи (рис. 4).

Рис.4. Общая схема

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

Простейшим видом регистра сдвига с обратной связью является регистр сдвига с линейной обратной связью, РСЛОС (Linear Feedback Shift Register, LFSR). Обратная связь представляет собой XOR некоторых битов регистра; эти биты называются отводной последовательностью.

РСЛОС (n-битовый) может находиться в одном из внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом битов. (Число внутренних состояний и период равны , потому что заполнение РСЛОС нулями приведет к тому, что сдвиговый регистр будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно.) Только при определенных отводных последовательностях РСЛОС циклически пройдет через все внутренних состояний. Такие РСЛОС имеют максимальный период. Получившийся pезультат называется М-последовательностью. Для того чтобы конкретный РСЛОС имел максимальный период, многочлен, ассоциированный с отводной последовательностью, должен быть примитивным по модулю 2 — то есть не раскладываться на произведение двоичных многочленов меньшей степени.

Сами по себе РСЛОС являются хорошими генераторами псевдослучайных последовательностей, но они обладают некоторыми нежелательными неслучайными свойствами. Для РСЛОС длины внутреннее состояние представляет собой предыдущие выходных битов генератора. Даже если схема обратной связи хранится в секрете, она может быть определена по выходным битам генератора с помощью алгоритма Берлекэмпа-Мэсси.

В качестве примера метода, рассмотрим 4-х битовый LFSR с отводом от первого и четвёртого битов:

Выходной последовательностью будет строка младших значащих битов 111101011101000:

№ такта	Состояние регистров	Выходной бит
0	1111	-
1	0111	1
2	1011	1
3	0101	1
4	1010	1
5	1101	0
6	0110	1
7	0011	0
8	1001	1
9	0100	1
10	0010	1
11	0001	0
12	1000	1
13	1100	0
14	1110	0
15	1111	0

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

A5

А5 — это поточный шифр, используемый для шифрования GSM (Group Special Mobile), — европейского стандарта для цифровых сотовых мобильных телефонов. А5 состоит из трех PCЛОС длиной 19, 22 и 23. Выходом является XOR трех PCЛОС. В А5 используется изменяемое управление тактированием. Каждый регистр тактируется в зависимости от своего среднего бита, затем выполняется XOR с обратной пороговой функцией средних битов всех трех регистров. Обычно на каждом этапе тактируется два РСЛОС. Существует тривиальная атака на открытом тексте, основанная на предположении о содержании первых двух РСЛОС и попытке определения третьего РСЛОС по ключевой последовательности. Тем не менее идеи, лежащие в основе А5, позволяют проектировать надежные поточные шифры. Алгоритм эффективен и удовлетворяет всем известным статистическим тестам, единственная его слабость — короткие регистры. Варианты А5 с более длинными сдвиговыми регистрами и более плотными многочленами обратной связи позволяют противостоять силовой атаке.

Задания к лабораторной работе

1. Разработать алгоритм для шифрования сообщений поточным методом Виженера;

2. Разработать алгоритм для дешифрования сообщений зашифрованных поточным методом Виженера;

3. Составить приложение для шифрования/дешифрования с использованием поточного метода Виженера с кодовым словом.

8