# RSA: Creating a key of desired length

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?

-
Choose the highest two bits of both numbers to be 11. –  j.p. May 6 '11 at 10:09
Please see the update in my post. –  wh1t3cat1k May 25 '11 at 17:08

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.

-
The last paragraph is of course just a special case of the previous case; if you calculate √b to k digits, just set the first k digits greater than that. –  ShreevatsaR May 26 '11 at 3:00
I couldn't quite understand if this was a little mistake: $BASE^{2n+1}$ actually has to have at least $2n+2$ digits, as, e.g. $10^2$ has $2+1=3$ digits of length in base 10. Also, could you please add a few words of explanation for the dumb - why the second paragraph' method would work? "At least $\sqrt(b)$" - did you mean "more" or am I wrong again? Sorry for such questions, I really want to understand the case, not just hard-code it) –  wh1t3cat1k May 28 '11 at 19:16
@wh1t3cat1k: Sorry, (2n+1) should have been (2n-1); I've fixed it. And note that "an integer at least 31.6" is the same as "an integer more than 31.6" — both actually mean "at least 32". So if your base is not a square (i.e. $\sqrt{b}$ is not an integer), you can interpret "at least" above as "more than". In any case, it's safe to use "more" instead of "at least"; your region will still be large enough. –  ShreevatsaR May 28 '11 at 20:27

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.

-
Gadi A - what is that: p=rand(big_num) + big_num;. I'm sorry I can't quite get it. –  wh1t3cat1k May 6 '11 at 12:52
A pseudocode; What language are you using? –  Gadi A May 6 '11 at 13:41
It's not enough to set the MSB to $1$ -- the product of two $n$-bit numbers is either $2n$ or $2n-1$ bits, and the OP needs a $2n$-bit product. You have to set the top two bits to $1$, as jug said. –  TonyK May 6 '11 at 15:11
Gadi A, I am using C#. Thank you for the answer! Another problem is that my numbers may have arbitrary digit base. I'll edit my question in order to reflect the problem instead of asking a new one. –  wh1t3cat1k May 8 '11 at 8:25