Breaking RSA when some bits of one prime are known RSA primes are 100 bit. You know first 80 bits of one of the primes. In this system, come up with an efficient way to decrypt the cipher-text. 


This was the question on my quiz. I'm not sure how to go about it. Any hints?
The attack here is a simple factoring of the modulus. If you know the first 80 bits of a prime, you have 20 bits of search space using the most naïve trial division method, and 19 bits by just throwing out even numbers. Now you could use more advanced factoring techniques, but for only 19 bits of search space, you have 524288 candidates to test, which would take most modern processors a couple of seconds at the very most, so unless you have a large number of bad RSA keys to break, not much more effort than that needs be invested.

After factoring the modulus, you can decrypt at will.

The simplest approach is to make a counter, start at 1, and increment by two every iteration. Add the counter to the known starting point, and try to divide the modulus. If there's a remainder, continue the loop.

If the known bits are anything but the large end, its only slightly more complicated, and the search space is larger as we can't automatically throw out even numbers, so you have just over a million candidates to test. Here we use a counter then shift the bits into a mask to add to the known bit vector.