Introducción a la Criptografía Moderna CC5301 (2012/01)
Profesor: Alejandro Hevia
Propósito: El propósito del curso es dotar al estudiante de herramientas de análisis para diseñar y evaluar formalmente algoritmos y protocolos criptográficos
tales como sistemas de encriptación simétrica y asimétrica, esquemas de
firmas digitales, entre otros.
Aspectos administrativos:
Cátedra: Miércoles, Viernes 10:15am-11:45am, [Sala por anunciar]
Auxiliar: Lunes 10:15am-11:45am, [Sala por anunciar]
Sitio web oficial (especialmente el Foro de Discusión): ucursos
Carga académica: 10 UD,
Requisitos: (CC30A, CC30B, MA34A) o (MA47A), o Autorización (por revisar)
Carácter del curso: electivo Cs. de la Computación
Novedades
Material de lectura del curso
Se recomienda suplementar el material de cátedra con los
siguientes libros:
Sin embargo, los textos anteriores pueden no cubrir toda la materia discutida en clases.
Calendario de lectura del curso
Estas lecturas son altamente recomendadas para las clases de cátedra/
auxiliares indicadas.
- Semana 12 de Marzo 2012: capítulos 1 y 2 de [BR-pre]
(Introducción y
Criptografía clásica).
Y capítulos 1 y 2 del libro de KL
- Semana 19 de Marzo 2012: capítulos 2 de [BR-pre]
y capítulos 3.1 del libro de [KL]
- Semana 26 de Marzo 2012: capítulos
3 (block ciphers) y
4 (pseudo-random functions) de [BR-pre]
(también ver capítulos
3 y
4 de
los apuntes de postgrado de [BR-post]).
Capítulo 5 y 3 del libro de [KL]
- Semana 2 de Abril 2012: capítulos sobre PRF en [BR], esto es
el 4 en [BR-pre], y el 3 en [BR-post]. En [KL] ver
Capítulos 3.6.1., 3.6.3 y 5.
- Semana 9 de Abril 2012: capítulos 4 y 5 del [BR-pre]
y/ó 3 y 4 del [BR-post].
Capítulo 3 entero (Privacidad de Encriptación simétrica)
del libro de [KL]
- Semana 16 de Abril 2012: capítulo
4 del [BR-post].
Secciones 3.5,3.6,3.7 (Privacidad de Encriptación simétrica)
del libro de [KL]
- Semana 23 de Abril 2012:
capítulo
5 del [BR-post],
Sección 4.6 (Funciones de Hash) del libro de [KL]
- Semana 30 de Abril 2012:
capítulo
5 y
6 del [BR-post],
Sección 4.6 (Funciones de Hash) del libro de [KL]
- Semana 7 de Mayo 2012:
capítulo
6 del [BR-post],
Capítulo 4 (MACs) del libro de [KL]
- Semana 14 de Mayo 2012: capítulos
9 y
10 (secciones 10.1 y 10.2, excepto 10.2.2) del [BR-post],
Sección 7.1 (excepto 7.1.4 y 7.1.5), 7.2, 7.2.1, 7.2.2, 7.3, 8.2, 8.2.1, 8.2.4 del libro de [KL]
- Semana 28 de Mayo 2012: capítulos
10 (seccion 10.2.2) y
11 del [BR-post].
Sección 7.1 (excepto 7.1.4 y 7.1.5), 7.2, 7.2.1, 7.2.2, 7.3, 8.2, 10.1,10.2,10.5, 10.6 del libro de [KL]
Tareas
- Tarea 1: fecha entrega Lunes 23 de Abril, 23:59hrs. Disponible en (PDF).
- Tarea 2: fecha entrega Lunes 21 de Mayo, 23:59hrs. Disponible en (PDF).
Temario
- Elementos Básicos:
- Introducción
- Conceptos Básicos: objetivo de seguridad (privacidad,
autentificación), adversarios, recursos.
Seguridad demostrable como una reducción.
- Criptografía Clásica (cifrados de sustitución
y variantes, ataques). One-time pad y seguridad perfecta, limitaciones.
- Criptografía Simétrica (Clave Privada):
- Cifradores de Bloque: Modelos, construcciones (DES, AES)
- Funciones Pseudo-aleatorias
- Encriptación Simétrica: Modelos de seguridad,
construcciones basadas en cifradores de bloque
- Funciones unidireccionales y resistentes a colisiones:
potenciales candidatos (MD5, SHA-1, SHA-256, otros), modelos de
seguridad, el ataque de los cumpleaños
- Autentificación de Mensajes: modelos y construcciones
(CBC-MAC, HMAC, UMAC, CMAC, y otros)
- Criptografía Asimétrica (Clave Pública):
- Teoría de Números Computacional
- Primitivas basadas en teoría de números
- Encriptación Asimétrica
- Firmas Digitales
- Criptografía en la Práctica:
- Infraestructura de Clave Pública (PKI)
- Autentificación e identificación (passwords),
vía terceras partes confiables (Needham-Schroeder, Kerberos)
- Acuerdo de Claves: Diffie-Hellman y intercambio de claves
autentificado (AKE).
- Canales seguros (SSL y Encriptación autentificada)
- Problemas al implementar algoritmos criptográficos
- Tópicos Avanzados (si el tiempo lo permite)
- Mecanismos para compartir secretos (Secret Sharing)
- Generación de bits pseudo-aleatorios
- Introducción a demostraciones interactivas y
protocolos de Nula Divulgación (Zero Knowledge)
- Introducción a protocolos criptográficos
genéricos (Computación Multi-partita Segura,
Votación Electrónica)
Evaluación:
La evaluación se basa en un control, un proyecto y un exámen
(con apuntes) más varias (entre 3 y 4) tareas cortas.
El proyecto es desarrollado durante el semestre.
Posibles alternativas para el proyecto incluyen
- Desarrollo teórico de un sistema criptográfico (con seguridad demostrable)
para algún problema propuesto por el estudiante o el profesor,
- Diseño o implementación de un ataque criptoanalítico
reciente, o de un software criptográfico novedoso.
- Escritura y presentación de un artículo corto tipo
estado del arte,
discusión de artículo reciente, o
investigación en algún tema relativo al curso.
Temas para Posibles Proyectos
- Survey on tecnicas y ataques usando
"related-key
attacks", más info en
este paper
o en
ésto.
- Survey de leakeage-resilient cryptography.
- Survey de ataques sobre hash functions actuales.
Incluir discusión respecto a cómo se
diseñó, las otras funciones de hash
actualmente discutidas para el
nuevo estándar,
detalles y ataques.
- Hacer un resumen, explicar, y quizas sugerir mejoras al paper
de cómo implementar PRF a partir de funciones
aún más débiles que PRF.
- Programa que detecta idioma de un texto, si está
comprimido, si es un ejecutable, imagen, etc., sin estar
necesariamente depender de que exista header de formato
Proyectos ya asignados:
- Estado del arte e implementación de un sistema
para demostrar entre dos participantes que es posible recuperar
un cierto archivo muy grande sin enviar el archivo.
Referencia.
Asignado: Francisco Plana.
- Estudiar, mejorar y/o implementar el ataque de
Bleichenbacher
de texto cifrado escogido ante RSA. Mejorarlo a 15 mil ataques.
Ver este
video donde explican el ataque (no dan muchos detalles, pues el ataque
al parecer no ha sido publicado).
O implementar este otro, similar.
Lo otro es ver un ataque del mismo estilo para
obtener PINs
encriptado con RSA en tarjetas
inteligentes. Asignado: Nicolas Ulriksen.
- Reimplementar ataque basado en factores comunes
en los módulos RSA de clave públicas de empresas
que hacen factura electrónica o que tienen en certificados
emitidos por autoridades certificadoras locales.
Se denomina ataque de
módulos de RSA. El
paper original describe el ataque en detalle.
Más info acá. Asignado: Jorge Bahamondes.
- Calculadora criptográfica: debe permitir ingresar
números p y n, donde el primero es un primo (verificar)
si ya compuesto, y luego calcular
suma, multiplicación, etc. en GF(2^m).
Debe calcular inversos, generadores en grupos cíclicos
(mod p), así como cálculos simples
en enteros mod p, raíces cuadradas mod p.
También debe poder testear si un entero es residuo
cuadrático (mod p o mod n) o no.
Asignado: (por confirmar nombre...).
- Survey de fully homomorphic encryption,
resultados recientes,
variantes,
críticas,
implementaciones, etc. No es necesario incluir el artículo original
de Gentry [es difícil, puede ayudar ver
su tesis], pero si debiera incluir artículos
como el de difusión
en la revista ACM (altamente recomendado), o la charla de Eurocrypt 2010 de título
"Fully homomorphic encryption over the integers" de M. van Dijk,
C. Gentry, S. Halevi, and V. Vaikuntanathan. También los
challenges (o "desafíos") que apoyan la idoneidad de los
supuestos criptográficos (ver challenges).
Asignado: Pablo Muñoz.
- Implementar un esquema eficiente de firmas transitivas de grafos
(recientemente propuesto). Asignado: Matías Ibáñez.
- Hacer un estado del arte de votación electrónica verificable.
Asignado: Javiera Born.
Tareas
Las tareas consistirán en demostraciones y resolución de
problemas, tanto teóricos como relativos a implementaciones en software.
Nota Magister y Doctorado: La opción (3.)
arriba es la alternativa
sugerida para estudiantes
de Magister o Doctorado tomando el curso. Dependiendo del caso y
del alcance del proyecto, estudiantes de postgrado podrán
convalidar la nota del proyecto como nota simultánea de
proyecto y tareas. Tal convalidación debe ser aprobada
por el profesor al momento de presentar el tema del proyecto.
Notas y situación final
Dada la nota de control C1, notas de las n>=3 tareas T1,T2,..,Tn, la nota del proyecto NProyecto, y la
nota del examen Ex, la ponderación será la siguiente:
- NC = (C1+NProyecto + EX)/3
- NT = (NT1+.. +NTn)/n
- NF = 0,7*NC + 0,3*NT
El examen no reemplazaró la nota de control (C1).
Para aprobar el curso se requiere:
- NC≥4.0
- NProyecto ≥ 4.0
- NT ≥ 4.0
Bibliografía:
- Mihir Bellare y Phil Rogaway, “Introduction to Cryptography, Lecture Notes”, University of California San Diego, 2006.
(Disponible en versiones del curso para
pregrado, y de
postgrado) Se recomienda revisar ambos.
- J. Katz and Y. Lindell.
Introduction to Modern Cryptography, Chapman & Hall/CRC Press, 2007.
Disponible en biblioteca. Ver la errata y la sec. 4.6.3
revisada.
- J. Katz, Digital Signatures, Springer, 2010
- Douglas Stinson, “Cryptography, Theory and Practice”, Second edition, Editorial Cgapman and Hall/CRC, 2002
- Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, “Handbook of Applied Cryptography”, CRC press, 1997.
Disponible
gratis!.
- Oded Goldreich, “Foundations of Cryptography, Basic Tools”, Cambridge University Press, 2001
- Oded Goldreich, “Foundations of Cryptography, Basic Applications”, Cambridge University Press, 2004
- Josef Pieprzyk, Thomas Hardjono, Jennifer Seberry, “Foundamentals of Computer Security”, Springer, 2003
Última modificación: 13 de Abril 2012.
|