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

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

2-е издание, исправленное

Басалова Г.В.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Основы криптографии/ Г.В. Басалова - М.: Национальный Открытый Университет “ИНТУИТ”, 2016

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

(c) ООО “ИНТУИТ.РУ”, 2011-2016
(c) Басалова Г.В., 2011-2016

3

Введение

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

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

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

Необходимо отметить, что материал, изучаемый в рамках курса “Основы
криптографии” предполагает наличие у студентов знаний по некоторым разделам
таких дисциплин, как “Математика”, “Информатика”, “Теория информации”,
“Математическая логика и теория алгоритмов”.

4

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

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

Цель лекции: познакомить студента с основными понятиями криптографии.

Предмет и задачи криптографии

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

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

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

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

5

применения определенной технологии проявления.

В условиях повсеместного использования информационных технологий возникают
новые стеганографические приемы. Например, известен способ, при котором секретное
сообщение прячется в файле графического изображения. При использовании этого
способа младший значащий бит в описании каждого пикселя изображения заменяется
битом сообщения. Разделив все исходное сообщение на биты и разместив эти биты по
всему графическому файлу, мы пересылаем изображение с замаскированным
сообщением получателю. Графическое изображение при этом меняется не слишком
сильно, особенно если использовался режим с большим количеством цветов, например,
с глубиной цвета 24 бита на пиксел. Это связано с тем, что человеческий глаз не может
различать такое большое количество цветов. В результате в картинке размером всего
32 на 32 точки можно вместить тайное сообщение длиной 1024 бита или 128 байт.

Третий способ защиты информации – наиболее надежный и распространенный в наши
дни – криптографический . Этот метод защиты информации предполагает
преобразование информации для сокрытия ее смысла от противника. Криптография в
переводе с греческого означает “тайнопись”. В настоящее время криптография
занимается поиском и исследованием математических методов преобразования
информации.

Наряду с криптографией развивается и совершенствуется криптоанализ – наука о
преодолении криптографической защиты информации. Криптоаналитики исследуют
возможности расшифровывания информации без знания ключей. Успешно
проведенный криптоанализ позволяет получить ключ шифрования, или открытый
текст, или то и другое вместе. Иногда криптографию и криптоанализ объединяют в
одну науку – криптологию (kryptos - тайный, logos - наука), занимающуюся вопросами
обратимого преобразования информации с целью защиты от несанкционированного
доступа, оценкой надежности систем шифрования и анализом стойкости шифров.

В настоящее время криптография прочно вошла в нашу жизнь. Перечислим лишь
некоторые сферы применения криптографии в современном информатизированном
обществе:

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

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

6

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

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

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

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

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

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

Шифр – совокупность заранее оговоренных способов преобразования исходного
секретного сообщения с целью его защиты.

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

Символ - это любой знак, в том числе буква, цифра или знак препинания.

Алфавит - конечное множество используемых для кодирования информации символов.
Например, русский алфавит содержит 33 буквы от А до Я . Однако этих тридцати трех
знаков обычно бывает недостаточно для записи сообщений, поэтому их дополняют
символом пробела, точкой, запятой и другими знаками. Алфавит арабских цифр – это
символы 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 . Этот алфавит содержит 10 знаков и с его
помощью можно записать любое натуральное число. Любое сообщение может быть
записано также с помощью двоичного алфавита , то есть с использованием только
нулей и единиц.

7

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

Преобразование открытого текста в криптограмму называется зашифрованием.
Обратное действие называется расшифрованием. В англоязычной литературе терминам
“зашифрование/ расшифрование” соответствуют термины “enciphering/deciphering”.

Ключ – информация, необходимая для шифрования и расшифрования сообщений.

С точки зрения русского языка термины “расшифрование” и “дешифрование” являются
синонимами. Однако в работах по криптографии последних десятилетий часто эти
слова различают. Будем считать, что термины “расшифрование” и “дешифрование” не
являются синонимами. Примем, что расшифрованием занимается легальный
получатель сообщения (тот, кто знает ключ), а человек, которому послание не
предназначено, пытаясь понять его смысл, занимается дешифрованием .

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

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

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

Все методы преобразования информации с целью защиты от несанкционированного
доступа делятся на две большие группы: методы шифрования с закрытым ключом и
методы шифрования с открытым ключом . Шифрование с закрытым ключом
(шифрование с секретным ключом или симметричное шифрование) используется
человеком уже довольно долгое время. Для шифрования и расшифрования данных в
этих методах используется один и тот же ключ, который обе стороны стараются
хранить в секрете от противника. Системы шифрования с закрытым ключом подробно
рассматриваются в лекциях 2-9. Шифрование с открытым ключом (асимметричное
шифрование) стало использоваться для криптографического закрытия информации
лишь во второй половине ХХ века. В эту группу относятся методы шифрования, в
которых для шифрования и расшифрования данных используются два разных ключа.
При этом один из ключей (открытый ключ) может передаваться по открытому
(незащищенному) каналу связи. Алгоритмам преобразования информации с открытым
ключом посвящены лекции 10-14 учебного пособия.

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

8

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

Требования к криптографическим системам защиты информации

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

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

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

Реализация криптографических методов

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

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

9

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

В настоящее время выпускаются и комбинированные модули шифрования, так
называемые программно-аппаратные средства. В этом случае компьютер дополняется
своеобразным “криптографическим сопроцессором” – аппаратным вычислительным
блоком, ориентированным на выполнение специфических криптографических
операций. Меняя программное обеспечение для такого устройства, можно выбирать
тот или иной метод шифрования. Такое программно-аппаратное средство объединяет в
себе достоинства программных и аппаратных методов.

Сведения из истории криптографии

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

Древние греки оставили документальные подтверждения о различных применяемых
ими шифровальных системах. Греками, а вернее спартанцами, во время
многочисленных войн применялось одно из первых шифровальных устройств –
Сцитала. Сцитала представляла собой цилиндрический жезл определенного диаметра.
На Сциталу виток к витку наматывалась узкая полоска папируса (или кожаного ремня).
На намотанной ленте вдоль оси жезла писали открытое сообщение. Затем ленту
разматывали и переправляли адресату. После снятия папируса с жезла выходило как
будто буквы сообщения написаны в беспорядке поперек ленты. Если папирус попадал
в руки противника, то секретное сообщение прочитать было невозможно. Для
получения исходного текста была необходима Сцитала точно такого же диаметра – на
нее наматывалась полученная полоска папируса, строки сообщения совмещались, и в
результате можно было прочитать секретное послание. Ключом в данном методе
шифрования являлся диаметр Сциталы. Интересно, что изобретение дешифровального
“устройства” приписывается Аристотелю. Предполагается, что именно он предложил
использовать конусообразное “копье”, на которое наматывалась перехваченная лента с
зашифрованным сообщением. Лента с буквами передвигалась вдоль оси конуса до тех
пор, пока не появлялся осмысленный текст.

В Древней Греции использовались и другие шифры. Так, например, там был изобретен
шифр, который в дальнейшем стал называться “квадратом Полибия”. Согласно этому

10