Классификация криптографических алгоритмов шифрования

РКЛ по дисциплине «Информационная безопасность»

Раздел 2. Организация и технология обеспечения информационной безопасности

Часть 2

 

Основы криптографии

Основные понятия и определения

Как и любая наука, криптография опирается на базовые понятия и определения. Рассмотрим основные из них.

Криптография  (от др.-греч. κρυπτός (криптос) – тайный, скрытый  и γράφω (графо) – пишу) – наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним), целостности данных (невозможности незаметного изменения информации) и аутентификации (проверки подлинности авторства или иных свойств объекта), а также невозможности отказа от авторства.

Изначально криптография изучала методы шифрования информации – обратимого преобразования открытого (исходного) текста на основе секретного алгоритма и/или ключа в шифрованный текст (шифротекст). Традиционная криптография образует раздел симметричных криптосистем, в которых шифрование и расшифровывание проводится с использованием одного и того же секретного ключа. Помимо этого раздела современная криптография включает в себя асимметричные криптосистемы, использующие два ключа, системы электронной подписи (ЭП), хеш-функции, управление ключами, получение скрытой информации, квантовую криптографию.

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

Шифр (от арабского sifr «ноль», откуда французское chiffre «цифра»; родственно слову «цифра») – это совокупность условных знаков (условная азбука из цифр или букв) для секретной переписки, для передачи текста секретных документов, в том числе  по техническим средствам связи. В общем случае понятие шифр идентично понятию криптосистема и означает семейство обратимых преобразований открытого текста в шифрованный. Шифр состоит, по меньшей мере, из четырех элементов:

· открытый текст X;

· функция шифрования f(X);

· ключ К;

· закрытый текст Y.

Открытый (исходный) текст – данные (текстовые или иного вида), представляемые и/или передаваемые без использования криптографии.

Шифротекст, шифрованный (закрытый) текст – данные, полученные после применения криптосистемы (обычно с некоторым указанным ключом).

Код – это алгоритм криптографических преобразований (шифрования) множества возможных открытых данных во множество возможных зашифрованных данных, и обратных им преобразований.

Ключ – это параметр криптографического алгоритма, обеспечивающий выбор одного преобразования из совокупности преобразований, возможных для этого алгоритма. В современной криптографии предполагается, что вся секретность криптографического алгоритма сосредоточена в ключе, но не деталях самого алгоритма (принцип Керкгоффса).

Шифры могут использовать один ключ для шифрования и дешифрования или два различных ключа. По этому признаку различают симметричный и асимметричный шифры.

Симметричный шифр – это шифр, который использует один ключ для шифрования и расшифровывания.

Асимметричный (несимметричный) шифр – это шифр, который для шифрования и расшифровывания использует два различных ключа, определенным образом связанных между собой.

Шифрование – процесс нормального применения криптографического преобразования открытого текста на основе алгоритма и ключа, в результате которого возникает шифрованный текст.

Расшифровывание(расшифровка) – процесс нормального применения криптографического преобразования шифрованного текста в открытый (то есть, на основе известного алгоритма и ключа).

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

Криптоаналитик – человек, создающий и применяющий методы криптоанализа.

Криптография и криптоанализ составляюткриптологию как единую науку о создании и взломе шифров (такое деление привнесено с Запада, ранее в СССР и России не применялось специального деления).

Дешифрование (дешифровка) – процесс извлечения открытого текста без знания криптографического ключа на основе известного шифрованного текста. Термин «дешифрование» обычно применяют по отношению к процессу криптоанализа шифротекста. В некоторых источниках понятия дешифрования и расшифровывания объединяют вместе под термином дешифрование.

Криптографическая стойкость – способность криптографического алгоритма противостоять криптоанализу, то есть к дешифрованию без знания ключа.

Алфавит – конечное множество используемых для кодирования информации знаков. В качестве примеров алфавитов можно привести следующие:

- алфавит Z₃₃ - 32 буквы русского алфавита и пробел;

- алфавит Z₂₇ - 26 букв латинского алфавита и пробел;

- алфавит Z₂₅₆ - символы, входящие в стандартные коды ASCII и КОИ-8;

- бинарный алфавит – Z₂ = {0,1};

- восьмеричный или шестнадцатеричный алфавит.

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

 

Немного истории

 

История криптографии насчитывает около 4 тысяч лет. В качестве основного критерия периодизации криптографии можно использовать технологические характеристики используемых методов шифрования. В связи с этим историю криптографии можно условно разделить на четыре периода.

Первый период (приблизительно с 3-го тысячелетия до н.э. до IX в. на Ближнем Востоке и до XV в. в Европе) характеризуется господством моноалфавитных шифров (основной принцип – замена алфавита исходного текста другим алфавитом через замену букв другими буквами или символами). Хорошо известен, в частности, моноалфавитный шифр, вошедший в историю как Шифр Цезаря, получивший свое развитие в более поздние времена. В шифре Цезаря каждая буква алфавита циклически сдвигается на определенное число позиций. Величину сдвига можно рассматривать как ключ шифрования. Сам Цезарь использовал сдвиг на три позиции. Буквы исходного алфавита заменялись затем на буквы «сдвинутого» алфавита.

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

 

 

 

Рис. 2.15. Внешний вид сциталы

 

С именем полководца Энея Тактика (IVв. до н.э.) связывают несколько техник шифрования и тайнописи. Диск Энея представлял собой диск диаметром 10 – 15 см с отверстиями по числу букв алфавита. Для записи сообщения нитка протягивалась через отверстия в диске, соответствующие буквам сообщения. При чтении получатель вытягивал нитку и получал буквы, правда, в обратном порядке. Хотя недоброжелатель мог прочитать сообщение, если перехватит диск, Эней предусмотрел способ быстрого уничтожения сообщения – для этого было достаточно выдернуть нить, закрепленную на катушке в центре диска.

Первым действительно криптографическим инструментом можно назвать линейку Энея, реализующую шифр замены. Вместо диска использовалась линейка с отверстиями по числу букв алфавита, катушкой и прорезью. Для шифрования нить протягивалась через прорезь и отверстие, после чего на нити завязывался очередной узел. Для расшифровывания необходимо было иметь саму нить и линейку с аналогичным расположением отверстий. Таким образом, даже зная алгоритм шифрования, но, не имея ключа (линейки), прочитать сообщение было невозможно.

Второй период (хронологические рамки – с IX в. на Ближнем Востоке и с XV в. в Европе – до начала XX в.) ознаменовался введением в обиход полиалфавитных шифров. Назовем наиболее известных криптологов, с именем которых связана разработка новых шифров. Отцом западной криптографии называют ученого эпохи Возрождения Леона Баттиста Альберти. Изучив методы вскрытия использовавшихся в Европе моноалфавитных шифров, он попытался создать шифр, который был бы устойчив к частотному криптоанализу. Трактат о новом шифре был представлен им в папскую канцелярию в 1466 г. Альберти предложил вместо единственного секретного алфавита, как в моноалфавитных шифрах, использовать два или более, переключаясь между ними по какому-либо правилу. Однако флорентийский ученый так и не смог оформить свое открытие в полную работающую систему, что было сделано уже его последователями.

Очередной известный результат принадлежит перу германского аббата Иоганна Тритемия (по некоторым источникам Иоганн Трисемус), которого многие историки считают вторым отцом современной криптологии. В пятой книге серии Polygraphia, изданной в 1518 г., он описал шифр, в котором каждая следующая буква шифруется своим собственным шифром сдвига. Однако самым известным криптографом XVI в. можно назвать Блеза де Виженера (фр. Blaise de Vigenere). В своем трактате 1585 г. он описал шифр, подобный шифру Тритемия, однако изменил систему выбора конкретного шифра замены для каждой буквы. Одной из предложенных техник было использование букв другого открытого текста для выбора ключа каждой буквы исходного текста.

Описанный шифр известен как шифр Виженера и при длине случайного ключа, равной длине открытого текста, является абсолютно стойким шифром, что было математически доказано много позже (в XX в. в работах К.Э. Шеннона). Другая техника использовала результат шифрования для выбора следующего ключа – то, что впоследствии использует Фейстель и компания IBM при разработке шифра DES в 1970-х гг.

Для рассматриваемого периода характерно развитие криптологической деятельности под эгидой государства. В России датой учреждения первой государственной шифровальной службы можно считать 1549 г. – образование «посольского приказа» с «циферным отделением». А как минимум с 1702 г. Петра I сопровождала походная посольская канцелярия под руководством первого министра Ф.А. Головина, которая с 1710 г. приобрела статус постоянного учреждения. В нем сосредоточилась криптографическая работа, связанная  с перепиской между Петром, его приближенными и различными получателями, а также по созданию новых шифров. К началу XVIII в. подобные шифровальные кабинеты были по всей Европе, в том числе Die Geheime Kabinettskanzlei в Вене, первое дешифровальное отделение в Германии под начальством графа Гронсфельда, группа Джона Валлиса в Англии и т.д.

Получила развития работа по механизации процесса шифрования-расшифровывания.

В 1790-х гг. будущий президент США Томас Джефферсон построил одну из первых механических роторных машин, упрощавшую использование полиалфавитных шифров. Среди других авторов-изобретателей стоит отметить полковника Десиуса Вадсворта, изобре­тателя машины с вращательными шифровальными дисками с различным количеством букв. Хотя он изобрел ее в 1817 г., вся слава досталась Чарлзу Уитстону за аналогичную машину, представленную на Всемирной выставке 1867 г. в Париже. Однако распространение роторные машины получили лишь в начале XX в.

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

Третий период (с начала XX в. и до конца 70-х гг. XX в.) характеризуется внедрением электромеханических устройств в работу шифровальщиков. При этом продолжалось использование полиалфавитных шифров. В начале этого периода правительства разных стран вновь бросили значительные силы на шифрование и криптоанализ. В 1914 г. Британия открыла «Комнату 40», в 1917 г. США – MI-8, ставшую предшественницей совре­менного АНБ.

Во время Первой мировой войны криптография и, в особенности, криптоанализ становится одним из инструментов ведения войны. Известны факты расшифровки русских сообщений австрийцами, русскими же был расшифровыван немецкий шифр (благодаря найденной водолазами копии кодовой книги), после чего результаты были переданы союзникам. Для перехвата радиосообщений были построены специальные подслушивающие станции, в результате работы которых (вместе с умением дешифровать немецкий шифр, использовавшийся в том числе турками) русский флот был осведомлен о составе и действиях противника. В британском адмиралтействе «Комнатой 40» за время войны расшифровало около 15 тысяч сообщений. Этот результат сыграл важную роль в сражении при Доггер-банке и в Ютландском сражении.

Что касается применения для шифрования электромеханических устройств, то здесь можно назвать электрическую роторную шифровальную машину «Энигма», используемую в Германией в период 1920 – 1940 гг., главным образом, в военных целях (см. рис. 2.16), и  американскую машину М-209 на дисках. В СССР производились оба типа машин.

 

 

Рис. 2.16. Внешний вид шифровальной машины «Энигма»

 

Германские военные постоянно совершенствовали «Энигму». Без учета настройки положения колец (нем. Ringstellung) количество различных ключей составляло 10¹⁶. В конце 1920-х – начале 1930-х гг. британские разведчики считали шифр «Энигмы» невзламываемым. Только усилиями польских математиков-энтузиастов, сотрудничавших с британской разведкой, а также на основе анализа множества перехваченных сообщений, кодовых книг, донесений разведки, результатов усилий военных и даже террористических атак удалось «вскрыть» шифр «Энигмы».

Однако  с 1940 г. высшее германское командование начало использовать новый метод шифрования, названный британцами Fish. Для шифрования использовалось новое устройство Lorenz SZ 40, разработанное по заказу военных (см. рис. 2.17).

 

 

Рис. 2.17. Внешний вид шифровальной машины Lorenz SZ 40

 

Шифрование основывалось на принципе одноразового блокнота (шифр Вернама, одна из модификаций шифра Виженера, описанная в 1917 г.) и при правильном использовании гарантировало абсолютную криптостойкость (что было доказано позже в работах Шеннона). Однако для работы шифра требовался «надежный» генератор случайной последовательности, который бы синхронизировался на передающей и принимающей стороне. Если криптоаналитик сумеет предсказать следующее число, выдаваемое генератором, он сможет расшифровать текст. Дешифровать сообщения Lorenz SZ 40 американцам удалось в 1943 г. на основе использования одной из первых программируемых вычислительных машин Colossus, созданной Максом Ньюменом и Томми Флауэрсом при участии Алана Тьюринга. Colossus осуществил криптоанализ на основе переборавсех возможные вариантов исходного сообщения.

Четвертый период (с конца 70-х гг. XX в. по настоящее время) характеризуется переходом к математической криптографии. В работе К.Э. Шеннона появляются строгие математические определения количества информации, передачи данных, энтропии, функ­ций шифрования. Обязательным этапом создания шифра считается изучение его уязвимости к различным известным атакам – линейному и дифференциальному криптоанализу. Однако до 1975 г. криптография оставалась «классической», или же, более корректно, криптографией с секретным ключом.

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

Современная криптография образует отдельное научное направление на стыке математики, информатики, физики – работы в этой области публикуются в научных журналах, организуются регулярные конференции. Практическое применение криптографии стало неотъемлемой частью жизни современного общества – ее используют в таких отраслях, как электронная коммерция, электронный документооборот (включая электронные подписи), телекоммуникации и др. Кроме очевидных применений – собственно, для передачи информации, она используется в сотовой связи, платном цифровом телевидении при подключении к Wi-Fi и на транспорте для защиты билетов от подделок, и в банковских операциях, и даже для защиты электронной почты от спама.

Технологической основой современной криптографии и криптоанализа является программно-аппаратный комплекс информационно-технологической инфраструктуры.

Еще одна особенность современного периода – открытое формирование государственных стандартов на криптографические протоколы и криптографические алгоритмы.

 

Классификация криптографических алгоритмов шифрования

 

Криптографические алгоритмы шифрования информации подразделяются на следующие группы: симметричные, несимметричные и гибридные. Кроме того, алгоритмы подразделяются по типу преобразования и по способу обработки информации (рис. 2.18).

В симметричных криптографических алгоритмах шифрование и расшифровывание производятся с помощью одного и того же ключа. И соответственно этот ключ необходимо хранить в секрете (отсюда другое название симметричных криптоалгоритмов – криптоалгоритмы с секретным ключом).

В несимметричных криптографических алгоритмах существуют два разных ключа – один используется для шифрования, который еще называют открытым, другой – для расшифровывания, который называют закрытым [1]. Главное отличие асимметричных криптоалгоритмов заключается в том, что даже тот, кто с помощью открытого ключа зашифровал сообщение, не сможет его самостоятельно расшифровать без знания закрытого ключа. Поэтому эти криптоалгоритмы называются несимметричными (асимметричными), или алгоритмами с открытым ключом.

 

 

Рис. 2.18. Классификация криптографических алгоритмов шифрования

 

Если криптоалгоритм использует индивидуальное сообщение и индивидуальный открытый ключ, то он называется криптоалгоритмом с одним открытым ключом.

Если криптоалгоритм использует одно сообщение и п ключей (в схеме с п агентами), то он называется криптоалгоритмом с несколькими открытыми ключами.

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

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

По типу шифрующего преобразования криптосистемы делятся на:

- шифры замены (подстановки);

- шифры перестановок;

- шифры гаммирования;

- шифры, основанные на аналитических преобразованиях шифруемых данных;

- композиционные шифры.

Шифрование заменой (подстановкой) заключается в том, что символы шифруемого текста заменяются символами того же или другого естественного алфавита в соответствии с заранее обусловленной схемой замены. Этот тезис можно сформулировать по-другому: символы шифруемого текста на естественном языке заменяются символами специального алфавита для записи шифротекста, сконструированного на базе естественного языка по заранее обусловленному правилу.

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

По сути дела, шифры перестановки и замены являются кирпичиками, из которых строятся различные более стойкие шифры.

Шифрование гаммированием заключается в том, что символы шифруемого текста складываются с символами некоторой случайной последовательности, именуемой гаммой шифра. Стойкость шифрования определяется в основном длиной (периодом) неповторяющейся части гаммы шифра. Поскольку с помощью ЭВМ можно генерировать практически бесконечную гамму шифра, то данный способ является одним из основных для шифрования информации в автоматизированных системах.

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

Идея, лежащая в основе составных, или композиционных, шифров, состоит в построении криптостойкой системы путем многократного применения относительно простых криптографических преобразований, в качестве которых К. Шеннон предложил использовать преобразования подстановки (substitution) и транспозиции (permutation) [2]. Многократное использование этих преобразований позволяет обеспечить два свойства, которые должны быть присущи стойким шифрам: рассеивание (diffusion) и перемешивание (confusion).

Рассеивание предполагает распространение влияния одного знака открытого текста, а также одного знака ключа на значительное количество знаков шифротекста.

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

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

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

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