Guía de Aprendizaje - etsisi upm...IN_02 Define con precisión criptosistema, criptograma, texto en...

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).


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

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

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



P2: Programación en Maple (2h.)

Preparar P2 Completar Práctica 2 Hacer cuestionarios T1

TG1 Cuestionario on-line T1



Estudiar T2 Hacer ejercicios Hacer cuestionarios T2

TG1 EntregaTG1 (30-sept)

2 y 5 de octubre


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


Estudiar T3 Hacer cuestionarios T3



9

SEMANA Actividades Aula Laboratorio Trabajo

Individual

Trabajo en Grupo

Actividades

Evaluación

30 de oct y 2 nov.



TG2

6 de noviembre

P4: Criptosistemas de clave pública (2h.)


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)


Tema5: Teoría y problemas (3h)

Problemas del T5 con Maple (1h)

Estudiar T5 Hacer cuestionarios T5

TG3


Tema 5 (1 h): Problemas

Tema 6(1h)

P6: Práctica de Códigos (2h.)

Hacer ejercicios repaso Hacer cuestionarios 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)



17 y 21 de diciembre

Seminarios (3h)

Prueba T5 yT6 (1h)

PE3(T5 y T6)

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%



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

http://wwwdi.ujaen.es/~mlucena

http://moodle.upm.es/titulaciones/oficiales/

Guía de Aprendizaje - etsisi upm...IN_02 Define con precisión criptosistema, criptograma, texto en...

Documents

Transcript of Guía de Aprendizaje - etsisi upm...IN_02 Define con precisión criptosistema, criptograma, texto en...