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

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.

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.