Un caso controvertido

Las Matemáticas han tenido una gran influencia en el desarrollo de la criptografía en las últimas cuatro décadas. Sin embargo, el trabajo de criptógrafos y el de matemáticos es muy distinto. En 2007, Neal Koblitz publicó en el Notices de la Sociedad Matemática Norteamericana un artículo muy controvertido,¹⁴ en donde apunta dos aspectos, que él considera indeseables, del efecto de la investigación matemática en criptografía. El primero se refiere a la tendencia en anunciar potenciales aplicaciones criptográficas de cualquier desarrollo en matemáticas, con el solo fin de obtener apoyos económicos, y estas supuestas aplicaciones criptográficas son inexistentes en los peores casos, o triviales y marginales en los mejores (en el caso estadunidense esta tendencia propicia además, según Koblitz, el surgimiento de actitudes chovinistas pues un patrocinador importante es la NSA (National Security Agency). El segundo se refiere a que en criptografía se tiende a “matematizar” cualesquiera desarrollos, sobre todo cuando se pretende demostrar formalmente que éstos son robustos. Efectivamente, apuntaría yo, un enunciado de la forma “Tal protocolo es inmune a tales ataques” no puede equipararse a un enunciado “Tal teorema es válido ante tales hipótesis” pues en el primero ha de tenerse en cuenta que intervienen “atacantes pragmáticos”, en tanto que el segundo es propio de la “epistemología matemática”. Para cerrar su artículo, Koblitz cita a un criptógrafo de la NSA diciendo que en la criptografía de la vida real una falla de seguridad puede ocasionar pérdidas millonarias o de vidas humanas, en el caso de un enfrentamiento bélico, en tanto que en la criptografía de ambientes universitarios una falla puede significarle a sus autores la oportunidad de añadir más artículos a sus curricula. Uno de los autores de Introduction to Modern Cryptography (introducción a la criptografía moderna), Jonathan Katz de la Universidad de Maryland, responde¹⁵ a Koblitz argumentando que las pruebas formales han transformado a la criptografía de un arte a una ciencia (y hace un reproche severo a los editores del Notices por haber publicado el artículo de Koblitz sin contraponerlo a una opinión opuesta).

Como lo mencioné anteriormente, las funciones unidireccionales son cruciales en los esquemas criptográficos, y en ellas, el cálculo de las funciones inversas debe ser “computacionalmente difícil”. En la Teoría de la Complejidad hay diversas nociones de “dificultad”. Hay problemas que de plano son irresolubles o no-computables (por ejemplo los llamados Problema de la Parada o Problema de Post de la Correspondencia) y también, fija una clase de problemas computables, se considera a aquellos a los cuales se reduce cualquier problema en esa clase mediante un procedimiento de conversión dentro de esa clase. Por ejemplo, la clase NP consta de los problemas tales que soluciones hipotéticas de ellas pueden verificarse como soluciones actuales de ellos por programas de computadora que corren en un tiempo polinomial en el tamaño de sus instancias. La clase P consta de los problemas cuyas soluciones son constructibles en tiempo polinomial. Naturalmente, P está contenida en NP, pero no se sabe en la actualidad si esa contención es propia. Uno de los problemas abiertos que se espera sean resueltos en el siglo XXI es decidir si P = NP. Un problema es difícil en la clase NP (o difícil-NP) si cualquier problema en NP se reduce a él en tiempo polinomial. Pues bien, es evidente que el problema de factorización de enteros y el problema del logaritmo discreto están en la clase NP (dadas soluciones hipotéticas se verifica sin esfuerzo alguno si éstas son en realidad soluciones verdaderas). Pero no se sabe a la fecha si acaso son difíciles-NP. Se conocen algoritmos de tiempo exponencial (o subexponencial pero superpolinomial) para resolverlos, pero ni se ha probado que cualquier problema en NP se reduce a ellos en tiempo polinomial, ni tampoco que no existan procedimientos polinomiales para resolverlos efectivamente (en el Cómputo Cuántico se ha diseñado algoritmos polinomiales para resolverlos, pero sus funciones primitivas entrañan una complejidad exponencial cuando se las quiere simular por esquemas clásicos).

Así que nos encontramos con que los esquemas criptográficos actuales son robustos de manera “condicional”: Si hubiese un algoritmo polinomial para calcular las inversas de las funciones unidireccionales y éste se descubriese entonces los esquemas dejarían de ser robustos, mas si no hubiese tal algoritmo y esto se probase se habría demostrado que los esquemas son efectivamente robustos. A la fecha, ¡los esquemas usuales son seguros porque “creemos” que lo son!