Предисловие

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

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

В первой главе содержатся основы теории чисел и криптографические алгоритмы, базирующиеся на теоретико-числовых принципах. Читателю, знакомому с теорией чисел, можно ограничиться чтением шестого и седьмого пунктов из §3, и продолжить чтение начиная с §5. Указанные разделы содержат описания вероятностных тестов на простоту, криптосистем, основанных на теоретико-числовых принципах (таких как RSA, Диффи-Хеллмана), методы построения доказуемо простых чисел. Описания криптосистем сопровождаются доказательствами их стойкости.

Вторая глава посвящена алгебраическим основам теории чисел и таким алгебраическим структурам как кольца многочленов. На кольцах и полях многочленов построены некоторые криптосистемы, в частности AES.

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

В разделе «Задачи и упражнения» приведены задачи, решение которых поможет закрепить изученный теоретический материал. Примеры решения подобных задач читатель может найти в тексте пособия в соответствующем разделе. Ответы к задачам приведены в конце раздела.

В Приложении 1 приведена таблица простых чисел и порождающих элементов циклических групп целых чисел, им соответствующих.

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