close

Вход

Забыли?

вход по аккаунту

?

МСЗКИ 1 и 2 лабораторные работы

код для вставкиСкачать
Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования "Ивановский государственный энергетический университет имени В. И. Ленина"
Кафедра программного обеспечения компьютерных систем
Основы криптографии
Методические указания к лабораторным работам № 1,2 по курсу "Методы и средства защиты информации"
Иваново 2004
Составитель Е. Б. ИГНАТЬЕВ
Редактор В. А. ГУСЕВ
Цель настоящих методических указаний - помочь студентам выполнить лабораторные работы по курсу "Методы и средства защиты информации".
Методические указания предназначены для студентов IV курса направления "Информатика и вычислительная техника".
Методические указания утверждены цикловой методической комиссией факультета информатики и вычислительной техники
Рецензент
кафедра программного обеспечения компьютерных систем ГОУ ВПО "Ивановский государственный энергетический университет"
ОСНОВЫ КРИПТОГРАФИИ
МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ЛАБОРАТОРНЫМ РАБОТАМ № 1,2 ПО КУРСУ "МЕТОДЫ И СРЕДСТВА ЗАЩИТЫ ИНФОРМАЦИИ"
Составитель Игнатьев Евгений Борисович
Редактор Н.С. Работаева Лицензия ИД № 05285 от 4 июля 2001 г.
Подписано в печать 4.11.04. Формат 60х84 1/16.
Печать плоская. Усл. печ. л. 1,39.
Тираж 50. Заказ № . ГОУ ВПО "Ивановский государственный энергетический университет"
153003, г. Иваново, ул. Рабфаковская, 34
Отпечатано в РИО ИГЭУ
Введение
Криптография является одним из наиболее мощных средств обеспечения конфиденциальности и контроля целостности информации.
В криптографической терминологии исходный текст именуют открытым текстом (plaintext или clear text). Чтобы скрыть смысл исходного текста применяются два типа преобразований: кодирование и шифрование. Для кодирования (encode) используются кодировочные книги или таблицы, содержащие наборы часто используемых фраз. Каждой из этих фраз соответствует произвольно выбранное кодовое слово, которое чаще всего задается набором цифр. Для декодирования (decoding) требуется такая же книга или таблица.
Шифрование, или зашифрование (encryption), представляет собой процедуру преобразования открытого текста в зашифрованное сообщение, или шифротекст (cipher text). Процесс, при котором из шифротекста извлекается открытый текст, называют расшифрованием (decryption). Обычно в процессе шифрования и расшифрования используется некий ключ и алгоритм обеспечивает, что расшифрование можно сделать, лишь зная этот ключ.
Ключ - конкретное секретное состояние некоторого параметра (параметров), обеспечивающее выбор одного преобразования из совокупности возможных для используемого метода шифрования.
Ключ не зависит от шифруемого сообщения. Изменение ключа должно приводить к изменению зашифрованного сообщения. Незашифрованное сообщение будем обозначать символом P (от слова plaintext). Зашифрованное сообщение будем обозначать символом С (от слова chiphertext). Безопасность, обеспечиваемая традиционной криптографией, зависит от нескольких факторов. Во-первых, криптографический алгоритм должен быть достаточно сильным, чтобы передаваемое зашифрованное сообщение невозможно было расшифровать без ключа, используя только различные статистические закономерности зашифрованного сообщения или какие-либо другие способы его анализа. Во-вторых, безопасность передаваемого сообщения должна зависеть от секретности ключа, но не от секретности алгоритма. Алгоритм должен быть проанализирован специалистами, чтобы исключить наличие слабых мест, при которых плохо скрыта взаимосвязь между незашифрованным и зашифрованным сообщениями. К тому же при выполнении этого условия производители могут создавать дешевые аппаратные чипы и свободно распространяемые программы, реализующие данный алгоритм шифрования. В-третьих, алгоритм должен быть таким, чтобы нельзя было узнать ключ, даже зная достаточно много пар (зашифрованное сообщение, незашифрованное сообщение), полученных при шифровании с использованием данного ключа.
Лабораторная работа №1. Шифрование простой подстановкой и перестановкой. Генераторы псевдослучайных чисел, гаммирование Было доказано, что в криптографии существуют только два основных типа преобразований - замены и перестановки.
Перестановки
В простейших перестановочных шифрах символы открытого текста изменяют свое местоположение. Например, в шифрах колонной замены. Открытый текст построчно вписывается в матрицу с нумерованными столбцами. Столбцы переставляются в соответствии с заданной последовательностью. Затем текст считывается опять построчно.
К перестановочным шифрам принадлежат такие шифры, как "маршрутная транспозиция", "решетка Кардано" и т.п.
Замены
Шифрование методом замены (подстановки) основано на алгебраической операции, называемой подстановкой. Подстановкой называется взаимно однозначное отображение некоторого конечного множества М на себя. В шифрах замены символ открытого текста заменяется одним или несколькими символами зашифрованного текста.
В криптографии рассматриваются четыре типа подстановки (замены): моноалфавитная, гомофоническая, полиалфавитная и полиграммная.
Моноалфавитная подстановка
Такие подстановки называются прямыми подстановками или простой замены.
При моноалфавитной замене каждой букве алфавита открытого текста ставится в соответствие одна буква шифротекста из этого же алфавита.
Преобразование может быть задано с помощью таблицы подстановки или формулой, например:
C = (aP + s) mod N ,
гдеP - код символа исходного текста;
C - код символа зашифрованного текста;
N - количество символов в алфавите;
a - десятичный коэффициент (a и N не должны иметь общих делителей);
s - коэффициент сдвига.
Пpимеp1.
Открытый текст: "ШИФРОВАНИЕ_ЗАМЕНОЙ".
Подстановка задана таблицей:
Алфавит открытого текста: А Б В Г Д ...
Алфавит шифротекста: _ Я Ю Э Ь ...
Шифротекст: "ИШМРТЮ_УШЫАЩ_ФЫУТЧ".
Этот шифр легко поддается частотному анализу встречаемости символов и пар символов.
Гомофоническая подстановка
Гомофоническая замена одному символу открытого текста ставит в соответствие несколько символов шифротекста. Этот метод применяется для искажения статистических свойств шифротекста. Пример 2.
Открытый текст: "ЗАМЕНА". Подстановка задана таблицей: Алфавит открытого текста:А Б ... Е Ж З ... М Н ... 17 23 ... 97 47 76 ... 32 55 ... Алфавит шифротекста: 31 44 ... 51 67 19 ... 28 84 ...
48 63 ... 15 33 59 ... 61 34... Шифротекст: "76 17 32 97 55 31". Таким образом, при гомофонической замене каждая буква открытого текста заменяется по очереди цифрами соответствующего столбца.
Полиалфавитная подстановка
Полиалфавитная подстановка использует несколько алфавитов шифротекста. Пусть используется k алфавитов. Тогда открытый текст: Х=x1x2... xkxk+1... x2kx2k+1...
заменяется шифротекстом: Y=f1(x1)f2(x2)... fk(xk)f1(xk+1)... fk(x2k)f1(x2k+1)...
где fi(xj) означает символ шифротекста i-го алфавита для символа открытого текста xj. Пример 3. Открытый текст: "ЗАМЕНА", k=3. Подстановка задана таблицей из примера 2. Шифротекст: "76 31 61 97 84 48". К полиалфавитным подстановкам относится шифр Вижинера, в котором шифрование выполняется по формуле
Ci = (Pi + Kj) mod N ,
гдеPi - код i-го символа открытого текста в алфавите (0 >= Pi >= N-1, 0 >= i >= M-1);
M - число символов открытого текста;
Ci - код i-го символа зашифрованного текста в алфавите (0 >= Ci >= N-1);
N - количество символов в алфавите;
Kj - код j-го символа ключа (j = i mod L; 0 >= j >= L-1);
L - длина ключа.
Таблица кодов символов алфавита:
_АБВГДЕЖЗИЙ012345678910 КЛМНОПРСТУФ1112131415161718192021
ХЦЧШЩЪЫЬЭЮЯ2223242526272829303132Пример 4. Открытый текст: "ЗАМЕНА".
Ключ: "КЛЮЧ".
L=4; M=6.
ЗАМЕНАКЛЮЧКЛ С0 = 8 + 11 (mod 33)= 19 → Т
С1 = 1 + 12 (mod 33)= 13 → М
С2 = 13+ 31 (mod ЗЗ)= 11→ К
С3 = 6 + 24 (mod 33)= 30 → Э
С4 = 14+11 (mod 33)= 25 → Ш
С5 = 1 +12 (mod 33)= 13 → М
Шифротекст: "ТМКЭШМ".
Шифры Бофора (также полиалфавитные) используют формулы: уi = ki - xi (mod n) и yi = xi - ki (mod n).
Полиграммная подстановка
Полиграммная замена формируется из одного алфавита с помощью специальных правил. В качестве примера рассмотрим шифр Плэйфера. В этом шифре алфавит располагается в матрице. Открытый текст разбивается на пары символов XiXi+1. Каждая пара символов открытого текста заменяется на пару символов из матрицы следующим образом: 1) если символы находятся в одной строке, то каждый из символов пары заменяется на стоящий правее его (за последним символом в строке следует первый); 2) если символы находятся в одном столбце, то каждый символ пары заменяется на символ, расположенный ниже его в столбце (за последним нижним символом следует верхний); 3) если символы пары находятся в разных строках и столбцах, то они считаются противоположными углами прямоугольника. Символы заменяются на символы, находящиеся в тех же столбцах, но соответствующие другим углам прямоугольника; 4) если в открытом тексте встречаются два одинаковых символа подряд, то перед шифрованием между ними вставляется специальный символ (например, тире). Пример 5. Открытый текст: "ШИФР_ПЛЭЙФЕРА".
Матрица алфавита:
АХБМЦВЧГНШДОЕЩ,ХУП.ЗЪРИЙСЬКЭТЛЮЯ_ЫФ- Шифротекст: "РДЫИ,-СТ-И.ХЧС" Обратимые операции
При шифровании часто применяются обратимые (биективные) операции. Самая популярная - операция "Исключающего ИЛИ" - XOR:
a  b = 1, если a  b;
a  b = 0, если a = b.
Например:
10 xor 250 = 240; 240 xor 250 = 10 .
Обратимой операцией является также операция сложения по модулю 2n, где n - число разрядов у операндов, участвующих в сложении. Например:
(10 + 250) mod 256 = 4; (4 - 250) mod 256 = 10 .
Если мы имеем дело с байтовыми переменными, то будут справедливы следующие операторы: c := a + b; a:= c - b.
Гаммирование
Принцип шифрования гаммированием заключается в генерации гаммы шифра с помощью датчика псевдослучайных чисел (ПСЧ) и наложении полученной гаммы на открытые данные с помощью обратимой операции, например - XOR.
Процесс расшифрования данных сводится к повторной генерации гаммы шифра при известном ключе и наложению такой гаммы на зашифрованные данные. Полученный зашифрованный текст является достаточно трудным для раскрытия в том случае, если гамма шифра не содержит повторяющихся битовых последовательностей.
Задания
1. Напишите программу генерации шифра для заданных a и s по формуле: Ci = (a Pi + s) mod N , гдеPi - код i-го символа открытого текста (0 ≤ Pi ≤ N-1);
Ci - код i-го символа зашифрованного текста (0 ≤ Ci ≤ N-1);
N - количество символов алфавита;
a - десятичный коэффициент;
s - коэффициент сдвига.
Напишите программы шифрования и расшифрования для метода моноалфавитной подстановки по заданному шифру. Язык русский. Шифр, открытый текст и зашифрованный текст должны находиться в текстовых файлах. Тестовый файл с открытым текстом должен содержать не менее 1000 символов текста художественного произведения. 2. Напишите программы шифрования и расшифрования для метода многоалфавитной подстановки для заданного ключа. Язык английский. Шифрование выполняется по формуле
Ci = (Pi + Kj) mod N , гдеPi - код i-го символа открытого текста (0 ≤ Pi ≤ N-1);
Ci - код i-го символа зашифрованного текста (0≤Ci≤ N-1);
N - количество символов алфавита;
Kj - код j-го символа ключа (j = i mod L; 0 ≤ j ≤ L-1);
L - длина ключа.
Ключ, открытый текст и зашифрованный текст должны находиться в отдельных текстовых файлах. Программы должны уметь работать с большими текстовыми файлами. Тестовые файлы должны содержать не менее 1000 символов текста. Попробуйте выразить функцию Pi(Ci) одной формулой.
Проведите последовательно несколько раз шифрование текстового файла с разными ключами.
Попытайтесь расшифровать полученный шифр, применяя столько же раз обратное преобразование.
3. Напишите программу подсчета слов русского языка из текстового файла, основы которых (слова без суффикса и окончания) были найдены в словаре основ естественного языка. Словарь необходимо считывать предварительно в память и организовать так, чтобы сравнение шло как можно быстрее. Напишите программу кодирования (раскодирования), которая заменяет одни основы слов на другие. 4. Напишите программу перекодировки символов из одной кодировки в другую для кодировок ASCII, КОИ-8, Windows и т. п. Используя эту программу, напишите программы шифрования и расшифрования для русского текста путем перекодирования. Последовательность перекодировок должна задаваться целым числом, каждая цифра которого обозначает ту или иную кодировку. 5. В России в XIII в. для тайнописи применяли "тарабарскую грамоту". В этой системе согласные буквы заменяются по схеме
БВГДЖЗКЛМНЩШЧЦХФТСРП При шифровании буквы, расположенные на одной вертикали, переходят одна в другую, остальные буквы остаются без изменения. Напишите программы шифрования, расшифрования и дешифрования для текстовых файлов.
6. Напишите программы шифрования и расшифрования с использованием "цифирной азбуки". В госархиве сохранились письма Петра I, в которых он передавал цифири различным деятелям для корреспонденции (П. А. Толстому, А. Д. Меньшикову и др.). Цифирь - это шифр простой замены, в котором буквам сообщения соответствовали шифрообозначения, представляющие собой буквы, слоги, слова или другие какие-нибудь знаки. При этом использовались и "пустышки" - шифрообозначения, которым не соответствовали никакие знаки открытого текста. Буквы русского алфавита приводите к одному регистру. Все, что не шифруется, переписывайте в выходной файл без изменения.
А-меБ-лиВ-коГ-инД-зеЕ-жуЖ-нюЗ-оюИ-пыК-раЛ-суМ-тиН-уО-хиП-отР-цаС-чуТ-шеУ-амФ-икХ-ъЦ-тоЧ-ьШ-юЩ-яЪ-фЫ-асЬ-беЭ-заЮ-гуЯ-ди" "-е 7. Напишите программу, обеспечивающую генерацию случайным или псевдослучайным образом моноалфавитной подстановки для алфавита из n символов. Сформируйте массив [0..255], содержащий коды подстановки символов. Для остальных (255-n) символов, не вошедших в алфавит, в ячейки массива запишите код 0. Напишите программы шифрования и расшифрования, использующие полученный массив. Подстановочная таблица, открытый текст и зашифрованный текст должны находиться в текстовых файлах.
8. Напишите программу, порождающую случайным образом перестановку последовательности чисел от 1 до n. Напишите программы шифрования и расшифрования для метода перестановки групп символов (заданной длины) в заданном порядке. Шифр, открытый текст и зашифрованный текст должны находиться в текстовых файлах. Размеры файлов открытого и зашифрованного текста не должны отличаться.
9. Напишите программу дешифрования зашифрованного методом перестановки символов текста в группе, если известно, что открытый текст содержит текст: "Совершенно секретно". Учесть, что длина файла с зашифрованным текстом должна быть кратна длине группы. Перед перестановкой проверяйте в соседних группах наличие всех требуемых символов. 10. Напишите программу, порождающую случайным или псевдослучайным образом перестановку последовательности чисел от 1 до n. Напишите программы шифрования и расшифрования, использующие получаемую последовательность для перестановки символов в группах. Открытый текст и зашифрованный текст должны находиться в текстовых файлах.
11. Напишите программу, порождающую шифр "решетка Кардано", и программы шифрования и расшифрования текстовых файлов по этому методу. Решетка Кардано - это прямоугольная карточка с отверстиями (рис. 1), чаще всего квадратная. или
Рис. 1. Шифрование с помощью решетки Кардано
Число строк и столбцов в карточке четно. Отверстия в карточке сделаны так, что при последовательном поворачивании каждая клетка лежащего под ней листа с текстом будет видна только один раз. Карточку сначала поворачивают вдоль вертикальной оси симметрии на 180°, а затем - вдоль горизонтальной оси также на 180°. И вновь на 180° вдоль вертикальной оси симметрии. Для квадратных карточек возможны последовательные повороты на 90°.
При шифровании символы исходного текста вписываются в прорези, а при расшифровании считываются из них.
Карточки можно представлять матрицами [ai,j] i=1,...,n; j=1,...,m. Для квадратных матриц размерностью nn доказано, что матрица может служить ключом для шифрования, если i и j элементы: ai,j, aj,(n-i+j), a(n-j+i),i , a(n-i+j),(n-j+i) содержат точно одну прорезь. Реализуйте программу для квадратных и прямоугольных карточек, для поворотов на 90 и 180°.
12. Напишите программы шифрования и расшифрования методом маршрутной транспозиции. Метод состоит в том, что каждый блок символов открытого текста вписывается в заданный прямоугольник [m x n] змейкой. Столбцы нумеруются в порядке следования букв алфавита в ключевой фразе. Последний блок дополняется до полного символами алфавита - А Б В ... Считывается результат по столбцам.
Например. Пусть m=9, n=7, а порядок столбцов задается ключевым словом "СВЯТОСЛАВ". СВЯТОСЛАВ629857413
629857413СЕДЛАЙБРАРОБИОВСЕТЗЫИКОМОНИТОГИТИОМАОВИОСЕДЛАКСЬРУКУИНАНАПЕРЕДИ В результате получится зашифрованный текст: РЕНМЛИД ЕОЫОВСН АТИААНИ БСООДУЕ АООТСУЕ СРЗТОКА ЙВМИЕКР ЛИКИОРП ДБИГИЬА.
Имена текстовых файлов с исходным и зашифрованным сообщением, константы m и n должны задаваться в качестве параметров.
13. Напишите программы шифрования и расшифрования методом перестановки символов открытого текста, нанесенных на грани "кубика Рубика". Последовательность поворотов одна и та же для всех групп символов. 14. Напишите программу генерации псевдослучайных чисел (ПСЧ), применяя линейный конгруэнтный генератор ПСЧ, вырабатывающий последовательность T1, T2, ..., Tm, ..., используя соотношение
Ti+1 = (a Ti + c) mod m ,
где a и c - константы (с - нечетное, а mod 4 = 1);
T0 - исходная величина, выбранная в качестве порождающего числа;
m - константа; обычно устанавливается равной 2b или 2b-1;
b - длина слова ЭВМ в битах (взять b=8). Сгенерируйте m чисел. Определите числа от 0 до m-1, которые ни разу не были сгенерированы. Определите числа, сгенерированные более одного раза.
Постройте график частоты попадания 100 000 сгенерированных чисел в интервалы по 1000 чисел. Такой же график постройте для функции Random() языка Pascal. Исследуйте, как влияют на характер распределения генерируемой последовательности чисел константы a и c. Определите период повторяемости генерируемых чисел.
15. Напишите программы шифрования и расшифрования, использующие генератор ПСЧ (см. задание №14). Программы должны применять операцию "исключающее ИЛИ" для объединения очередного сгенерированного числа и символа из текста. Открытый и зашифрованный тексты должны находиться в текстовых файлах.
16. Напишите программы шифрования и расшифрования методом многоалфавитной подстановки (см. задание №2). Kj получайте с помощью генератора ПСЧ. Начальное (инициализационное) число псевдослучайной последовательности чисел будет являться ключом шифра.
17. Напишите программы шифрования и расшифрования с использованием файла со стихотворением. Каждую букву открытого текста шифруют парой чисел - номером строки, где встречается эта буква, и номером буквы в ней. Поиск следующего символа начнется от только что найденного. Открытый, ключевой и зашифрованный тексты должны находиться в текстовых файлах.
18. Были перехвачены два зашифрованных сообщения:
05262C5269143F314C2A69651A264B5E7EE9
610728413B63072C52222169720B425E7DA745
Здесь они приведены в шестнадцатеричном виде. Известно, что применялось шифрование методом гаммирования. Код каждого символа сообщения с помощью операции XOR накладывался на код, полученный от генератора псевдослучайных чисел. В обоих случаях было передано одно и то же сообщение и использована одна и та же гамма. Но во втором случае в начало исходного сообщения был добавлен один пробел. Требуется дешифровать это сообщение.
19. Напишите программы шифрования и расшифрования текстового файла с использованием ключа, заданного строкой символов. При шифровании, к коду каждого символа строки исходного файла прибавить код очередного символа ключа и вычесть порядковый номер символа в строке. В выходной файл символы зашифрованной строки записывать в обратном порядке. 20. В дисковом массиве уровня RAID5, состоящем из 4-х дисков, вышел из строя Disk 2. Вы должны написать программу восстановления содержимого испорченного диска и прочитать текст, который был записан в дисковом массиве. Ниже приводится содержимое дисков в шестнадцатеричном виде.
Disk 0Disk 1Disk 2Disk 3726573756E64617B7433207272616A206F6620276E716470656E6F656E74202D696B7373 Размер блоков данных для данного массива равен одному байту. Для ускорения записи и чтения в дисковом массиве RAID5 блоки данных (Х1, Х2, Х3) и контрольные суммы (Хр) записываются параллельно на все диски с циклическим сдвигом (см. рис.). Контрольные суммы вычисляются с помощью операции  (xor) следующим образом: Хp=Х1  Х2  Х3.
Лабораторная работа №2. Дешифрование, частотный анализ. Маскировка длины символа
Дешифрование
Процесс нахождения открытого сообщения, соответствующего заданному закрытому, при неизвестном криптографическом преобразовании называется дешифрованием. Исследованием возможности дешифрования информации без знания ключей занимается криптоанализ.
Клод Шеннон ввел понятия диффузии и конфузии для описания стойкости алгоритма шифрования. Диффузия - это рассеяние статистических особенностей и закономерностей незашифрованного текста в широком диапазоне статистических особенностей и закономерностей зашифрованного текста. Это достигается тем, что значение каждого элемента незашифрованного текста влияет на значения многих элементов зашифрованного текста или, что то же самое, любой элемент зашифрованного текста зависит от многих элементов незашифрованного текста. Конфузия - это уничтожение статистической взаимосвязи между зашифрованным текстом и ключом. Если Х - это исходное сообщение и K - криптографический ключ, то зашифрованный передаваемый текст можно записать в виде Y = EK [X].
Получатель, используя тот же ключ, расшифровывает сообщение X = DK [Y].
Противник, не имея доступа к K и Х, должен попытаться узнать Х, K или и то, и другое. Частотный анализ
Шифры простой замены легко поддаются дешифровнию методом частотного анализа встречаемости букв и пар букв. Все естественные языки и большинство искусственных имеют характерное частотное распределение букв и других знаков. Например, в английском языке буква E встречается наиболее часто, а буква Z - наиболее редкая (рис. 2). Если подсчитать в зашифрованном сообщении частоты встречаемости символов и сопоставить их с характерными частотами для данного языка, то сообщение довольно легко может быть прочитано. Чем больше длина шифротекста, тем легче его дешифровать. Так же можно определить вероятности появления пар букв. Окажется, что для многих пар вероятность почти равна нулю. При дешифровании текста если встречается такая пара, то такой вариант отбрасывается. Криптоаналитики часто используют индекс соответствия текстов, вычисляемый по формуле
где fi - общее число встречаемости буквы i в тексте;
N - общее число букв в тексте;
A - первая буква в алфавите;
z - последняя буква в алфавите.
По определению ИС представляет собой оценку суммы квадратов вероятностей каждой буквы. При многоалфавитной подстановке для английского языка, в зависимости от количества используемых при шифровании алфавитов (m), ИС ожидается:
m:1234510
ИС:0,0660,0520,0470,0450,0440,041
При гаммировании криптостойкость определяется размером ключа. Покажем это на примере:
C1 = P1  K
С2 = P2  K
C1  С2 = P1  P2 ,
где K - символ гаммы;
P1 и P2 - символы разных открытых текстов, зашифрованных на одной гамме;
C1 и С2 - зашифрованные символы, соответствующие P1 и P2.
Далее, применяя к полученной сумме метод вероятностных слов или статистического анализа, есть вероятность найти оба открытых сообщения. На одном ключе может быть выработано конечное число символов гаммы, поскольку через определенное количество символов она начнет повторяться, то есть генератор гаммы всегда имеет некоторый период. Поэтому необходимо добиваться как можно большего периода или чаще менять секретный ключ.
Маскировка длины символа
Чтобы усложнить задачу криптоаналитиков, для изменения длины каждого символа применяют сжатие. Для тех же целей иногда зашифрованный текст по определеному закону "разбавляют мусором", а при расшифровании этот "мусор" по этому же закону "выбрасывается".
Выполнение битовых операций
Для выполнения заданий по данной лабораторной работе могут потребоваться операции с битами. Ниже приводятся некоторые простейшие манипуляции с битами на языке Pascal.
Младший (самый правый) разряд считается нулевым. 1. Выделить i-й бит из переменной A:
(A shr i) AND $01.
Распечатать содержимое переменной A как последовательность битов:
for i:=7 downto 0 do
write ((A ShR i) AND $01).
2. Установить i-й бит
а) в 1:A OR ($01 ShL i);
б) в 0:A AND NOT ($01 ShL i).
3. Обнулить A:
A XOR A.
4. Поменять местами i-й и j-й биты целого числа:
type bitik = 0..14;
bin = 0..1;
var i,J : bitik;
bi,bj : bin;
X,a,ap: Integer;
...
bi:=(a ShR i) AND $01; bj:=(a ShR J) AND $01;
if bi<>bj then
if bi=1
then begin ap:=a-(1 ShL i); ap:=ap+(1 ShL j) end
else begin ap:=a-(1 ShL j); ap:=ap+(1 ShL i) end;
5. Циклический сдвиг содержимого n-разрядной переменной A на i битов
а) влево: ROL (A, i)или(A shl i) OR (A shr (n-i));
б) вправо: ROR (A, i) или(A shr i) OR (A shl (n-i)).
Сжатие методом Хаффмана
При сжатии этим методом 8-битовый код каждого символа заменяется на код, у которого разрядность зависит от частоты встречаемости данного символа.
Допустим, алфавит, для которого мы хотим применить сжатие, содержит всего шесть символов. Возьмем файл с текстом из этих символов и подсчитаем, сколько раз каждый символ встретился в этом файле. Отсортируем символы по возрастанию их встречаемости в тексте. R N O A T E
5 6 7 8 9 13
Возьмем два символа с наименьшей частотой: R (5) и N (6). Сформируем из узлов R и N новый узел, частота вхождения для которого будет равна сумме частот R и N (11). После этого снова ищем два узла с самыми низкими частотами вхождения, исключая из просмотра R и N и рассматривая вместо них новый узел с суммарной частотой вхождения. И так продолжаем до тех пор, пока не получим вершину дерева с общим количеством символов. В результате получится дерево для генерации кодов (рис. 3).
Рис. 3. Дерево кодов для сжатия по методу Хаффмана
Спускаясь по дереву из корневого узла до терминального символа, мы пишем 0, если проходим по левой ветви, и пишем 1 - если по правой. Таким образом для символов нашего алфавита получим следующие коды:
E - 11А - 101N - 001Т - 01O - 100R - 000 Для наиболее часто встречающихся символов мы получили более короткие коды. Сжатый файл вместо 48 байт будет занимать 16 байт [(53+63+73+83+92+132) / 8].
Задания
1. Напишите программу дешифрования зашифрованного по методу моноалфавитной подстановки текста (см. задание №1, лаб. работы №1), использующую частотный анализ встречаемости букв и пар букв заданного алфавита. Программа должна выдавать несколько наиболее вероятных результатов дешифрования для дальнейшей оценки.
2. Напишите программу частотного анализа встречаемости символов и пар символов.
Проведите частотный анализ для алфавитов английского языка: * "_", "A", ..., "Z"
* "_", "A", ..., "Z", "a", ..., "z", "0", ..., "9", "(", ")", "[", "]", "{", "}", ".", ",", ":", ";", "?", "!", "-", """, "+", "=", "№", "%", "*", "/"
* все символы с кодами от 0 до 255.
Результаты анализа должны быть записаны в текстовый файл, в каждой строчке которого был записан символ (или пара символов) и через пробел частота в процентах. Строки должны быть отсортированы "по убыванию" частоты встречаемости (отдельно для символов и для 20 наиболее часто встречающихся пар символов.
Вычислите индекс соответствия для нескольких больших файлов текста на русском и английском языках, с учетом регистра букв и без учета. Если в текстовом файле встретится символ, который не входит в исследуемый алфавит, то его не нужно учитывать при подсчитывании N.
3. Проведите частотный анализ встречаемости символов и пар символов (условия см. задание №2) для алфавитов русского языка: * "_", "А", ..., "Я"
* "_", "А", ..., "Я", "а", ..., "я", "0", ..., "9", "(", ")", "[", "]", "{", "}", ".", ",", ":", ";", "?", "!", "-", """, "+", "=", "№", "%", "*", "/"
* все символы с кодами от 0 до 255.
4. Напишите программу, генерирующую подпрограммы для шифрования и расшифрования текстовых файлов, использующих монофонический шифр. Монофонический шифр представляет собой многоалфавитный шифр подстановки, уравнивающий частоту появления зашифрованных знаков. Для знаков, встречающихся часто, назначается относительно большое количество подстановочных знаков. В то же время для нечасто используемых исходных знаков может оказаться достаточным одного или двух знаков подстановки. При шифровании знаки подстановки для одного и того же знака в исходном тексте выбираются по очереди циклически.
На вход программы подается текстовый файл с алфавитом и большой текстовый файл для частотного анализа. На выходе должна получаться таблица подстановочного шифра, используемого в дальнейшем процедурами шифрования и расшифрования.
Проведите частотный анализ встречаемости символов для алфавитов:
* "_", "А", ..., "Я"
* "_", "A", ..., "Z",
соответственно в русских и английских текстах без учета регистра, и сгенерируйте шифры. Проверьте работу процедур шифрования и расшифрования. Проведите частотный анализ для зашифрованных таким методом текстов.
5. Напишите программу вычисления индекса соответствия текстов. Проведите вычисления ИС для нескольких больших текстовых файлов английского языка.
Используя программы шифрования и расшифрования методом многоалфавитной подстановки (см. задание №3), вычислите ИС для зашифрованных текстов при длине ключа от 1 до 15 знаков.
6. Напишите программы шифрования и расшифрования с использованием тюремной азбуки. Азбука устроена следующим образом: в прямоугольную матрицу 6 х 5 вписываются по строкам буквы русского алфавита в обычном порядке следования, кроме букв ё, й, ъ. Код каждой буквы теперь можно определить парой чисел - номером строки и столбца. Для каждого числа используйте по три бита. Для обозначения пробела - 000. Оставшиеся в конце закодированного сообщения биты заполните нулями.
7. Напишите программы сжатия и развертывания текстов по принципу замены наиболее часто встречающихся символов более короткими кодами, предложенному Хаффманом. Пусть тексты состоят только из заглавных букв русского алфавита и пробелов. Для английского алфавита коды Хаффмана могут быть следующие:
A1111G00001M00011S0110Y00000B011100H0101N1100T001Z1101000100C01000I1010O1110U00010D11011J110100000P110101V1101001E100K110100011Q1101000101W011101F01001L01111R1011X110100001 8. Напишите программы шифрования и расшифрования с использованием азбуки Морзе (русского варианта), в которой точки заменены битом 1, а тире - 0.
А-10Б-0111В-100Г-001Д-011Е-1Ж-1110З-0011И-11Й-1000К-010Л-1011М-00Н-01О-000П-1001Р-101С-111Т-0У-110Ф-1101Х-1111Ц-0101Ч-0001Ш-0000Щ-0010Ы-0100ЪЬ-0110Э-11011Ю-1100Я-1010 1-100002-110003-111004-111105-11116-011117-001118-000119-000010-00000[.]-111111[,]-101010[:]-000111[;]-01010[!]-001100["]-101101[()]-010010[-]-011110[/]-01101 Начало-011001Конец-10101 Перед кодом каждого символа необходимо вставлять по три бита, в которых будет храниться длина кода символа в битах. Оставшиеся в конце закодированного сообщения биты заполните нулями. Для разделения отдельных слов используйте код - 10001.
9. Напишите программы шифрования и расшифрования методом перестановки битов в группе из 4 битов открытого (зашифрованного) текста. Все возможные перестановки битов хранятся в массиве. Например: 0-1234, 1-2134, 2-3214, 3-4231, 4-1324, 5-1432, 6-1243 и т. д. Индекс используемой последовательности битов задается числом, которое выдается генератором ПСЧ. Открытый текст и зашифрованный текст должны находиться в текстовых файлах.
10. Напишите программы шифрования и расшифрования методом циклического сдвига. Каждая порция открытого текста состоит из m блоков. Каждый блок, состоящий из n байт, сдвигается влево (при расшифровании вправо) на k0, k1, ..., km-1 битов соответственно. Проверьте работу программ при m=3, n=4 и K=11,5,9.
11. Напишите программы шифрования и расшифрования методом подстановки, используя квадрат Полибия [8x8] для русского алфавита ("_", "А", ... , "Я", "0", ..., "9", "(", ")", "[", "]", "{", "}", ".", ",", ":", ";", "?", "!", "-", """, "+", "=", "№", "%", "*", "/"). В квадрат по строкам последовательно вписываются все символы алфавита. Каждый символ открытого текста кодируется парой чисел - номером строки и номером столбца. Для кодирования номера строки и номера столбца используются по 3 бита. Открытый текст храните в текстовом файле. Строчные буквы русского алфавита заменяйте на прописные.
12. Реализуйте программно генератор последовательности битов (регистр сдвига), изображенный на рис. 4. Рис. 4. Генератор битовой последовательности
Генерация кодирующей последовательности битов производится циклически из небольшого начального объема информации - ключа (10000) по следующему алгоритму. Из текущего набора битов выбираются значения определенных разрядов (0-го и 3-го) и складываются по XOR между собой. Все разряды сдвигаются на 1 бит, а только что полученное значение (0 или 1) помещается в освободившийся самый младший разряд. Значение, находившееся в самом старшем разряде до сдвига, добавляется в кодирующую последовательность, становясь очередным ее битом. Очередной бит кодирующей последовательности складывается по XOR с очередным битом исходного потока. В результате получается очередной бит зашифрованной информации. Определите, на каком шаге генерируемая последовательность начнет повторяться?
Напишите программы поточного шифрования и расшифрования методом гаммирования, используя полученный регистр сдвига для выработки гаммы шифра.
13. Напишите программу дешифрования текста, зашифрованного методом перестановки битов в каждом байте, если известно, что открытый текст должен начинаться с известной подстроки, например: "Совершенно секретно". 14. Напишите программы шифрования и расшифрования с использованием файла с ключевым текстом, который будет использоваться следующим образом: очередной символ исходного текста ищется в ключевом тексте; смещение от текущей позиции файла до позиции с найденным символом и будет кодом зашифрованного символа. Поиск следующего символа начнется от только что найденного. По достижении конца ключевого файла поиск продолжите с начала файла. Есть ли возможность дешифровать с помощью статистических методов зашифрованный таким образом текст? Открытый, ключевой и зашифрованный тексты должны находиться в текстовых файлах.
15. Напишите программы шифрования и расшифрования с использованием метода Дика Френдберга, выпускника университета Беркли. Этот метод комбинирует многоалфавитную подстановку с генератором псевдослучайных чисел для получения шифра подстановки с характеристиками "бесконечного ключа". Алгоритм метода:
1). Установить генератор псевдослучайных чисел с заданным порождающим числом R0. Установить список подстановки из n знаков. 2). Определить, есть ли еще какие-либо символы открытого (зашифрованного) текста, которые необходимо зашифровать (расшифровать)? Если нет, то ОСТАНОВ.
3). Определить место (a) следующего символа открытого (зашифрованного текста) в исходном алфавите (списке подстановки). Подставить вместо него соответствующий знак из списка подстановки (первоначального исходного алфавита). 4). Сгенерировать псевдослучайное число R в интервале от 1 до n.
5). Переставить R-й и a-й знаки в исходном алфавите.
6). Перейти к пункту 2.
Постройте диаграммы частотного распределения зашифрованного текста для сообщения, состоящего из 100, 1000 и 10000 пробелов.
16. Напишите программы шифрования и расшифрования методом двойного ключа, где два периодических ключа длиной в 125 и 123 слова добавляются по модулю 2 к исходному тексту. С каждым i-м словом открытого текста (из первых 123 слов) складываются первое слово первого ключа и i-ое слово второго ключа, то есть получается что-то вроде шифрования с одним ключом длиной, равной произведению длин двух ключей (в нашем случае 125 х 123 = 15375 слов). Открытый текст, каждый из ключей и зашифрованный текст должны находиться в текстовых файлах.
17. Напишите программы шифрования и расшифрования методом "Сигнатура". Алгоритм зашифрования заключается в преобразовании (с помощью байтов ключа) битов входной последовательности в выходную последовательность битов: 0). В текущий байт B помещается синхропосылка S, а в текущий байт ключа K помещается первый байт из файла содержащего ключевую информацию. 1). Текущий байт B складывается с текущим байтом ключа K с помощью операции XOR (рис. 5).
2). Подсчитывается сумма битов (по модулю 2) полученного байта, т.е. все биты байта складываются по правилу 1+1=0, 1+0=1, 0+1=1, 0+0=0 так, чтобы в результате получился один бит.
3). Полученный бит складывается со следующим битом файла открытого текста (входного потока).
4). Левый бит текущего байта B записывается в выходной поток, и весь текущий байт сдвигается влево на один бит. Вместе с ним сдвигается и текущий байт ключа K.
5). На освободившийся правый бит в текущем байте B записывается бит, полученный в пункте 3, а на освободившийся правый бит в текущем байте ключа K записывается очередной бит из файла ключевой информации.
И так продолжается до тех пор, пока не закончится входная последовательность. Открытый текст, ключ и зашифрованный текст должны находиться в текстовых файлах.
Рис. 5. Генератор битовой последовательности
18. Напишите программу помещения (извлечения) содержимого текстового файла в тело (из тела) графического файла. Для этого можно использовать метод последнего значащего бита (Lasst Significant Bit, LSB). Например, полноцветные файлы в формате RGB кодируют каждый пиксел тремя байтами для представления соответственно красной, зеленой и синей составляющих. Изменение каждого из трех младших битов (для записи битов скрываемого сообщения) приведет к изменению цвета данной точки менее чем на 1%, что абсолютно незаметно. Таким образом в файле размером 800 килобайт можно скрыть сообщение размером до 100 килобайт. Методы направленные на скрытие самого присутствия конфиденциальной информации называются стеганографией. 19. Напишите программы перевода произвольного файла в формат Base64 и обратно. Эта система широко используется в электронной почте для представления бинарных файлов в тексте письма (транспортное кодирование). Для того, чтобы преобразовать данные в base64, первый байт помещается в самые старшие восемь бит 24-битного буфера, следующие в средние восемь и третий в младшие значащие восемь бит. Если кодируется менее чем три байта, то соответствующие биты буфера устанавливаются в ноль. Далее каждые шесть бит буфера, начиная с самых старших, используются как индексы строки "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/" и её символы, на которые указывают индексы, помещаются в выходную строку. Если кодируются только один или два байта, используются только первые два или три символа строки и выходная строка дополняется двумя или одним символами "=". Это предотвращает добавление дополнительных битов к восстановленным данным. Процесс повторяется над оставшимися входными данными.
20. Было получено следующее сообщение, закодированное кодом Хемминга (7,4):
0x0E750FF62BD8A8 При передаче в некоторых битах сообщения появились ошибки. Напишите программы кодирования и декодирования по методу Хемминга. Декодируйте приведенный в задании текст с автоматическим исправлением ошибок.
Коды Хемминга относятся к самокорректирующиеся кодам. Если во время передачи данных произошли ошибки, то при приеме эти ошибки автоматически будут исправлены. Построение кодов Хемминга основано на принципе проверки на четность числа единичных символов (битов): к последовательности добавляется элемент такой, чтобы число единичных символов в получившейся последовательности было четным. r1 = i1  i2  ...  ik, знак  здесь означает сложение по модулю 2. То есть к проверочным битам (i) добавляется необходимое количество контрольных битов (r). Для кода Хемминга (7,4): 7 - количество элементов последовательности, 4 - количество проверочных символов.
Для классического кода Хемминга (7,4) контрольные биты: r1 = i1  i2  i3; r2 = i2  i3  i4; r3 = i1  i2  i4.
Кодовые слова кода Хемминга (7,4):
i1i2i3i4r1r2r3i1i2i3i4r1r2r30000000100010100010111001110001011010100110011101101100001001111100010010110011010010110001111010001110101111111 При приеме последовательности вычисляется синдром S = (s1, s2, s3):
s1=r1i1i2i3; s2=r2i2i3i4; s3=r3i1i2i4.
Если синдром отличен от 000, то возможно при передаче последовательности один бит был передан неверно. Синдром000001010011100101110111Ошибка в символенет ошибкиr3r2i4r1i1i3i2 Зная в каком бите произошла ошибка, можно его заменить на противоположный и таким образом автоматически исправлять однократные ошибки. Если в последовательности были переданы неправильно 2 и более бит (что маловероятно), то автоматическое исправление будет работать неверно.
2
Документ
Категория
Рефераты
Просмотров
190
Размер файла
336 Кб
Теги
мсзки, работа, лабораторная
1/--страниц
Пожаловаться на содержимое документа