ITBA - primer cuatrimestre, 2005
Bases Matemáticas para la Criptografía

Profesor:

Horario y aulas:

Contenidos

Objetivos

Este curso pretende dar una introducción al lenguaje y técnicas matemáticas e informáticas elementales empleados en criptografía. Así como brindar facilidad en los manejos esenciales a los desarrollos criptográficos. En particular en lo que concierne a aritmética modular, estructuras algebráicas --dentro de Álgebra--, a los modelos de computación elementales, estimaciones de complejidad, y nociones sobre problemas tratables e intratables --en cuanto a informática teórica--, y manejos elementales de probabilidades discretas.

Las clases prácticas están dedicadas a estudiar aplicaciones de las herramientas y conceptos de criptografía introducidos en las clases teóricas.

Programa:

• Álgebra.
• Números enteros. Divisibilidad. Algoritmo de división. Congruencias. Máximo común divisor y mínimo común múltiplo. Ecuaciones diofánticas y ecuaciones de congruencia. Primos. Teorema fundamental de la aritmética. Pequeño teorema de Fermat. Teorema Chino del Resto.
• Polinomios. Divisibilidad. Algoritmo de división. Irreducibilidad. Anillos cociente.
• Estructuras Algebraicas. Cuerpos. Anillos cocientes, ejemplos. Grupos, grupos cíclicos, grupos finitos. Cuerpos, cuerpos finitos GF(2^m)
• Informática.
• Computabilidad. Lenguajes regulares, automatas finitos. No determinismo. Tesis de Church-Turing. Máquinas de Turing (deterministicas, no deterministicas y probabilísticas). Variantes. Decibilidad. Halting problem.
• Complejidad. Clases de complejidad. Estimaciones de complejidad. Problemas intratables. NP-completitud. Ejemplos.
• Probabilidades discretas. Espacios de probabilidad. Definiciones. Combinatoria. Ejemplos de distribuciones (binomial, geométrica, hipergeométrica, etc.).

Bibliografía:

• Álgebra
  • "Notas de Álgebra", por Enzo Gentile. EUDEBA.
  • "Estructuras algebráicas I", por Enzo Gentile. OEA.
  • "A course in number theory and cryptography", por Neal Koblitz 2ed., GTM 114, Springer, 1994
• Informática
• "Structural Complexity (I)", Balcazar, Diaz, Gabarros. Springer, 1995.
• "Computer and intractability- a guide to the theory of NP-completeness", por M.R.Garey, D.S. Johnson.
• Probabilideades discretas
• "Introduction to Probability Theory and its Applications, v. 1", W. Feller
• "Probabilidade: um curso em nível intermediário", por James, Barry R. Instituto de Matemática Pura e Aplicada. Rio de Janeiro 1981

Administrativia

Los alumnos que hayan resoluelto los problemas seleccionados de las prácticas de ejercicios (en tiempo y forma) tienen derecho a final.

Cada clase, rotativamente, un alumno distinto será seleccionado para tomar apuntes y pasar las notas a formato LaTeX. Estos apuntes estarán disponibles en la página Web de la materia. Usen, por favor el formato preamble.tex, tomando como ejemplo el fichero sample.tex.

Clases prácticas:

Clase #1 - 6/4/2005

Motivación. Adversarios en la pre-historia de la criptografía y adversarios modernos. Los primeros pasos de stream ciphers (LFSR, algoritmo de Berlekamp-Massey, híbridos, correlación y ataque de Siegenthaler).

Bibliografía:

• Capítulo 6 de "Handbook of applied Cryptography", Alfred Menezes, Paul van Oostroch, Scott Vanstone.
• El survey en Ciphers by Ritter.

Clase #2 - 11/4/2005

Repaso de Inducción, recurrencias, sumas y series. (Práctica 0)

Bibliografía: Capítulos 1 y 2 de "Concrete Mathematics". "Notas de Álgebra", Enzo R. Gentile, Eudeba.

Clase #3 - 18/4/2005

Problemas computacionales en teoría de grupos.

• Isomorfismo de grafos. Aplicación a Zero-knowledge proofs.
• Problemas de igualdad de palabras y conjugación en grupos. Aplicación a Braid groups: Cryptosystem de Anshel, Anshel, Goldfeld (1999) y ataque de Hughes y Tannenbaum (2002).
• Logaritmos discretos. Problemas Computational Diffie-Hellman, y Decisional Diffie Hellman. Aplicación a sistemas de Diffie-Hellman y ElGammal. Mencionamos los resultados de Goldwasser, Micali (1984) y los ataques de Boneh, Joux, Nguyen (2000) a textbook ElGammal.

Bibliografía:

• Dan Boneh "Decisional Diffie-Hellman problem" In Proceedings of the Third Algorithmic Number Theory Symposium, Lecture Notes in Computer Science, Vol. 1423, Springer-Verlag, pp. 48--63, 1998.
• Dan Boneh, Antoine Joux, Phong Nguyen, "Why Textbook ElGamal and RSA Encryption are Insecure" In Proceedings AsiaCrypt '00, Lecture Notes in Computer Science, Vol. 1976, Springer-Verlag, pp. 30--44, 2000.
• Karl Mahlburg "An overviwe of braid group cryptography" Notes.
• Hughes, Tannenbaum "Length-based attacks for certain group based encryption rewritting systems". Securité des communications sur Internet, 2002.

Clase #4 - 25/4/2005

RSA, método de encriptado y ataques.

• RSA: algoritmos de encripción y desencripción. Complejidad. Conjetura RSA.
• Ataque de exponente bajo para varias encripciones del mismo mensaje.
• Ataque de Franklin-Reiter.

Bibliografía:

• D. Boneh "Twenty years of attacks on the RSA system". In Notices of the American Mathematical Society (AMS), Vol. 46, No. 2, pp. 203--213, 1999.
• D. Coppersmith, M. Franklin, J.Patarin, y M. Reiter "Low exponent RSA with related messages". Advances in Cryptology -- Eurocrypt '96 Proceedings, 1997.

Clase #5 - 2/5/2005

Residuos cuadráticos y esquemas de encriptado y firma de Rabin.

• Residuos: definición, ejemplos, símbolos de Legendre y Jacobi, Lema de Gauss.
• Esquemas de Rabin: definiciones, algoritmos de encriptado y firma, resultado de seguridad (romper estos esquemas es tan difícil como factorizar).

Bibliografía:

• K. Ireland, M. Rosen: "A classical introduction to number theory". GTM Series. Springer.
• M.O. Rabin, "Digitalized Signatures and Public-Key Functions as Intractable as Factorization", MIT/LCS/TR-212, MIT Laboratory for Computer Science, 1979.

Clase #6 - 9/5/2005

Algoritmo de Tonelli para cálculo de raices cuadradas en cuerpos finitos.

Bibliografía:

• Eric Bach and Jeffrey Shallit, "Algorithmic Number Theory (vol. 1)", MIT Press, 1996.

Clase #7 - 16/5/2005

Álgebra:

• Nociones elementales de álgebra conmutativa.
• Problemas sobre anillos de Polinomios: Vimos que el problema de "decidir si una variedad Q-definible es vacía sobre los complejos" es NP-completo (i.e., es reducible a 3SAT).

Bibliografía:

• Luis M. Pardo, "How Lower and Upper Complexity Bounds Meet in Elimination Theory", LNCS 948, Proceedings of the 11th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, pp 33 - 69, 1995.
• M. Giusti, H. Heintz, Kronecker's smart, little black-boxes", Proceedings of Foundations of Computational Mathematics, Oxford 1999 (FoCM'99), A. Iserles and R. DeVore, eds., 284, 2001, 69-104, Cambridge University Press.

Clases #8 y #9- 16/5/2005 y 23/5/2005

Scientific computing: Cotas inferiores para la resolución de problemas de álgebra computacional para codificaciones

• densa
• rala
• straight-line program

Bibliografía:

• Luis M. Pardo, "How Lower and Upper Complexity Bounds Meet in Elimination Theory", LNCS 948, Proceedings of the 11th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, pp 33 - 69, 1995.
• M. Giusti, H. Heintz, Kronecker's smart, little black-boxes", Proceedings of Foundations of Computational Mathematics, Oxford 1999 (FoCM'99), A. Iserles and R. DeVore, eds., 284, 2001, 69-104, Cambridge University Press.

Clase #10 - 30/5/2005

Definiciones de seguridad para primitivas criptográficas para el caso de block ciphers. Argumentos híbridos. Seguridad PRP.

Bibliografía:

• Apuntes de Phillip Rogaway del curso CS220 (2001).
• A. Waissbein. ``Temas de Criptografía - apuntes''. En preparación.

Clases #11,12 - ./6/2005

Generadores psuedo-aleatorios. Los alumnos presentaron el capítulo de generadores del textbook de Goldreich.

Bibliografía:

• Goldreich, O "Foundations of Cryptology (V. 1)". Cambriedge Press. 2001.

Prácticas de ejercicios:

• Práctica 0.
• Práctica 1. Hacer todos los ejercicios. Fecha de entrega Lunes 9 de Mayo.
• Práctica 2. Hacer todos los ejercicios. Fecha de entrega Lunes 13 de Junio.
• Práctica 3. Hacer todos los ejercicios. Entrega Miercoles 13 de Julio.
• Práctica 4. (Por Pablo Fierens.) Hacer todos los ejercicios.

Return to index.

Last modified September 18th, 2005