Практическая криптография

Краткое содержание учебной дисциплины, модуля / Brief summary

Алгебраические основы.

Группа. Подгруппа. Факторгруппа. Алгоритмы возведения в степень. Задача дискретного логарифмирования. Кольцо. Идеал. Простые и максимальные идеалы. Факторкольцо. Теорема о гомоморфизме колец. Поле. Конечные поля. Число элементов в конечном поле. Мультипликативная группа конечного поля. Критерий неприводимости многочленов над конечными полями. Алгоритм Берлекэмпа.

Теоретико-числовые основы.

Алгоритм Евклида. Квадратичные вычеты по модулю p. Символ Лежандра. Символ Якоби. Квадратичный закон взаимности. Вычисление символа Якоби. Китайская теорема об остатках. Первообразные корни.

Эллиптические кривые. Аффинное и проективное пространства. Уравнение Вейерштрасса над полями различной характеристики. Определение эллиптической кривой.  Групповой закон на множестве точек эллиптической кривой. Формулы сложения точек в аффинных и проективных координатах. Вычисление кратной точки. Вычисление порядка группы точек эллиптической кривой над конечным полем.  Дзета-функция эллиптической кривой. Теорема Вейля для эллиптической кривой. Теорема Хассе о порядке группы точек эллиптической кривой над конечным полем.

Алгоритмы факторизации и проверки числа на простоту

Факторизация целых чисел с помощью эллиптических кривых.  Детерминированные тесты на простоту. Вероятностные тесты Соловея-Штрассена и Миллера-Рабина на простоту.

Криптосистемы с открытым ключом

Понятие односторонней функции. Протокол обмена ключами Диффи–Хеллмана. Криптосистема Эль-Гамаля. Криптосистема RSA. Атаки на криптосистему RSA. Криптосистема Рабина.

Электронная цифровая подпись

Схема электронной цифровой подписи Эль-Гамаля. Схема электронной цифровой подписи на эллиптических кривых.

Algebraic Basics. Group. Subgroup. Factor group. Algorithms for exponentiation. Discrete logarithm problem. Ring. Ideal. Simple and maximum ideals. Factor ring. Ring homomorphism theorem. Field. Finite fields. The number of elements in a finite field. Multiplicative group of a finite field. A criterion for the irreducibility of polynomials over finite fields. Berlekamp’s algorithm.

Number theoretic foundations. Euclid’s algorithm. Quadratic residues modulo p. Legendre symbol. Jacobi symbol. Quadratic reciprocity law. Calculation of the Jacobi symbol. Chinese remainder theorem. Primitive roots.

Elliptic curves. Affine and projective spaces. Weierstrass equation over fields of various characteristics. Definition of an elliptic curve.  Group operation on a set of points on an elliptic curve. Formulas for adding points in affine and projective coordinates. Calculation of multiple point. Calculation of the order of an elliptic curve over a finite field.  Zeta function of an elliptic curve. Weyl theorem for an elliptic curve. Hasse’s theorem on elliptic curves over finite fields.

Algorithms for factorization and checking numbers for primality. Factorization of integers using elliptic curves.  Deterministic primality tests. Solovay-Strassen and Miller-Rabin probabilistic primality tests.

Public key cryptosystems. The concept of a one-way function. Diffie-Hellman key exchange protocol. El Gamal cryptosystem. RSA cryptosystem. Attacks on the RSA cryptosystem. Rabin cryptosystem.

Electronic digital signature. El Gamal electronic digital signature scheme. Electronic digital signature on elliptic curves.

Формируемые компетенции / The formed competences

Специализированная компетенция:

быть способным применять на практике алгоритмы криптографии и помехоустойчивого кодирования.

Specialized competence:

be able to apply cryptography and error-correcting coding algorithms in practice.

Результаты обучения (знать, уметь, владеть) / Learning outcomes (know, can, be able)

В результате освоения учебной дисциплины студент должен

знать:

–  общие математические основы построения криптосистем с открытым ключом;

–   протоколы работы широко используемых криптосистем;

уметь:

–     производить вычисления в конечных полях;

–     находить символы Лежандра и Якоби;

–     находить порядок группы точек специальных эллиптических кривых над конечными полями;

–     строить конечные поля заданного порядка;

–     строить расширения полей и выполнять вычисления в них;

владеть:

–   основными навыками решения задач связанных с эллиптическими кривыми и конечными полями;

–   методами доказательств основных теорем, встречающихся в дисциплине «Практическая криптография».

– навыками самообразования и способами использования аппарата алгебры и теории чисел для проведения математических и междисциплинарных исследований.

As a result of mastering the academic discipline, the student must

know:

– general mathematical foundations for constructing public key cryptosystems;

– protocols for the operation of widely used cryptosystems;

can:

– perform calculations in finite fields;

– find Legendre and Jacobi symbols;

– find the order of elliptic curves over finite fields;

– construct finite fields of a given order;

– construct field extensions and perform calculations in them;

be able to apply:

– basic skills in solving problems related to elliptic curves and finite fields;

– methods of proof of the main theorems found in the discipline “Practical Cryptography”.

– self-education skills and ways to use the apparatus of algebra and number theory to conduct mathematical and interdisciplinary research.

Семестр изучения учебной дисциплины, модуля / Semester of study

2

2

Пререквизиты / Prerequisites

Трудоемкость в зачетных единицах (кредитах) / Credit units

6 зачетных единиц.

6 credit units.

Количество аудиторных часов и часов самостоятельной работы / Academic hour of students’ class work,

hours of self-directed learning

Всего 214 часов, из них 72 аудиторных часа и 142 часа самостоятельной работы.

A total of 214 hours, of which 72 academic hours of students’ class work and 142 hours of self-directed learning.

Требования и формы текущей и промежуточной аттестации / Requirements and forms of current and interim certification

Устный опрос, контрольная работа, коллоквиум.

Зачет. Экзамен.