RSA: Creating a key of desired length

Question

Thanks and with respect to the users of this site, I've succeeded in creating an Encryption/Decryption procedure for the RSA algorithm.

I also implemented a Miller-Rabin probabilistic primality test.

Now my question is much simpler, but my head really cannot make up an answer.

Suppose I need a key of length 1024, and I've generated two primes, each 512 bits worth. But their product won't necessarily be 1024-bit long, it may be smaller.

What should I do in this case? Discard the primes and try again? Is there a smarter solution?

Thank you very much!

============ UPDATE ===================

Thanks to jug and Gadi A, I've managed to learn that for binary numbers, setting two most significant bits to 1 is enough to gen desired bit-length.

Another challenge is that in my library big numbers may have arbitrary digit base;

So the actual structure is a_0 mod BASE | a_1 mod BASE | ... | a_(n-1) mod BASE.

What should I do in order to get a key of n digits length, where all digits have numeric base BASE?

Answer 1

I guess your updated question is: How can I generate two n-digit primes (in base $b$) such that their product has 2n digits?

One way: Have both of them greater than $\sqrt{b^{2n-1}}$. (Then their product is greater than $b^{2n-1}$ and thus has 2n digits.) You will still have a large region in which you can randomly generate the primes. For instance, to generate two 2-digit primes in base 10 whose product has 4 digits, you just have to make sure that they are both at least 32. (Since $\sqrt{1000}\approx31.6$.)

More simply, if you don't want to calculate $\sqrt{b^{2n-1}} = (\sqrt{b})b^{n-1}$ precisely, you can just make sure that the first digit of the primes is something at least $\sqrt{b}$. Thus for instance, when generating two n-digit primes in base 10, just make sure that the first digit of both primes is at least 4. (Since $\sqrt{10}\approx3.16$.) This would mean that each prime is at least $\sqrt{b}b^{n-1}$ as before, thus their product is at least $b^{2n-1}$ and has $2n$ digits.

Answer 2

You should simply pick the numbers at random in a way that ensures they are larger from some big number; it can be done by setting the MSB to be 1, as was suggested in the comment. You can also do something like

p=rand(big_num) + big_num;

One additional tip - most of the time you won't need Miller-Rabin to discover that a random number is not a prime - keep a table of the first 100 primes or so and attempt to divide the number you're testing by them first. It usually saves a lot of time in practice.