4
$\begingroup$

I am not exactly sure if this is for math stackexchange or crypto:

A TRNG outputs numbers in $[0,1]$ in a Gaussian distribution. I would like to convert them into uniform random bytes ($[0,255] $) to perform byte operations. What is s cryptographically secure method of doing this?

Here is an example distribution from my generator before normalized between $[0,1]$: enter image description here

Edit:

Output from my original methodology: Normalize values to to be within $[0,1]$, remove first and second decimal place via $x*100-floor(x*100)$, then put between value discrete values in $[0,255]$ via $floor(x*255)$. The resulting distribution is as follows: enter image description here

Improve this question
$\endgroup$
15
  • $\begingroup$ What are the parameters of the gaussian generator? What is the actual distribution of output bytes? $\endgroup$
    – Thomas
    Commented Jul 25, 2015 at 10:51
  • $\begingroup$ @Thomas I cleared up my question. $\endgroup$
    – dylan7
    Commented Aug 1, 2015 at 17:29
  • $\begingroup$ A Gaussian distribution is defined from $-\infty$ to $+\infty$. The [0,1] range doesn't make any sense. $\endgroup$
    – Chris
    Commented Aug 1, 2015 at 18:51
  • $\begingroup$ @Chris I will post a picture of it when i get a chance. It is Normal but it might be discrete values in $[0,1]$ i.e. 3 decimal floating. $\endgroup$
    – dylan7
    Commented Aug 1, 2015 at 18:56
  • $\begingroup$ A Normal distribution is continous and not discrete. I'm afraid you are mixing up a number of things here. $\endgroup$
    – Chris
    Commented Aug 1, 2015 at 19:22

2 Answers 2

Reset to default
3
$\begingroup$

There is no such thing like a Gaussian distribution over [0,1]; this doesn't make any sense. So it is not clear what you have to begin with.

However, if you have independent random values, you can generate a random bit by taking two values A and B and comparing them. E.g., if $A<B$ you set the bit to 0, otherwise you set the bit to 1. A sequence of 8 such bits is then a (uniformly distributed) random byte.

PS: As correctly mentionned by Ilmari Karonen, if you have a non-negligible probability to have A=B, you have to check for this and if it happens you have to discard A and B.

Improve this answer
$\endgroup$
8
  • $\begingroup$ As I said above in my commrnt to the prevoous answer, I tested that with a normal pseudo rng, and a histogram of the bytes produced a distribution far from uniform. Are the bits themselves only suppose to be uniformly distributed ? $\endgroup$
    – dylan7
    Commented Aug 2, 2015 at 14:46
  • 2
    $\begingroup$ Note that, for this method to really generate unbiased bits, you'll have to discard both $A$ and $B$ and repeat the process if $A=B$. In fact, such rejection sampling is unavoidable in general: for input distributions having less than 0.5 bits of entropy, there's no way to get an unbiased output bit without sometimes consuming more than two input samples. Also note that this scheme relies on the samples being independent; if subsequent samples may be linked (as they, inevitably, are for PRNGs; good PRNGs try to hide this dependence, more or less successfully), the output can easily be biased. $\endgroup$
    – Ilmari Karonen
    Commented Aug 2, 2015 at 14:46
  • 1
    $\begingroup$ @dylan7: You may have just demonstrated that your pseudo-RNG isn't as random as you think it is. In fact, serial correlation between successive samples is a common flaw in popular LCRNGs. $\endgroup$
    – Ilmari Karonen
    Commented Aug 2, 2015 at 14:56
  • 1
    $\begingroup$ @dylan7: Ah, no. You don't need the mean for anything. What Chris is saying is that you should take two random values, and see which one is greater. Assuming that they're independent and identically distributed, and that they don't happen to be equal, that will give you one unbiased bit. Then take two more values and compare them to get another bit, and so on. $\endgroup$
    – Ilmari Karonen
    Commented Aug 2, 2015 at 15:41
  • 2
    $\begingroup$ @dylan7: If the two values are equal, you'll need to discard them both, and get two new values. Basically, you're taking in two random values A and B (from any distribution) and returning either 1 (if A > B), 0 (if A < B) or no value (if A = B). Otherwise, you may end up with biased results. For reference, this is basically a variant of von Neumann whitening, extended to non-binary input distributions. $\endgroup$
    – Ilmari Karonen
    Commented Aug 2, 2015 at 17:58
1
$\begingroup$

Depending on the parameters of the Gaussian, every $X_i$ byte will have some entropy < 8 bits. So you cannot produce cryptographically random bytes from each of them, unless you add some entropy from another source.

You can, however, turn them into smaller values. For example, if they have at least 1 bit of entropy, you can turn them into bits. Like if the distribution had a peak at 127.5, you could just map everything smaller than that to 0 and larger to 1. Since the transform is not an injection, it's non-invertible. The resulting output is uniformly random and independent.

Or you can use a secret key and a one way transform to produce an output byte stream, like the first byte of $H(K||X_i||i)$ for some hash function $H$. But the $X_i$ aren't really doing a whole lot in that case – you could be using just $H(K||i)$.

Improve this answer
$\endgroup$
12
  • $\begingroup$ Thank you. One thing I was able to do was put the values between 0 and 1 chop off the tenths place. And then convert then back to 0->255. This produce a uniform distribution, since it stops them from "cluttering around a mean value" it makes them more "independent (not in the probability sense)". Is this also cryptographically secure, do they still lose entropy ? $\endgroup$
    – dylan7
    Commented Jul 25, 2015 at 14:41
  • $\begingroup$ @dylan7, I'm not really sure what you mean... if you convert a byte into a floating point between 0-1 and chop something off, you will probably no longer be able to get every possible value in $[0,255]$ when you convert them back. That would definitely not be good enough for anything crypto. $\endgroup$
    – otus
    Commented Jul 25, 2015 at 16:58
  • $\begingroup$ My fault I realized I wasn't clear enough. $X_i $ is converted to between 0 and 1 (floating point) then do $X_i_float * 100 - floor (X_i_float *100)$ then convert back to [0-255]. This changes the 10ths and 100ths. So I believe all values 0-255 are covered. $\endgroup$
    – dylan7
    Commented Jul 25, 2015 at 21:04
  • $\begingroup$ @dylan7, from a quick test in Python, less than half the numbers are possible outputs. Anyway, with any such transform you either have a bijection that only shuffles the probabilities, or you lose some codomain values due to collisions. You can't get a uniform distribution with a deterministic mapping $[0,255] \mapsto [0,255]$ if the original isn't uniform. $\endgroup$
    – otus
    Commented Jul 26, 2015 at 5:52
  • $\begingroup$ When I did it in MATLAB I was able to get a uniform distribution. The values came in as 0 to 1 then the transformation was performed then converted them to 0->255 [discrete values ->flooring the result, so there were no floating points. So the whole thing is really $[0,1] \mapsto [0,255] $ . If it's not really a uniform distribution , because you said it can't happen, what else could be causing what I am seeing? Thank you again $\endgroup$
    – dylan7
    Commented Jul 26, 2015 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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