# 1 semester

## The name of the discipline

Cryptography and computer security

## Curriculum Specialties

Master Program, first year,

Mathematics;

Web programming and Internet technologies;

Mathematical and software support for mobile devices;

Computer mathematics and system analysis.

Autumn Semester

4

Vasilyev D.V.

## Aims of the study of the discipline

Tuition students mathematical methods underlying the construction of modern public key cryptosystems; introduction to methods of providing computer and network security, mathematical foundation of public key cryptography algorithms; acquaintance with methods of analysis of cryptosystems.

As a result of the study of the discipline the student should be able to:

• know mathematical foundations of construction of public key cryptosystems;
• with the help of an advanced Euclid algorithm to be able to solve linear congruences on an arbitrary module;
• apply the Chinese remainder theorem to speed up an arithmetic calculation with large numbers;
• calculate the degree of group elements using different versions of the binary algorithm;
• perform multiplication of integers by the Karatsuba method;
• perform the multiplication in the residue-class ring by methods of Montgomery and Barrett;
• solve algebraic equations over a simple finite field;
• apply Miller-Rabin and some deterministic primality tests for constructing large prime numbers;
• find elements of a given order in cyclic groups;
• perform arithmetic operations in a group of points of an elliptic curve;
• generate and verify an electronic digital signature on the scheme El Gamal, ECDSA, GOST R 34.10-2012, STB 34.101.45-2013.

## Prerequisites

Algebra and number theory

## The content of the discipline

Divisibility in the ring of integers. GCD, LCM, solvability of linear Diophantine equations.

The law of distribution of Prime numbers, the evaluation of distances between neighboring primes.

Euclidean algorithm,extended Euclidean algorithm, computational complexity of the Euclidean algorithm.

Residues, their properties, a solution of a linear residue, the Chinese remainder theorem, multiplicative functions, Euler’s function, Euler’s theorem, Fermat’s little theorem.

Binary algorithms of exponentiation. Sliding window method.

Computational complexity of algorithms: polynomial, subexponential, exponential algorithms.

Quadratic residues. The Legendre Symbol. Euler’s theorem for quadratic residues, Quadratic reciprocity law. Jacobi Symbols. The calculation of the Legendre symbol.

An algorithm for solving quadratic residues. A general algorithm of solutions of polynomial residues.

The Karatsuba method for multiplying integers. Multiplication of integers using the Chinese remainder theorem. An operation of Montgomery and Barrett reduction.

Deterministic primality test, the Miller-Rabin primality test. The algorithm for constructing large prime numbers.

Algorithm for finding the element of a cyclic group with a given order.

Elliptic curves, a group of elliptic curve points. Obtaining of the addition formulae. The algorithm for computing multiples of a point.

Efficient methods for computing the addition operation on elliptic curve points. Curves in the form of Weierstrass, Montgomery, Edwards.

The RSA cryptosystem.

Diffie-Hellman algorithm for key distribution.

Signature scheme of El Gamal.

Algorithms for digital signature on elliptic curves ECDSA, GOST R 34.10-2012, STB 34.101.45-2013.

## The recommended literature

1. Vinogradov I.M. Elements of number theory. Dover Publications Inc., 2015.
2. Yu. V. Nesterenko, Teoriya chisel, Akademiya, M., 2008 , 272 pp.
3. Knuth D.E. The Art of Computer Programming. Vol.2. Seminumerical Algorithms. Third Edition. Reading, Massachusetts: Addison-Wesley, 1997. 762 p.
4. Harin Y.S., Agievich S.V., Vasilyev D.V., Matveev G.V. Kryptology. Minsk, BSU, 2014. 512 p.
5. Vasilenko O.N. Number-theoretic Algorithms in Cryptography. AMS, 2007. 328 p.
6. Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. Wiley, 1996. 758 p.

## Methods of teaching

Verbal, visual, problem-based, practical, dialog-based and heuristic.

Russian

## Conditions (requirements), formative and summative assessment

• – check of individual tasks,
• – tests.

Examinations marks are given taking into account:

• 40% – semester work,
• 60% – oral answer in an examination

an examination