Dialog Factoring with a Hint

You can reach this dialog via the menu entry Individual Procedures \ RSA Cryptosystem \ Lattice Based Attacks on RSA \ Factoring with a Hint.

The dialog Factoring-with-a-Hint offers two different modes, which can be chosen in the upper part of the window:
1. Enter the RSA-modulus N, the bitlength of p and the known part P can be entered manually.
2. Enter the bitlength of N and of p and let the program generate a random example.

Steps to proceed:
  1. Depending on the above mentioned choice either N itself or the bitlength of N can be entered.
    The group "Base of numbers" allows to change the representation of N, p and P.
  2. In both cases the bitlength of p has to be entered (for this attack the bitlength of p has to be exactly known!).
  3. Consequently it is selected, whether the upper most significant or least significant bits of p are known.
  4. Depending on the chosen mode either the known part P of p is entered manually or P is generated by entering the number of bits known and clicking "Generate example".
    Note:
    When entering P manually it has to be identical with p in its binary representation in e.g. 40 bits. If you choose option 1 you may want to change to the binary or hexadecimal representation every once in a while to check, whether the bits are indentical!
  5. The attack is started by clicking the "Start" button.

The section "Attack" provides information about the elapsed time of the running attack and how many lattice reductions have been completed. After the attack is finished, the found factors p and q are displayed. Furthermore the number of required bits (n / 4+1), which is calculated depending on N, is shown. From the number of known bits also follows the size of the latticebase: the more bits of one of the factors are known, the smaller the lattice can be.

Example:

Proceed according to option 1:

Attack on a RSA modulus N with a length of 200 bits:

  1. The attacker enters the publicly known value for N:
    N = 1100928820568180272388944445745883306779673638843521865435523
  2. In most of the cases both factors have exactly half the length of N. The same holds here:
    Bitlength of p: 100
  3. The attacker selects, that the upper most significant bits of p are known.
  4. He enters P = 831311796601422049670156.
  5. The attack is started by clicking "Start".

Dialog corresponding to this example:

Annotations:

  1. How much of the factor p of N has to be known does not depend on the size of p but on the size of N. To be able to determine N of a bit length of n, at least (n/4) +1 bit have to be known, but this results in a lattice the size of n, which is hard to solve from a size of n=128.
  2. When P and p match in either their decimal or hexadecimal representation they rarely match exactly in their binary representation. An attack, however, can only succeed if they exactly match binary.