3
$\begingroup$

I'm using Crypto++ to implement my protocol to mask a value $y_i$ by a pseudo-random value $r_i$ such that $m_i=y_i \cdot r_i$. Since there are many $r_i$'s I want to generate them using PRNG and then only store the seed for the PRNG. With the seed any I can regenerate $r_i$, then compute $r^{-1}_i$ to remove $r_i$'s. But in crypto++ the seed (key) cannot be accessible.

So my question is: how can I use PRNG of crypto++ to accommodate the above technique?

Let $r_i \stackrel{R} \leftarrow \mathbb{Z}_p$ and $y_i \in \mathbb{Z}_p$, where p is a prime number.

|improve this question
$\endgroup$
4
$\begingroup$

Formally, what you're really looking for is a key derivation function (KDF).

The Crypto++ API includes a PasswordBasedKeyDerivationFunction class, but that doesn't really seem optimal for your purposes; since you already have a high-entropy random seed, what you really want is a simple key-based KDF, not a fancy key-stretching KDF meant for use with passwords.

Fortunately, it's not hard to implement one yourself. A very simple approach would be to use your "seed" as the key for a stream cipher (or to, say, AES in CTR mode), and use the keystream (which you can obtain by encrypting a bunch of null bytes) as your source of random bytes.

(You can then convert these random bytes into uniform random integers in your desired range e.g. by rejection sampling: to generate a random number between $0$ and $m$ inclusive, first find $k = \lceil\log_2m\rceil$, i.e. the length of $m$ in bits, then generate a random $k$-bit string. If this bitstring, interpreted as a binary number, is less than or equal to $m$, you're done; else, toss it out and repeat. It's not hard to prove that, on average, you'll end up rejecting less than half of all bitstrings (since $m \ge \frac12 2^k$). Note, however, that this does potentially leak some statistical timing information about the most significant bits of $m$, which might matter if you want to keep it secret.)

Alternatively, with only slightly more work, you can implement a standard construction like HKDF (RFC 5869), or one of the DRBG algorithms from NIST SP 800-90A (note: do not implement Dual_EC_DRBG!). CTR_DRBG, in particular, is very similar to the simple "use seed as key to AES-CTR, take keystream" suggestion above.

|improve this answer
$\endgroup$
  • $\begingroup$ One problem I have is that in PRG I cannot access the seed generated, In other words, I dont know how to access the seed the underlying function (e.g. randompool,...) generates. $\endgroup$ – user13676 Feb 15 '15 at 12:09
  • 3
    $\begingroup$ That's why I would suggest not using RandomPool. (Another reason is that, as far as I can tell, the exact algorithm used by RandomPool is not documented, so there's no guarantee that the output won't change between different Crypto++ versions.) Instead, just implement your own pseudorandom bitstream generator (like one of the NIST DRBG algorithms) using the primitives provided by Crypto++ (e.g. SymmetricCipher or HMAC). $\endgroup$ – Ilmari Karonen Feb 15 '15 at 16:15
  • $\begingroup$ NIST SP800-108 contain alternate KDF's. HKDF and the NIST ones have been implemented in Bouncy Castle (initially by me) if you want a reference (and there are test vectors available from NIST - more than you want probably). Reading this again it might be better to create your own DRBG just to be sure, KDF's are usually not meant to create an endless stream of data. $\endgroup$ – Maarten Bodewes♦ Feb 16 '15 at 14:55
  • $\begingroup$ Meaning that KDF's are usually not meant to create an endless stream of data - you probably need to supply the required key size up front (out of time for comment :) ) $\endgroup$ – Maarten Bodewes♦ Feb 16 '15 at 15:01
  • 1
    $\begingroup$ @Maarten: True enough. FWIW, HKDF can generate an endless stream of data, at least if you implement it yourself; perhaps more usefully, even if you're using a pre-built implementation that wants the output length up front, it can still generate arbitrarily many quasi-independent output strings, if you feed it distinct info strings for each output. So, to generate a key X with a rejection sampling scheme, you could ask for keyX/1, then keyX/2, etc., until you get an acceptable output. $\endgroup$ – Ilmari Karonen Feb 17 '15 at 3:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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