Introducción a la Criptografía Moderna CC51Q/CC5301 (2010/02)

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, [B214]
Auxiliar: Lunes 4:15pm-6:45pm, [B211]
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

  • [6 de Sept 2010] El listado de proyectos posibles está disponible.
  • [6 de Sept 2010] Cambio en fechas del proyecto:
    • Elección y comunicación del proyecto al profesor: 10 de Sept 2010.
    • Reporte de Avance: 6 de Oct 2010.
  • [6 de Sept 2010] Calendario de próximas lecturas está actualizado.
  • Importante: Escoger un proyecto y comunicarselo al profesor antes del Viernes 10 de Septiembre. Ver listado de proyectos posibles.
  • Fechas Importantes:
    1. Entrega Reporte de Avance proyecto: Miércoles 6 de Octubre, 2010
    2. Control 1: Viernes 1 de Octubre, 2010

Material de Lectura

 Estas lecturas son altamente recomendadas para las clases de cátedra/ auxiliares indicadas.

Temario

  1. Elementos Básicos:
    1. Introducción
    2. Conceptos Básicos: objetivo de seguridad (privacidad, autentificación), adversarios, recursos. Seguridad demostrable como una reducción.
    3. Criptografía Clásica (cifrados de sustitución y variantes, ataques). One-time pad y seguridad perfecta, limitaciones.
  2. Criptografía Simétrica (Clave Privada):
    1. Cifradores de Bloque: Modelos, construcciones (DES, AES)
    2. Funciones Pseudo-aleatorias
    3. Encriptación Simétrica: Modelos de seguridad, construcciones basadas en cifradores de bloque
    4. Funciones unidireccionales y resistentes a colisiones: potenciales candidatos (MD5, SHA-1, SHA-256, otros), modelos de seguridad, el ataque de los cumpleaños
    5. Autentificación de Mensajes: modelos y construcciones (CBC-MAC, HMAC, UMAC, CMAC, y otros)
  3. Criptografía Asimétrica (Clave Pública):
    1. Teoría de Números Computacional
    2. Primitivas basadas en teoría de números
    3. Encriptación Asimétrica
    4. Firmas Digitales
  4. Criptografía en la Práctica:
    1. Infraestructura de Clave Pública (PKI)
    2. Autentificación e identificación (passwords), vía terceras partes confiables (Needham-Schroeder, Kerberos)
    3. Acuerdo de Claves: Diffie-Hellman y intercambio de claves autentificado (AKE).
    4. Canales seguros (SSL y Encriptación autentificada)
    5. Problemas al implementar algoritmos criptográficos
  5. Tópicos Avanzados (si el tiempo lo permite)
    1. Mecanismos para compartir secretos (Secret Sharing)
    2. Generación de bits pseudo-aleatorios
    3. Introducción a demostraciones interactivas y protocolos de Nula Divulgación (Zero Knowledge)
    4. 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 4 y 5) tareas cortas. El proyecto es desarrollado durante el semestre. Posibles alternativas para el proyecto incluyen

  1. Desarrollo de un software criptográfico (con informe) o
  2. 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 en Side-Channel attacks.
  • Survey on functional encryption
  • Survey on fully homomorphic encryption (paper de Gentry [si es posible], y "Fully homomorphic encryption over the integers" de M. van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan, ver http://crypto.rd.francetelecom.com/events/eurocrypt2010/talks/he-integers.ppt)
  • Survey en Non-Interactive verifiable computing (ver crypto 2010)
  • Survey on tecnicas y ataques usando "related-key attacks"
  • Survey en criptografia bajo adversarios racionales (o "cryptography and game theory")
  • Survey de tecnicas de dise~no, ataques, y otras ideas sobre hash functions (concurso SHA-3)
  • Survey en esquemas de encriptacion circularmente seguros
  • Construcciones y conceptos de construccion de Funciones de hash con Multi-Property-Preserving Domain Extension
  • Criptografía cuántica: qué es, cómo funciona, estado actual de los computadores cuánticos.
  • Implementación (en computador paralelo o sistema distribuído) de algoritmo eficiente para resolver el problema del 'logaritmo discreto'.
  • Implementación (en computador paralelo o sistema distribuído) de algoritmo eficiente para encontrar colisiones en MD5 o similar.
  • Estado del arte o implementación de encriptación funcional. Referencia (nuevas referencias por publicar).
  • 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.
  • 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.
  • Estado del arte de las posibilidades, 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.
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:

  1. 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.
  2. Douglas Stinson, “Cryptography, Theory and Practice”, Second edition, Editorial Cgapman and Hall/CRC, 2002
  3. Oded Goldreich, “Foundations of Cryptography, Basic Tools”, Cambridge University Press, 2001
  4. Oded Goldreich, “Foundations of Cryptography, Basic Applications”, Cambridge University Press, 2004
  5. Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, “Handbook of Applied Cryptography”, CRC press, 1997
  6. Josef Pieprzyk, Thomas Hardjono, Jennifer Seberry, “Foundamentals of Computer Security”, Springer, 2003

Última modificación: 15 de Agosto 2010.