Códigos Correctores e Criptografía

Coñecer algunhas das aplicacións máis importantes das matemáticas ás TIC, en particular á transmisión precisa e segura da información.

Manexar as nocións e métodos básicos da teoría de códigos correctores de erros e da criptografía e tamén os algoritmos fundamentais destas disciplinas.

Coñecer as familias de códigos máis importantes e algunhas das súas aplicacións máis interesantes (transmisións a longa distancia, discos compactos, etc.).

Comprender a noción de seguridade para esquemas criptográficos e tamén algúns dos máis importantes ataques criptoanalíticos e as técnicas utilizadas para rexeitalos.

Manexar implementacións en SageMath de algúns dos máis importantes algoritmos da teoría de códigos e da criptografía.

1. Introdución á teoría de códigos. (4 h. expositivas)
Ideas básicas sobre a teoría de códigos. Algúns exemplos: códigos de barras, ISBN, NIF ...

2. Códigos detectores e correctores de erros. (5 h. expositivas)
Canles ruidosos. Regras de decisión. Distancia de Hamming e descodificación por distancia mínima. Códigos perfectos. O problema principal da teoría de códigos.

3. Códigos lineares. (5 h. expositivas)
Matrices xeratrices e de control. Descodificación para códigos lineares. Descodificación por síndrome.

4. Tipos especiais de códigos lineares. (6 h. expositivas)
Códigos de Hamming. Códigos de Golay. Códigos de Reed-Muller. Algunhas aplicacións (telefonía, transmisións desde sondas espaciais, etc.). Introdución ós códigos cíclicos. Os códigos que se usan nos CD.

5. Introdución á criptografía. (5 h. expositivas)
Criptografía, criptoloxía e criptoanálise. Criptosistemas clásicos e a súa criptoanálise. A cifra de Vigenère e o índice de coincidencia.

6. Seguridade criptográfica. (5 h. expositivas)
Seguridade incondicional. O caderno de uso único. Introdución á complexidade computacional. Seguridade computacional.

7. Criptosistemas de bloques. (5 h. expositivas)
O "Advanced Encryption Standard" (AES). Os modos de operación. Autenticación por medio de MAC's.

8. Teoría de números algorítmica e criptografía de clave pública. (7 h. expositivas)
Algoritmos básicos. Primalidade, factorización e logaritmos discretos. Funcións de dirección única. O intercambio de Diffie-Hellman. O criptosistema RSA. Sinaturas dixitais.

Bibliografía básica

Gómez Pardo, J.L. Introduction to Cryptography with Maple. Springer, 2013.
Trappe, W. and Washington, L.C. Introduction to Cryptography with Coding Theory. Prentice-Hall, 2002.

Bibliografía complementaria

Bard, G.V., SageMath for Undergraduates, dispoñible en http://www.gregorybard.com/SAGE.html
Buchmann, J.A. Introduction to Cryptography, 2nd. Edition. Springer, 2004.
Gómez Pardo, J.L. and Gómez-Rodríguez, C. The Advanced Encryption Standard and its modes of operation,
(dispoñible en https://www.maplesoft.com/applications/app_center_view.aspx?AID=2286).
Gómez Pardo, J.L. Linear Codes and Syndrome Decoding,
(dispoñible en https://www.maplesoft.com/applications/view.aspx?SID=154536).
Hoffstein, J., Pipher, J. and Silverman, J.H. An Introduction to Mathematical Cryptography, 2nd. Edition. Springer, 2014.
Lidl, R. and Pilz, G. Applied Abstract Algebra, 2nd Ed., Springer, 1998.
Roman, S. Coding and Information Theory, Springer, 1992.

Contribuír a acadar as competencias xerais, específicas e transversais recollidas na Memoria do Título de Grao en Matemáticas da USC e, en especial, as seguintes:
- Comunicación escrita e oral de coñecementos, métodos e ideas xerais relacionadas coas matemáticas e as TIC (CG4).
- Utilizar ferramentas de procura de recursos bibliográficos sobre os temas da materia, incluíndo o acceso por Internet. Manexar ditos recursos en diferentes idiomas, especialmente en inglés (CT1, CT5).
- Utilizar programas informáticos para resolver problemas e implementar algoritmos (CE8, CE9).
- Comprender o papel das matemáticas como unha ferramenta de ampla aplicabilidade (CG2).

Competencias específicas da materia:

- Familiarizarse cos códigos básicos de identificación: NIF, ISBN, códigos de barras ...
- Coñecer os principios xerais usados no deseño de "bos códigos".
- Manexar os códigos lineares por medio do cálculo de matrices xeratrices, matrices de control, distancia mínima, etc.
- Construír a táboa estándar, realizar a descodificación por síndrome e utilizar os procedementos específicos de descodificación para códigos de Hamming e de Golay.
- Saber criptoanalizar sistemas clásicos: substitucións monoalfabéticas, criptosistema de Vigenère e criptosistema de Hill.
- Coñecer polo miúdo o funcionamento do AES e os seus modos de operación, utilizando diversas implementacións existentes.
- Manexar os algoritmos básicos necesarios para a implementación de RSA, en particular, o algoritmo de Euclides e a expoñenciación binaria.
- Comprender a importancia dos esquemas de autenticación e sinatura dixital e a súas aplicacións (DNI electrónico, etc.).
- Saber utilizar SageMath para explorar algúns dos algoritmos mais importantes da teoría de códigos e da criptografía. En particular, algúns dos códigos mais importantes e a súa descodificación, experimentos sobre a distribución dos números primos, test de Miller-Rabin, etc.

Seguiranse as indicacións metodolóxicas xerais que figuran na Memoria do Título de Grao en Matemáticas da USC.
A docencia impartirase en clases expositivas, clases con ordenador e titorías con e sen ordenador, ademais de titorías en grupos moi reducidos.

Nas clases, presentaranse os contidos esenciais da materia, resolveranse problemas e proporanse as actividades que o alumnado deberá realizar para a avaliación continua: resolución de problemas, elaboración de traballos,... (competencias CB3, CB4, CG1, CG2, CG4, CG5, CT1, CT5). Nas clases e titorías con ordenador utilizarase SageMath como ferramenta de traballo (competencias CE8, CE9).

Haberá dous cursos online, un no campus virtual da USC (na actualidade sobre Moodle) e outro en CoCalc. O primeiro, con materiais e recursos relativos ás clases expositivas, servirá tamén para canalizar as comunicacións, as propostas e entregas de tarefas así como a realización de probas de auto-avaliación e avaliación continua, tanto individuais coma en grupos. O segundo será utilizado para compartir prácticas e proxectos, supervisar e asistir nas clases interactivas e titorías, así como para realizar probas de avaliación con ordenador.

Para o cómputo da cualificación final (F) terase en conta a avaliación continua (C) e a cualificación do exame final (E) e aplicarase a seguinte fórmula:

F = max{E, 0.40*C+0.60*E}

Para a avaliación continua terase en conta as tarefas e probas desenvolvidas ao longo do curso: dous boletíns de problemas, cos correspondente controles de autoría) e unha práctica presencial con ordenador, todas elas comúns para todos os grupos. A participación nas clases expositivas e interactivas de laboratorio e nas titorías poderá ser valorada con ata + 1 punto. A nota da avaliación continua tamén será tida en conta na segunda oportunidade co mesmo peso na nota global.

O exame final terá dúas partes: unha escrita, de teoría e problemas, (2/3 da nota) e outra con ordenador (1/3 da nota) e será necesario acadar un mínimo do 40% en cada parte e ter F >= 5 para superar a materia.

No exame final avaliaranse as competencias recollidas na memoria do Grao, con especial atención a CG4, CG5, CT1 e CT5. Na avaliación continua avaliaranse CB3, CB4, CG2, CG4, CG5, CT1, CT5, CE8 e CE9. A cualificación de "non presentado" será outorgada a quen non se presente a ningunha das partes do exame final.

Para o caso de realización fraudulenta de exercicios ou probas será de aplicación o recollido na Normativa de avaliación do rendemento académico dos estudantes e revisión de cualificacións, en particular o recollido no artigo 16:
A realización fraudulenta dalgún exercicio ou proba esixida na avaliación da materia implicará a cualificación de suspenso na convocatoria correspondente, con independencia do proceso disciplinario que se poida seguir contra a persoa infractora.

Seguindo as directrices establecidas na Memoria do Título de Grao en Matemáticas da USC, o tempo que o alumnado deberá dedicar á preparación da materia consiste en:

+ 58 horas de traballo presencial:

- 42 horas en clases expositivas
- 14 horas en clases interactivas de laboratorio
- 2 horas de titorías en grupos moi reducidos

+ 92 horas de traballo persoal que comprenden as seguintes actividades:

- Estudo autónomo: 50 horas.
- Elaboración de traballos e resolución de problemas: 20 horas.
- Traballos con ordenador: 15 horas.
- Búsqueda de documentación: 3 horas.
- Probas de avaliación: 4 horas.

As materias que se aconsella ter cursado previamente son: Linguaxe matemática, conxuntos e números; Álxebra linear e multilinear; Estructuras alxébricas.
En xeral, é aconsellable ter asimilados os coñecementos matemáticos incluídos nas materias do primeiro curso da Titulación.

Recoméndase a asistencia e participación activa nas clases e titorías programadas, complementada co traballo diario para asimilar os conceptos da materia e realizar as actividades (problemas, traballos) que se irán propoñendo periodicamente.