This course examines two major applications of mathematics in information technologies: error-correcting codes and cryptography. This course studies the tools that are arranged so that the information can be transmitted reliably and safely.



To do this, concepts of abstract algebra, which were studied in previous courses, are applied. For example, concepts and techniques studied in Linear Algebra and Geometry I, Algebraic Structures, Conmutative Algebra and Algebraic Equations are useful. Codes and Cryptography is part of a module together with Algorithm Design, which analyses their complexity.



Students acquire the basic techniques of this area to enable them to use them in other fields of mathematics and, if they wish, to undertake a deeper study of algebra through other optional subjects in their fourth year.

SPECIFIC COMPETENCES

M09CM01 An ability to understand the idea of coding and a code to detect and correct errors

M09CM02 Knowing how to use syndrome-based correction method.

M09CM03 Knowing how to obtain some linear codes (Hamming codes, BCH codes,...)

M09CM04 An ability to understand the idea of Public Key Cryptography.

M09CM05 An ability to understand RSA and Diffie-Hellman systems.

M09CM06 An ability to understand digital signatures and certificates.



LEARNING OUTCOMES

Knowing how to encode and decode messages using linear codes employing the appropriate method.

Knowing how to calculate the minimum distance of a linear code.

Knowing how to calculate generator and parity-check matrix

Knowing how to encrypt and decrypt messages, using the cryptographic private key and public key systems studied.

1. LINEAR CODES. Introduction. Error-correcting codes: basic definitions. Hamming distance. Equivalent codes. Perfect codes. Linear codes: definition and main properties. Generator and parity-check matrix for linear codes. Encoding with a linear code. Decoding with a linear code. Example of linear codes: Hamming codes.



2. CYCLIC CODES. Definition and construction of cyclic codes. Generator polynomial and generator matrix of a cyclic code. Check polynomial and parity-check matrix of a cyclic code. Encoding and decoding with a cyclic code. Cyclic decodification. Example of cyclic codes: BCH codes.



3. PRIMALITY TESTS. Primality tests: definition and types. Deterministic primality tests. Fermat primality test. Pseudoprime numbers. Miller-Rabin primality test. Strong pseudoprime numbers



4. CRYPTOGRAPHY. Cryptography schemes. Private key cryptography: affine cyphers, Hill cryptosystem, substitution cyphers and DES. Public key cryptography: RSA cryptosistem, ElGamal cryptosystem. Hash functions. Diffie-Hellman key exchange method. Digital signatures.



COMPUTER PRACTICAL

Students will design and implement using Mathematica, computer programs related to the five units of the course.

Lectures: The master class methodology will be used to develop the theoretical part of the subject.



Classroom practical: Proposed problems related to the theoretical content of each topic will be solved.



Seminar: In these sessions students take on a more active role and must demonstrate the skills acquired to date in the relevant competences. Depending on the session, different activities will be performed, such as doing individual work, solving problems, etc. Attendance is mandatory.



Computer Practical: There will be two-hour biweekly sessions. Attendance is mandatory. In these hours, programs related to the subject matter presented in the lectures will be designed and implemented using the Mathematica symbolic calculation program.

• Final Assessment System
• Tools and qualification percentages:
  • See Guidelines and decline to sit (%): 100

The theoretical-practical competences of the subject will be evaluated through the following tests:



1. Final written exam, with theory, questions and problems on the theoretical contents of the course accounting for 80% of the final mark, to be taken on the date set in the official exam calendar.



2. Computer practical exam to be taken during week 15, for 10% of the final mark.



3. Partial written exam on the course to be taken during weeks 9-10, for 10% of the final mark.



To apply the above percentages it is necessary to have obtained 4 out of 10 on the final exam and to have performed all the computer practical assignments given in class.

There will be a final written exam on the date set in the official exam calendar in which all the theoretical and practical competences of the course will be evaluated.



This test will consist of two parts, which must be passed independently to be able to pass the course:



1. Examination of theory, with questions and problems on the theoretical contents of the course accounting for 90% of the final mark.



2. Practical computer exam and to have performed all the computer practical exercises, accounting for 10% of the final mark.



Students who have passed the Computer Practical part of the ordinary call and are satisfied with their mark do not need to take the computer practical exam.

Lecture notes and example, exercise and computer programming sheets

Basic bibliography

AKRITAS, A.G. Elements of computer algebra with applications, John Wiley and Sons, New York, 1989.

BRESSOUD, D.M. Factorization and primality testing, Springer-Verlag, New York, Iberoamericana, Wilmington, 1989.

HILL, R. A first course in coding theory. Ed. Clarendon Press, 1986.

HOFFSTEIN, J, PIPHER, J, SILVERMAN, J.H. An introduction to mathematical cryptography, Springer Science+Business Media, LLC, 2008.

MUNUERA, J., TENA, J. Codificación de la Información. Universidad de Valladolid, Secretariado de Publicaciones e Intercambio Científico, 1997.

ROMAN, S. Coding and Information Theory, Springer-Verlag, New York, 1992.

STINSON, R. S. Cryptography Theory and Practice, 2nd. ed., Chapman and Hall, Boca Raton, 2002.

In-depth bibliography

KOBLITZ, N. A course in number theory and cryptography. Ed. Springer-Verlag.
MENEZES, A.J., VAN OORSCHOT, P.C., VANSTONE, S.A. Handbook of applied cryptography CRC Press.
SMART, N. Cryptography: an introduction. Ed. McGraw-Hill.
VAN LINT, J.H., VAN DER GEER, G. Introduction to coding theory and algebraic geometry. Ed. Birkhäuser.
VAN LINT, J.H. Introduction to coding theory. Ed. Springer-Verlag.

Journals

Web addresses

GARCIA, M.A., MARTINEZ, L., RAMÍREZ, T. Introducción a la Teoría de Códigos. https://ocw.ehu.eus/course/view.php?id=446
QUIROS, A. La Teoría de Códigos: una introducción a las Matemáticas de la transmisión de información http://www.grupoalquerque.es/ferias/2012/archivos/pdf/teoriacodigos.pdf