So What Was The Problem With The Estonian ID System and TPMs? Weak Prime Number Generators (and RSA!)

The march of time in cryptography often means that something which is secure now may not be secure in a few years time. As long as humans introduce flaws into the implementation of the methods too, we will have weaknesses. But we should always have ways to revoke public keys and update our system. And so Estonia received a jolt in the usage of their ID system, and at the core of the problem was the availability of the public key and in the weak generation of prime numbers.

Let’s start with the method that RSA uses to generate our keys [calc]:

We can see that the core element of the method is the generation of N, which is the multiplication of two prime numbers (p and q). If the value of N can be factorized, we can find the private key.

The flaw in the implementation of the Estonian ID system comes from the usage of a certain library — RSALib — and where a research team found that the variation of the values used to generate the prime numbers did not look quite…