La Teoría de Números se ha considerado siempre como una de las ramas más claramente inútiles de la Matemática Pura. Contra esta acusación no hay defensa válida; y no es más justa que cuando se dirige contra la parte de la Teoría que se dedica al estudio de los primos. Una ciencia se considera útil si su desarrollo tiende a acentuar las desigualdades existentes en la distribución de la riqueza, o más directamente promueve la destrucción de la vida humana. La Teoría de los números primos no satisface ninguno de estos criterios. Aquellos que la estudian, si son suficientemente sabios, no intentan justificar su interés en una materia tan trivial y remota, y se consuelan con el pensamiento de que los grandes matemáticos de todas las edades han encontrado en ellos una misteriosa atracción imposible de resistir. (G. H. Hardy, Prime Numbers, British Association Report 10 (1915) 350–354)
He de reconocer que, muy a mi pesar, lo que escribió Hardy ya no es cierto. Pero quiero hacer notar que acertó cuando definió qué es una ciencia útil. La Matemática se subvenciona desde que los militares se dieron cuenta de la importancia que tiene en la creación de nuevos armamentos. Y, por ejemplo, dos de las aplicaciones más celebradas de las matemáticas creo que satisfacen exactamente la definición de Hardy: El modelo de Black-Scholes-Merton que permite valorar el precio de activos financieros en una fecha futura, y el algoritmo RSA para las transacciones seguras por internet.
Pero eso no lo vamos a cambiar y los primos se han convertido en la base de nuestra seguridad, económica y militar. Por eso es tan importante el trabajo publicado hace unos días:
Los autores señalan un error en la generación de primos en una importante empresa de hardware criptográfico. El error data del año 2012 y estiman que hay decenas de millones de afectados. Entre ellos el DNI electrónico español.
De manera que el conocimiento de la clave pública es suficiente en muchos casos para atacar la encriptación. El ataque a una de estas claves puede hacerse con ordenadores trabajando en paralelo con lo que se obtienen tiempos muy razonables para descifrar los mensajes. Además hay un criterio directo y muy rápido para averiguar cuáles son las claves susceptibles a este nuevo ataque.
Al parecer las claves de los bancos no estén afectadas. Yo tengo mis dudas de que si lo estuvieran llegáramos a saberlo. Los autores del artículo dicen que han comprobado 13 tarjetas de banco, 6 de ellas contenían el chip del fabricante que ha introducido el error, pero que estas 13 tarjetas no eran vulnerables. Por comparación comprobaron el dni de 130152 estonianos, encontrando que el 54.87% eran vulnerables.
Un poco de la matemática del problema.
El método RSA depende de dos primos grandes \(p\) y \(q\). Con ellos se fabrican dos elementos. Por un lado, la clave pública: una pareja de números \((e,N)\), donde \(N=pq\) es el producto de los dos primos; y, por otro, la parte secreta: otro número \(d\).
La seguridad del método depende de que es relativamente fácil conseguir primos grandes \(p\) y \(q\), y multiplicarlos para formar \(N\). En cambio, si los números son suficientemente grandes, la factorización de \(N\), es decir, el cálculo de \(p\) y \(q\) a partir de \(N\), es una tarea prácticamente imposible. Nadie, al menos públicamente, ha conseguido factorizar un módulo \(N\) de 1024 bits adecuadamente construido. El mayor modulo factorizado ha sido uno de 768 bits, después de un esfuerzo de cálculo distribuido en cientos de CPU durante varios años. No tardarán en caer los módulos de 1024 bits, por eso se recomienda 2048 o 4096 bits. En 1994 Peter Shor mostró que los computadores cuánticos, que podrían estar cerca, romperían todos estos sistemas.
La seguridad del método depende esencialmente de que los primos \(p\) y \(q\) sean aleatorios. Cualquier forma especial de ellos podría usarse para facilitar la factorización. En cada transacción la tarjeta genera nuevos primos. La tarjeta contiene un chip, pero hay un problema práctico, la capacidad de cálculo de los chips es límitada y queremos generarlos sin mucho esfuerzo. La empresa Infineon Technologies AG es una de las que fabrican los chips. Los investigadores detectaron que los \(p\) y \(N\) producidos por estos chips presentaban una distribución no uniforme de \(p\bmod x\) y \(N\bmod x\), para valores de \(x\) pequeños. Esta pista les llevó a detectar que los primos producidos por los chips de este fabricante eran todos de la forma
$$p=k\cdot M+(65537^a\mod M),\qquad 65537=2^{16}+1$$
siendo \(k\) y \(a\) números relativamente pequeños y \(M\) es el producto de los primeros primos
$$ M=\prod_{n=1}^{39} p_n,\quad M=\prod_{n=1}^{71} p_n,\quad M=\prod_{n=1}^{126} p_n,\quad M=\prod_{n=1}^{225} p_n$$
según el tamaño de los primos buscados. De manera que \(p\approx M\).
Una primera consecuencia es que si se emplea este método para fabricar \(p\) y \(q\),tendremos que
$$ N\equiv 65537^{a+b}=65537^{c}\pmod{M}. $$
La existencia de este \(c\) sirve para caracterizar las claves vulnerables. En general el problema de encontrar \(c\) es complicado, pero en este caso el grupo \(G\) que genera \(65537\) en \((\mathbf{Z}/(M\mathbf{Z}))^*\) tiene un orden que es un número suave, es decir, con muchos factores primos pequeños, por ser un divisor de \(\varphi(M)\). Eso hace fácil encontrar \(c\) con muy poco cálculo y por tanto saber de antemano que el método de desencriptar esta clave tendrá éxito.
Vemos que la dificultad de encontrar un primo de cientos de dígitos se ha reducido a encontrar los números \(k\) y \(a\) con muchos menos dígitos. Esto es lo que ayuda a la factorización de \(N\). El problema no es trivial y necesita el uso de un algoritmo previo: el método de Coppersmith.
El método de Coppersmith permite resolver una ecuación polinómica \(p(x)=0\), pero entendida módulo un cierto número natural \(m\). Es decir, buscamos un valor de \(x\) tal que \(p(x)\) sea divisible por \(m\). La matemática brilla aquí con toda su fuerza. El método de Coppersmith usa otro algoritmo bien conocido el algoritmo LLL, o bien, el algoritmo de simplificación de bases de retículos de Lenstra-Lenstra-Lovász.
De este modo vemos como la Matemática es, lo que siempre fue, la técnica de resolver problemas. How to solve it? Independientemente del posible uso que otros puedan dar a nuestros métodos.
Para saber más.
La noticia en la web:
Otro con información sobre como comprobar tus primos.
No es la primera vez que algo de este tipo sucede:
En 2013 afectando el dni en Taiwan.
Trabajo de investigación sobre otros problemas del mismo tipo. (Descarga pdf)
Dejar una contestacion