search

Co-dfns / mystika

High-end Cryptographic Library
GNU Affero General Public License v3.0
43 stars 26 forks source link

RSA Step 1 in Key Generation #32

Open Tikhon03 opened 9 years ago

Tikhon03 commented 9 years ago

The number in RSA-2048 , 3072, and 4096 indicates the number of bits of the binary representation of n=pq. The primes p,q must be carefully designed with the following properties.

(1) p, q should each have the same number of bits as n^(1/2) (2) |p-q| should be at least 2*n^(1/4).

This means that p,q each have 1024, 1536, or 2048 bits respectively, half as many as n, and that their difference must have more than 1/4 as many bits as n.

Sketch of the construction of p and q.

Let N=1024, 1536, or 2048

Step 1: pick M random numbers in the interval [2^(N-1), 2^(N-1)+2^(N-2)-2^(N/2)) Step 2: pick M random numbers in the interval [2^(N-1)+2^(N-2)+2^(N/2), 2^N) Step 3: Check primality of the numbers constructed in steps 1-2. Step 4: Repeat steps 1-3 until at least two primes are obtained satisfying conditions (1) and (2) above. If the algorithm happens to produce more than two, keep only the largest and smallest.

Remarks

  1. The intervals used in steps 1 and 2 are chosen so that if at least on prime is found in each interval, then property (2) is automatically satisfied, hence there is no need to implement the square root function for big numbers.
  2. By the prime number theorem, the probability that an N bit number is prime is about 1/(N_ln(2)). For N=1024 this is about 1/710 and for N=2048 it is about 1/1420. If the M random numbers are uniformly distributed in the interval, we can expect the probability of finding a prime to 1-(1-1/(N_ln(2))^M. If we take M=N/2 then the probability of success is slightly greater than 1/2.
  3. To improve our probability of finding actual primes, it may be helpful to weed out numbers that are clearly not prime before applying AKS.
Tikhon03 commented 7 years ago

I think my description above may need to be revised a bit. In any case for AKS you need big number functions not implemented yet (and not mentioned in any of the issues). As such, I think this needs to be put on the side for now. I will update my description once the relevant functions are available.