Cracked my first weak RSA implementation challenge today. Feels pretty awesome.

Involved primes that were very close, which means you can factorize the modulus quickly to get the private key. Normally, you would never use close primes as prime factorization's difficulty relies a certain amount on some distance between the two values.

The reason you can brute force close primes has to do with them being close in value to the square root of the function, meaning that you can search far quicker than if you were to try every combination of primes.

  • 0
    It might also be that since no one is going to use low primes with few digits I assume must algorithms start at the square and work down.

    Which means starting with the closest primes.
  • 0
    The best way to factorize close enough primes
Add Comment