Teoría de códigos

La teoría de códigos es una especialidad matemática que trata de las leyes de la codificación de la información. A grandes rasgos, codificar es transformar una información en una señal convenida para su comunicación. Decodificar sería el proceso inverso y complementario del anterior por el cual la señal comunicada es transformada en la información original. El auge de las comunicaciones a partir de la segunda mitad del siglo XX motivó un fuerte desarrollo de la teoría de códigos.

Introducción e historiaEditar

Cronología[1]
Año Acontecimiento
55 a. C. Julio César, al invadir Gran Bretaña, utiliza
códigos para enviar mensajes a sus generales.
1750 d.C. Leonhard Euler sienta las bases de la criptografía
de clave pública con su teorema.
1844 Samuel Morse transmite su primer mensaje
utilizando su código.
Década
de 1920
Se desarrolla la máquina Enigma.
1950 Richard Hamming publica un artículo fundamental
para crear códigos que detectan y corrigen errores.
Década
de 1970
Desarrollo de la criptografía de clave pública.

Puesto que los códigos se usan para comunicar información, uno de los problemas a los que todo código se enfrenta es el error sistemático y, también, el fortuito. La redundancia es el único medio de prevenir el error. Los lenguajes humanos tienen una gran redundancia que les da flexibilidad a costa, eso sí, de eficacia. Los códigos matemáticos utilizan una redundancia más racional.

Hay códigos llamados de detección de errores, que permiten detectar alteraciones en un mensaje codificado. Se utilizan sobre todo en entornos donde el mensaje puede ser reenviado tantas veces como se necesite. Los protocolos de Internet, por ejemplo, están formados por un anidamiento de codificaciones desde el nivel de transporte hasta el nivel físico, teniendo cada nivel su propio sistema de detección de errores.

Este tipo de códigos resulta inadecuado en entornos donde la comunicación no se puede repetir y se necesita asegurar hasta cierto punto que se va a recibir la información correcta. Un ejemplo típico y vistoso es cuando se envía una nave espacial a los confines del sistema solar y desde allí debe enviar una serie de fotografías antes de que se le acaben, digamos, las pilas. Se trata de una situación delicada, porque si las ondas electromagnéticas que portan la información llegan distorsionadas toda la misión fracasa. Un código que solo detectase que la información es incorrecta no serviría para nada. Es necesario algo más, un código no solo detector sino corrector de errores.

Por ejemplo, el sistema de codificación más sencillo puede consistir en que un "0" se representa un "no" y con un "1" un sí. En este caso, si quiero transmitir un "si", y se comete un error al transmitir un "0" en vez del "1", el receptor del mensaje hará lo opuesto a lo pedido. Pero si en cambio se conviene que "00" sea "no" y "11" sea "sí", entonces, si se comete un error en un dígito, y por ejemplo el receptor recibe un "01", detectará que hubo un error, aunque no sabrá cual es el mensaje correcto. En cambio si la convención es que "000" es "no" y "111" un sí, y se supiese que al transmitir un mensaje solo es posible, por la metodología utilizada, cometer un solo error de dígito, entonces, si al recibir un "001", el receptor sabrá que se trata de un "no". Así siguiendo, si transmitimos un bloque de ceros, o un bloque de unos, aunque se cometan algunos errores en la transmisión de algunos dígitos, se tendrá la casi certeza de cual es el error cometido en el mensaje recibido, y corregirlo.[2]

En la actualidad, los avances que se están produciendo en esta disciplina están encaminados hacia la utilización de las bases de Groebner como herramienta para la codificación y decodificación en los códigos detectores de errores.

El problema de la codificación eficienteEditar

Uno de los principales problemas de la teoría de códigos es el siguiente. Supongamos que tenemos una fuente de información que emite o transmite "símbolos" de cierto conjunto   que por propósitos pedagógicos llamaremos simplemente "palabras", de forma que la probabilidad de emisión de una palabra sea independiente del símbolo anterior  , siendo  . Si   es un alfabeto de D "letras", ¿qué código debe asignársele a la palabra   usando "letras" del alfabeto de tal manera que se consiga una codificación tan económica como sea posible?[3]​ Formalmente una codificación es una aplicación   del conjunto de "palabras" en el conjunto de secuencias finitas de "letras" del alfabeto. Un mensaje es una secuencia finita de palabras,  , si se dispone de una codificación de palabras, ésta se extiende inmediatamente a mensajes mediante concatenación:

 

Algunos tipos de codificaciones interesantes son:

  • Una codificación es unívocamente descifrable si cualquier secuencia finita de   es la imagen de como mucho un mensaje, es decir, cuando la aplicación E es inyectiva.
  • Una codificación es instantáneamente descifrable, o de tipo prefijo, si no existen dos palabras diferentes   y   tal que   es una secuencia inicial de  .

Desigualdad de KraftEditar

Desigualdad de McMillanEditar

Codificación criptográficaEditar

La criptografía o codificación criptográfica es la práctica y el estudio de técnicas de comunicación segura en presencia de terceros (llamados adversarios).[4]​ En términos más generales, se trata de construir y analizar protocolos que bloquean a los adversarios;[5]​ diversos aspectos de la seguridad de la información, como la confidencialidad, la integridad de los datos, la autenticación y el no repudio[6]​ son fundamentales para la criptografía moderna. La criptografía moderna existe en la intersección de las disciplinas de matemáticas, informática e ingeniería eléctrica. Las aplicaciones de la criptografía incluyen tarjetas de cajero automático, contraseñas de ordenador y comercio electrónico.

La criptografía antes de la era moderna era efectivamente sinónimo de cifrado, la conversión de información de un estado legible a aparentes nonsense. El autor de un mensaje cifrado compartió la técnica de decodificación necesaria para recuperar la información original solo con los destinatarios previstos, evitando así que personas no deseadas hicieran lo mismo. Desde la Primera Guerra Mundial y el advenimiento del ordenador, los métodos utilizados para llevar a cabo la criptología se han vuelto cada vez más complejos y su aplicación más extendida.

La criptografía moderna se basa en gran medida en la teoría matemática y la práctica informática; Los algoritmos criptográficos están diseñados en torno a suposiciones de dureza computacional, lo que hace que dichos algoritmos sean difíciles de romper en la práctica por parte de cualquier adversario. En teoría, es posible romper un sistema de este tipo, pero no es factible hacerlo por ningún medio práctico conocido. Por lo tanto, estos esquemas se denominan computacionalmente seguros; Los avances teóricos, por ejemplo, las mejoras en los algoritmos de factorización de enteros y la tecnología informática más rápida requieren que estas soluciones se adapten continuamente. Existen esquemas de seguridad teórica de la información que probablemente no se pueden descifrar ni siquiera con un poder de cómputo ilimitado; un ejemplo es la libreta de un solo uso, pero estos esquemas son más difíciles de implementar que los mejores mecanismos teóricamente rompibles pero computacionalmente seguros.

ReferenciasEditar

NotasEditar

  1. Basado en "50 cosas que hay que saber sobre matemáticas", de Tony Crilly.
  2. Ejemplo obtenido en el libro de "50 cosas que hay que saber sobre matemáticas", de Tony Crilly
  3. Dominic Welsh, 1988, p. 15
  4. Rivest, Ronald L. (1990). «Cryptology». En J. Van Leeuwen, ed. Handbook of Theoretical Computer Science 1. Elsevier. 
  5. Bellare, Mihir; Rogaway, Phillip (21 September 2005). «Introduction». Introduction to Modern Cryptography. p. 10. 
  6. Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A. (1997). Handbook of Applied Cryptography. ISBN 978-0-8493-8523-0. (requiere registro). 

BibliografíaEditar

Véase tambiénEditar