КНИГИ ПО ТЕОРИИ ВЕРОЯТНОСТЕЙ, СТАТИСТИКЕ, КРИПТОГРАФИИ, ДИСКРЕТНОЙ МАТЕМАТИКЕ

Нил Коблиц
Курс теории чисел и криптографии

Цена: 398,00 руб. (обложка)
      506,00 руб. (переплет)

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

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

Содержание:

Предисловие

"... Гаусс, а также другие математики, по-видимому, справедливо утверждали, что существует, по крайней мере, одна наука (теория чисел), которая, ввиду своей отдаленности от обыденной человеческой деятельности, остается чистой и благородной."

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

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

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

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

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

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

Зависимость между материалом глав следующая (исходя из ссылок в главах V и VI на предыдущий материал):

За основу этой книги взяты курсы, прочитанные в университете штата Вашингтон (Сиэтл) в 1985-86 годах и в Институте математики (Мадрас, Индия) в 1987 году. Мне приятно поблагодарить Гэри Нельсон и Дугласа Линда за апробацию рукописи и полезные замечания.

Рисунок на фронтисписе, принадлежащий профессору А.Т.Фоменко из Московского государственного университета, иллюстрирует тему книги. Обратите внимание, что коды десятичных цифр на стенах здания вовсе не случайны.

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

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

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

Следующий список суммирует основные изменения во втором издании.

• Внесены исправления и разъяснения, добавлены многочисленные ссылки.
• В главу VI добавлен раздел о доказательствах с нулевым разглашением и скрытой передаче.
• В главу V добавлен раздел о разложении на множители методом квадратичного решета.
• В главу VI включен раздел об использовании эллиптических кривых в тестах на простоту.
• Добавлено беглое обсуждение следующих вопросов: (n,k)-пороговые схемы, вероятностное шифрование, хеш-функции, рюкзачная криптосистема Чора-Райвеста и американский стандарт цифровой подписи DSS.

Нил Коблиц
Сиэтл, май 1994 года

Глава I. Некоторые вопросы элементарной теории чисел

1.1 Временные оценки сложности арифметических операций

1.2 Делимость и алгоритм Евклида

1.3 Сравнения

1.4 Некоторые применения к разложению на множители

Глава II. Конечные поля и квадратичные вычеты

2.1 Конечные поля

2.2 Квадратичные вычеты и закон взаимности

Глава III. Криптография

3.1 Некоторые простые криптосистемы

3.2 Шифрующие матрицы

Глава IV. Открытый ключ

4.1 Суть криптографии с открытым ключом

4.2 Криптосистема RSA

4.3 Дискретное логарифмирование

4.4 Задача о рюкзаке

4.5 Протоколы с нулевым разглашением и скрытая передача

Глава V. Простота и факторизация

5.1 Псевдопростые числа

5.2 Ро-метод

5.3 Факторизция Ферма и факторные базы

5.4 Метод цепных дробей

5.5 Метод квадратичного решета

Глава VI. Эллиптические кривые

6.1 Основные факты

6.2 Криптосистемы на эллиптических кривых

6.3 Критерий простоты, использующий эллиптические кривые

6.4 Разложение на множители при помощи эллиптических кривых

Ответы к упражнениям

Предметный указатель

2001, 260 cтр., ISBN 5-85484-014-6, 5-85484-012-X, на русском языке