Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
1  
Think about what your search space is. What is your search space for brute-force if you know nothing about the primes? Now, what is your search space given the 80 bits you know. –  mikeazo May 14 at 11:44
    
An Elliptic-curve factoring program such as GMP-ECM will quickly find a 100-bit factor in any integer of several thousands bits, so the first sentence alone makes no practical sense. I wonder if we could find a better-than-bruteforce method that would work with all parameters scaled up, say by 10. –  fgrieu May 15 at 8:45

1 Answer 1

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.

share|improve this answer
    
Thanks for the help...I guess brute force would have been enough as a solution on the quiz. –  user3199040 May 16 at 1:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.