Introduccion a la Criptografía Moderna CC51Q (2009/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.
Aspectos administrativos:
Cátedra: Martes, Jueves 4:15pm-5:45pm, [Sala por definir]
Auxiliar: Lunes 4:15pm-6:45pm, [Sala por definir]
Sitio web oficial (especialmente el Foro de Discusión): ucursos
Carga académica: 10 UD,
Requisitos: (CC30A, CC30B, MA34A) o (MA47A), o Autorización
Carácter del curso: electivo Cs. de la Computación
Novedades
- [31 de Marzo 2009] El listado de proyectos posibles está disponible.
- [31 de Marzo 2009] Cambio en fechas del proyecto:
- Elección y comunicación del proyecto al profesor:
7 de Abril 2009.
- Reporte de Avance: 23 de Abril 2009.
- [31 de Marzo 2009] Calendario de próximas lecturas está
actualizado.
- Importante: Escoger un proyecto y comunicarselo al profesor antes
del Martes 7 de Abril. Ver listado de proyectos
posibles.
- Fechas Importantes:
- Entrega Reporte de Avance proyecto: Jueves 23 de Abril, 2009
- Control 1: Jueves 14 de Mayo, 2009
Material de Lectura
Estas lecturas son altamente recomendadas para las clases de cátedra/
auxiliares indicadas.
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
(sin apuntes) má varias (entre 4 y 5) tareas cortas.
El proyecto es desarrollado durante el semestre.
Posibles alternativas para el proyecto incluyen
- Desarrollo de un software criptográfico (con informe) o
- 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
- Informe del estado del arte de técnicas
criptoanalíticas (del tipo criptoanálisis
diferencial) para cifradores de bloque.
En que consisten las últimas técnicas y
sus resultados (mejores ataques) sobre algunos de los cifradores
populares o más recientes.
Preliminarmente asignado: Francisca.
- Criptografía cuántica: qué es, cómo
funciona, estado actual de los computadores cuánticos.
Preliminarmente asignado: Felipe Chacón.
- Estado del arte de los algoritmos criptográficos sobre
computadores cuánticos (incluyendo explicacion del
algoritmo de Shor para factorizar). Revisión de
qué algoritmos pueden quebrar computadores cuánticos
y cuáles (se conjetura) que no.
Preliminarmente asignado: Andres Abeliuk.
- Estado del arte de funciones de hash criptográficas.
Propuestas recientes,
ataques, modelos de seguridad.
Referencia 1 y
Referencia 2.
Preliminarmente asignado: Liliana Alcayaga.
- Estado del arte de (o implementación de algún)
algoritmos para extraer y expandir
aleatoriedad. Estos algoritmos toman uno o más strings
provenientes
de una fuente de aleatoriedad pobre y devuelven strings cuya
distribución es cercana a uniforme. Un uso posible
es 'hashing' de passwords para generar claves.
Referencia 1 y/o
Referencia 2.
- Estado del arte de algoritmos criptográficos con curvas
elípticas.
Preliminarmente asignado: Rodrigo Diaz.
- Implementación (en computador paralelo o sistema
distribuído) de algoritmo eficiente para resolver el
problema del 'logaritmo discreto'.
Preliminarmente asignado: Hernán Arroyo.
- Estado del arte o implementación de encriptación
funcional.
Referencia.
Preliminarmente asignado: Jong Bor Lee.
- Implementar un esquema de broadcast asíncrono seguro.
Referencia 1
o bien
Referencia 2
.
Preliminarmente asignado: Guillermo Campos.
- Implementar un plugin para un lector de correo (ej. Thunderbird)
de un esquema de firmas grupales específico
(por ej: multifirmas, firmas anillo, firmas de grupo)
Preliminarmente asignado: Natalia Tapia.
- Revisión y descripción de librerías
de protocolos criptográficos para
"evaluación segura de funciones"
(secure function evaluation) e implementación de una
interfaz para evaluar una función específica
(por ej. cálculo de una permutación
aleatoria). Debe incluir evaluación de eficiencia.
Preliminarmente asignado: Rodrigo Porra.
- Implementar un plugin para Firefox del protocolo de Blum para
"Lanzar una moneda por teléfono" entre dos
participantes. Debe incluir alguna extensión a
más de dos participantes.
Preliminarmente asignado: Alvaro Balmaceda.
- Descripción e implementación de tres esquemas basados
en el twin Diffie-Hellman problem. Concretamente,
implementar la variante del esquema de encriptación
Elgamal y la variante del esquema de Cramer-Shoup, e
implementar una demo del protocolo intercambio de claves.
Referencia.
Preliminarmente asignado: Carlos Cabrera.
- Estado del arte de las imposibilidades e implementaciones
de ofuscación de programas.
Referencia 1 y
Referencia 2.
- 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.
Preliminarmente asignado: Antonio Jimenez.
- Estado del arte o implementación de sistema de
e-cash basado en el trabajo de
mencionado aquí.
Preliminarmente asignado: Alonso Gaete Morales.
- Estado del arte e implementación de un sistema
para encriptar usando la modalidad "key wrapping" propuesta
y analizada en
este artículo.
Preliminarmente asignado: Fabián Soto.
- Estado del arte del uso de cifradores de bloque para implementar
funciones de hash criptográficas. Incluye una revisión de las construcciones propuestas, asi como de las garantias
teóricas y prácticas de las construcciones.
Referencias:
artículo 1,
artículo 2, y
artículo 3.
Preliminarmente asignado: Lissette Cabrera.
- Implementación de esquema de firma digital del tipo
"anillo".
Preliminarmente asignado: Sebastián Gamboa.
- Estado del arte de criptografía visual.
Preliminarmente asignado: Mario Jara.
Solicitar directamente al profesor el tema (por email y luego en persona),
quien le clarificará el alcance del proyecto.
Cualquier otro tema o posible forma del proyecto queda a criterio del profesor
y debe ser consultado con él.
Nota: En caso de eventuales solicitudes "simultáneas" de un mismo tema,
la asignación del tema se hará según orden de
llegada del email al profesor, pero tal asignación debe ser
confirmada en una reunión en persona con el profesor.
De lo contrario, el tema podrá ser asignado a otra persona.
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 (2.)
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.
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.
- Douglas Stinson, “Cryptography, Theory and Practice”, Second edition, Editorial Cgapman and Hall/CRC, 2002
- Oded Goldreich, “Foundations of Cryptography, Basic Tools”, Cambridge University Press, 2001
- Oded Goldreich, “Foundations of Cryptography, Basic Applications”, Cambridge University Press, 2004
- Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, “Handbook of Applied Cryptography”, CRC press, 1997
- Josef Pieprzyk, Thomas Hardjono, Jennifer Seberry, “Foundamentals of Computer Security”, Springer, 2003
Última modificación: 31 de Marzo 2009.
|