Secure random number of aproximately given size

Question

I'm doing a Secret Sharing algorithm which encrypts a a message. To do that I need a bigger than message prime and some random numbers of aproximately the same size as the message.

I can do the first with BigInteger.probablePrime(MsgSize+8) but I do not know how to do the later.

I was using Random and later SecureRandom but they don't generate numbers of a given length. My solution was to do randomInt ^ randomInt to BigInteger but is obviously a bad solution.

Some ideas?

Answer 1

Is it Shamir's Secret Sharing that you're implementing? If so, note that you don't actually need a prime bigger than the entire message — it's perfectly fine to break the message into chunks of some manageable size and to share each chunk separately using a fixed prime.

Also, Shamir's Secret Sharing doesn't need a prime-sized field; it's possible to use any finite field GF(pⁿ), including in particular the binary fields GF(2ⁿ). Such fields are particularly convenient for computer implementation, since the both the secret and share chunks will then be simply n-bit bitstrings.

The only complications are that, in non-prime fields, you'll have to implement finite field arithmetic (or find an existing implementation) and that you'll need to choose a particular reducing polynomial and agree upon it. However, the former isn't really as complicated as it might seem, and the latter isn't really any harder than choosing and agreeing on a prime. (In particular, a reducing polynomial for GF(2ⁿ) can be naturally represented as an n-bit bitstring, dropping the high bit which is always 1.)