 |
Лабораторная работа № 1. Шифры замены
|
|
|
|
Кафедра «Информационные технологии и системы»
В.В. Анисимов
КРИПТОГРАФИЯ
Методические указания
по выполнению лабораторных работ
по дисциплине
«Информационная безопасность и защита информации»
Хабаровск
Издательство ДВГУПС
УДК 003.26 (075.8)
ББК З 973.2 – 018.2я73
А 674
Рецензент:
Доцент кафедры «Информационные технологии и системы»
Дальневосточного государственного университета путей сообщения,
кандидат технических наук
В.И. Медник
Анисимов В.В.
А 674 Криптография: Методические указания / В.В. Анисимов. – Хабаровск: Изд-во ДВГУПС, 2004. – 32 с.: ил.
Методические указания соответствуют Государственному образовательному стандарту направления 654700 «Информационные системы» специальности 071900 «Информационные системы и технологии».
В указаниях приведены общие сведения о криптографии. Рассмотрены основные методы симметричного и асимметричного шифрования. Приведены задания на выполнение лабораторных работ и даны рекомендации по их выполнению.
Указания предназначены для студентов любых форм обучения, изучающих информационную безопасность и защиту информации, а также специалистов, ведущим проектирование, разработку и эксплуатацию информационных систем.
© ГОУ ВПО «Дальневосточный государственный университет путей сообщения МПС России» (ДВГУПС), 2004
ВВЕДЕНИЕ
На современном этапе развития общества ключевая роль во всех сферах человеческой деятельности отводиться информации. Тезис «кто владеет информацией, тот владеет миром» становиться все более актуальным. В настоящее время основная доля информационных ресурсов храниться в системах, основанных на компьютерных технологиях. Процесс подключения компьютеров к локальным сетям и глобальной сети Internet носит повсеместный характер. Это приводит к значительному повышению доступности информации, в т.ч. и конфиденциальной.
|
|
|
В связи с этим вопросам защиты компьютерной информации в последнее время уделяется повышенное внимание. При этом под защитой информации понимается комплекс правовых, организационных и технических мероприятий и действий по предотвращению угроз информационной безопасности и устранению их последствий в процессе ее сбора, хранения, обработки и передачи в информационных системах.
Одним из самых распространенных средств защиты компьютерной информации является шифрование, которое широко используется для обеспечения конфиденциальности как хранимой, так и передаваемой по сетям информации.
Настоящие методические указания предназначены для изучения основ шифрования информации. В первой главе даны основные криптографические понятия, а также приведена классификация шифров. В остальных главах рассмотрены особенности шифрования, присущие каждому классу шифров, и приведены примеры конкретных алгоритмов шифрования.
Целью данных указаний является первоначальное ознакомление с основами шифрования и дешифрования информации. В них не рассматриваются теоретические основы криптографии, криптографические протоколы и т.д. Для этих целей рекомендуется воспользоваться [1, 2, 3].
Программа практических занятий разбита на пять лабораторных работы. Каждая из них рассчитана на срок от двух до трех занятий и посвящена изучению одного класса шифров. В течение первых трех лабораторных работ студент должен освоить базовые алгоритмы симметричного шифрования (шифры замены, перестановки и гаммирования). В четвертой лабораторной работе он должен изучить основы блочного шифрования на примере бывшего американского стандарта шифрования DES. В пятой лабораторной работе проводится описание трех алгоритмов асимметричного шифрования.
|
|
|
В течение этих занятий студент должен практически освоить весь материал по каждой лабораторной работе, выполнить задание, оформить отчет и защитить работу. При защите студент должен продемонстрировать степень усвоения материала, а также ответить на вопросы, связанные с темами текущей и уже пройденных лабораторных работ.
ОСНОВЫ КРИПТОГРАФИИ
Разработкой методов преобразования информации с целью обеспечения ее конфиденциальности и целостности занимается криптография (в переводе с греческого означает «тайнопись»). О важности сохранения информации в тайне знали уже в древние времена, когда с появлением письменности появилась и опасность прочтения ее нежелательными лицами. Более того, первоначально письменность сама по себе была криптографической системой, так как в древних обществах ею владели только избранные. С широким распространением письменности криптография стала формироваться как самостоятельная наука.
Одно из основных понятий криптографии - шифр (от арабского «цифра»; арабы первыми стали заменять буквы на цифры для защиты конфиденциальной информации). Шифр - совокупность методов и способов обратимого преобразования информации с целью ее защиты от несанкционированного доступа. В данном определении под преобразованием понимаются два обратных процесса: шифрование и дешифрование
Шифрование (зашифрование) — процесс применения шифра к защищаемой информации, т.е. преобразование защищаемой информации (открытого текста) в шифрованное сообщение (шифртекст, шифрограмму, криптограмму) с помощью определенных правил, содержащихся в шифре [2].
Дешифрование — процесс преобразование шифрованного сообщения в защищаемую информацию с помощью определенных правил, содержащихся в шифре [2].
Любой шифр состоит, как минимум, из двух составляющих: алгоритма и ключа преобразования.
Алгоритм криптографического преобразования — набор математических правил, определяющих содержание и последовательность операций по шифрованию и дешифрованию информации [4].
Ключ – конкретное состояние некоторых параметров алгоритма криптографического преобразования, обеспечивающее выбор одного преобразования из совокупности всевозможных для данного алгоритма [4].
|
|
|
Используя понятие ключа, процессы шифрования и дешифрования можно описать в виде следующих соотношений:
f(P, K1) = C, (1)
g(C, K2) = P, (2)
где P, C - открытое и шифрованное сообщение;
f, g - алгоритмы шифрования и дешифрования;
К1, К2 - ключи шифрования и дешифрования.
В зависимости от особенностей алгоритма криптографического преобразования шифры можно разделить на следующие классы.
| Криптографические алгоритмы | ||||||||||||
| ||||||||||||
| Одноключевые (симметричные) | Двухключевые (асимметричные) | Квантовые | Комбини-рованные (составные) | |||||||||
| Замены | Перестановки | Аддитивные (гаммирования) | Детермини-рованные | Вероят-ностные |
Рис.1. Классификация криптографических алгоритмов
В одноключевых шифрах для шифрования и дешифрования используется один и тот же ключ (К1 = К2). В шифрах замены отдельные части открытого текста (буквы, слова, числа и т.п.) при шифровании заменяются на другие буквы, числа, значки и т.п. Таким образом, для записи открытых текстов и шифрограмм используются два разных алфавита, между символами которых есть взаимнооднозначное соответствие. В шифрах перестановки все символы открытого текста попадают в шифрограмму в неизменном виде, но меняют свое местоположение. В аддитивных шифрах символы алфавита заменяются числами, которые затем складываются по модулю с числами секретной числовой последовательности (гаммы, зависящей от ключа) или непосредственно ключа. Обычно для шифрования методом гаммирования используется сложение по модулю 2.
В двухключевых шифрах для шифрования и дешифрования используется два совершено разных ключа. При использовании детерминированного алгоритма шифрование и расшифрование посредством одной пары ключей возможно только единственным способом. Вероятностный алгоритм при шифровании может давать разные шифртексты, которые при расшифровании дают один и тот же результат.
|
|
|
Квантовые шифры основываются на законах квантовой физики. Самым ценным свойством этого вида шифрования является то, что при посылке сообщения отправляющая и принимающая стороны с достаточно большой вероятностью (99.99…%) могут установить факт перехвата зашифрованного сообщения. Следует отметить, что квантовое шифрование в настоящее время пока находиться на стадии теоретических разработок и экспериментальных исследований. В связи с этим оно в данных методических указаниях не рассматривается.
Комбинированные шифры предполагают использование для шифрования сообщения сразу нескольких методов (например, сначала замену символов, а затем их перестановку).
Кроме приведенной на рис.1 классификации, шифры в зависимости от особенностей алгоритма делят также на потоковые и блочные. В потоковых шифрах одна и та же процедура преобразования выполняется над каждым символом независимо от других. В блочных шифрах исходное сообщение разбивается на блоки фиксированной длины, каждый из которых шифруется и расшифровывается отдельно.
Одним из ключевых понятий в криптографии является стойкость шифра (криптостойкость) - способность шифра противостоять всевозможным атакам на него. Под атакой на шифр понимают попытку вскрытия этого шифра [2].
Среди наиболее важных показателей кpиптостойкости: количество всех возможных ключей шифра и среднее время, необходимое для криптоанализа (вскрытия).
Понятие стойкости шифра является центральным для криптографии. Хотя качественно понять его довольно легко, но получение строгих доказуемых оценок стойкости для каждого конкретного шифра – проблема нерешенная. Поэтому стойкость конкретного шифра оценивается только путем всевозможных попыток его вскрытия и зависит от квалификации криптоаналитиков, атакующих шифр. Такую процедуру иногда называют проверкой стойкости [2].
В зависимости от стойкости шифры делятся на три группы:
- совершенные шифры – шифры, заведомо неподдающиеся вскрытию (при правильном использовании);
- шифры, допускающие неоднозначное вскрытие (при попытке вскрытия противником конкретной шифрограммы он может получить несколько правдоподобных вариантов исходного сообщения);
- шифры, допускающие однозначное вскрытие (основная масса шифров).
ЛАБОРАТОРНАЯ РАБОТА № 1. ШИФРЫ ЗАМЕНЫ
Сущность шифрования методом замены заключается в следующем [2]. Пусть шифруются сообщения на русском языке и замене подлежит каждая буква этих сообщений. Тогда, для буквы А исходного алфавита строится некоторое множество символов (шифрозамен) МА, для Б – МБ, …, для Я – МЯ. Шифрозамены выбираютсятаким образом, чтобы любые два множества (МI и МJ, i ¹ j) не содержали одинаковых элементов (МI Ç МJ = Æ).
|
|
|
Таблица, приведенная на рис.2, является ключом шифра замены. Зная ее, можно осуществить как шифрование, так и расшифрование.
При шифровании каждая буква А открытого сообщения заменяется любым символом из множества МА. Если в сообщении содержится несколько букв А, то каждая из них заменяется на любой символ из МА. За счет этого с помощью одного ключа можно получить различные варианты шифрограммы для одного и того же открытого сообщения.
Так как множества МА, МБ,..., МЯ попарно не пересекаются, то по каждому символу шифрограммы можно однозначно определить, какому множеству он принадлежит, и, следовательно, какую букву открытого сообщения он заменяет. Поэтому расшифрование возможно и открытое сообщение определяется единственным образом.
Метод замены часто реализуется многими пользователями при работе на компьютере. Если по забывчивости не переключить на клавиатуре набор символов с латиницы на кириллицу, то вместо букв русского алфавита при вводе текста будут печататься буквы латинского алфавита («шифрозамены»).
Шифры замены можно разделить на следующие подклассы:
- шифры однозначной замены (одноалфавитные). Количество шифрозамен для каждого символа исходного алфавита равно 1 (½ Мi ½=1);
- шифры многозначной замены (многоалфавитные). Количество шифрозамен для отдельных символов исходного алфавита больше 1 (½ Мi ½≥1).
Для записи исходных и зашифрованных сообщений используются строго определенные алфавиты. Под алфавитом в данном случае понимается набор символов, служащий для записи сообщений. Алфавиты для записи исходных и зашифрованных сообщений могут отличаться. Символы обоих алфавитов могут быть представлены буквами, их сочетаниями, числами, рисунками и т.п. В качестве примера можно привести пляшущих человечков из рассказа А. Конан Дойла (
) и рукопись рунического письма (
) из романа Ж. Верна «Путешествие к центру Земли».
Шифры однозначной замены. Максимальное количество ключей для любого шифра этого вида не превышает n!, где n – количество символов в алфавите. С увеличением числа n значение n! растет очень быстро (1!=1, 5!=120, 10!=3628800, 15!=1307674368000). При больших n для приближенного вычисления n! можно воспользоваться формулой Стирлинга
. (3)
Шифр Цезаря (1 век до н.э.). Данный шифр был придуман Гаем Юлием Цезарем и использовался им в своей переписке. Применительно к русскому языку суть его состоит в следующем. Выписывается исходный алфавит (А, Б,..., Я), затем под ним выписывается тот же алфавит, но с циклическим сдвигом на 3 буквы влево.
| А | Б | В | Г | Д | Е | Е | Ж | З | И | Й | К | Л | М | Н | О | П | Р | С | Т | У | Ф | Х | Ц | Ч | Ш | Щ | Ы | Ь | Ъ | Э | Ю | Я |
| Г | Д | Е | Е | Ж | И | И | К | Л | М | Н | О | П | Р | С | Т | У | Ф | Х | Ц | Ч | Ш | Щ | Ы | Ь | Ъ | Э | Ю | Я | А | Б | В |
Рис.3. Таблица шифрозамен для шифра Цезаря
При зашифровке буква А заменяется буквой Г, Б - на Д и т. д. Так, например, исходное сообщение «АБРАМОВ» после шифрования будет выглядеть «ГДУГПСЕ». Получатель сообщения «ГДУГПСЕ» ищет эти буквы в нижней строке и по буквам над ними восстанавливает исходное сообщение «АБРАМОВ».
Ключом в шифре Цезаря является величина сдвига нижней строки алфавита. Количество ключей для всех модификаций данного шифра применительно к алфавиту русского языка равно 33.
Лозунговый шифр. Для данного шифра построение таблицы шифрозамен основано на лозунге (ключе) – легко запоминаемом слове. Вторая строка таблицы шифрозамен заполняется сначала словом-лозунгом (причем повторяющиеся буквы отбрасываются), а затем остальными буквами, не вошедшие в слово-лозунг, в алфавитном порядке. Например, если выбрано слово-лозунг «ДЯДИНА», то таблица имеет следующий вид.
| А | Б | В | Г | Д | Е | Е | Ж | З | И | Й | К | Л | М | Н | О | П | Р | С | Т | У | Ф | Х | Ц | Ч | Ш | Щ | Ы | Ь | Ъ | Э | Ю | Я |
| Д | Я | И | Н | А | Б | В | Г | Е | Е | Ж | З | Й | К | Л | М | О | П | Р | С | Т | У | Ф | Х | Ц | Ч | Ш | Щ | Ы | Ь | Ъ | Э | Ю |
Рис.4. Таблица шифрозамен для лозунгового шифра
При шифровании исходного сообщения «АБРАМОВ» по приведенному выше ключу шифрограмма будет выглядеть «ДЯПДКМИ».
Полибианский квадрат. Шифр изобретен греческим писателем и историком Полибием. Прямоугольная таблица заполняется буквами алфавита в случайном порядке. Размер прямоугольника и порядок букв является ключом.
Каждая буква открытого сообщения заменяется буквой, расположенной ниже в том же столбце. Если буква находится на последней строке таблицы, то для ее шифрования берут самую верхнюю букву столбца. Например, если исходное сообщение «АБРАМОВ», то шифрограмма – «УФВУЭЬТ».
Шифрующая система Трисемуса. Является сочетанием лозунгового шифра и полибианского квадрата. В таблицу сначала вписывается ключевое слово, причем повторяющиеся буквы отбрасываются. Затем эта таблица дополняется не вошедшими в нее буквами алфавита. На рис.6 изображена таблица с ключевым словом «ДЯДИНА».
Шифрование выполняется как и в предыдущем шифре (исходное сообщение «АБРАМОВ», зашифрованное – «ИЙЪИХШК»).
Одним из существенных недостатков шифров однозначной замены является их легкая вскрываемость. При вскрытии шифрограмм используются различные приемы, которые даже при отсутствии мощных вычислительных средств позволяют добиться положительного результата. Один из таких приемов базируется на том, что в шифрограммах остается информация о частоте встречаемости букв исходного текста. Если в открытом сообщении часто встречается какая-либо буква, то в шифрованном сообщении также часто будет встречаться соответствующий ей символ. Для разных языков мира существуют специальные таблицы с оценкой вероятности появления тех или иных букв в текстах. Так, например, для русского языка такая таблица выглядит следующим образом [7].
Таблица 1
Вероятности появления букв русского языка в текстах*
| Буква (символ) | Вероят- ность | Буква | Вероят- ность | Буква | Вероят- Ность | Буква | Вероят- ность |
| Пробел | 0.146 | Р | 0.042 | Я | 0.017 | Ж | 0.007 |
| О | 0.094 | Л | 0.039 | З | 0.016 | Ш | 0.006 |
| Е | 0.071 | В | 0.038 | Ы | 0.015 | Ц, Ю | 0.005 |
| А | 0.069 | К | 0.029 | Г | 0.014 | Щ | 0.004 |
| И | 0.064 | М | 0.027 | Ь, Б | 0.013 | Ф | 0.003 |
| Н | 0.057 | П | 0.026 | Ч | 0.012 | Э | 0.002 |
| Т | 0.054 | Д | 0.024 | Й | 0.010 | Ъ | 0.001 |
| С | 0.046 | У | 0.023 | Х | 0.008 |
*) В таблице приведены оценки вероятностей появления букв русского языка и пробела, полученные на основе анализа научно-технических и художественных текстов общим объемом более 1000000 символов.
Существуют подобные таблицы для пар букв (биграмм). Например, часто встречаемыми биграммами являются «то», «но», «ст», «по», «ен» и т.д. Другой прием вскрытия шифрограмм основан на исключении возможных сочетаний букв. Например, в текстах (если они написаны без орфографических ошибок) нельзя встретить сочетания «чя», «щы», «ьъ» и т.п.
Для усложнения задачи вскрытия шифров однозначной замены еще в древности перед шифрованием из исходных сообщений исключали пробелы и/или гласные буквы.
Шифры многозначной замены. Другое направление повышения стойкости шифров замены состоит в том, чтобы каждое множество шифрообозначений Мi содержало более одного элемента. При использовании такого шифра одну и ту же букву (если она встречается несколько раз в сообщении) заменяют на разные шифрозамены из Мi. Это позволяет скрыть истинную частоту встречаемости букв открытого сообщения.
Книжный шифр. Во время второй мировой войны разведорганы различных государств часто использовали так называемые книжные шифры. Шифрозамена для каждой буквы определялась набором цифр, которые указывали на номер страницы, строки и позиции в строке. Количество книг, изданных за всю историю человечества, является величиной ограниченной (по крайней мере, явно меньше, чем 15!). Однако отсутствие полной электронной базы по изданиям делает процедуру вскрытия шифрограмм почти не выполнимой. В связи с этим книжный шифр относят к категории совершенных.
Система омофонов. Число шифрозамен для каждого символа берется пропорциональным вероятности его появления в открытых текстах. Так, если ориентироваться на табл.1, то число шифрозамен для буквы О должно составлять 94, для буквы Е – 71 и т.д. При этом каждая шифрозамена должна состоять из 3 цифр и их общее количество равно 1000. На рис.7 представлен фрагмент таблицы шифрозамен.
| № п/п | Пробел | А | Б | В | … | М | … | О | … | Р | … | Я |
| … | … | … | … | |||||||||
| … | … | … | … | |||||||||
| … | … | … | … | … | … | … | … | … | … | … | … | … |
| … | … | … | … | |||||||||
| … | … | … | … | … | … | … | … | … | … | … | … | |
| … | … | … | … | |||||||||
| … | … | … | … | … | … | … | … | … | … | |||
| … | … | … | ||||||||||
| … | … | … | … | … | … | … | ||||||
| … | ||||||||||||
| … | … | … | … | … | … | |||||||
| … | ||||||||||||
| … | … | … | … | |||||||||
| … | … | … | ||||||||||
| … | … | |||||||||||
Рис.7. Фрагмент таблицы шифрозамен для системы омофонов
При шифровании символ исходного сообщения заменяется на любую шифрозамену из своего столбца. Если символ встречается повторно, то, как правило, используют разные шифрозамены. Например, исходное сообщение «АБРАМОВ» после шифрования будет выглядеть «357 990 374 678 037 828 175».
Система шифрования Виженера. Шифр описан в 1585 г. французом Блезом де Виженером в «Трактате о шифрах». Этот шифр задается квадратной таблицей, со стороной равной n, где n – количество символов в алфавите. В первой строке матрицы записываются буквы в порядке их очередности в алфавите, во второй – та же последовательность букв, но с циклическим сдвигом на одну позицию влево, в третьей – с циклическим сдвигом на две позиции влево и т.д.
| А | Б | В | Г | Д | … | М | Н | 6О | П | Р | … | Э | Ю | Я |
| Б | В | Г | Д | Е | … | Н | О | П | Р | С | … | Ю | Я | А |
| В | Г | Д | Е | Ж | … | О | П | Р | С | Т | … | Я | А | Б |
| Г | Д | Е | Ж | З | … | П | Р | С | Т | У | … | А | Б | В |
| 1Д | Е | 7Ж | З | И | … | Р | С | Т | У | 3Ф | … | Б | В | Г |
| … | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
| 4И | Й | К | Л | М | … | Ф | Х | Ц | Ч | Ш | … | Е | Ж | З |
| … | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
| Н | О | П | Р | С | … | 5Щ | Ъ | Ы | Ь | Э | … | К | Л | М |
| … | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
| Я | 2А | Б | В | Г | … | Л | М | Н | О | П | … | Ь | Э | Ю |
Рис.8. Фрагмент таблицы шифрозамен для системы шифрования Виженера
Перед шифрованием выбирается ключ из символов алфавита. Сама процедура шифрования заключается в следующем. По i-ому символу открытого сообщения в первой строке определяется столбец, а по i-ому символу ключа в крайнем левом столбце – строка. На пересечении строки и столбца будет находиться i-ый символ, помещаемый в шифрограмму. Если длина ключа меньше сообщения, то он используется повторно.
Например, исходное сообщение «АБРАМОВ», ключ – «ДЯДИНА», шифрограмма – «ДАФИЩОЖ» (числами на рис.8 показаны символы, попавшие в шифрограмму).
|
|
|
