Dialog Attack on Small Secret Keys

You can reach this dialog via the menu entry Individual Procedures \ RSA Cryptosystem \ Lattice Based Attacks on RSA \ Attack on small secret Keys.

The user has the choice between two modes of attack on small secret keys:
1. Enter all input data and start the attack
The user enters the values for e and N and estimates the value for d according to delta.
2. Generate sample input data and start the attack
The user chooses the bit length of N and the wanted delta to have a sample created by the program.

1. Enter all input data and start the attack

  1. First of all N and e have to be entered.
  2. Then the estimation for delta has to be added. If you choose to enter d directly, delta will be calculated. This step is not mandatory to perform the attack but leaves you with the option to check whether the key in use is vulnerable to attack.
  3. Now the attack can commence by clicking on “Start.”

In the “Attack” group information on the current attack are shown and in case of success the factors p and q are displayed.

Example

The attacker enters e=741077250369232479059668207375016571081542804590833038433249892326787378484956638636330841 and N=1259723741173449567548189641230786965150346729930314335887552587458506570619692703188420329 and estimates the size of d with delta=0.260.

2. Generate sample input data and start the attack

To generate your own example you have to choose the bit length of N (i.e. 300) and a delta (i.e. 0.260). After clicking “Generate random key” the attack can be started by clicking "Start".

Annotations

In both cases the parameter m can be changed. m influences the dimension of the lattice and should not be chosen to be too big since an increase in the number negatively influences the runtime of the program. It depends on m to which size delta can be chosen so that the attack can succeed. The calculation of the maximum delta is not exact for small N (N <1000 bit), so the chosen delta should be approximately 0.05 less than the maximum value of delta. The formula used to calculate delta is:

Here the root of an equation in two unknowns has to be found. To do so, two short vectors are used and two polynomials are build. These two polynomials do not necessarily reveal the sought root. For that reason this attack has to be considered as a heuristic. From the found polynomials the resultant is built. That means that from two polynomials in two unknown a new polynomial in one unknown is created.