Основные понятия классической криптографии

Классическая криптография решает фактически лишь две задачи: защиту передаваемых сообщений от прочт ения и от модификации посторонними лицами. Симметричная схема шифрования прекрасно работает, пока между участниками информационного обмена есть взаимное доверие. Если же его нет, то могут возникать различные проблемы. Получатель может сам изготовить зашифр ованное сообщение и затем объявить, что оно им получено от законного отправителя. Рассматриваемая криптографическая схема не позволяет однозначно подтвердить или опровергнуть авторство сообщения. Кроме того, эта схема нуждается в специальной службе, занима ющейся изготовлением секретных ключей и доставкой их участникам информационного обмена.
Ограничения классической криптографии и постоянно возникающие новые задачи привели к тому, что бы ...

Содержание
_Toc373277073
Содержание
Введение
История криптографии
Основные понятия
Симметричные криптосистемы
Шифры простой замены
Шифры сложной замены
Шифры перестановки
Заключение
Литература

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

Зашифрование и расшифрование выполняются в соответствии с криптографическим алгоритмом (cryptographic algorithm). Как правило, криптографический алгоритм содержит сменный элемент – криптографический ключ (cryptographic key), позволяющий выбрать одно конкретное преобразование из множества преобразований, реализуемых данным алгоритмом.Целью криптографических преобразований является обеспечение недоступности информации для лиц, не имеющих ключа, и поддержание с требуемой надежностью обнаружения несанкционированных искажений [6].Существует два основных типа криптографических алгоритмов: симметричные, для которых ключ расшифрования совпадает с ключом зашифрования или может быть легко из него получен, и асимметричные, использующие для зашифрования и расшифрования два разных ключа. Асимметричныеалгоритмы также называют алгоритмами с открытым ключом, и их история начинается с 1975 года, в то время как симметричные алгоритмы использовались многие тысячелетия. Классическая криптография опирается на использование симметричных алгоритмов шифрования.Симметричные алгоритмы можно разделить на две категории. К первой категории относятся алгоритмы, которые обрабатывают шифруемые данные побитово (или посимвольно), и такие алгоритмы называют потоковыми шифрами. Ко второй категории относят алгоритмы, производящие операции над группами битов. Такие группы битов называют блоками, а алгоритмы – блочными шифрами [7].Получение открытого текста из шифртекста без знания правильного ключа и/или всех деталей алгоритма является основной задачей криптоанализа и называется дешифрованием. Попытка криптоанализа называется атакой [7].Раскрытие ключа шифрования без привлечения методов криптоанализа называется компрометацией [7].К криптографическим функциям, кроме алгоритмов зашифрования и расшифрования, относят и некоторые другие операции. Так, например, в современной криптографии применяются криптографические хэш-функции (cryptographic hash-functions) для вычисления значения хэша (hash value), называемого еще дайджестом сообщения (message digest). Также существуют криптографические генераторы псевдослучайных чисел (random number generator) [7]. Зашифрование и расшифрование с помощью симметричного алгоритма записывается следующим образом:Обозначим открытый текст сообщения буквой М (от английского «message» сообщение), а просто открытый текст буквой Р (от «plaintext» - открытый текст). Это может быть последовательность (поток) битов, текстовый файл, точечный рисунок, оцифрованный звук, цифровое изображение и т.д. Для компьютеров М – это просто двоичные данные. Открытый текст предназначен для хранения или передачи. В любом случае М – это сообщение, которое необходимо зашифровать [5].Обозначим шифртекст буквой С (от английского «ciphertext»). Это тоже двоичные данные, иногда того же размера, что и М, а иногда большего. (Если шифрование сочетается со сжатием, размер С может быть меньше, чем М. Однако шифрование не обеспечивает сжатие информации.) К – ключ. Функция зашифрования Е, оперируя с М, создает С. Или в математической форме [5]:EkМ=С; DkC=M.При восстановлении исходного открытого текста справедливо следующее равенство:DkEkM=M.До появления компьютеров, криптография основывалась на текстовых алгоритмах. Различные криптографические алгоритмы выполняли или замену одних символов другими, или перестановку символов. Лучшие алгоритмы выполняли и ту, и другую операцию, причем многократно [6].В наше время все значительно усложнилось, однако философия остается прежней. Основное изменение заключается в том, что современные алгоритмы обрабатывают биты, а не символы. Это означает всего лишь изменение размера алфавита: вместо 26 элементов (в английском алфавите, где А – это 0 символ, В – 1 и т.д.) до двух. Однако и поныне большинство хороших криптографических алгоритмов все еще сочетают подстановки и перестановки [6]. В криптографии используются следующие основные алгоритмы шифрования [8]:Алгоритм замены (подстановки) – символы шифруемого текста заменяются символами того же или другого алфавита в соответствии с заранее обусловленной схемой замены. Получатель шифртекста выполняет обратную подстановку, восстанавливая открытый текст. Алгоритм перестановки – символы шифруемого текста переставляются по определенному правилу в пределах некоторого блока этого текста;Гаммирование – символы шифруемого текста складываются с символами некоторой случайной последовательности;Аналитическое преобразование – преобразование шифруемого текста по некоторому аналитическому правилу (формуле).Как уже упоминалось выше, процессы шифрования и расшифрования осуществляются в рамках некоторой криптосистемы. Для симметричной криптосистемы характерно применение одного и того же ключа как при шифровании, так и при расшифровании сообщений. В асимметричных криптосистемах для зашифрования данных используется один (общедоступный) ключ, а для расшифрования – другой (секретный) ключ [8].Симметричные криптосистемыРассмотрим традиционные (классические) методы симметричного шифрования, отличающиеся простотой и наглядностью.Шифры простой заменыСистема шифрования Цезаря - частный случай шифра простой замены. Метод основан на замене каждой буквы сообщения на другую букву того же алфавита, путем смещения от исходной буквы на K букв. Этот шифр может быть описан уравнением C=(M+K)mod26.Пример 1. Зашифруем фразу «Я люблю тебя, жизнь». Для этого распишем русский алфавит от А до Я и пронумеруем, начиная с нуля:абвгдеёжзийклмноп0123456789101112131415163334353637383940414243444546474849рстуфхцчшщъыьэюя1718192021222324252627282930313250515253545556575859606162636465В алфавите используется нумерация по второму кругу, так в некоторых случаях происходит возврат. Шифрование: для шифрования фразы (открытого текста) используется сдвиг по алфавиту на К символов вправо каждой буквы открытого текста. Возмем К=3. Запятая меняется на «зпт», точка на «тчк». Открытый текст шифруется без пробелов.Расшифрование: сдвиг по алфавиту влево на количество символов ключа (в нашем случае на К=3) каждой буквы шифртекста.Я ЛЮБЛЮ ТЕБЯ, ЖИЗНЬЯЛЮБЛЮТЕБЯЗПТЖИЗНЬялюблютебязптжизньвобдобхздвктхйлкряВ первой строке таблицы открытый текст, во второй строке полученный шифртекст.Шифр ВиженераВ XVI веке француз Блез де Виженер усложнил шифр Цезаря, предложив менять ключ к этому шифру с определенной периодичностью. Шифруя сообщение по этому методу, выбирают ключ, который рассматривают как блоковую последовательность букв, а сообщение разбивают на блоки длиной, соответствующей длине ключа. Затем при выполнении операций дискретного сложения по модулю для каждой буквы в каждом блоке исходного текста изменяют буквы-ключи в последовательности, соответствующей порядку расположения букв-ключей в блоке [6].Пример 2. Будем использовать слово ПИСЬМО, состоящее из 6 букв, как ключ. Алфавитным номерам букв соответствует блок чисел 14, 8, 16, 27, 11, 13. Чтобы зашифровать сообщение при помощи этого ключа, исходный текст разбивается на блоки длинной в 6 букв каждый. Затем к каждому числовому представлению первой буквы блока надо прибавить 14, к числовому представлению второй буквы – 8, третьей – 16, четвертой – 27, пятой – 11, шестой – 13. Получающиеся суммы по модулю представляют числовые значения шифртекста. Полибианский квадратГреческим писателем Полибием за 100 лет до н.э. был изобретен так называемый полибианский квадрат размером 5*5, заполненный алфавитом в случайном порядке. Греческий алфавит имеет 24 буквы, а 25-м символом является пробел. Для шифрования на квадрате находили букву текста и записывали в шифртекст букву, расположенную ниже ее в том же столбце. Если буква оказывалась в нижней строке таблицы, то брали верхнюю букву из того же столбца.Рассмотрим шифр «полибианский квадрат» для русского алфавита. Используем квадрат 6×6 (36=33 буквы русского алфавита + 3 знака препинания (точка, запятая, пробел)). Квадрат заполняется хаотично. Шифртекст образуется списыванием буквы, находящейся на строчку ниже (в этом же столбце) от шифруемой буквы (буквы открытого текста). Если шифруемая буква находится на самой нижней строчке, то берем самую верхнюю букву этого столбца. При дешифровании смотреть на букву, которая находится выше буквы шифртекста. Возможно использование различных модификаций этого метода: шифрование по диагонали в обе стороны, а также вправо и влево [6].Пример 3. Зашифруем сообщение методом полибианского квадрата: «Я люблю тебя жизнь» Ключ – полибианский квадрат следующего вида:аъвгдеёфзиклмуопрстнхцчшяжй.,_щбыьэю Итак, полученный шифртекст:ялюблютебяжизньщюсеъсеюялъщюбпожгШифры сложной заменыШифр ГронсфельдаШифр Гронсфельда – это шифр сложной замены. Он состоит в модификации шифра Цезаря числовым ключом. Для этого под буквами сообщения записывают цифры числового ключа. Если ключ короче сообщения, то его запись циклически повторяют. Шифртекст получают примерно также, как в шифре Цезаря, но отсчитывают не третью букву по алфавиту (как в шифре Цезаря), а ту, которая смещена по алфавиту на соответствующую цифру ключа. Пример 4. Пусть в качестве ключа используется группа из трех цифр – 314, тогда зашифруем сообщение:Сообщение СОВЕРШЕННО СЕКРЕТНОКлюч 3143143143143143143Шифртекст ФПИСЬИОССАХИЛФИУССШифр многоалфавитной заменыВ шифрах многоалфавитной замены для шифрования каждого символа исходного сообщения применяется свой шифр простой замены (свой алфавит). АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ_ААБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ_Б_АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯВЯ_АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮГЮЯ_АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЪЫЬЭ.…………ЯВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ_АБ_БВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ_АКаждая строка в этой таблице соответствует одному шифру замены аналогично шифру Цезаря для алфавита, дополненного пробелом. При шифровании сообщения его выписывают в строку, а под ним ключ. Если ключ оказался короче сообщения, то его циклически повторяют. Шифртекст получают, находя символ в колонке таблицы по букве текста и строке, соответствующей букве ключа. Пример 5. Например, используя ключ АГАВА, получаем:СообщениеПРИЕЗЖАЮ_ШЕСТОГОКлючАГАВААГАВААГАВААШифртекст ПНИГЗЖЮЮЮАЕОТМГОВ компьютере такая операция соответствует сложению кодов ASCII символов сообщения и ключа по модулю 256 [8].Шифры перестановкиМетод одиночной перестановкиСледующая иллюстрация показывает пример перестановочного шифрования с применением ключа (ВСТРЕЧА) – метод одиночной перестановки. Обратим внимание на следование букв ключа в алфавите и с помощью этих цифр пронумеруем столбцы, а открытый текст запишем как последовательность строк под ключом. Шифртекст образуется путем чтения по столбцам, начиная со столбца, номер которого наименьший в алфавите и т.д.Пример 6. Используем ту же фразуВСТРЕЧА2564371тишеедешьдальшебудешь(если остаются пустые клетки, заполните их буквой х)В результате считывания по столбцам в соответствии с их номерами получается шифртекст: «ешьтшеельеадиьбшдудьш» [8].Магический квадратМагическими квадратами называются квадратные таблицы с вписанными в их клетки последовательными натуральными числами, начиная с единицы, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число. Для шифрования необходимо вписать исходный текст по приведенной в квадрате нумерации и затем переписать содержимое таблицы по строкам. В результате получается шифртекст, сформированный благодаря перестановке букв исходного сообщения [8].Пример 7.163213оирт510118зшею96712-жас415141егопПРИЕЗЖАЮ-ШЕСТОГО12345678910111213141516Число магических квадратов очень резко возрастает с увеличением размера его сторон: для таблицы 3*3 таких квадратов -1; для таблицы 4*4 - 880; а для таблицы 5*5 - 250 000 [8].Метод двойных перестановокДля реализации этого метода необходимы два цифровых ключа:Первым ключом будут являться номера столбцов таблицы, с помощью которой будет зашифровано сообщение (возьмем например, 3,4,2,5,1)Вторым ключом будут являться номера строк таблицы (возьмем например, 4,2,3,1)Ключ берется произвольно. Большее число ключа определяет размер таблицы (количество строк и столбцов в ней). Ключи берутся в зависимости от размера сообщения , которое необходимо зашифровать.Пример 8. Зашифруем сообщение. В нашем случае таблица будет состоять из 5 столбцов и 4 строк. Следующим шагом берем открытый текст (сообщение): НА УЛИЦЕ ПАСМУРНО. Записываем сообщение в таблицу. Текст сообщения вносится в таблицу с пробелами:342514на_ул2ице_п3асмур1но___Зашифруем исходное сообщение. Для этого, сначала переставим в порядке возрастания столбцы. Получим следующее:123454Л_НАУ2ПЕИЦ_3РМАСУ1__НО_Теперь переставим в порядке возрастания строки. Получим:123451__НО_2ПЕИЦ_3РМАСУ4Л_НаУПолученный шифртекст записываем в строку (списываем поочередно строки таблицы):_ _НО_ПЕИЦ_РМАСУЛ_НАУ Дешифрование производим в обратном порядке, то есть сначала переставляются строки в порядке следования цифр ключа, а затем столбцы.Шифр Кардано К шифрам перестановки относится и Шифр Кардано. В середине 16 века итальянским математиком Кардано была выдвинута идея использования части самого передаваемого открытого текста в качестве ключа и новый способ шифрования, получивший название «решетка Кардано». Для ее изготовления берется квадратный кусок картона в котором по специальным правилам прорезаются «окна». При шифровании решетка накладывалась на лист бумаги и открытый текст вписывался в окна.