27
may
09

Números primos, criptología y codificación

barrow En el libro “¿Por qué el mundo es matemático?” (1992) de John D. Barrow viene recogida una idea sobre codificación usando números primos y la idea de las “funciones trampilla”. Llama la atención que un concepto tan sencillo pueda ser tan útil en criptología (la negrita, como acostumbro, es mía).

… Hemos distinguido entre operaciones que son computables y las que no lo son. Pero en la vida real, el ser computable quizá no sea muy útil si el programa que efectúa la computación requerida necesita un millón de años para llevarla a cabo. El mundo podría ser matemático, e incluso lleno de funciones computables, y aun así podría ser de una profundidad y complejidad tal que seamos incapaces de encontrarlas en nuestros ordenadores más rápidos incluso si estuvieran funcionando durante miles de años. De hecho, la existencia de problemas tan “difíciles” se explota en gran medida en el mundo moderno. Muchos códigos sofisticados utilizados para proteger secretos militares o comerciales se basan en codificaciones que son indescifrables en la práctica aunque no lo son en principio. Con esto queremos decir que sería necesario utilizar los ordenadores más rápidos durante miles de años para explorar todas las posibilidades de acceso al código (que para entonces, obviamente, ya habría sido cambiado).

Códigos como éste explotan la existencia de operaciones matemáticas llamadas funciones “trampilla”, que son muy fáciles de ejecutar en una dirección pero prácticamente imposibles de ejecutar a la inversa, igual que es fácil caer por una trampilla pero no es tan fácil salir de nuevo. Por ejemplo, si tomamos dos números primos muy grandes, cada uno de ellos con cientos de cifras, y los multiplicamos entre sí, entonces ésta es una operación sencilla que un ordenador puede realizar en una fracción de segundo. Pero demos a un ordenador de cualquier tipo el número resultante de doscientos dígitos y pidámosle que encuentre los dos números primos en que se factoriza: podría ser necesario el tiempo de toda una vida para llegar a la respuesta. Consideremos la lección de este ejemplo; la naturaleza podría estar codificada de algún modo por las matemáticas y la codificación equivaldría quizá a alguna ley de la naturaleza. Sería posible que descubriésemos esta codificación utilizando sólamente algunos principios de simetría, consistencia y simplicidad, y aún seríamos incapaces en la práctica de aplicarla al revés para determinar la verdadera naturaleza de las cosas a partir de las apariencias codificadas.

candado Podemos ilustrar de qué forma se utilizan las funciones trampilla para codificación con un ejemplo sencillo. Supongamos que yo quiero enviarle un mensaje secreto. Mi “codificación” es bastante primitiva y consiste en colocarlo en un cofre metálico y poner un candado. La “decodificación” corresponde a abrir el cofre. ¿Cómo puedo hacerle llegar el mensaje sin enviarle la llave de alguna forma y hacerlo así vulnerable a terceras personas que están tratando de robarlo? A primera vista parece imposible, pero no lo es; yo cierro la caja con el candado y se la envío a usted, guardándome mi llave. Usted coloca también su propio candado en la caja, lo cierra, conserva su llave y me devuelve la caja con dos candados. Yo retiro mi candado con mi llave y le devuelvo a usted la caja, y entonces quita su candado y saca el mensaje. ¡Y ninguno de los dos necesita saber nada sobre la llave del otro! En la vida real se utilizan números en lugar de llaves. Codifique su mensaje en algún número grande, N, y multiplíquelo por su número primo grande secreto p para obtener el número Np. Transmítame Np y yo lo multiplico por mi número primo secreto q para obtener el nuevo número Npq. Yo le devuelvo a usted Npq y usted lo divide por p para obtener Nq que luego me devuelve. Yo lo divido por q y obtengo N que es el mensaje. En ninguna etapa necesito conocer p ni usted conocer q, y si cualquier otro intercepta los números compuestos que nos estamos enviando de ida y vuelta, se enfrentaría con la tarea de encontrar los divisores primos de cierto número gigantesco, lo que le llevaría decenas o centenas de años. Para evitar dicha posibilidad cambiamos simplemente nuestros números p y q con cierta frecuencia. Aunque esta idea es brillante y sencilla, sólo se viene utilizando desde hace menos de veinte años.

About these ads

2 Responses to “Números primos, criptología y codificación”


  1. junio 11, 2009 en 3:34 am

    ¡Hola! He estado trabajando en una cifra en la estatua Kryptos en la Cia y tenía la gran idea que puede ser que esté en una diversa lengua. Tenía cierto francés y español en High School secundaria pero no bastante intentar una cifra de substitución y esperar que puedo coger las palabras correctas. ¿Usted sabe buenos programas en línea o tiene sugerencias de lo que podría intentar? Voy a buscar para los blogs de WordPress que discute códigos y las cifras (esperanzadamente) tan si visité accidentalmente su sitio y no tiene nada hacer con códigos/cifras/rompecabezas, lo siento realmente. ¡Las gracias por cualquier ayuda cualquier persona pueden darme!

  2. junio 11, 2009 en 9:07 am

    Lo siento, no tengo suficientes conocimientos sobre el tema. Sólo escribí este post porque me llamó la atención cuando lo leí y pensé que estaría bien darlo a conocer, pero no soy ni mucho menos un experto en la materia. De todas formas, ¡buena suerte!


Deja un comentario

Por favor, inicia sesión con uno de estos métodos para publicar tu comentario:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


Categorías

Archivos

Blog Stats

  • 164,622 hits

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

A %d blogueros les gusta esto: