1
GUÍA DE APRENDIZAJE
CODIFICACIÓN DE LA INFORMACIÓN
GRADUADO EN INGENIERÍA DE
COMPUTADORES
DATOS DESCRIPTIVOS1
CENTRO RESPONSABLE E.U. de Informática
OTROS CENTROS
IMPLICADOS
CICLO Grado sin atribuciones
MÓDULO
MATERIA: Optativa
ASIGNATURA: CODIFICACIÓN DE LA INFORMACIÓN
CURSO: 4º
DEPARTAMENTO
RESPONSABLE
MATEMÁTICA APLICADA (ESCUELA
UNIVERSITARIA DE INFORMÁTICA)
CRÉDITOS EUROPEOS: 6
CARÁCTER: Optativa
ITINERARIO:
CURSO ACADÉMICO: 2012/2013
PERIODO DE
IMPARTICIÓN: Primer Semestre (Septiembre-Enero)
IDIOMAS IMPARTICIÓN: Español
OTROS IDIOMAS DE
IMPARTICIÓN:
HORAS/CRÉDITO 26
1 Paso 0 en la aplicación EUROPA
2
PROFESORADO2
NOMBRE Y APELLIDOS
DESPACHO Correo electrónico EN INGLÉS
ANA ISABEL LIAS QUINTERO (COORDINADORA)
2005/6108 [email protected] No
ALFONSA GARCIA LOPEZ 2105 [email protected] No
TUTORÍAS
NOMBRE Y
APELLIDOS
TUTORÍAS
LUGAR DÍA DE A
ANA ISABEL LIAS QUINTERO
2005/6108 6h. a determinar en septiembre
ALFONSA GARCIA LOPEZ
2105 6h. a determinar en septiembre
GRUPOS
Nº de Grupos3
GRUPOS ASIGNADOS EN:
Teoría 1
Prácticas 0
Laboratorio 1
REQUISITOS PREVIOS NECESARIOS4
ASIGNATURAS
SUPERADAS:
OTROS REQUISITOS
CONOCIMIENTOS PREVIOS RECOMENDADOS
ASIGNATURAS PREVIAS
RECOMENDADAS:
Haber superado las asignaturas
Matemática Discreta
Álgebra
2 Paso 2 en la aplicación EUROPA.
Si no se sabe el horario de tutorías, poner sólo el despacho. 3 Los grupos son de teoría y/o de laboratorio (no de prácticas).
4 Paso 3 en la aplicación EUROPA
3
CONOCIMIENTOS
PREVIOS
OTROS CONOCIMIENTOS o Manejar con soltura la aritmética modular y el cálculo matricial.
o Entender y hacer demostraciones matemáticas sencillas.
4
COMPETENCIAS5
CÓDIGO COMPETENCIA NIVEL RA
E6 Capacidad para comprender, aplicar y gestionar la garantía y seguridad de los sistemas informáticos.
N1 RA_01
G1 Comunicación oral y escrita. N2 RA_02
G10 Capacidad de análisis y síntesis. N2 RA_03 RA_04
G14 Resolución de problemas. N2
RA_05 RA_06 RA_07 RA_10 RA_12
G7 Uso de Tecnologías de la Información y de las Comunicaciones. N2 RA_09 RA_13
G8 Trabajo en equipo. N2 RA_08
I1
Capacidad para la resolución de los problemas matemáticos que puedan plantarse en la ingeniería. Aptitud para aplicar los conocimientos sobre: algebra, cálculo diferencial e integral y métodos numéricos; estadística y optimización.
N2 RA_04 RA_05 RA_11
I12 Conocimiento y aplicación de los procedimientos algorítmicos básicos de las tecnologías informáticas para diseñar soluciones a problemas, analizando la idoneidad y complejidad de los algoritmos propuestos.
N1 RA_04
I13 Conocimiento, diseño y utilización de forma eficiente los tipos y estructuras de datos más adecuados a la resolución de un problema.
N1 RA_09 RA_13
I3
Capacidad para comprender y dominar los conceptos básicos de matemática discreta, lógica, algorítmica y complejidad computacional, y su aplicación para el tratamiento automático de la información por medio de sistemas computacionales y su aplicación para la resolución de problemas propios de la ingeniería.
N3
RA_05 RA_06 RA_07 RA_11
I7
Capacidad para diseñar, desarrollar, seleccionar y evaluar aplicaciones y sistemas informáticos, asegurando su fiabilidad, seguridad y calidad, conforme a principios éticos y a la legislación y normativa vigente
N1 RA_09
RESULTADOS DE APRENDIZAJE
CÓDIGO DESCRIPCIÓN
RA_01 Utiliza los distintos tipos de codificación de la información según el objetivo perseguido (corregir errores, encriptar información o comprimirla)
RA_02 Distingue y conoce criptosistemas de clave pública y clave privada. RA_03 Cifra y descifra utilizando los criptosistemas de traslación, afín y matricial afín. RA_04 Cifra y descifra utilizando los criptosistemas RSA y ElGamal.
RA_05 Conoce y aplica protocolos de autenticación (firma digital) e intercambio de claves basados en criptosistemas de clave pública
RA_06 Codifica, detecta y corrige errores utilizando los códigos lineales. RA_07 Conoce y aplica test de primalidad deterministas y probabilísticos. RA_08 Comprime ficheros, usando códigos compresores adecuados.
RA_09 Utiliza adecuadamente software para la resolución de problemas de codificación de la información.
RA_10 Conoce la complejidad computacional de las operaciones aritméticas elementales y es capaz de determinar la de ciertos algoritmos sencillos.
RA_11 Describe con precisión protocolos de codificación de la información
RA_12 Distribuye adecuadamente las tareas para trabajo en equipo, realiza las tareas encomendadas y asume el principio de corresponsabilidad.
RA_13 Desarrolla aplicaciones criptográficas utilizando los recursos disponibles conforme a la legislación vigente y siguiendo principios éticos.
5 Paso 4 y 5 en la aplicación EUROPA. Hay que poner un RA por cada competencia que tenga
la asignatura en el Plan de Estudios. Imprescindible poner todas las competencias.
5
INDICADORES DE LOGRO6
CÓDIGO INDICADOR RA
IN_01 Distingue distintos tipos de códigos según el objetivo perseguido RA_03
IN_02 Define con precisión criptosistema, criptograma, texto en claro y longitud de un mensaje.
RA_10
IN_03 Obtiene el equivalente numérico de un mensaje. RA_05 RA_06 RA_13
IN_04 Cifra y descifra mensajes utilizando los criptosistemas de traslación, afín y matricial afín.
RA_05 RA_13
IN_05 Realiza ataques a criptogramas mediante análisis de frecuencias para cifradores monoalfabéticos y ataques a texto en claro conocido para los criptosistemas de traslación, afín y matricial afín.
RA_05 RA_13
IN_06 Define complejidad en tiempo y en espacio de un algoritmo. RA_04
IN_07 Calcula la complejidad, en número de operaciones bit, de cálculos y bucles sencillos.
RA_04
IN_08 Distingue la complejidad de un problema y la de un algoritmo RA_04
IN_09 Conoce y aplica el algoritmo de exponenciación (modular) rápida. RA_04
IN_10 Conoce la función Phi de Euler y la evalúa de modo eficiente, usando sus propiedades.
RA_06
IN_11 Conoce y aplica correctamente los teoremas de Euler y Fermat. RA_06
IN_12 Obtiene raíces primitivas módulo n en casos sencillos. RA_06
IN_13 Conoce y aplica el protocolo de intercambio de claves de Diffie-Hellman. Aplica las propiedades de los códigos de Huffman para la comprensión de archivos.
RA_01 RA_13
IN _14 Cifra y descifra mensajes numéricos mediante los criptosistemas de ElGamal y RSA.
RA_06 RA_13
IN_15 Aplica correctamente el criptosistema RSA en protocolos de firma digital. RA_01 RA_13
IN_16 Comprueba la primalidad de un número aplicando de modo eficiente test deterministas.
RA_11 RA_13
IN_17 Conoce la diferencia entre test de primalidad deterministas y probabilísticos.
RA_11
IN_18 Conoce y aplica los test de primalidad de Fermat, de Miller y de Miller-Rabin.
RA_11 RA_13
IN_19 Reconoce las propiedades de un código lineal binario como espacio vectorial
RA_07
IN_20 Conoce la relación entre matriz generadora y matriz de control de un código lineal binario.
RA_07 RA_13
IN_21 Detecta y corrige errores aplicando códigos lineales adecuados. RA_07 RA_13
IN_22 Implementa algoritmos para la corrección de errores mediante códigos de Hamming.
RA_07 RA_13
IN_23 Aplica las propiedades de los códigos de Huffman para la comprensión de archivos.
RA_12
IN_24 Cumple las tareas de trabajo en grupo en tiempo y forma RA_08
IN_25 Redacta con claridad, sin faltas de orttografía y respetando las especificaciones los protocolos cripotográficos que utiliza
RA_02
IN_26 Respeta la legislación vigente en el desarrollo de aplicaciones RA_09
6 Paso 6 en la aplicación EUROPA
6
CONTENIDOS ESPECÍFICOS (TEMARIO)7
TEMA APARTADOS LOGRO
Tema 1 Introducción a la Codificación de la información y Criptología
1.1 Trasmisión de la Información.
1.2 Tipos de Códigos.
1.3 Introducción a la Criptología: Criptografía y Criptosistemas.
1.4 Criptosistemas de clave secreta: traslación, afín y matricial.
1.5 Criptoanálisis.
Tema 2 Complejidad computacional
2.1 Problemas, algoritmos.
2.2 Complejidad de las operaciones aritméticas elementales.
2.3 Clasificación de problemas según su complejidad.
Tema 3 Teoría de números
3.1 El grupo multiplicativo de las unidades módulo n.
3.2 Función φ de Euler.
3.3 Teoremas de Euler y Fermat.
3.4 Orden de un elemento. Raíz primitiva módulo n.
3.5 Logaritmo discreto.
Tema 4 Criptosistemas de clave pública
4.1 Protocolo de intercambio de claves de Diffie- Hellman
4.2 Criptosistema RSA.
4.3 Criptosistema El Gamal.
4.3 Firma digital.
4.4. Otras aplicaciones de la criptografía de clave pública.
Tema 5 Test de primalidad
5.1 Test deterministas: Criba de Eratóstenes y Divisiones sucesivas.
5.2 Test probabilísticos: Test de Fermat, de Miller y de Miller-Rabin.
Tema 6 Códigos correctores de errores y códigos compresores
6.1 Códigos lineales. Códigos de Hamming.
6.2 Códigos de redundancia cíclica.
6.3 Códigos de Huffman.
7 Paso 7 en la aplicación EUROPA
7
BREVE DESCRIPCIÓN DE LAS MODALIDADES ORGANIZATIVAS UTILIZADAS
Y MÉTODOS DE ENSEÑANZAS EMPLEADOS8
MODALIDAD DESCRIPCIÓN MÉTODO MÉTODOS DE
ENSEÑANZA
CLASES DE
TEORÍA
Se trata de clases magistrales participativas en las que se presentan conceptos, resultados y ejemplos.
CLASES DE TEORÍA
CLASES
PROBLEMAS
En ellas los estudiantes, siguiendo las indicaciones del profesor, resolverán individualmente o en grupo un conjunto de problemas de cuyos enunciados disponen con antelación.
CLASES PROBLEMAS
PRÁCTICAS Están previstas seis sesiones de 2 horas de trabajo en laboratorio. Se usará el sistema de cálculo matemático Maple para programar algoritmos y resolver problemas relacionados con los objetivos del curso.
PRÁCTICAS
TRABAJOS
AUTÓNOMOS
Los estudiantes realizarán de modo autónomo las siguientes tareas: a) Estudiar conceptos y propiedades.
b) Resolver ejercicios y problemas.
c) Responder cuestionarios on-line.
TRABAJOS
AUTÓNOMOS
TRABAJOS
EN GRUPOS
Los alumnos deberán realizar cuatro trabajos en grupos de dos personas sobre distintos temas del curso, en los que deberán programar en Maple diversos algoritmos y usarlos para resolver los problemas que se les señalen en las especificaciones de cada trabajo.
TRABAJOS EN GRUPOS
TUTORÍAS Salvo que surja una necesidad concreta, sólo se contemplan tutorías individuales en el horario establecido por cada profesora.
8 Paso 10 de la aplicación EUROPA
8
CRONOGRAMA DE TRABAJO DE LA ASIGNATURA9
SEMANA Actividades Aula Laboratorio Trabajo
Individual
Trabajo en Grupo
Actividades
Evaluación
4 y 7 de septiembre
7-IX Presentación (programa y normas, 1h) Tema 1: Teoría (1h)
Estudiar T1 Ejercicios (prerrequisitos)
11 y 14 de septiembre
Tema 1: Teoría y problemas (2h)
P1: Introducción al sistema Maple. (2h.)
Estudiar T1 Hacer ejercicios Completar Práctica 1
18 y 21 de septiembre
Tema 1: Teoría y problemas (2h)
P2: Programación en Maple (2h.)
Preparar P2 Completar Práctica 2 Hacer cuestionarios T1
TG1 Cuestionario on-line T1
25 y 28 de septiembre
Tema 2: Teoría y problemas (4h)
Estudiar T2 Hacer ejercicios Hacer cuestionarios T2
TG1 EntregaTG1 (30-sept)
2 y 5 de octubre
Tema 2: Teoría y problemas (4h)
Estudiar T1 T2 Hacer ejercicios
Cuestionario on-line T2
9 de octubre
Prueba T1y T2 (1h.) Tema 3: Teoría y problemas (3h)
Estudiar T3 Hacer ejercicios
PE1(T1 y T2)
16 y 19 de octubre
Tema3: Teoría y problemas (2h)
P3: Construcción de librerías Maple (2h.)
Estudiar T3 Hacer ejercicios Completar Práctica 3
23 y 26 de octubre
Tema 3: Teoría y problemas (4h)
Estudiar T3 Hacer cuestionarios T3
Cuestionario on-line T3
9 Paso 8 en la aplicación EUROPA
9
SEMANA Actividades Aula Laboratorio Trabajo
Individual
Trabajo en Grupo
Actividades
Evaluación
30 de oct y 2 nov.
Tema 4: Teoría y problemas (4h)
Estudiar T4 Hacer ejercicios Hacer cuestionarios T4
TG2
6 de noviembre
P4: Criptosistemas de clave pública (2h.)
TG2 Cuestionario on-line T4
EntregaTG2 (11-nov)
13 y 16 de noviembre
Prueba T3 y T4 (1h)
Tema 5: Teoría (2h)
P5: Firma digital (1h) Estudiar T5
PE2 (T3 y T4)
Entrega P5 (18-nov)
20 y 23 de noviembre
Tema5: Teoría y problemas (3h)
Problemas del T5 con Maple (1h)
Estudiar T5 Hacer cuestionarios T5
TG3
27 y 30 de noviembre
Tema 5 (1 h): Problemas
Tema 6(1h)
P6: Práctica de Códigos (2h.)
Hacer ejercicios repaso Hacer cuestionarios T5
TG3 Cuestionario on-line T5
EntregaTG3 (2-dic)
4 de diciembre
Tema 6: Teoría y Problemas (2h)
Estudiar T6 Completar P6
EntregaP6 (9-dic)
10 y 14 de diciembre
Tema 6: Teoría y Problemas (4h)
Estudiar T6 Hacer ejercicios Hacer cuestionarios T5
Cuestionario on-line T6
17 y 21 de diciembre
Seminarios (3h)
Prueba T5 yT6 (1h)
PE3(T5 y T6)
10
11
CRITERIOS DE CALIFICACIÓN DE LA ASIGNATURA
CRITERIOS DE CALIFICACIÓN
PRUEBA DÍA LUGAR PESO
Cuestionarios on-line A lo largo del curso Moodle 10%
Prueba escrita sobre los temas 1 y 2 9-10-12 Aula 10%
Prueba escrita sobre los temas 3 y 4 13-11-12 Aula 15%
Prueba escrita sobre los temas 5 y 6 21-12-12 Aula 15%
Trabajo práctico: Criptosistemas de clave privada 8-10-12 Moodle 12%
Trabajo práctico: Criptosistemas de clave pública 19-11-12 Moodle 12%
Trabajo práctico: Test de primalidad 3-12-12 Moodle 12%
Práctica de Firma digital 18-11-12 Moodle 4%
Práctica de Códigos 9-12-12 Moodle 10%
DESCRIPCIÓN GENERAL DE LAS ACTIVIDADES QUE SE EVALÚAN Y DE LOS
CRITERIOS DE CALIFICACIÓN
Cuestionarios on line:
Los estudiantes podrán realizar un cuestionario on-line, con diez preguntas sobre cada tema del
curso. Cuando la calificación de dicho cuestionario sea superior a 7 se sumará 0.2 a la nota
final acumulada, hasta un máximo de un punto.
Pruebas escritas:
Se realizan en horario presencial y en ellas los estudiantes deben responder a cuestiones
teóricas y resolver ejercicios y problemas.
En la calificación, al menos el 70% corresponderá a logros de objetivos básicos y se exigirá
precisión en el lenguaje y rigor en la presentación de resultados.
Trabajo práctico: Criptosistemas de clave privada
Se realizará parejas y consistirá en programar en Maple el cifrador Matricial Afín e identificar
casos particulares. Los estudiantes deberán cifrar y descifrar algunos mensajes y criptoanalizar
varios textos, definiendo previamente una función Maple para hacer el análisis de frecuencias.
Valoración: Procedimientos definidos 50% (valorando eficiencia, claridad y documentación del
código), resolución de los ejercicios 40%, rigor matemático, elegancia en la presentación de
resultados y precisión en el lenguaje 10%.
Trabajo práctico: Criptosistemas de clave pública
Se realizará parejas y consistirá en hacer una librería Maple que incluya funciones para
generar claves cifrar y descifrar con el criptosistema ElGamal. Como material de apoyo, los
estudiantes dispondrán de una librería análoga para el criptosistema RSA.
Valoración: Procedimientos definidos 60%, construcción de la librería y páginas de ayuda
12
20%, realización de pruebas adecuadas 10%, rigor matemático, elegancia en la presentación de
resultados y precisión en el lenguaje 10%.
Trabajo práctico: Test de primalidad
Se realizará por parejas y consistirá en hacer una librería Maple con tres funciones que
implementen test de primalidad, hacer pruebas con números grandes y comparar tiempos de
ejecución.
Valoración: Procedimientos definidos 60%, construcción de la librería 10%, realización de
pruebas adecuadas 10%, análisis de los resultados 10%, rigor matemático, elegancia en la
presentación de resultados y precisión en el lenguaje 10%.
Entrega de las prácticas: Firma Digital y Códigos lineales
Consistirá en la entrega de dichas prácticas finalizadas, cuyo desarrollo inicial se hará en las
sesiones presenciales.
PARA LA ALTERNATIVA DE EVALUACIÓN MEDIANTE SÓLO PRUEBA FINAL Y
LA CONVOCATORIA EXTRAORDINARIA
Los alumnos que elijan la opción de examen único deberán solicitarlo antes del día 23 de
noviembre.
El examen final se realizará en la fecha marcada por la Jefatura de estudios (17/1/13) y tendrá
dos partes: una prueba escrita relativa a los contenidos teóricos de la asignatura (definiciones,
propiedades, ejercicios y problemas) y una práctica. El valor de cada una de estas dos pruebas
es del 50% de la nota final.
Para la parte práctica deberán traer una librería Maple, en la que hayan programado las
funciones más importantes con las que se trabaja a lo largo del curso, que usarán para resolver
los ejercicios que se les propongan. Dicha librería Maple contendrá al menos las funciones de
la tabla adjunta.
TABLA DE FUNCIONES PARA LA LIBRERÍA MAPLE (OPCIÓN EXAMEN FINAL) Funciones de criptografía simétrica
Función Parámetros de Entrada Salida
Cifra_Vigenère
Un mensaje, un alfabeto y una
palabra clave, todos ellos
expresados como tiras de
caracteres.
Criptograma resultante de cifrar el
mensaje con el algoritmo de
Vigenère y la clave dada.
Descifra_Vigenère
Criptograma, un alfabeto y una
palabra clave.
Texto en claro
Cifrador Matricial
Afín (Cma)
Un mensaje, un alfabeto, (tiras de
caracteres), una matriz cuadrada y
un vector de la misma dimensión.
Criptograma resultante de cifrar el
mensaje con el criptosistema
matricial afín y la clave dada.
Funciones de criptografía asimétrica Función Parámetros de Entrada Salida
mensaje_numérico Un mensaje y un alfabeto
(tiras de caracteres). Valor numérico del mensaje de acuerdo
con el alfabeto.
mensaje_texto Un número natural m, y
un alfabeto A. Mensaje cuyo valor numérico es m.
Genera_claves_RSA
Un entero k y un nombre
priv. Una clave pública RSA, construida a
partir de dos números primos p y q de k
dígitos.
La clave privada se almacenará en la
13
variable priv.
RSA (Función de
cifrado y descifrado)
Su primer argumento, m,
será un mensaje
(expresado como tira de
caracteres) o bien un
criptograma (expresado
como lista de naturales),
el segundo un alfabeto y
el tercero una clave RSA.
Si m es una tira de caracteres la función
lo divide en tiras de longitud adecuada,
codifica, con el algoritmo RSA, el valor
numérico de cada tira y devuelve el
criptograma, como lista de números
naturales.
Si m es una lista de naturales, la función
desencripta el criptograma y devuelve
el texto en claro.
Genera_claves_ELG
amal
Un entero k y un nombre
priv.
Una clave pública, para ElGamal ,
construida a partir de un primo aleatorio
de k dígitos.
La clave privada se almacenará en la
variable priv.
ElGamal
(Cifrado y
descifrado)
Su primer argumento, m,
es un mensaje (tira de
caracteres) o un
criptograma (lista de
pares de números
naturales).
El segundo un alfabeto y
el tercero una clave.
Si m es una tira de caracteres, la función
divide el mensaje en tiras del tamaño
adecuado, codifica, con el algoritmo
ElGamal, el valor numérico de cada tira
y devuelve el criptograma, que es una
lista de pares de números naturales.
Si m es una lista de pares de naturales,
la función desencripta el criptograma y
devuelve el texto en claro.
Funciones de test de primalidad Función Parámetros de Entrada Salida
Divisiones_sucesivas
Un número entero true o false
Si el número no es primo se mostrará el
primer divisor encontrado
Miller-Rabin Un número entero
Una cota de error
true o false según que el número pase el
test (puede ser primo) o no lo pase (no
es primo)
Si el número no es primo se mostrará un
certificado
Funciones de Códigos Correctores Función Parámetros de Entrada Salida
L_Síndrome
Un síndrome s (lista de 0's y 1's)
y una matriz generadora G (en
forma estándar)
El líder de la órbita
correspondiente
C_Hamming
Un entero r mayor o igual que 2 Matriz de control de un código de
Hamming binario de redundancia
r, con sus columnas ordenadas en
orden creciente de la
representación binaria
RECURSOS DIDÁCTICOS
14
TIPO DESCRIPCIÓN
BIBLIOGRAFÍA [1] Buchmann, Johannes A.: “Introduction to Cryptography”.
Second Edition. Springer-Verlag. 2004.
[2] Koblitz, Neal: “A Course in Number Theory and
Cryptography”. Second Edition. Springer-Verlag. 1994.
[3] Lucena, Manuel José: “Criptografía y Seguridad en Computadores”. 1999. wwwdi.ujaen.es/~mlucena
[4] Munuera, Carlos; Tena, Juan: “Codificación de la
Información”. Universidad de Valladolid. 1997.
[5] Ramió, Jorge: “Aplicaciones Criptográficas”. Escuela
Universitaria de Informática. U. Politécnica de Madrid. 1998.
[6] Rincón, Félix; García, Alfonsa; Martínez, Ángeles: “Cálculo
científico con Maple”. RA-MA. 1995.
[7] Trappe, Wade; Washington, Lawrence C.: “Introduction to
Crytography with Coding Theory”. Prentice-Hall. 2002.
RECURSOS WEB Entorno Moodle de la UPM:
http://moodle.upm.es/titulaciones/oficiales/
Contiene información y material de apoyo
EQUIPAMIENTO Instrumentación de Laboratorio: Ordenadores personales
Aplicaciones Software: Maple, Moodle