Number theory has always been regarded as one of the most clearly useless areas of pure mathematics. Against this accusation there is no valid defence; and it is no more fair than when it is directed against that part of the Theory which is devoted to the study of primes. A science is considered useful if its development tends to accentuate existing inequalities in the distribution of wealth, or more directly to promote the destruction of human life. Prime number theory satisfies neither of these criteria. Those who study it, if they are wise enough, do not attempt to justify their interest in so trivial and remote a subject, and comfort themselves with the thought that the great mathematicians of all ages have found in it a mysterious attraction impossible to resist. (G. H. Hardy, Prime Numbers, British Association Report 10 (1915) 350–354)
I must admit that, much to my regret, what Hardy wrote is no longer true. But I want to note that he got it right when he defined what is a useful science. Mathematics has been funded ever since the military realised its importance in the creation of new weaponry. And, for example, two of the most celebrated applications of mathematics I believe meet Hardy’s definition exactly: the Black-Scholes-Merton model that allows us to value the price of financial assets at a future date, and the RSA algorithm for secure internet transactions.
But we are not going to change that and primes have become the basis of our security, economically and militarily. That is why the work published a few days ago is so important:
The authors point to a bug in the generation of primes at a major cryptographic hardware company. The error dates back to 2012 and they estimate that tens of millions of people are affected. Among them is the Spanish electronic ID card.
This means that knowledge of the public key is sufficient in many cases to attack the encryption. The attack on one of these keys can be carried out with computers working in parallel, which results in very reasonable times for decrypting messages. In addition, there is a direct and very fast criterion to find out which keys are susceptible to this new attack.
It seems that bank passwords are not affected. I have my doubts that if they were, we would know about it. The authors of the article say that they checked 13 bank cards, 6 of which contained the chip of the manufacturer that introduced the bug, but that these 13 cards were not vulnerable. By comparison, they checked the IDs of 130,152 Estonians, finding that 54.87% were vulnerable.
A bit of the maths behind the problem
The RSA method depends on two large primes \(p\) and \(q\). Two elements are made from them. On the one hand, the public key: a pair of numbers \((e,N)\), where \(N=pq\) is the product of the two primes; and, on the other hand, the secret part: another number \(d\).
The safety of the method depends on the fact that it is relatively easy to get large primes \(p\) and \(q\), and multiply them to form \(N\). On the other hand, if the numbers are sufficiently large, factoring \(N\), i.e. calculating \(p\) and \(q\) from \(N\), is a virtually impossible task. No one, at least publicly, has succeeded in factoring a properly constructed 1024-bit \(N\)-module. The largest factored modulus has been a 768-bit one, after a computational effort spread over hundreds of CPUs over several years. It will not be long before 1024-bit modules will be dropped, so 2048 or 4096 bits are recommended. In 1994 Peter Shor showed that quantum computers, which could be close, would break all these systems.
The security of the method depends essentially on the primes \(p\) and \(q\) being random. Any special form of them could be used to facilitate factorisation. At each transaction the card generates new primes. The card contains a chip, but there is a practical problem, the computing power of the chips is limited and we want to generate them without much effort. Infineon Technologies AG is one of the manufacturers of the chips. The researchers detected that the \(p\) and \(N\) produced by these chips had a non-uniform distribution of \(p\bmod x\) and \(N\bmod x\), for small \(x\) values. This clue led them to detect that the primes produced by this manufacturer’s chips were all of the form
$$p=k\cdot M+(65537^a\mod M),\qquad 65537=2^{16}+1$$
being \(k\) and \(a\) relatively small numbers and \(M\) is the product of the first primes
$$ 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$$
depending on the size of the primes sought. So \(p\approx M\).
A first consequence is that if this method is used to produce \(p\) and \(q\), we will have that
$$ N\equiv 65537^{a+b}=65537^{c}\pmod{M}. $$
The existence of this \(c\) serves to characterise vulnerable keys. Usually the problem of finding \(c\) is complicated, but in this case the group \(G\) which generates \(65537\) in \((\mathbf{Z}/(M\mathbf{Z}))^*\) has an order which is a smooth number, i.e. with many small prime factors, because it is a divisor of \(\varphi(M)\). That makes it easy to find \(c\) with very little computation and therefore to know in advance that the method of decrypting this key will succeed.
We see that the difficulty of finding a prime of hundreds of digits has been reduced to finding the numbers \(k\) and \(a\) with far fewer digits. This is what helps the factorisation of \(N\). The problem is not trivial and requires the use of a prior algorithm: the Coppersmith’s attack.
Coppersmith’s attack allows us to solve a polynomial equation \(p(x)=0\), but understood modulo a certain natural number \(m\). That is, we look for a value of \(x\) such that \(p(x)\) is divisible by \(m\). Mathematics shines here in full force. Coppersmith’s method uses another well-known algorithm, the LLL algorithm, i. e., the Lenstra-Lenstra-Lovász lattice basis reduction algorithm.
Thus we see how mathematics is, what it always was, the technique of solving problems. How to solve it? Regardless of the possible use that others may make of our methods.
Learn more
The news on the web:
Otro con información sobre como comprobar tus primos.
This is not the first time something like this has happened:
In 2013 affecting the ID card in Taiwan.
Research paper on other similar problems. (Downloadable pdf)
Leave a Reply