МР_к_ЛПЗ_по_ОП.01_09.02.02. Методические указания по проведению лабораторно практических занятий по оп. 01. Основы теории информации для специальности 09. 02. 02 Компьютерные сети
 Скачать 1.36 Mb.
|
Пример задания:Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Если таким способом закодировать последовательность символов БАВГ и записать результат шестнадцатеричным кодом, то получится 1) 4B16 2) 41116 3)BACD16 4) 102316 Решение: из условия коды букв такие: A – 00, Б –01, В – 10 и Г – 11, код равномерный последовательность БАВГ кодируется так: 01 00 10 11 = 1001011 разобьем такую запись на тетрады справа налево и каждую тетраду переведем в шестнадцатеричную систему (то есть, сначала в десятичную, а потом заменим все числа от 10 до 15 на буквы A, B, C, D, E, F); получаем 1001011 = 0100 10112 = 4B16 правильный ответ – 1.
Пример задания:Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
Определить, какой набор букв закодирован двоичной строкой 0110100011000 1) EBCEA 2) BDDEA 3) BDCEA 4) EBAEA Решение (вариант 1, декодирование с начала): здесь используется неравномерное кодирование, при котором декодирование может быть неоднозначным, то есть, заданному коду может соответствовать несколько разных исходных сообщений попробуем декодировать с начала цепочки, первой буквой может быть B или E, эти случаи нужно рассматривать отдельно пусть первая буква – E с кодом 011, тогда остается цепочка 0100011000 для кода 0100011000 первой буквой может быть только B с кодом 01, тогда остается 00011000 ( начало исходной цепочки – EB?) для кода 00011000 первой буквой может быть только A с кодом 000, тогда остается 11000, а эта цепочка не может быть разложена на заданные коды букв поэтому наше предположение о том, что первая буква – E, неверно пусть первая буква – B с кодом 01, тогда остается цепочка 10100011000 для кода 10100011000 первой буквой может быть только D с кодом 10, тогда остается 100011000 (можно полагать, что начало исходной цепочки – BD?) для кода 100011000 первой буквой может быть только С с кодом 100, тогда остается 011000 (начало исходной цепочки – BDC?) Несмотря на то, что среди ответов есть единственная цепочка, которая начинается с BDC, здесь нельзя останавливаться, потому что «хвост» цепочки может «не сойтись» для кода 011000 на первом месте может быть B (код 01) или E (011); в первом случае «хвост» 1000 нельзя разбить на заданные коды букв, а во втором – остается код 000 (буква А), поэтому исходная цепочка может быть декодирована как BDCEA правильный ответ – 3
Решение (вариант 2, декодирование с конца): для кода 0110100011000 последней буквой может быть только А (код 000), тогда остается цепочка 0110100011 для 0110100011 последней может быть только буква E (011), тогда остается цепочка 0110100 для 0110100 последней может быть только буква C (100), тогда остается цепочка 0110 для 0110 последней может быть только буква D (10), тогда остается 01 – это код буквы B таким образом, получилась цепочка BDCEA правильный ответ – 3
Решение (вариант 3, кодирование ответов): в данном случае самое простое и надежное – просто закодировать все ответы, используя приведенную таблицу кодов, а затем сравнить результаты с заданной цепочкой получим 1) EBCEA – 01101100011000 2) BDDEA – 011010011000 3) BDCEA – 0110100011000 4) EBAEA – 01101000011000 сравнивая эти цепочки с заданной, находим, что правильный ответ – 3.
Пример задания:Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? 1) 1 2) 1110 3) 111 4) 11 Решение (вариант 1, метод подбора): рассмотрим все варианты в порядке увеличения длины кода буквы Г начнем с Г=1; при этом получается, что сообщение «10» может быть раскодировано двояко: как ГА или Б, поэтому этот вариант не подходит следующий по длине вариант – Г=11; в этом случае сообщение «110» может быть раскодировано как ГА или В, поэтому этот вариант тоже не подходит третий вариант, Г=111, дает однозначное раскодирование во всех сочетаниях букв, поэтому… … правильный ответ – 3.
Решение (вариант 2, «умный» метод): для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода; это условие называют условием Фано как и в первом решении, рассматриваем варианты, начиная с самого короткого кода для буквы Г; в нашем случае код Г=1 является началом кодов букв Б и В, поэтому условие Фано не выполняется, такой код не подходит код Г=11 также является началом другого кода (кода буквы В), поэтому это тоже ошибочный вариант третий вариант кода, Г=111, не является началом никакого уже известного кода; кроме того, ни один уже имеющийся код не является началом кода 111; таким образом, условие Фано выполняется поэтому правильный ответ – 3.
Пример задания:Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.
Для компактности результат записали в шестнадцатеричной системе счисления. Выберите правильную запись кода. 1) BD9AA5 2) BDA9B5 3) BDA9D5 4) DB9DAB Решение: «вытянем» растровое изображение в цепочку: сначала первая (верхняя) строка, потом – вторая, и т.д.:
в этой полоске 24 ячейки, черные заполним единицами, а белые – нулями:
поскольку каждая цифра в шестнадцатеричной системе раскладывается ровно в 4 двоичных цифры, разобьем полоску на тетрады – группы из четырех ячеек (в данном случае все равно, откуда начинать разбивку, поскольку в полоске целое число тетрад – 6):
переводя тетрады в шестнадцатеричную систему, получаем последовательно цифры B (11), D(13), A(10), 9, D(13) и 5, то есть, цепочку BDA9D5 поэтому правильный ответ – 3.
Пример задания:Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110). Определите, какое число передавалось по каналу в виде 01010100100111100011? 1) 59143 2) 5971 3) 102153 4) 10273 Решение: сначала разберемся, как закодированы числа в примере; очевидно, что используется код равномерной длины; поскольку 2 знака кодируются 10 двоичными разрядами (битами), на каждую цифру отводится 5 бит, то есть 2 → 00101 и 3 → 00110 как следует из условия, четыре первых бита в каждой последовательности – это двоичный код цифры, а пятый бит (бит четности) используется для проверки и рассчитывается как «сумма по модулю два», то есть остаток от деления суммы битов на 2; тогда 2 = 00102, бит четности (0 + 0 + 1 + 0) mod 2 = 1 3 = 00112, бит четности (0 + 0 + 1 + 1) mod 2 = 0 но бит четности нам совсем не нужен, важно другое: пятый бит в каждой пятерке можно отбросить! разобъем заданную последовательность на группы по 5 бит в каждой: 01010, 10010, 01111, 00011. отбросим пятый (последний) бит в каждой группе: 0101, 1001, 0111, 0001. это и есть двоичные коды передаваемых чисел: 01012 = 5, 10012 = 9, 01112 = 7, 00012 = 1. таким образом, были переданы числа 5, 9, 7, 1 или число 5971. Ответ: 2. Отчет Отчет должен содержать: наименование работы; цель работы; задание; последовательность выполнения работы; ответы на контрольные вопросы; вывод о проделанной работе. Контрольные вопросы 1. Где применяется кодирование информации? 2. Дать определение понятие декодер? 3. Какие существуют методы декодирования? Лабораторная работа №10 Тема: Практическое применение криптографии Цель работы: исследование простейших методов криптографической зашиты информации. Время выполнения: 2 часа Оборудование: ПК. Программное обеспечение: операционная система, калькулятор. Часть 1 Теоретические основы Под конфиденциальностьюпонимают невозможность получения информации из преобразованного массива без знания дополнительной информации (ключа). Аутентичность информации состоит в подлинности авторстваи целостности. Криптоанализобъединяет математические методы нарушения конфиденциальности и аутентичности информации без знания ключей. Алфавит - конечное множество используемых для кодирования информации знаков. Текст- упорядоченный набор из элементов алфавита. В качестве примеров алфавитов можно привести следующие: алфавит Z33 - 32 буквы русского алфавита (исключая "ё") и пробел; алфавит Z256 - символы, входящие в стандартные коды ASCII и КОИ-8; двоичный алфавит - Z2 = {0, 1}; восьмеричный или шестнадцатеричный алфавит Под шифромпонимается совокупность обратимых преобразований множества открытых данных на множество зашифрованных данных, заданных алгоритмом криптографического преобразования. В шифре всегда различают два элемента: алгоритм и ключ. Алгоритм позволяет использовать сравнительно короткий ключ для шифрования сколь угодно большого текста. Криптографическая система, или шифр представляет собой семейство Тобратимых преобразований открытого текста в шифрованный. Членам этого семейства можно взаимно однозначно сопоставить число k, называемое ключом. Преобразование Тkопределяется соответствующим алгоритмом и значением ключа k. Ключ - конкретное секретное состояние некоторых параметров алгоритма криптографического преобразования данных, обеспечивающее выбор одного варианта из совокупности всевозможных для данного алгоритма. Секретность ключа должна обеспечивать невозможность восстановления исходного текста по шифрованному. Пространство ключей K- это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита. Следует отличать понятия "ключ" и "пароль". Парольтакже является секретной последовательностью букв алфавита, однако используется не для шифрования (как ключ), а для аутентификации субъектов. Электронной (цифровой) подписью называется присоединяемое к тексту его криптографическое преобразование, которое позволяет при получении текста другим пользователем проверить авторство и целостность сообщения. Зашифрованиемданных называется процесс преобразования открытых данных в зашифрованные с помощью шифра, а расшифрованиемданных - процесс преобразования закрытых данных в открытые с помощью шифра. Дешифрованием называется процесс преобразования закрытых данных в открытые при неизвестном ключе и, возможно, неизвестном алгоритме, т.е. методами криптоанализа. Шифрованием называется процесс зашифрования или расшифрования данных. Также термин шифрование используется как синоним зашифрования. Однако неверно в качестве синонима шифрования использовать термин "кодирование" (а вместо "шифра" - "код"), так как под кодированием обычно понимают представление информации в виде знаков (букв алфавита). Криптостойкостьюназывается характеристика шифра, определяющая его стойкость к дешифрованию. Обычно эта характеристика определяется периодом времени, необходимым для дешифрования. Криптология - это наука о преобразовании информации для обеспечения ее секретности, состоящая из двух ветвей: криптографии и криптоанализа. Криптоанализ - наука (и практика ее применения) о методах и способах вскрытия шифров. Криптография - наука о способах преобразования (шифрования) информации с целью ее защиты от незаконных пользователей. Исторически первой задачей криптографии была защита передаваемых текстовых сообщений от несанкционированного ознакомления с их содержанием, известного только отправителю и получателю, все методы шифрования являются лишь развитием этой философской идеи. С усложнением информационных взаимодействий в человеческом обществе возникли и продолжают возникать новые задачи по их защите, некоторые из них были решены в рамках криптографии, что потребовало развития новых подходов и методов. Шифры простой замены Система шифрования Цезаря - частный случай шифра простой замены. Метод основан на замене каждой буквы сообщения на другую букву того же алфавита, путем смещения от исходной буквы на K букв. Известная фраза Юлия Цезаря VENIVIDIVICI, где
пришел, увидел, победил, зашифрованная с помощью данного метода, преобразуется в SBKF SFAF SFZF при смещении на 4 символа влево. Греческим писателем Полибием за 100 лет до н.э. был изобретен так называемый полибианский квадрат размером 5*5, заполненный алфавитом в случайном порядке. Греческий алфавит имеет 24 буквы, а 25-м символом является пробел. Для шифрования на квадрате находили букву текста и записывали в зашифрованное сообщение букву, расположенную ниже ее в том же столбце. Если буква оказывалась в нижней строке таблицы, то брали верхнюю букву из того же столбца.
Схема шифрования Вижинера. Таблица Вижинера представляет собой квадратную матрицу с n2 элементами, где n — число символов используемого алфавита. На рисунке показана верхняя часть таблицы Вижинера для кириллицы. Каждая строка получена циклическим сдвигом алфавита на символ. Для шифрования выбирается буквенный ключ, в соответствии с которым формируется рабочая матрица шифрования.
Таблица Вижинера Осуществляется это следующим образом. Из полной таблицы выбирается первая строка и те строки, первые буквы которых соответствуют буквам ключа. Первой размещается первая строка, а под нею — строки, соответствующие буквам ключа в порядке следования этих букв в ключе шифрования. Пример такой рабочей матрицы для ключа «книга» . Процесс шифрования осуществляется следующим образом: 1. под каждой буквой шифруемого текста записываются буквы ключа. Ключ при этом повторяется необходимое число раз. 2. каждая буква шифруемого текста заменяется по подматрице буквами находящимися на пересечении линий, соединяющих буквы шифруемого текста в первой строке подматрицы и находящимися под ними букв ключа. 3. полученный текст может разбиваться на группы по несколько знаков. Пусть, например, требуется зашифровать сообщение: максимально допустимой ценой является пятьсот руб. за штуку. В соответствии с первым правилом записываем под буквами шифруемого текста буквы ключа. Получаем: максимально допустимой ценой является пятьсот руб. за штуку книгакнигакнигакнигакнигакнигакнигакнигакнигакнигак
Дальше осуществляется непосредственное шифрование в соответствии со вторым правилом, а именно: берем первую букву шифруемого текста (М) и соответствующую ей букву ключа (К); по букве шифруемого текста (М) входим в рабочую матрицу шифрования и выбираем под ней букву, расположенную в строке, соответствующей букве ключа (К),— в нашем примере такой буквой является Ч; выбранную таким образом букву помещаем в зашифрованный текст. Эта процедура циклически повторяется до зашифрования всего текста. Эксперименты показали, что при использовании такого метода статистические характеристики исходного текста практически не проявляются в зашифрованном сообщении. Нетрудно видеть, что замена по таблице Вижинера эквивалентна простой замене с циклическим изменением алфавита, т.е. здесь мы имеем полиалфавитную подстановку, причем число используемых алфавитов определяется числом букв в слове ключа. Поэтому стойкость такой замены определяется произведением стойкости прямой замены на число используемых алфавитов, т.е. число букв в ключе. Расшифровка текста производится в следующей последовательности: над буквами зашифрованного текста последовательно надписываются буквы ключа, причем ключ повторяется необходимое число раз. в строке подматрицы Вижинера, соответствующей букве ключа отыскивается буква, соответствующая знаку зашифрованного текста. Находящаяся под ней буква первой строки подматрицы и будет буквой исходного текста. полученный текст группируется в слова по смыслу. Нетрудно видеть, что процедуры как прямого, так и обратного преобразования являются строго формальными, что позволяет реализовать их алгоритмически. Более того, обе процедуры легко реализуются по одному и тому же алгоритму. Одним из недостатков шифрования по таблице Вижинера является то, что при небольшой длине ключа надежность шифрования остается невысокой, а формирование длинных ключей сопряжено с трудностями. Нецелесообразно выбирать ключи с повторяющимися буквами, так как при этом стойкость шифра не возрастает. В то же время ключ должен легко запоминаться, чтобы его можно было не записывать. Последовательность же букв не имеющих смысла, запомнить трудно. С целью повышения стойкости шифрования можно использовать усовершенствованные варианты таблицы Вижинера. Приведем только некоторые из них: во всех (кроме первой) строках таблицы буквы располагаются в произвольном порядке. В качестве ключа используется случайность последовательных чисел. Из таблицы Вижинера выбираются десять произвольных строк, которые кодируются натуральными числами от 0 до 10. Эти строки используются в соответствии с чередованием цифр в выбранном ключе. Известны также и многие другие модификации метода. Алгоритм перестановки Этот метод заключается в том, что символы шифруемого текста переставляются по определенным правилам внутри шифруемого блока символов. Рассмотрим некоторые разновидности этого метода, которые могут быть использованы в автоматизированных системах. Самая простая перестановка — написать исходный текст задом наперед и одновременно разбить шифрограмму на пятерки букв. Например, из фразы ПУСТЬ БУДЕТ ТАК, КАК МЫ ХОТЕЛИ. получится такой шифротекст: ИЛЕТО ХЫМКА ККАТТ ЕДУБЪ ТСУП В последней группе (пятерке) не хватает одной буквы. Значит, прежде чем шифровать исходное выражение, следует его дополнить незначащей буквой (например, О) до числа, кратного пяти: ПУСТЬ-БУДЕТ-ТАККА-КМЫХО-ТЕЛИО. Тогда шифрограмма, несмотря на столь незначительные изменения, будет выглядеть по-другому: ОИЛЕТ ОХЫМК АККАТ ТЕДУБ ЬТСУП Кажется, ничего сложного, но при расшифровке проявляются серьезные неудобства. Во время Гражданской войны в США в ходу был такой шифр: исходную фразу писали в несколько строк. Например, по пятнадцать букв в каждой (с заполнением последней строки незначащими буквами). П У С Т Ь Б У Д Е Т Т А К К А К М Ы Х О Т Е Л И К Л М Н О П После этого вертикальные столбцы по порядку писали в строку с разбивкой на пятерки букв: ПКУМС ЫТХЬО БТУЕД ЛЕИТК ТЛАМК НКОАП Если строки укоротить, а количество строк увеличить, то получится прямоугольник-решетка, в который можно записывать исходный текст. Но тут уже потребуется предварительная договоренность между адресатом и отправителем посланий, поскольку сама решетка может быть различной длины-высоты, записывать к нее можно по строкам, по столбцам, по спирали туда или по спирали обратно, можно писать и по диагоналями, а для шифрования можно брать тоже различные направления. Шифры сложной замены Шифр Гронсфельдасостоит в модификации шифра Цезаря числовым ключом. Для этого под буквами сообщения записывают цифры числового ключа. Если ключ короче сообщения, то его запись циклически повторяют. Зашифрованное сообщение получают примерно также, как в шифре Цезаря, но используют не одно жестко заданное смещение а фрагменты ключа. Пусть в качестве ключа используется группа из трех цифр – 314, тогда сообщение С О В Е Р Ш Е Н Н О С Е К Р Е Т Н О 3 1 4 3 1 4 3 1 4 3 1 4 3 1 4 3 1 4 Ф П Ё С Ь З О С С А Х З Л Ф З У С С В шифрах многоалфавитной замены для шифрования каждого символа исходного сообщения применяется свой шифр простой замены (свой алфавит).
Каждая строка в этой таблице соответствует одному шифру замены аналогично шифру Цезаря для алфавита, дополненного пробелом. При шифровании сообщения его выписывают в строку, а под ним ключ. Если ключ оказался короче сообщения, то его циклически повторяют. Зашифрованное сообщение получают, находя символ в колонке таблицы по букве текста и строке, соответствующей букве ключа. Например, используя ключ АГАВА, из сообщения ПРИЕЗЖАЮ ШЕСТОГО получаем следующую шифровку: ПРИЕЗЖАЮ_ШЕСТОГО АГАВААГАВААГАВАА ПОИГЗЖЮЮЮШЕПТНГО Такая операция соответствует сложению кодов ASCII символов сообщения и ключа по модулю 256. Практическое задание Придумайте 3 фразы, каждая минимум из 7 слов. Реализуйте шифрование этой фразы всеми перечисленными видами шифрования. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
