Criptografía desde el punto de vista computacional

Abstract

RESUMEN: La criptografía es la ciencia que estudia métodos para enviar información de forma segura en forma eficiente. Los cimientos teóricos de la criptografía se basan en teoría de la complejidad computacional y estadística que la hacen poco accesible. Este trabajo dará una introducción a la teoría de generación de números aleatorios, que es de suma importancia por sus aplicaciones a los cifradores en flujo. Para ello, se introducirán todos los conceptos básicos necesarios para entender la teoría. Se comenzará introduciendo la teoría de lenguajes formales y su relación con las clases de complejidad P, NP y BPP. A continuación, hablaremos de las funciones one-way (de un solo sentido) para introducir Hard-Core bits que son necesarios para definir algunos generadores de números pseudoaleatorios seguros y por último discutiremos algunas construcciones de generadores.

ABSTRACT: Cryptography concerns with algorithms to secure information from unauthorized third parties. The theorical basis are supported by complexity theory and statistics. This bachelor thesis gives an introduction to the theory of pseudorandom number generation. This subject is specially important for its applications to stream ciphers. All the necessary concepts to understand the thesis are given in the first chapters. These concepts include the ones from Formal Language theory and a introductory exposition of complexity classes P, NP and BPP. Next, the definition of one-way functions is given and the related concept of hard-core bits is explained. The last part is devoted to several constructions of secure pseudorandom number generators.