<< Предыдущая

стр. 3
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>


зисов. Если Вы хотите что-то прочно закрепить в памяти, то
это должны быть именно утверждения, приведенные в этом
разделе.
- Дополнительная литература. Каждая глава содержит список
нескольких книг или статей, из которых можно получить даль­
нейшую полезную информацию. Эти ссылки относятся, глав­
ным образом, к тому материалу, изучению которого подго­
товила Вас данная глава. Поскольку практически любая тема
криптографии освещена в НАС^ я не включаю этот справоч­
ник в каждый список дополнительной литературы. Он оста­
влен как общая книга, которой есть что сказать по каждой
теме, представленной в этом учебнике.
- Упражнения. В книге они разделены на три типа:
• Контрольные вопросы. На них следует отвечать по памя­
ти сразу после прочтения. Фактически, они предназначе­
ны ц^ля проверки: удержалось ли у Вас в голове хоть что-
нибудь в результате подробного знакомства с главой.
• Лабораторные работы. Поскольку большинство студентов
прикладных дисциплин сейчас требуют практических за­
даний, я включил в некоторые главы примеры возможных
упражнений по программированию, рассчитанные на уро­
вень студентов.
• Упражнения. Они не потребуют от Вас много времени. Их
цель — заставить Вас немного напрячься и глубже понять
материал. В некоторых из задач требуется доказать не­
сложные математические факты, используемые, но непро­
веренные в основном тексте. Поэтому многие вопросы из
этого раздела можно использовать преподавателям в каче­
стве домашнего задания или J\ля составления экзамена.
В тексте отсутствуют ссылки на предшествующие работы. Это —
учебник, и мне не хотелось ломать плавный поток изложения пе­
рекрестными ссылками. Однако Вы не должны считать отсутствие
ссылок свидетельством тому, что ЛЮБОЙ из результатов книги —
мой собственный. Фактически, здесь нет НИ ОДНОГО моего ре­
зультата. Тот, кто хочет получить сведения о первоисточниках, дол­
жен обратиться к одной из книг, упомянутых в разделе «Дополни­
тельная литература», или заглянуть в НАС.
Разные студенты в разнообразных институтах изучают различ­
ные языки программирования. В то время как студенты, обучаю­
щиеся на факультетах вычислительной математики и кибернетики.
Предисловие

специализируются в языке С или Java^ студенты-математики впол­
не счастливы, овладев алгебраическим пакетом программ на подо­
бие Maple или Mathematica. Некоторые предпочитают языки функ­
ционального программирования аналогичные Haskell^ а другим бо­
лее удобен объектно-ориентированный язык похожий на (7++.
В Бристоле мы пытаемся воспитать «многоязычных» специалистов,
с первого курса преподавая множество языков программирования
одновременно. Аналогичный прием использован и здесь, где при­
меняются различные приемы (и языки) для наилучшего объяснения
алгоритмов.
Задания по программированию формулируются на нейтральном
языке и вполне могут быть выполнены любым студентом, не ис-
пытываюш;им патологического отвраш;ения к компьютеру. Иногда
при рассказе о программах я использую конкретный язык, но толь­
ко тогда, когда от этого выигрывает понимаемость текста. Напри­
мер, задание рекурсивной функции наиболее естественно выглядит
в командах языка Haskell, За исключением таких ситуаций для опи­
сания алгоритмов я использую естественный язык или С-подобный
псевдокод.
Желаюш,им реализовать на компьютере какие-то из алгоритмов,
приведенных в книге, необходимо освоить описание и оперирование
с достаточно большими целыми числами и элементами конечных
полей. В такие языки как Java^ Haskell или алгебраический пакет
Maple, достаточно большие целые числа и операции над ними уже
встроены. А вот «пишущим» на языках С и С-\--{- придется организо­
вать доступ к соответствующим библиотекам или самостоятельно
написать соответствующие процедуры. Этого будет вполне доста­
точно для оперирования с большими целыми числами в образова­
тельных или экспериментальных целях, но каждый должен отдавать
себе отчет в том, что на практике в криптографических системах
используются специальные средства повышения эффективности.
В некоторые из языков, например, Java, встроены доступные
криптографические алгоритмы. Например, библиотека стандарт­
ных программ языка Java содержит возможности для вычисления
хэш-функций и передачи электронной цифровой подписи. Кроме то­
го, в нем имеются средства для работы с протоколом Х,509 (Х.509
certificates). В нем также есть различные криптографические би­
блиотеки, называемые Java Cryptographic Engines или JCEs,
Я не ставлю перед собой цель детально описать классы стан­
дартных библиотек. Любой компетентный студент может в них ра-
Предисловие

зобраться в течение нескольких часов. Вместо этого в качестве по­
мощи читателю в приложении Б приведено несколько примеров, ис­
пользующих обе упомянутые библиотеки стандартных программ и
программу API для машин SUN JCE. Точнее говоря, я использовал
версию Cryptix для SUN JCE.
Работа со стандартными криптографическими программами и
J СЕ API аналогична работе с большинством процедур языков С
и (7++, так что я ограничился примерами на Java^ поскольку на
сегодняшний день он является самым изучаемым языком в универ­
ситетах. Доступные криптографические библиотеки дают возмож­
ность преподавателям заниматься практическими исследованиями
или создавать учебные проекты для студентов.
Книга состоит из четырех частей. В первой даны краткие ма­
тематические сведения, необходимые для изучения криптографии.
Поэтому при первом чтении ее можно пропустить, возвращаясь к
началу по мере необходимости. Часть II посвящена обсуждению
симметричных алгоритмов шифрования и проблеме распределения
ключей, возникающей в связи с их применением. В части III рас­
сказано о криптосистемах с открытым ключом и электронных под­
писях вместе с некоторыми дополнительными темами, касающими­
ся ключей, такими, например, как сертификаты (certificates), схе­
мы передач и доказательство с нулевым разглашением. Часть IV —
наиболее сложная и охватывает множество проблем, относящихся к
более теоретической области криптографии, включал современное
понятие доказуемой стойкости. Обсуждение алгоритмов с откры­
тым ключом в третьей части было построено таким образом, что­
бы подготовить читателя к восприятию основных концепций части
IV. Последнюю часть следует рассматривать как щадящее, а не аб­
солютно строгое, введение в теоретические аспекты современной
криптографии.
Тем преподавателям, кто планирует дать быстрый обзор (за 20-
30 лекций) современной криптографии, я советую включить в курс
главы 3, 5, 7, 10 и 12, посвятив первую лекцию главе 1, чтобы во­
оружить студентов информацией, необходимой для понимания по­
следующего материала. Лекторам, читающим курс криптографии с
акцентом на ее математическом фундаменте, необходимый для со­
временных криптосистем с открытым ключом, (например для сту­
дентов, специализирующихся в математике), я предлагаю ориенти­
роваться на главы 3, 7, 8, 9 и 11. Тем же, кто обучает будущих спе­
циалистов в вычислительной технике, вероятно, следует выбросить
Предисловие

из курса главы 2, 8 и 9, поскольку они слишком математизированы.
Если позволяет время, то в курс лекций можно включить прак­
тически весь материал учебника. Например, в Бристоле курс, по­
священный только шифрованию, мы читаем беря за основу главы 3,
4, 5, 7 и 15. А в другом мы рассказываем о проблемах, относяш;ихся
к управлению ключами, цифровой подписи и РК1^ т. е. проблемах,
отраженных в главах 6, 10, 12 и 13. Кроме того, мы включаем во
второй курс темы, касающиеся теоретико-информационной стой­
кости, не вошедшие в эту книгу. В нем шифрование представлено
просто как «нажимание на кнопки», отвечающие за шифрование и
расшифр ование.
Множество тем, приобретающих все более важное значение, так
и не вошло в книгу. Один из основных пробелов — подробное обсу­
ждение линейного криптоанализа блочных шифров. Мне показалось,
что эта тема больше подходит р,ля курсовой работы или дополни­
тельного чтения. Второе упущение — то, что я не упоминаю времен­
ной анализ, мощный дифференциальный анализ и другие стороны
исследования информационных каналов. Это становится все более
и более важной областью, связанной с реализацией криптографи­
ческих алгоритмов, поскольку наиболее распространенные из них
находятся во враждебной среде, как, например, изящная кредитная
карта в Вашем бумажнике.
Я хотел бы поблагодарить студентов Бристольского универси­
тета, давших полезные комментарии к обоим нашим курсам и чер­
новому варианту этой книги. Кроме того, следующие люди помо­
гли мне, обеспечивая взаимосвязь между многообразными главами
и темами: Ян Блэк (Ian Blake), Флориан Хесс (Florian Hess), Ник
Хоугрэйв-Грэхам (Nick Howgrave-Graham), Джон Мэлон-Ли (John
Malone-Lee), Венбо Мао (Wenbo Мао), Джон Мерриман (John Мег-
riman), Фонг Нгуен (Phong Nguyen), Дэн Пэйдж (Dan Page), Вин­
сент Риймен (Vincent Rijmen), Эдлин Теск (Edlyn Teske) и Фриде-
рик Веркаутерен (Prederik Vercauteren). Я хотел бы выразить свою
признательность сотрудникам издательства Мак-Гроу Хилл, кото­
рые мне очень помогали на всем протяжении работы над книгой,
в особенности Конору Грэхем (Conor Graham) и Максу Элвей (Мах
Elvey).


Найджел Смарт
Университет Бристоля
Предисловие

Дополнительная литература
А. J. Menezes, Р. van Oorschot and S. A. Vanstone. The Handbook of
Applied Cryptography, CRC Press, 1997.

Дополнительные благодарности
Автор благодарен своим коллегам, способствовавшим в написании
этой книги:
- Д-р X. Эшман (Н. Ashman) — университет Нотингема.
- Проф. Д. Эспиналл (D. Aspinall) — университет Эдинбурга.
- Д-р М. Хае (М. Huth) — Имперский колледж Лондонского уни­
верситета.
- Д-р С. Джассим (S. Jassim) — университет Бэкингема.
- Д-р С. Мэрфи (S. Murphy) — Королевский колледж Лондон­
ского университета (Holloway).
- Проф. Ф. Мэртаф ( F. Murtagh) — Королевский университет,
Белфаст.
- Д-р Р. Пэуит (R. Poet) — университет Глазго.
- Д-р Н. Жэан (N. Zhang) — университет Манчестера.
ЧАСТЬ I


ПРЕДВАРИТЕЛЬНЫЕ
МАТЕМАТИЧЕСКИЕ
СВЕДЕНИЯ



Прежде чем вплотную заняться криптографией, нам необходимо
осветить некоторые основные математические факты. Многое из
того, что изложено в этой части, можно найти в университетском
курсе «Дискретная математика» или учебниках, посвященных про­
граммированию. Поэтому Вам далеко не все параграфы покажутся
незнакомыми. Читателю, желающему узнать более формализован­
ные определения или понятия, предназначено приложение А, распо­
ложенное в конце книги.
Эта часть — по существу краткий обзор необходимых сведений,
позволяющий приступить к изучению основного материала книги.
Поэтому Вы можете при желании сразу начать чтение со второй
части, возвращаясь к первой по мере необходимости, тогда, когда
встретите незнакомое Вам понятие.
ГЛАВА I
АРИФМЕТИКА
ОСТАТКОВ,
ГРУППЫ,
КОНЕЧНЫЕ ПОЛЯ
И ВЕРОЯТНОСТЬ

Ц е л и главы
• Понять арифметику остатков.
• Познакомиться с группами и конечными полями.
• Выучить основную технику — алгоритм Евклида, китайская
теорема об остатках и символ Лежандра.
• Освоить основные идеи теории вероятностей.


1.1. Арифметика остатков
Эта книга во многом посвящена приложениям арифметики остат­
ков, поскольку именно она является основой современной крипто­
графии и криптосистем с открытым ключом в частности. В связи
с этим в данной главе вводятся необходимые основные понятия и
техника арифметики остатков.
Идея арифметики остатков по существу очень проста и похо­
жа на «арифметику часов», с которой Вы знакомитесь в детстве.
«Арифметика часов» связана с пересчетом времени из 24-часовой
системы в 12-часовую и обратно, ведь в сутках 24 часа, а на цифер­
блате их всего 12. Делается это довольно просто. Чтобы перевести
значение в 24-часовой системе в 12-часовую, достаточно разделить
его на 12. Остаток от деления и будет искомым значением в 12-
часовой системе. Например, 13:00 в 24-часовой системе — то же
самое, что и один час в 12-часовой, поскольку остаток от деления
13 на 12 равен 1.
1.1, Арифметика остатков

Объясним более четко, что такое арифметика остатков. Прежде
всего мы фиксируем положительное натуральное число iV, которое
называется модулем. Если разность двух целых чисел Ь — а делится
на N нацело, то пишут а = b (modN) и говорят, что числа а и 6
сравнимы по модулю iV. Очевидно, что в этом случае числа а и b
имеют один и тот же остаток^ от деления на N. Часто мы будем
лениться и писать просто а = Ь^ если ясно по какому модулю N
происходит сравнение.
Кроме того, мы будем использовать (modN) как обозначение
оператора модуля на множестве целых чисел, который вычисляет
наименьшее натуральное число, сравнимое с данным по модулю N.
Например,
18 (mod 7) = 4, - 1 8 (mod 7) = 3.
Оператор модуля похож на оператор % в языке программирования
С, за тем исключением, что в нашей книге значения этого оператора
обычно неотрицательны. Например, в языках С или Java оператор
модуля действует так:

(-3)У,2=-1,

а мы будем полагать, что (—3) (mod 2) = 1.
Все возможные остатки от деления чисел на N образуют множе­
ство
Z/NZ= {О, . . . , 7 V - 1 } .
Очевидно, Z/NZ — множество значений оператора модуля (mod N).
Заметим, что некоторые авторы обозначают это множество через
ZAT. Тем не менее в этой книге мы будем придерживаться обозначе­
ния Z/7VZ. Еш;е раз отметим, что любой элемент множества Z/iVZ —

<< Предыдущая

стр. 3
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>