ref-17947 (Криптология: подстановочно-перестановочный шифр и его применение)

2016-07-31СтудИзба

Описание файла

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

Онлайн просмотр документа "ref-17947"

Текст из документа "ref-17947"

Седьмая научная конференция молодых исследователей

«Шаг в будущее, Москва»

регистрационный номер

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

криптография:

подстановочно - перестановочный шифр и его применение

Автор: Калашников Алексей Александрович,

Школа №1959, 11 класс «А»

Научный руководитель: Троицкий Игорь Иванович, доцент

Кафедры «Информационная

Безопасность»(ИУ-8), МГТУ им. Н. Э.

Баумана, кандидат технических наук.

Москва - 2004

Содержание:

Появление шрифтов………………………….…..…….….стр.3

Становление науки криптологии…………………………стр.3

Криптология в новое время…………….…………...……..стр.12

Шифр Цезаря……………………………….…………..…..стр.15

-Программный код………………………...……..…….стр.15

Появление шифров

Ряд систем шифрования дошел до нас из глубокой древности. Скорее всего, они появились одновременно с письменностью в 4 тысячелетии до нашей эры. Методы секретной переписки были изобретены независимо во многих древних обществах, таких как Египет, Шумер и Китай, но детальное состояние криптологии в них неизвестно. Криптограммы выискиваются даже в древние времена, хотя из-за применяемого в древнем мире идеографического письма в виде стилизованных картинок были примитивны. Шумеры, по-видимому, пользовались тайнописью. Археологами найдены глиняные клинописные таблички, где первая запись замазывалась слоем глины, на котором делалась вторая запись. Происхождение таких странных таблиц могло быть вызвано и тайнописью, и утилизацией. Оттого что число знаков идеографического письма было более тысячи, то запоминание их представляло собой трудную задачу - тут не до шифрования. Тем не менее, коды, появившиеся вместе со словарями, были хорошо известны в Вавилоне и Ассирии, а древние египтяне применяли, по меньшей мере, 3 системы шифрования. С развитием фонетического письма письменность резко упростилась. В древнем семитском алфавите во 2-м тысячелетии до нашей эры было всего около 30 знаков. Ими обозначались согласные звуки, а также некоторые гласные и слоги. Упрощение письма стимулировало развитие криптографии.

Даже в Библии можно найти примеры шифровок, хотя мало кто это замечает. В книге пророка Иеремии (25,26) читаем: "...а царь Сессаха выпьет после них". Такого царя или царства не было - неужели ошибка писца? Нет, просто порой священные иудейские тексты шифровались простой заменой. Вместо первой буквы алфавита писалась последняя, вместо второй - предпоследняя и так далее. Этот древний метод шифрования назывался атбаш. Читая по нему слово СЕССАХ, на языке оригинала получаем слово ВАВИЛОН, и смысл библейского текста может быть принят даже не верящим слепо в истинность писания.

Вот что об этом сообщает Гай Светоний: "Существуют и его письма к Цицерону и письма к близким о домашних делах: в них, если нужно было сообщить что-нибудь негласно, он пользовался тайнописью, то есть менял буквы так, чтобы из них не складывалось ни одного слова. Чтобы разобрать и прочитать их, нужно читать всякий раз четвертую букву вместо первой, например, D вместо А и так далее". Это означает, что каждая буква шифровки заменялась четвертой по счету от нее в алфавите: А-В-С-D, или D вместо А. Послание сенату VENI VIDI VICI, то есть ПРИШЕЛ, УВИДЕЛ, ПОБЕДИЛ, сделанное Цезарем после однодневной войны с понтийским царем Фарнаком, выглядело бы шифровкой SBKF SFAF SFZF.

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

Для прочтения шифровки нужно не только знать систему засекречивания, но и обладать ключом в виде палочки, принятого диаметра. Зная тип шифра, но, не имея ключа, расшифровать сообщение было сложно. Этот шифр именовался скитала по названию стержня, на который наматывались свитки папируса, что указывает на его происхождение. Он был весьма популярен в Спарте и много раз совершенствовался в позднейшие времена. О его важном значении и большом распространении говорит свидетельство Плутарха в "Сравнительных жизнеописаниях", когда историк сообщает о жизни греческого полководца Алкивиада: "Однако Лисандр обратил внимание на эти слова не раньше, чем получил из дома скиталу с приказанием отделаться от Алкивиада..."

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

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

Приборы для шифрования тоже существовали с древних времен. Спарта, наиболее воинственная из греческих государств, имела хорошо проработанную систему секретной военной связи еще в V веке до нашей эры. С помощью скитала, первого известного криптографического устройства, спартанские эфоры (эфоры - члены коллегиального правительства Спарты.) шифровали послания, используя метод простой перестановки. Ленивые и оттого юбретательные римляне в IV веке до нашей эры, чтобы упростить процедуру шифрования, стали применять шифрующие диски. Каждый из 2 дисков, помещенных на общую ось, содержал на ободе алфавит в случайной последовательности. Найдя на одном диске букву текста, с другого диска считывали соответствующую ей букву шифра. Такие приборы, порождающие шифр простой замены. Использовались вплоть до эпохи Возрождения. Для связи греки и римляне использовали код на основе полибианского квадрата с естественным заполнением алфавитом. Буква кодировалась номером строки и столбца, соответствующим ей в квадрате. Сигнал подавался ночью факелами, а днем флагами.

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

Становление науки криптологии

В ручных шифрах того времени часто используются таблицы, которые дают простые шифрующие процедуры перестановки букв в сообщении. Ключом в них служат размер таблицы, фраза, задающая перестановку или специальная особенность таблиц. Простая перестановка без ключа - один из самых простых методов шифрования, родственный шифру скитала. Например, сообщение НЕЯСНОЕ СТАНОВИТСЯ ЕЩЕ БОЛЕЕ НЕПОНЯТНЫМ записывается в таблицу по столбцам. Для таблицы из 5 строк и 7 столбцов это выглядит так:



Н О Н С Б Н Я

Е Е О Я О Е Т

Я С В Е Л П Н

С Т И Щ Е О Ы

Н А Т Е Е Н М

После того, как открытый текст записан колонками, для образования шифровки он считывается по строкам. Если его записывать группами по 5 букв, то получится: НОНСБ НЯЕЕО ЯОЕТЯ СВЕЛП НСТИЩ ЕОЫНА ТЕЕНМ. Для использования этого шифра отправителю и получателю нужно договориться об общем ключе в виде размера таблицы. Объединение букв в группы не входит в ключ шифра и используется лишь для удобства записи несмыслового текста.

Более практический метод шифрования, называемый одиночной перестановкой по ключу очень похож на предыдущий. Он отличается лишь тем, что колонки таблицы переставляются по ключевому слову, фразе или набору чисел длиной в строку таблицы. Использовав в виде ключа слово ЛУНАТИК, получим такую таблицу.

Л У Н А Т И К

4 7 5 1 6 2 3

Н О Н С Б Н Я

Е Е О Я О Е Т

Я С В Е Л П Н

С Т И Щ Е О Ы

Н А Т Е Е Н М

до перестановки

А И К Л Н Т У

1 2 3 4 5 6 7

С Н Я Н Н Б О

Я Е Т Е О О Е

Е П Н Я В Л С

Щ О Ы С И Е Т

Е Н М Н Т Е А

после перестановки

В верхней строке ее записан ключ, а номера под ключом определены по естественному порядку соответствующих букв ключа в алфавите. Если в ключе встретились бы одинаковые буквы, они бы нумеровались слева направо. Получается шифровка: СНЯНН БОЯЕТ ЕООЕЕ ПНЯВЛ СЩОЫС ИЕТЕН МНТЕА. Для дополнительной скрытности можно повторно шифровать сообщение, которое уже было зашифровано. Этот способ известен под названием двойная перестановка. Для этого размер второй таблицы подбирают так, чтобы длины ее строк и столбцов были другие, чем в первой таблице. Лучше всего, если они будут взаимно простыми. Кроме того, в первой таблице можно переставлять столбцы, а во второй строки. Наконец, можно заполнять таблицу зигзагом, змейкой, по спирали или каким-то другим способом. Такие способы заполнения таблицы если и не усиливают стойкость шифра, то делают процесс шифрования гораздо более занимательным.

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





2 4 1 3

4 П P И Е

1 3 Ж A Ю

2 Ш Е С

3 Т О Г О

исходная

таблица

1 2 3 4

4 И П Е Р

1 A 3 Ю Ж

2 Е С Ш

3 Г Т О О

перестановка

столбцов

1 2 3 4

1 A 3 Ю Ж

2 Е С Ш

3 Г Т О О

4 И П Е Р

перестановка

строк

Получается шифровка АЗЮЖЕ СШГТООИПЕР. Ключом к этому шифру служат номера столбцов 2413 и номера строк 4123 исходной таблицы. Число вариантов двойной перестановки тоже велико: для таблицы 3х3 их 36, для 4х 4 их 576, а для 5 х 5 их уже 14400. Однако двойная перестановка очень слабый вид шифра, легко читаемый при любом размере таблицы шифрования.

Выдающимся английским философом и изобретателем Роджером Бэконом, предвосхитившим многие позднейшие открытия (наиболее значительное из его изобретений - очки, которые он предложил в 1268 году), был найден состав черного пороха. Так почему же традиционно считают его изобретателем Бертольда Шварца, по преданиям казненного императором Венцеславом на пороховой бочке? Карамзин по этому поводу писал: "Нет сомнения, что и монах Рогер Бакон за 100 лет до Бертольда Шварца умел составлять порох: ибо ясно говорит в своем творении de nulitate Magiae о свойстве и силе оного". Дело в том, что средневековые ученые, сделав открытие, отнюдь не всегда спешили его опубликовать в письмах коллегам, как это было тогда принято при отсутствии периодических научных изданий. Нередко ту часть открытия, которую теперь называют know how, они шифровали анаграммой, переставляя буквы сообщения по известному только им ключу. Например, названия древней и современной столиц Японии в русском написании тоже представляют собой анаграмму: КИОТО - ТОКИО.

В упомянутом труде Бэкона состав пороха был приведен в виде зашифрованной анаграммы, которую до появления сверхбыстродействующих ЭВМ не удавалось вскрыть, и слава открытия поэтому приписывалась Шварцу. Гораздо более сложная проблема возникает с приписываемым Галилео Галилею открытием спутников Юпитера. Долгое время приведенная им анаграмма читалась так: "Высочайшую планету двойною наблюдал", но в 1960-х годах с применением компьютеров при расшифровке был получен иной вариант прочтения: "Привет вам, близнецы, Марса порождение!" Конечно, открытие Фобоса и Деймоса на слабеньком телескопе за два с половиной столетия до американца Асафа Холла - событие мало реальное, но кто знает? Описал же Свифт в "Путешествиях Гулливера" спутники Марса за полтораста лет до астрономов с поразительной точностью! Может быть Свифт знал результаты Галилея, которые сейчас неизвестны? Шифры перестановки чрезвычайно коварны в том смысле, что могут дать несколько вариантов осмысленного прочтения, если не знать точного значения ключа.

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

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5057
Авторов
на СтудИзбе
456
Средний доход
с одного платного файла
Обучение Подробнее