Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)

БАБАШ А. В., ШАНКИН Г. П.

Серия книг “ Аспекты защиты

КРИПТОГРАФИЯ

Под редакцией В.П. Шерстюка, Э.А. Применко

Москва СОЛОН-ПРЕСС

2007

УДК 003.26 ББК 87.4 Б121

Бабаш А.В., Шанкин Г.П.

Б121 Криптография. Под редакцией В.П. Шерстюка, ЭЛ. Применко / А.В. Бабаш, Г.П. Шанкин. — М.: СОЛОН-ПРЕСС, 2007. — 512 с. — (Серия книг «Аспекты защиты»).

15ВЫ 5-93455-135-3

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

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

УДК 003.26 ББК 87.4

По вопросам приобретения обращаться: .ООО «АЛЬЯНС-КНИГА КТК» Тел: [phone], АУ\пу.аЬоок.ги

Сайт издательства «СОЛОН-ПРЕСС»: м^у.8о1оп-рге88.ги Е-таИ: $о1оп-ау1ог@соЪа.ги

к н и г а - почтой

Книги издательства «СОЛОН-ПРЕСС» можно заказать наложенным платежом (оплата при получении) по фиксированной цене. Заказ оформляется одним из двух способов:

1.Послать открытку или письмо по адресу: 123242, Москва, а/я 20.

2.Оформить заказ можно на сайте №Уж.$о1оп-рге$$.ги в разделе «Книга — почтой».

Бесплатно высылается каталог издательства по почте.

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

Через Интернет вы можете в любое время получить свежий каталог издательства «СОЛОН-ПРЕСС», считав его с адреса №оту.§о1оп-рге$8.ги/ка(.<1ос.

Интернет-магазин размещен на сайте чгюту.§о1оп-рге$$.ги.

18В1Ч 5-93455-135-3	©	А.В. Бабаш, Г.П. Шанкин, 2007
	©	Составление. Осипенко А.И., 2002
	©	Макет и обложка «СОЛОН-ПРЕСС», 2007

4

Предисловие редакторов

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

Во введении авторами указана степень математической подготовленности чи­ тателя, необходимая для усвоения излагаемого в книге материала.

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

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

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

Вцелом представляется, что книга, несомненно, может быть использована

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

Член-корр. АК РФ В.П. Шерстюк, кандидат физ.-мат. наук, доцент Э.А. Применко

I

5

Предисловие авторов

Предлагаемое учебное пособие в первую очередь предназначено для студентов, изучающих дисциплины по защите информации по про­ граммам, утвержденным учебно-методическим объединением вузов России (УМО):

1)по специальности 075500 - «Комплексное обеспечение информаци­ онной безопасности», квалификация - специалист по защите информа­ ции, ОПД.Ф. 13 - Криптографические методы защиты информации;

2)по специальности 075200 - «Компьютерная безопасность», квалифи­ кация - математик, ОПД.Ф. 13 - Криптографические методы защиты информации;

3)по специальности 075600 - «Информационная безопасность теле­ коммуникационных систем», квалификация - специалист по защите информации, ОПД.Ф. 03 - Криптографические методы защиты инфор­ мации;

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

Архитектура пособия двухуровневая. Первый уровень предна­ значен для читателей, впервые знакомящихся с учебными материалами по криптографии. Второй уровень - для людей, знакомых с азами крип­ тографии. Собственно линия раздела материала достаточно условна, в первую очередь она зависит от математической подготовки читателя. Материал, излагающийся в начальных главах и в начальных цараграфах этих глав, относится к первому уровню познания классической криптографии. Остальной материал относится ко второму уровню, в частности, параграфы 5.5, 6.7, 6.9, 7.4, 7.5 предназначены для адъюнк­ тов и аспирантов. Необходимым условием освоения пособия является знакомство читателя с двухсеместровым курсом теории вероятностей и статистики. Авторы сознательно пошли на отчасти автономное изло­ жение материалов глав. Их связывающим началом являются началь­ ные параграфы глав 1, 2, 3, содержащие основные понятия криптогра­ фии, свойства шифров и открытых текстов.

Внастоящее время развитие криптографии, и, в частности, ее практические проблемы во многом определяют общее развитие мате-

6

матики. Этот тезис, исповедуемый авторами, определил и методологи­ ческий подход к форме подачи материалов пособия. Как правило, каж­ дая из обсуждаемых криптографических задач затем формализуется и решается средствами математики. Кроме того, это положение отражено и содержанием параграфов 5.5, 6.7, 6.9, 7.4, 7.5, где в явном виде пока­ зано значение результатов математических исследований в крипто­ графии, и влияние криптографии на направления развития математики. Собственно, эти параграфы отчасти являются введением в теоретиче­ скую криптографию.

Большое значение мы придаем обучению студентов методикам численного расчета параметров методов анализа и синтеза шифров. При таком расчете, как правило, акцент делается на предварительный математический расчет (расчет параметров «на уровне средних значе­ ний»). Такой подход особенно заметен в параграфе 2.2, где в разнооб­ разных вероятностных моделях подсчитывается среднее значение ис­ торически известного параметра текста - «индекса совпадения Фрид­ мана».

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

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

Благодарим:

вице-президента Академии криптографии Российской Федерации Сачкова В.Н. (материалы к главе 6); доктора физико-математических наук, профессора, Академика АК Рос­ сии Балакина Г.В (материалы к главе 5);

доктора физико-математических наук, профессора, Академика АК Рос­ сии Нечаева А.А (материалы к главе 6); доктора физико-математических наук, профессора, Академика АК Рос­ сии Глухова М.М (материалы к главе 6);

7

профессора кафедры криптографии ИКСИ, доктора физикоматематических наук Проскурина Г.В. (материалы к главам 1, 2, 3); доктора физико-математических наук, профессора по кафедре крипто­ графия Рязанова Б.А. (материалы к главе 5); доктора физико-математических наук, старшего научного сотрудника Малышева Ф. М (материалы к главе 5);

кандидата физико-математических наук, старшего научного сотрудника Фомичева В. М. (материалы к главе 2); кандидата физико-математических наук Максимова К.Н. (материалы к главе 2); Тришина А.Е. (материалы к главе 1).

Основой книги служат открытые публикации. Некоторые из них использованы почти дословно. Такие параграфы помечены ссылками на использованную литературу. В этом отношении обилием ссылок вы­ деляется пособие Г.В. Проскурина “Принципы и методы защиты инфо­ рмации”, Московский государственный институт электроники и мате­ матики. Выражаем сожаление о том, что нам не удалось использовать материалы прекрасного учебного пособия “Основы криптографии” ве­ дущих специалистов в области криптографии: Алферова А.П., Зубова А.Ю., Кузьмина А.С., Черемушкина А.В.

Настоящее пособие посвящается памяти замечательных крипто­ графов - математиков Степанова Вадима Евдокимовича и Горчинского Юрия Николаевича. Многие их криптографические идеи и решения сейчас можно встретить рожденными заново в ряде пособий, моногра­ фий и научных статей по криптографии. Ряд таких идей лежат в основе и данной книги. С некоторыми работами упомянутых специалистов можно ознакомиться: Степанов В.Е. - журнал «Теория вероятностей и ее применения: 1957, т.2, N1; 1970, т.15, N2; 1972, т.17, N2; 1987, т.32, N4; Горчийский Ю.Н. - Труды по дискретной математике тома 1 (1997), 2 (1998), 3 (2000), далее, предположительно, в томах 4, 5.

Авторы с благодарностью примут все предложения и замечания по книге; их следует направлять по адресу: ЬаЬазН@уапс1ех.ги.

Горчинский Юрий Николаевич (1929-1999)

Горчинский Юрий Николаевич (1929-1999) родился в Хмельницкой области Украины. Полковник в отставке. В 1951 году закончил физикоматематический факультет Московского Государственного университета им. М.В. Ломоносова. В 1956 году окончил аспирантуру НТС 8-го Главного управления КГБ при СМ СССР. Доктор физико-математических наук. Про­ фессор. С 1951 по 1953 год сотрудник, старший сотрудник 2-го Управления Главного управления Специальной службы при ЦК ВКП(б). С 1953 по 1961 год помощник руководителя группы, старший сотрудник 1 категории, руко­ водитель группы отдела 8-го Главного управления при СМ СССР. С 1961 по 1978 год начальник отделения, научный консультант отдела Спецуправления 8-го Главного управления КГБ СССР. С 1978 по 1993 год научный консуль­ тант Спецуправления 8-го Главного управления КГБ СССР. В сентябре 1993 года уволен на пенсию по возрасту. С 1993 академик — секретарь отделения математических проблем криптографии Академии Криптографии РФ. Внес большой вклад в подготовку научных и инженерных кадров. Награжден орде­ нами «Красная звезла» и «Знак.Почета» и многими медалями. Лауреат госу­ дарственной премии за 1975 год. Награжден знаком «Почетный сотрудник госбезопасности».

1

9

•Г***!*

Степанов Вадим Евдокимович (1929 - 1986)

Степанов Вадим Евдокимович (1929-1986) родился в городе Днепропетров­ ске. В 1951 году окончил МГУ им. М.В.Ломоносова. В 1956 году окончил ас­ пирантуру 8-го Главного управления. Доктор физико-математических наук. Профессор. С 1951 по 1953 год работал лаборантом, младшим научным со­ трудником НИИ-1 ГУСС, с 1953 по 1959 год руководитель группы, замести­ тель начальника отделения, с 1959 по 1966 год старший научный сотрудник 8- го Главного Управления КГБ. С 1966 по 1976 год научный консультант Управления, а с 1976 по 1986 год начальник отдела. Внес большой вклад в подготовку научных и инженерных кадров для Специальной службы. Награ­ жден орденом «Красная Звезда» и многими медалями, в .том числе медалью «За боевые заслуги», Почетной грамотой Верховного Совета РСФСР, знаком «Почетный сотрудник госбезопасности». Лауреат Государственной премии

СССР посмертно. Полковник.

10

Основные обозначения

€ - принадлежит; V - для любого;

3 - существует; => - тогда;

<=> - тогда и только тогда; |К| - как правило, мощность множества К. В исключительных случаях,

абсолютная величина числа К; (а,Ъ) - как правило, общий наибольший делитель чисел а, Ь. Иногда

вектор с компонентами а, Ь, иногда семейство элементов (а,Ъ,...с); [а,Ъ] - как правило, наименьшее общее кратное чисел а, Ь. Иногда ин­ тервал изменения переменной величины, иногда [ ] - квадратные скобки, иногда целая часть числа; а|Ь - а делит Ь;

I* - как правило, множество всех слов в алфавите I. В ряде случаев * используется и в качестве индекса;

1Ь - множество всех слов в алфавите I длины Ь; Рг, ОР(2) - Поле из двух элементов; 0(Р(ц)) - поле из ц элементов;

ХхК - прямое произведение множеств X и К; Р: X—>У - отображение, функция;

{а,Ъ,...,с} - множество;