Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Введение в криптографию

Покупка
Артикул: 682433.01.99
В книге впервые на русском языке дается систематическое изложение научных основ криптографии от простейших примеров и основных понятий до современных криптографических конструкций. Понимание принципов крип- тографии стало для многих потребностью в связи с широким распространени- ем криптографических средств обеспечения информационной безопасности, поэтому книга может быть полезна массовому читателю. В книгу включены задачи олимпиад по криптографии для школьников. Книга рассчитана на школьников, студентов-математиков и специали- стов по информационной безопасности.
Ященко, В. В. Введение в криптографию: Учебное пособие / Ященко В.В., - 4-е изд. - Москва :МЦНМО, 2014. - 352 с.: ISBN 978-5-4439-2162-4. - Текст : электронный. - URL: https://znanium.com/catalog/product/958585 (дата обращения: 29.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
Введение в криптографию

Под редакцией В. В. Ященко

Электронное издание

Москва
Издательство МЦНМО
2014

УДК 003.26
ББК 32.973-18.2
В24

Введение в криптографию
Под общ. ред. В. В. Ященко
Электронное издание
М.: МЦНМО, 2014
347 с.
ISBN 978-5-4439-2162-4

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

Подготовлено на основе книги: Введение в криптографию / Под общ.
ред. В. В. Ященко. — 4-е изд., доп. М.: МЦНМО, 2012.

Издательство Московского центра
непрерывного математического образования
119002, Москва, Большой Власьевский пер., 11,
тел. (499)-241-74-83
http://www.mccme.ru

ISBN 978-5-4439-2162-4
© Коллектив авторов, 2012
© МЦНМО, 2014

Оглавление

Предисловия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5

Гл а в а 1. Основные понятия криптографии
9

§ 1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
§ 2. Предмет криптографии . . . . . . . . . . . . . . . . . . . . . . . . . .
10
§ 3. Математические основы
. . . . . . . . . . . . . . . . . . . . . . . . .
17
§ 4. Новые направления . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
§ 5. Заключение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26

Гл а в а 2. Криптография и теория сложности
27

§ 1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
§ 2. Криптография и гипотеза P ̸= NP . . . . . . . . . . . . . . . . . . . .
30
§ 3. Односторонние функции . . . . . . . . . . . . . . . . . . . . . . . . .
32
§ 4. Псевдослучайные генераторы
. . . . . . . . . . . . . . . . . . . . . .
34
§ 5. Доказательства с нулевым разглашением . . . . . . . . . . . . . . . .
37
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42

Гл а в а 3. Криптографические протоколы
44

§ 1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
§ 2. Целостность. Протоколы аутентификации и электронной подписи . .
47
§ 3. Неотслеживаемость. Электронные деньги
. . . . . . . . . . . . . . .
63
§ 4. Протоколы типа «подбрасывание монеты по телефону»
. . . . . . .
70
§ 5. Еще раз о разделении секрета . . . . . . . . . . . . . . . . . . . . . .
75
§ 6. Поиграем в «кубики». Протоколы голосования
. . . . . . . . . . . .
78
§ 7. За пределами стандартных предположений. Конфиденциальная передача сообщений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
§ 8. Вместо заключения . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87

Гл а в а 4. Алгоритмические проблемы теории чисел
89

§ 1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
§ 2. Система шифрования RSA . . . . . . . . . . . . . . . . . . . . . . . .
91
§ 3. Сложность теоретико-числовых алгоритмов . . . . . . . . . . . . . .
94
§ 4. Как отличить составное число от простого . . . . . . . . . . . . . . .
100

Оглавление

§ 5. Как строить большие простые числа . . . . . . . . . . . . . . . . . .
102
§ 6. Как проверить большое число на простоту . . . . . . . . . . . . . . .
106
§ 7. Как раскладывают составные числа на множители . . . . . . . . . .
113
§ 8. Дискретное логарифмирование
. . . . . . . . . . . . . . . . . . . . .
116
§ 9. Заключение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
122
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
122

Гл а в а 5. Математика разделения секрета
124

§ 1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
124
§ 2. Разделение секрета для произвольных структур доступа . . . . . . .
126
§ 3. Линейное разделение секрета
. . . . . . . . . . . . . . . . . . . . . .
129
§ 4. Идеальное разделение секрета и матроиды . . . . . . . . . . . . . . .
131
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
134

Гл а в а 6. Компьютер и криптография
136

§ 1. Вместо введения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
136
§ 2. Немного теории . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
138
§ 3. Как зашифровать файл? . . . . . . . . . . . . . . . . . . . . . . . . .
146
§ 4. Поучимся на чужих ошибках . . . . . . . . . . . . . . . . . . . . . . .
159
§ 5. Вместо заключения . . . . . . . . . . . . . . . . . . . . . . . . . . . .
169
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
170

Гл а в а 7. Олимпиады по криптографии для школьников
171

§ 1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
172
§ 2. Шифры замены . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
175
§ 3. Шифры перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . .
189
§ 4. Многоалфавитные шифры замены с периодическим ключом . . . . .
198
§ 5. Условия задач олимпиад по математике и криптографии . . . . . . .
206
§ 6. Указания и решения
. . . . . . . . . . . . . . . . . . . . . . . . . . .
221
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
259

П р и л о ж е н и е
А. Отрывок из статьи К. Шеннона «Теория связи
в секретных системах»
261

П р и л о ж е н и е Б. Аннотированный список рекомендованной литературы
298

П р и л о ж е н и е В. Словарь криптографических терминов
304

Алфавитный указатель русскоязычных терминов . . . . . . . . . . . . . .
341
Алфавитный указатель англоязычных терминов
. . . . . . . . . . . . . .
345

Предисловие к четвертому изданию

Настоящее издание можно считать в некотором смысле юбилейным:
минуло более десяти лет со дня выхода книги в свет. За это время она
стала настоящим бестселлером. Вышли 3 издания в МЦНМО, книга была
напечатана также в издательстве «Питер». Перевод на английский язык
издан Американским математическим обществом.
Основная причина популярности книги, безусловно, состоит в том,
что она остается единственной в своем жанре. Вместе с тем интерес
к проблемам криптографии и, в более широком смысле, к информационной
безопасности с каждым годом возрастает.
С момента выхода предыдущих изданий ситуация с математической
криптографией в стране немного изменилась. Курс лекций «Теоретическая криптография» теперь читается на факультете управления и прикладной математики МФТИ. Учебные курсы, посвященные этой математической дисциплине, появились на матмехе СПбГУ: Э. А. Гирш «Сложностная
криптография» и Ю. Лифшиц «Современные задачи криптографии».
В МГУ проводится ежегодная международная конференция «Математика и безопасность информационных технологий».
В настоящее издание внесены некоторые добавления и исправления.
В главе по теории чисел описан недавно открытый полиномиальный алгоритм проверки целых чисел на простоту. Добавлены список литературы
для дальнейшего чтения с краткими аннотациями и «Словарь криптографических терминов».

Март 2012 г.
В. Ященко

Предисловие к третьему изданию

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

Предисловия

безопасность), в перечень диссертационных специальностей — междисциплинарная специальность 051319. В Московском государственном университете им. М. В. Ломоносова с сентября 2000 г. начато обучение по
специализациям «Математические методы защиты информации» и «Программное обеспечение защиты информации». Научный фундамент этих
специализаций — криптография — наука о шифрах.
Систематических учебников по криптографии на русском языке пока
нет, они будут появляться по мере становления системы гражданского
криптографического образования. В этих условиях предлагаемая книга
«Введение в криптографию», которая уже выдержала два издания, может
быть рекомендована в качестве первого учебного пособия для студентовматематиков, специализирующихся в области информационной безопасности. Книга написана специалистами-криптографами с целью популяризации научных основ криптографии и поэтому доступна и может быть полезна
массовому читателю.

Ректор МГУ,
академик РАН
В. А. Садовничий

Сентябрь 2000 г.

Предисловия
7

Предисловие ко второму изданию

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

Cентябрь 1999 г.
В. Ященко

Предисловие к первому изданию

Криптография — наука о шифрах — долгое время была засекречена,
так как применялась в основном для защиты государственных и военных
секретов. В настоящее время методы и средства криптографии используются для обеспечения информационной безопасности не только государства, но и частных лиц, и организаций. Дело здесь совсем не обязательно
в секретах. Слишком много различных сведений «гуляет» по всему свету
в цифровом виде. И над этими сведениями «висят» угрозы недружественного ознакомления, накопления, подмены, фальсификации и т. п. Наиболее
надежные методы защиты от таких угроз дает именно криптография.
Пока криптографические алгоритмы для рядового потребителя—тайна
за семью печатями, хотя многим уже приходилось пользоваться некоторыми криптографическими средствами: шифрование электронной почты,
интеллектуальные банковские карточки и др. Естественно, что при этом
основной вопрос для пользователя — обеспечивает ли данное криптографическое средство надежную защиту. Но даже правильно сформулировать
этот элементарный вопрос непросто. От какого противника защищаемся?
Какие возможности у этого противника? Какие цели он может преследовать? Как измерять надежность защиты? Список таких вопросов можно
продолжить. Для ответа на них пользователю необходимы знания основных понятий криптографии.
Популярное изложение научных основ криптографии (речь идет только
о «негосударственной» криптографии; разделы криптографии, связанные
с государственной безопасностью, должны оставаться секретными) —цель
настоящей книги. Ее можно использовать и в качестве учебного пособия.
На русском языке аналогичных книг пока нет. Материалы ряда глав публиковались авторами ранее в других изданиях (глава 1— в книге С. А. Дориченко, В. В. Ященко, «25 этюдов о шифрах», М.: ТЭИС, 1994; главы 1, 2,
4, 5— в журнале «Математическое просвещение», третья серия, выпуск 2,
М.: МЦНМО, 1998; глава 7 — в газете «Информатика» (еженедельное

Предисловия

приложение к газете «Первое сентября»), № 4, январь 1998). При подготовке настоящего издания эти материалы были переработаны и дополнены.
Изложение материала рассчитано на читателя с математическим складом ума. В основном главы не зависят друг от друга (это достигнуто
за счет некоторых повторов) и их можно читать в произвольном порядке. Главу 1 — вводную — рекомендуется прочитать всем, поскольку в ней
на популярном уровне разъясняются все основные понятия современной
криптографии: шифр, ключ, стойкость, электронная цифровая подпись,
криптографический протокол и др. В других главах часть материала повторяется, но уже более углубленно. В главах 2, 3, 4, 5 используются некоторые сведения из высшей математики, известные ученикам математических
классов и студентам. Глава 6 ориентирована на знатоков компьютерных
технологий. Глава 7 содержит материалы олимпиад по криптографии для
школьников, и поэтому для ее чтения никаких знаний, выходящих за пределы школьной программы, не требуется.
Предупреждение: криптографические средства и программные продукты, упоминаемые в книге, используются только для иллюстрации общих
криптографических идей; авторы не ставили своей целью давать оценки
или сравнивать имеющиеся на рынке криптографические средства.
Криптография была поставлена на научную основу во многом благодаря работам выдающегося американского ученого Клода Шеннона. Его
доклад «Математическая теория криптографии» был подготовлен в секретном варианте в 1945 г., рассекречен и опубликован в 1948 г., переведен
на русский язык в 1963 г. Поскольку «Работы по теории информации
и кибернетике» (1963 г.) К. Шеннона стали библиографической редкостью,
мы включили в приложение основную часть статьи К. Шеннона «Теория
связи в секретных системах». Эту основополагающую работу рекомендуется прочитать всем интересующимся криптографией.
Для профессионального понимания криптографических алгоритмов
и умения оценивать их сильные и слабые стороны необходима уже серьезная математическая подготовка (на уровне математических факультетов
университетов). Это объясняется тем, что современная криптография
основана на глубоких результатах таких разделов математики, как теория
сложности вычислений, теория чисел, алгебра, теория информации и др.
Желающим серьезно изучать криптографию можно порекомендовать
обзорную монографию «Криптография в банковском деле» Анохина М. И.,
Варновского Н. П., Сидельникова В. М., Ященко В. В., М.: МИФИ, 1997.

Октябрь 1998 г.
В. Ященко

Глава 1

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

§ 1. Введение

Как передать нужную информацию нужному адресату в тайне
от других? Каждый из читателей в разное время и с разными целями
наверняка пытался решить для себя эту практическую задачу (для удобства
дальнейших ссылок назовем ее «задача ТП», т. е. задача Тайной Передачи). Выбрав подходящее решение, он, скорее всего, повторил изобретение
одного из способов скрытой передачи информации, которым уже не одна
тысяча лет.
Размышляя над задачей ТП, нетрудно прийти к выводу, что есть три
возможности.
1. Создать абсолютно надежный, недоступный для других канал связи
между абонентами.
2. Использовать общедоступный канал связи, но скрыть сам факт передачи информации.
3. Использовать общедоступный канал связи, но передавать по нему
нужную информацию в так преобразованном виде, чтобы восстановить ее
мог только адресат.
Прокомментируем эти три возможности.
1. При современном уровне развития науки и техники сделать такой
канал связи между удаленными абонентами для неоднократной передачи
больших объемов информации практически нереально.
2. Разработкой средств и методов скрытия факта передачи сообщения
занимается стеганография.

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

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

Также из детективов известен метод «микроточки»: сообщение записывается с помощью современной техники на очень маленький носитель (микроточку),
который пересылается с обычным письмом, например, под маркой или где-нибудь
в другом, заранее обусловленном месте.
В настоящее время в связи с широким распространением компьютеров известно много тонких методов «запрятывания» защищаемой информации внутри
больших объемов информации, хранящейся в компьютере. Наглядный пример
запрятывания текстового файла в графический можно найти в Интернете 1; он же
приведен в журнале «Компьютерра», № 48 (225) от 1 декабря 1997 г., на стр. 62.
(Следует отметить, что авторы статьи в журнале ошибочно относят стеганографию
к криптографии. Конечно, с помощью стеганографии можно прятать и предварительно зашифрованные тексты, но, вообще говоря, стеганография и криптография — принципиально различные направления в теории и практике защиты
информации.)

3. Разработкой методов преобразования (шифрования) информации
с целью ее защиты от незаконных пользователей занимается криптография. Такие методы и способы преобразования информации называются
шифрами.
Шифрование (зашифрование) —процесс применения шифра к защищаемой информации, т. е. преобразование защищаемой информации (открытого текста) в шифрованное сообщение (шифртекст, криптограмму) с помощью определенных правил, содержащихся в шифре.
Дешифрование — процесс, обратный шифрованию, т. е. преобразование шифрованного сообщения в открытый текст с помощью определенных
правил, содержащихся в шифре.
Криптография—прикладная наука, она использует самые последние—
прикладная наука, она использует самые последние достижения другой
стороны, все конкретные задачи криптографии существенно зависят от
уровня развития техники и технологии, от применяемых средств связи
и способов передачи информации.

§ 2. Предмет криптографии

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

1http://www.geocities.com/SiliconValley/Vista/6001/

§ 2. Предмет криптографии
11

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

A
B

р

Рис. 1

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

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

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

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

Криптография занимается методами преобразования информации, которые бы не позволили противнику извлечь ее из перехватываемых сообщений. При этом по каналу связи передается уже не сама защищаемая
информация, а результат ее преобразования с помощью шифра, и для
противника возникает сложная задача вскрытия шифра.
Вскрытие (взламывание) шифра — процесс получения открытого
текста из шифрованного сообщения без знания примененного шифра.
Однако помимо перехвата сообщений и вскрытия шифра противник
может пытаться получить защищаемую информацию многими другими способами. Наиболее известным из таких способов является агентурный, когда противник каким-либо путем склоняет к сотрудничеству одного из
законных пользователей и с помощью этого агента получает доступ к защищаемой информации. В такой ситуации криптография бессильна.
Противник может пытаться не получить, а уничтожить или модифицировать защищаемую информацию в процессе ее передачи. Это — совсем другой тип угроз для информации, отличный от перехвата сообщений
и вскрытия шифра. Для защиты от таких угроз разрабатываются свои
специфические методы.
Следовательно, на пути от одного законного пользователя к другому
информация должна защищаться различными способами, противостоящими различным угрозам. Возникает ситуация цепи из разнотипных звеньев,
которая защищает информацию. Естественно, противник будет стремиться
найти самое слабое звено, чтобы с наименьшими затратами добраться до
информации. А значит, и законные пользователи должны учитывать это
обстоятельство в своей стратегии защиты: бессмысленно делать какое-то
звено очень прочным, если есть заведомо более слабые звенья («принцип
равнопрочности защиты»).
Не следует забывать и еще об одной важной проблеме: проблеме соотношения цены информации, затрат на ее защиту и затрат на ее добывание. При современном уровне развития техники сами средства связи,
а также разработка средств перехвата информации из них и средств защиты информации требуют очень больших затрат. Прежде чем защищать
информацию, задайте себе два вопроса:
1) является ли она для противника более ценной, чем стоимость атаки;
2) является ли она для вас более ценной, чем стоимость защиты.