The script generated 4 numbers by:
The vulnerabililty here is that xs' bit length is small compared to n, so lattice-based attack could exploit it.
Howgrave-Graham and Seifert’s Attack had concluded that when given 4 public exponents whose private exponents' bit length is below times the bit length of n, it's likely to factorize n efficiently.
The bit length of x here is about .
By this relation of e and d, we can have 10 basic equations: ( is GCD and )
The basic idea is using these equations to construct a vector-matrix equation where is an upper triangle matrix and
For the purpose that will be mentioned later, we want to choose as many as possible and as less as possible.
My choice was:
This lead to:
and
Every row of is a vector much bigger than and is linear combination of these rows.
To apply lattice attack, we still need to be balanced. Notice that , , , , so is dominated by the last component .
Hence we need to multiply both and by a diagonal matrix
Now we can apply LLL algorithm to obtain and , then calculate . If is calculated correctly, the roots of will be p and q consequently.
The only thing left is that we don't know the GCD of and , it could be any even number. Hence for every possible , we need to multiply by first. It turned out that the GCD is just though.
Using the theorem, to increase the success rate of the attack, we need the volume of to be as large as possible. It means large components of , which means small right hand side of each equation we choose.
By some observation, all the right hand side of the equations consists of .
When choosing , we elimintae and but only multiply the number by . On the other hand, choosing multiplies the number by , which is much larger.
We can even calculate the upperbound of bit length of by the theorem.