Лаб.раб.8. Лаб.раб. Лабораторная работа 8 Классические криптографические системы Классические криптографические системы
Скачать 177.5 Kb.
|
ЛАБОРАТОРНАЯ РАБОТА №8 Классические криптографические системы
В I в. н.э. Ю.Цезарь во время войны с галлами, переписываясь со своими друзьями в Риме, заменял в сообщении первую букву латинского алфавита (А) на четвертую (D), вторую (B) - на пятую (E), наконец последнюю - на третью: ABCDEFGHIJKLMNOPQRSTUVWXYZ YHQL YLGL YLFL DEFGHIJKLMNOPQRSTUVWXYZABC Veni vidi vici - “Пришел, увидел, победил” Ю.Цезарь Донесение Сенату о победе над понтийским царем Вот что об этом сообщает Гай Светоний: "Существуют и его письма к Цицерону и письма к близким о домашних делах: в них, если нужно было сообщить что-нибудь негласно, он пользовался тайнописью, то есть менял буквы так, чтобы из них не складывалось ни одного слова. Чтобы разобрать и прочитать их, нужно читать всякий раз четвертую букву вместо первой, например, D вместо А и так далее". С современной точки зрения, в шифре Цезаря каждая буква замещается на букву, находящуюся k символами правее по модулю равному количеству букв в алфавите. Ck(j)=(j+k)(mod n), (1.1) где n — количество букв в алфавите (мощность алфавита). Очевидно, что обратной подстановкой является Ck-1(j)=Сn-k=(j+n-k)(mod n) (1.2) 1.2. Шифр Цезаря с ключевым словомВ данной разновидности шифра Цезаря ключ задается числом k(0<=k<=n-1) и коротким ключевым словом или предложением. Выписывается алфавит, а под ним, начиная с k-й позиции, ключевое слово. Оставшиеся буквы записываются в алфавитном порядке после ключевого слова. В итоге мы получаем подстановку для каждой буквы. Требование, чтобы все буквы ключевого слова были различными не обязательно — можно записывать ключевое слово без повторения одинаковых букв. Исходное сообщение: РИМ Шифротекст: ЗЧГ 1.3. Аффинная криптосистемаОбобщением системы Цезаря является аффинная криптосистема. Она определяется двум числами a и b, где 0<=a,b<=n-1 и n —является мощностью алфавита. Числа a и n должны быть взаимно простыми. Соответствующими заменами являются: Aa,b(j)=(a*j+b)(mod n), (1.3) A-1a,b(j)=(j-b)*a-1(mod n) (1.4) Обратную замену также можно получить, просто поменяв местами строки в таблице замен. Взаимная простота a и n необходима для однозначности отображения, в противном случае возможны отображения различных символов в один и неоднозначность дешифрирования. 1.4. Квадрат ПолибияСистема Цезаря не является старейшей. Возможно, что наиболее древней из известных является система греческого историка Полибия, умершего за 30 лет до рождения Цезаря. В Древней Греции (II в. до н.э.) был известен шифр, называемый “квадрат Полибия”1. Это устройство представляло собой квадрат 5*5, столбцы и строки которого нумеровали цифрами от 1 до 5. В каждую клетку записывалась одна буква (в греческом варианте одна клетка оказывалась пустой, а в латинском - в одну клетку помещали две буквы I,J). В результате каждой букве отвечала пара чисел по номеру строки и столбца. A B C D E 13 34 22 24 44 34 15 42 22 34 43 45 32 F G H I,J K L M N O P Cogito ergo sum - лат. “Я мыслю, следовательно, существую” Q R S T U Р.Декарт V W X Y Z 1.5. Решетка КарданоШироко известны шифры, принадлежащие к классу “перестановка”, в частности “решетка Кардано”2. Это прямоугольная карточка с отверстиями, чаще всего квадратная, которая при наложении на лист бумаги оставляет открытими лишь некоторые его части. Число строк и столбцов на карточке четно. Карточка сделана так, что при последовательном ее поворачивании каждая клетка лежащего под ней листа окажется занятой. Карточку поворачивают сначала вдоль вертикальной оси симметрии на 180, а затем вдоль горизонтально оси также на 180. И вновь повторяют ту же процедуру. 1.6. Таблица ВиженераНеудобство рассмотренных выше шрифтов очевидно, т.к. в случае использования стандартного алфавита таблица частот встречаемости букв алфавита позволяет определить один или несколько символов, а этого иногда достаточно для вскрытия шифра (“Плящущие человечки” Конан Дойля или “Золотой жук ” Эдгара По). Поэтому использовались различные приемы для того чтобы затруднить дешифрование, например использование “таблицы Виженера”, которая представляет собой квадратную таблицу с числом строк и столбцов равным количеству букв алфавита. Чтобы зашифровать какое-либо сообщение выбирают слово - лозунг (например, “монастырь”) и надписывают его над сообщением с необходимым повторением. Чтобы получить шифрованный текст, находят очередной знак лозунга, начиная с первого в вертикальном алфавите, а ему соответствующий знак сообщения в горизонтальном алфавите. На пересечении выделенных столбца и строки находим первую букву шифра. Очевидно, что ключом к такому шифру является используемый лозунг. Лозунг: м о н а с т ы р ь м о н а с т ы р ь м о н Исходный текст: р а с к и н у л о с ь м о р е ш и р о к о Шифротекст: э о я к щ а п ы й ю й щ о в ч ф ш л ь ш ы Таблица Виженера3 АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЭЮЯ БВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЭЮЯА ВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЭЮЯАБ ГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЭЮЯАБВ ДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЭЮЯФБВГ ЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЭЮЯФБВГД ЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЭЮЯФБВГДЕ ЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЭЮЯАБВГДЕЖ ИЙКЛМНОПРСТУФХЦЧШЩЬЫЭЮЯАБВГДЕЖЗ ЙКЛМНОПРСТУФХЦЧШЩЬЫЭЮЯАБВГДЕЖЗИ КЛМНОПРСТУФХЦЧШЩЬЫЭЮЯАБВГДЕЖЗИЙ ЛМНОПРСТУФХЦЧШЩЬЫЭЮЯАБВГДЕЖЗИЙК МНОПРСТУФХЦЧШЩЬЫЭЮЯАБВГДЕЖЗИЙКЛ НОПРСТУФХЦЧШЩЬЫЭЮЯАБВГДЕЖЗИЙКЛМ ОПРСТУФХЦЧШЩЬЫЭЮЯАБВГДЕЖЗИЙКЛМН ПРСТУФХЦЧШЩЬЫЭЮЯАБВГДЕЖЗИЙКЛМНО РСТУФХЦЧШЩЬЫЭЮЯАБВГДЕЖЗИЙКЛМНОП СТУФХЦЧШЩЬЫЭЮЯАБВГДЕЖЗИЙКЛМНОПР ТУФХЦЧШЩЬЫЭЮЯАБВГДЕЖЗИЙКЛМНОПРС УФХЦЧШЩЬЫЭЮЯАБВГДЕЖЗИЙКЛМНОПРСТ ФХЦЧШЩЬЫЭЮЯАБВГДЕЖЗИЙКЛМНОПРСТУ ХЦЧШЩЬЫЭЮЯАБВГДЕЖЗИЙКЛМНОПРСТУФ ЦЧШЩЬЫЭЮЯАБВГДЕЖЗИЙКЛМНОПРСТУФХ ЧШЩЬЫЭЮЯАБВГДЕЖЗИЙКЛМНОПРСТУФХЦ ШЩЬЫЭЮЯАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧ ЩЬЫЭЮЯАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШ ЬЫЭЮЯАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩ ЫЭЮЯАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЬ ЭЮЯАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧЩШЬЫ ЮЯАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЭ ЯАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЭЮ Архитекторы и исследователи Италии эпохи Возрождения считают, что один из самых важных этапов ренессансной архитектуры связан с именем Леона Батиста Альберти, написавшем десять книг о зодчестве, построившим палаццо Ручеллаи, церковь Иль Джезу и ряд других замечательных произведений зодчества средневековой Италии. Будучи теоретиком искусства, он обобщил опыт гуманистической науки в изучении античного наследия, написав ряд трактатов: "О статуе", "О живописи", "О зодчестве". С другой стороны, криптологи всего мира почитают его отцом своей науки. Главным достижением Альберти в криптологии было изобретение многоалфавитной замены, сделавших шифровку очень устойчивой к вскрытию. Кроме самого шифра он еще подробно описал устройства из вращающихся колес для его реализации. Этот шифр можно описать таблицей шифрования, которая и называетсятаблицей Виженера, по имени Блеза Виженера, дипломата XVI века, который развивал и совершенствовал криптографические системы. Итак, помимо ряда строений в античной манере, являющихся шедеврами архитектуры итальянского Возрождения, Альберти еще ввел в практику криптографии многоалфавитные шифры замены. Его книга "Трактат о шифре", написанная в 1466 году, представляла собой первый в мире научный труд по криптологии, если не считать арабских рукописей, с которыми Европа в это время вряд ли была хорошо знакома. 1.7. Одноразовый шифровальный блокнотПримером нераскрываемого шифра может служить так называемый “одноразовый шифровальный блокнот” - шифр, в основе которого лежит та же идея, что в шифре Цезаря. Назовем расширенным алфавитом совокупность букв алфавита, знаков препинания {. , : ; ! ? () – “ <пробел>}, число символов расширенного русского алфавита в данном варианте будет равно 44. Занумеруем символы расширенного алфавита числами от 0 до 43. Тогда любой передаваемый текст можно рассматривать как последовательность {an} чисел множества A={0,1,2,…,43}. Предположим, что имеем случайную последовательность {cn} из чисел множества А той же длины, что и передаваемый текст - ключ. Складывая по модулю 44 число из передаваемого текста an с соответствующим числом из множества ключа cn: an + cn bn (mod 44), 0<=bn<=43 получим последовательность {bn} знаков шифрованного текста. Чтобы получить передаваемый текст, можно воспользоваться тем же ключом: an bn - cn (mod 44), 0<=an<=43 У двух абонентов, находящихся в секретной переписке, имеются два одинаковых блокнота. В каждом из них на нескольких листах напечатана случайная последовательность чисел множества А. Отправитель свой текст шифрует указанным выше способом при помощи первой страницы блокнота. Зашифровав сообщение, он уничтожает использованную страницу и отправляет текст сообщения второму абоненту, получатель шифрованного текста расшифровывает его и также уничтожает использованный лист блокнота. Нетрудно видеть, что одноразовый шифр не раскрываем в принципе, так как символ в тексте может быть заменен любым другим символом и этот выбор совершенно случаен. 2. Описание программы шифрования информации с использованием классическихкриптосистемПрограмма представляет собой модель классических криптографических алгоритмов: код Цезаря, решетка Кардано, таблица Виженера и одноразовый шифровальный блокнот. Программа написана на языке Visual C++ с использованием библиотек CLR от Microsoft. Программа имеет оконный интерфейс, в ней возможен ввод пользовательского текста, а также предусмотрена возможность открывать и сохранять внешние файлы. В программе доступен только латинский алфавит, кириллический алфавит может быть реализован в дальнейших версиях по просьбе пользователей. В методах «код Цезаря» и «решетка Кардано» используются оба регистра, а в методах «одноразовый шифровальный блокнот» и «таблица Виженера» входной текст устанавливается в верхний регистр. В программе реализованы следующие алгоритмы шифрования. Алгоритм шифрования с помощью кода Цезаря Словесное описание алгоритма: каждая буква в кодируемой фразе замещается на букву того же алфавита, но с заданным смещением. В данной программе смещение задается пользователем. Код процедуры: System::String^ cesar(System::String^ input){ System::String^ output; System::String^ shft; dialogCatchWord^ dCW = gcnew dialogCatchWord(); dCW->labelCatchWord->Text = “Enter shift”; dCW->Text = “Shift”; dCW->textBoxCatchWord->MaxLength = 2; shft = dCW->ShowDlg(); System::Int32 shift; shift = System::Int32::Parse(shft); if ( shift > 25 ) { output = “Error 103! Shift must be < 26!!!”; return output; } for (int I = 0; I < input->Length; i++){ System::Char ch; if ( input[i] >= ‘A’ && input[i] <= ‘Z’ ) { ch = input[i] + shift; if ( input[i] + shift > 90 ) ch -= 26; } else if ( input[i] >= ‘a’ && input[i] <= ‘z’ ) { ch = input[i] + shift; if ( input[i] + shift > 122 ) ch -=26; } else ch = input[i]; output = System::String::Concat( output, ch.ToString() ); } return output; } Пример: veni vidi vici yhql ylgl ylfl – закодировано со смещением 3 zirm zmhm zmgm – закодировано со смещением 4 Алгоритм шифрования с помощью решетки Кардано Словесное описание алгоритма: решетка Кардано — это карточка с несколькими вырезанными окнами, примерно как на перфокарте. Когда карточка накладывается на зашифрованный текст, в ее окнах появляется скрытое сообщение. Таким образом, зашифровать и прочитать исходный текст можно, имея одну и ту же карточку. Код процедуры: System::String^ cardano(System::String^ input){ System::String^ output; int* code; code = new int[input->Length]; Random rnd; for ( int i = 0; i < input->Length; i++ ) code[i] = rnd.Next(2); for ( int i = 0; i < input->Length; i++ ) if ( code[i] && ( String::Compare(input[i].ToString(), " ") != 0 ) ) output = String::Concat(output, input[i].ToString()); else if ( String::Compare(input[i].ToString(), " ") == 0 ) output = String::Concat(output, " " ); return output; } Пример: mother washed a window-frame 010001 011011 0 011001011010 o r as ed in w fr m Алгоритм шифрования с помощью «одноразового шифровального блокнота» Словесное описание алгоритма: используется расширенный алфавит ABCDEFGHIJKLMNOPQRSTUVWXYZ!"(),-.?:; Каждый символ входного текста получает номер согласно позиции в расширенном алфавите. Далее с помощью генератора (псевдо)случайных чисел с интервалом от 0 до 36 создается последовательность той же длины, что и входной текст. Затем происходит посимвольное сложение по модулю 36 элементов входного текста и элементов последовательности. Получаемый выходной текст есть закодированный входной текст. Код процедуры: int getIntexLetter(System::Char letter, System::String^ aplphabeth){ int ret; for ( int i = 0; i < aplphabeth->Length; i++ ) if ( letter == aplphabeth[i] ) ret = i; return ret; } System::String^ notepad(System::String^ input){ System::String^ output; System::String^ alphabeth; System::Char ch; input = input->ToUpper(); for ( int i = 0; i < 37; i++ ){ if ( i < 26 ) ch = i + 65; if ( i == 26 ) ch = '!'; if ( i == 27 ) ch = '"'; if ( i == 28 ) ch = '('; if ( i == 29 ) ch = ')'; if ( i == 30 ) ch = ','; if ( i == 31 ) ch = '-'; if ( i == 32 ) ch = '.'; if ( i == 33 ) ch = '?'; if ( i == 34 ) ch = ':'; if ( i == 35 ) ch = ';'; if ( i == 36 ) ch = ' '; alphabeth = System::String::Concat(alphabeth, ch.ToString()); } int* code; code = new int[input->Length]; Random rnd; for ( int i = 0; i < input->Length; i++ ) code[i] = rnd.Next(37); for ( int i = 0; i < input->Length; i++ ){ int index = getIntexLetter(input[i], alphabeth); index += code[i]; if ( index > 36 ) index -= 36; output = System::String::Concat(output, alphabeth[index].ToString()); } return output; } Алгоритм шифрования с помощью таблицы Виженера Словесное описание алгоритма: таблица Виженера представляет собой квадратную таблицу с числом строк и столбцов, равным количеству букв алфавита. Выбирается какое-либо кодовое слово и записывается под входным текстом с определенным повторением. Пример: mother washed a window-frame father father f atherf ather ROMOII BALOIU F WBUHFB-FKHQV (кодовое слово father) comput ercomp u tercom puter OCFWYK ARUVQS U PMEFCI-ULTQV (кодовое слово computer) ABCDEFGHIJKLMNOPQRSTUVWXYZ BCDEFGHIJKLMNOPQRSTUVWXYZA CDEFGHIJKLMNOPQRSTUVWXYZAB DEFGHIJKLMNOPQRSTUVWXYZABC EFGHIJKLMNOPQRSTUVWXYZABCD FGHIJKLMNOPQRSTUVWXYZABCDE GHIJKLMNOPQRSTUVWXYZABCDEF HIJKLMNOPQRSTUVWXYZABCDEFG IJKLMNOPQRSTUVWXYZABCDEFGH JKLMNOPQRSTUVWXYZABCDEFGHI KLMNOPQRSTUVWXYZABCDEFGHIJ LMNOPQRSTUVWXYZABCDEFGHIJK MNOPQRSTUVWXYZABCDEFGHIJKL NOPQRSTUVWXYZABCDEFGHIJKLM OPQRSTUVWXYZABCDEFGHIJKLMN PQRSTUVWXYZABCDEFGHIJKLMNO QRSTUVWXYZABCDEFGHIJKLMNOP RSTUVWXYZABCDEFGHIJKLMNOPQ STUVWXYZABCDEFGHIJKLMNOPQR TUVWXYZABCDEFGHIJKLMNOPQRS UVWXYZABCDEFGHIJKLMNOPQRST VWXYZABCDEFGHIJKLMNOPQRSTU WXYZABCDEFGHIJKLMNOPQRSTUV XYZABCDEFGHIJKLMNOPQRSTUVW YZABCDEFGHIJKLMNOPQRSTUVWX ZABCDEFGHIJKLMNOPQRSTUVWXY 3. Порядок выполнения работыЦель лабораторной работыОзнакомление с принципами шифрования, используемыми в классических криптографических системах: код Цезаря, решетка Кардано, таблица Виженера и одноразовый шифровальный блокнот. Порядок выполнение работы
D:\ Криптография и стеганография_# группы |
Номер варианта | Контрольные вопросы |
1 | 2 |
1,5,7, 3,9,18 | Какие из рассмотренных вами систем шифрования относятся к моноалфавитным подстановкам? В чем их особенность? |
2,4,6,8, 20,22,24 | Какие из рассмотренных вами систем шифрования относятся к многоалфавитным подстановкам? В чем их особенность? |
11,13,15, 10,17,19 | Какие из рассмотренных вами систем относятся к перестановочным ? Приведите примеры перестановочных шифров. |
12,14,16 21,23,25 | Назовите элементы классических систем шифрования, используемые в современных криптографических системах. |
1 Полибий (200-120 гг до н.э.) древнегреческий историк
2 Кардано Джероламо (1501-1576) - выдающийся итальянский математик, имя которого дошло до нас благодаря изобретенному им шарнирному механизму и первой публикации о методе решения уравнений третьей степени. Его перу принадлежит несколько книг по криптографии.
3 Блез Виженер (1523-1596) - французский посол в Риме, написал большой труд о шифрах. Квадратный шифр Виженера на протяжении почти 400 лет не был дешифрован и считался недешифруемым.