In previous post I was testing and comparing different factorization algorithms.

Based on my observation, the two most critical factors determining the time required to crack private key are

• size (bit length)
• the mathematical properties of its prime factors.

bit length

Most straightforward factor. Most of the known algorithms has exponential complexity. So factoring 2048bit number is not twice as hard as 1024bit number – it is trillions time harder. Current standard is 4096, because it is completely impossible with current technology.

prime factor properties – hidden weakness

Pollard’s p-1 algorithm introduces “smoothness” concept. A number is “smooth” if all his prime factors are small. For example:

• 3,024 seems reasonably large. But its prime factorization is 2^4 × 3^3 × 7. Since its largest prime factor is just 7, this is a 7-smooth number.
• 3,026 is very close to 3,024. But its prime factorization is 2 × 1513. Because it has a large prime factor (1513), it is not a smooth number.

Pollard’s p-1 works incredibly fast, if p-1 or q-1 is smooth.

https://github.com/o-lenczyk/rsa/blob/master/rsa_from_scratch.py#L60

Above you can find a function to generate smooth primes, that can be used to create extremely insecure RSA key pair.

core logic

1. Dynamic smoothness bound calculation:
   Instead of a fixed bound, this function calculates initial smoothness bound, based on the required prime length. This ensures, that for larger primes, there is a larger pool of small primes to work with. Initially I tried fixed, small bound. This was leading to extremely long generation times.
2. Generating small primes:
   helper function to generate all prime numbers up to current smoothness_bound. Those primes will be building p-1
3. Constructing p-1
   function will multiply small primes, until p-1 is close to desired length of p
4. primality test of (p-1)+1
   initially it was done with sympy, but c library is many times faster
5. Smoothness check
   calculating max prime power of p-1 (e.g. 2^8, 3^5). Initially I was checking only for max factor, but this was insufficient. If p-1 contained a prime like 17^6 = 24 137 569, but maximum bound was set to 200 000, the attack would fail. Or took significantly more time.
6. max_prime_power threshold
   the function rejects primes where max prime power exceeds a predefined threshold – currently 20 000 000. Initially it was set to 200 000, because finding such a prime took a long time. Anyway, the longer we will look for vulnerable primes, the faster the Pollard’s p-1 will crack such a key.
7. iterative bound increase
   if no prime is found in 10 000 attempts, the current smoothness bound is doubled

vulnerable key

Finding such a weak example is not an easy task, but after tuning few parameters I was able to generate super-smooth 4096bit key:
https://github.com/o-lenczyk/rsa/blob/master/smooth-keys.txt

cracking it took just 8s. Cracking almost any other key is not possible.

Unique characteristic of this p-1 is max prime factor = 32309, same as max power. This is extremely small number for 2.39×10^599. Or two hundred thirty-nine octononagintacentillion. Or number 10^519 times larger than the number of atoms in the observable universe. Interestingly, computations took less than hour to finish. Below is full list of factors of vulnerable p-1:

Factors of p-1: {2: 1, 47: 1, 269: 1, 383: 1, 491: 1, 709: 1, 967: 1, 1277: 1, 1279: 1, 1381: 1, 1657: 1, 1667: 1, 2377: 1, 2887: 1, 2957: 1, 2969: 1, 3389: 1, 3793: 1, 4201: 1, 4349: 1, 4357: 1, 4517: 1, 4919: 1, 5407: 1, 5563: 1, 5573: 1, 5647: 1, 5867: 1, 6301: 1, 6577: 1, 6637: 1, 6733: 1, 6883: 1, 6959: 1, 7027: 1, 7459: 1, 7537: 1, 7879: 1, 7949: 1, 8179: 1, 8209: 1, 8297: 1, 8423: 1, 8627: 1, 8693: 1, 8699: 1, 8731: 1, 8821: 1, 8963: 1, 9311: 1, 9467: 1, 9623: 1, 9923: 1, 10061: 1, 10987: 1, 11093: 1, 11161: 1, 11621: 1, 12041: 1, 12253: 1, 12511: 1, 12613: 1, 12899: 1, 13109: 1, 13291: 1, 13469: 1, 13591: 1, 13711: 1, 14173: 1, 14431: 1, 14533: 1, 14561: 1, 14731: 1, 14747: 1, 14869: 1, 14951: 1, 15013: 1, 15139: 1, 15277: 1, 15559: 1, 15773: 1, 15907: 1, 15919: 1, 15959: 1, 16333: 1, 16921: 1, 16927: 1, 17033: 1, 17321: 1, 17327: 1, 17341: 1, 17683: 1, 17827: 1, 17957: 1, 18131: 1, 18223: 1, 18587: 1, 19267: 1, 19429: 1, 19463: 1, 19751: 1, 19867: 1, 19973: 1, 20123: 1, 20327: 1, 20389: 1, 20483: 1, 21397: 1, 21401: 1, 21529: 1, 21559: 1, 21839: 1, 22037: 1, 22073: 1, 22109: 1, 22147: 1, 22271: 1, 22409: 1, 22469: 1, 22619: 1, 22811: 1, 23011: 1, 23173: 1, 23677: 1, 25733: 1, 25799: 1, 26399: 1, 26731: 1, 27061: 1, 27673: 1, 27773: 1, 27917: 1, 28051: 1, 28297: 1, 28447: 1, 29131: 1, 29179: 1, 29201: 1, 29387: 1, 29483: 1, 29573: 1, 29587: 1, 29663: 1, 29983: 1, 30161: 1, 30203: 1, 30661: 1, 30949: 1, 31547: 1, 31667: 1, 31751: 1, 32261: 1, 32309: 1}

what to do

Easiest way to mitigate the risk is to generate “safe” prime:

• (p-1)/2 is a prime number. It means that p-1 has large prime factor, so it is not “smooth”. This structure completely neutralizes the vulnerability exploited by algorithms like Pollard’s p-1