Number-theoretic methods in cryptography

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

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

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

Тема 2. Конечные поля

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

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

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

Тема 4. Эллиптические кривые 

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

Тема 5. Вычисление порядка группы точек эллиптической кривой над конечным полем

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

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

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

Тема 7. Криптосистемы с открытым ключом

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

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

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

Topic 1. Algebraic foundations Group. Subgroup. Quotient group. Algorithms for raising to a power. Discrete logarithm problem. Ring. Ideal. Prime and maximal ideals. Quotient ring. Ring homomorphism theorem. Field. Characteristic of a field. Degree of field extension. Algebraic extensions. 

Topic 2. Finite fields The number of elements in a finite field. The multiplicative group of a finite field. The Frobenius automorphism. A criterion for the irreducibility of polynomials over a finite field. Berlekamp’s algorithm. Construction of irreducible polynomials over a finite field. 

Topic 3. Number-theoretical foundations Euclidean algorithm. Euler’s function. Euler’s theorem. Quadratic residues modulo p. Legendre symbol. Quadratic reciprocity law. Jacobi symbol. Calculating the Jacobi symbol. Chinese remainder theorem. Primitive roots. Existence of primitive roots. Topic 4. Elliptic curves Affine and projective spaces. Weierstrass equation over fields of different characteristics. Definition of an elliptic curve. Group law on the set of points of an elliptic curve. Formulas for addition of points in affine and projective coordinates. Calculating a multiple point. Elliptic curves over residue class rings. 

Topic 5. Calculating the order of a group of points of an elliptic curve over a finite field Formal power series ring. Zeta function of an elliptic curve. Weyl’s theorem for an elliptic curve. Hasse’s theorem on the order of a group of points of an elliptic curve over a finite field. 

Topic 6. Factorization algorithms and testing a number for primality Deterministic tests for primality. Mersenne primes. Solovay-Strassen and Miller-Rabin probabilistic primality tests. Factorization of integers using elliptic curves. Testing numbers for primality using elliptic curves. 

Topic 7. Public-key cryptosystems The concepts of a one-way function and a one-way function with a secret. The Diffie-Hellman key exchange protocol. The ElGamal cryptosystem. The RSA cryptosystem. Attacks on the RSA cryptosystem. The Rabin cryptosystem. 

Topic 8. Electronic digital signature General electronic digital signature scheme. The ElGamal electronic digital signature scheme. Electronic digital signature scheme on elliptic curves

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

Базовые профессиональные компетенции:

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

Применять основные алгебраические и геометрические понятия, конструкции и методы при решении теоретических и прикладных математических задач.

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

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

Basic professional competencies: 

Use concepts and methods of real, complex and functional analysis and apply them to study models of the surrounding world. 

Apply basic algebraic and geometric concepts, constructions and methods when solving theoretical and applied mathematical problems. 

Specialized competencies: 

Apply key methods of protecting information systems when implementing cryptographic applications.

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

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

знать:

•  общие математические основы построения криптосистем с открытым ключом;
•  протоколы работы широко используемых криптосистем;

уметь:

• производить вычисления в конечных полях;
• находить символы Лежандра и Якоби;
• находить порядок группы точек специальных эллиптических кривых над конечными полями; 
• строить конечные поля заданного порядка;
• строить расширения полей и выполнять вычисления в них;

владеть:

•  основными навыками решения задач связанных с эллиптическими кривыми и конечными полями;
•  методами доказательств основных теорем, встречающихся в дисциплине «Теоретико-числовые методы в криптографии».

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

As a result of studying the academic discipline, the student should: 

know: 

– general mathematical foundations of constructing public-key cryptosystems; 

– protocols of widely used cryptosystems; 

be able to: 

– perform calculations in finite fields; 

– find Legendre and Jacobi symbols; 

– find the order of a group of points of special elliptic curves over finite fields; 

– construct finite fields of a given order; 

– construct field extensions and perform calculations in them; 

possess: 

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

– methods of proving the main theorems encountered in the discipline “Number-theoretic methods in cryptography”; 

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

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

6

6

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

Алгебра и теория чисел

Algebra and Number Theory 

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

3 зачетные единицы.

3 credit units.

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

hours of self-directed learning

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

A total of 120 hours, of which 68 academic hours of students’ class work and 52 hours of self-directed learning.

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

Устный опрос, коллоквиум, 

контрольная работа.

Экзамен

Oral survey, colloquium, test. 

Exam