3
$\begingroup$

I am reading an article about cryptography of information and Pseudo Random Number Generator. The article said using 1$28$-bit entropy PRNG is safe in some cases of cryptography. I am not familiar with this field. But after doing some research, I got some understanding listed as follows (correct me if it is not correct)

  1. entropy is used to measure how random the information is. One typical definition of entropy is the Shannon entropy which is defined to as $$H(F) = -\sum P(x) \log_2(P(x))$$ So if the information is carried by 128-bit data so each bit is occurred at probability $P(x)=1/2^{128}$, thus the entropy is 128.

  2. I read several posts and they comes with a conclusion that PRNG does not add or increase entropy.

So based on above 2 points, can I say that a $n$-bit entropy PRNG is basically a random generator with initial state chosen as $n$-bit data not the algorithm of PRNG per se (assuming the PRNG implementation takes $128$-bit data of course). Is that correct?

If it is true, my question is as follow:

Should I get any $128$-bit data as initial state will make it result from PRNG random enough or that $128$-bit data should be prepared in specific way ?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ A string of 128 bit has 128 bit of entropy if and only if the probability of each bit to be set is exactly $1/2$ ( not $1/2^{128}$) and that they are statstically independent. In general (not just for cryptography), information entropy can not be increased by any kind of algorithm: If you have at most $x$ possible configurations at the start, then you can not have more than $x$ possible configurations after your algorithm is finished. However, I don't understand your actual questions, maybe add some more detail. $\endgroup$
    – tylo
    Jan 17, 2017 at 16:57
  • $\begingroup$ @user1285419: The idea of writing a routine to seed a PRNG on my own makes me very uncomfortable, as it is notoriously difficult (look at the Debian key disaster a few years back). Your idea does not sound good to me, but I cannot offer any idea at all. (I'm usually working on platforms where there is some true random number generator with specific usage instructions by the HW-producer.) The only recommendation I can give you is to ask another question with the title "How to seed a PRNG on [your device]?" and hope for a good answer. $\endgroup$
    – hope that's start
    Jan 18, 2017 at 12:39
  • $\begingroup$ @Paul Uszak: (comment to question) There are about $10^{38}$ possible values (as $2^{128}\approx 10^{38}$), but for entropy in bits you have to take the logarithm to base 2 ending up with 128 bit. $\endgroup$
    – hope that's start
    Jan 18, 2017 at 16:16
  • $\begingroup$ @PaulUszak The term pseudorandom doesn't have anything to do with entropy, but like hopethat'sstart points it out you have to take the logarithm to base $2$ from the number of possible values to get entropy. By the way, you can not know for sure that any kind of data is incompressible - because the Kolmogorov complexity is incomputable. All you can say is that on average that data is incompressible, but not each individual output of the generator. $\endgroup$
    – tylo
    Jan 19, 2017 at 9:17

1 Answer 1

Reset to default
3
$\begingroup$

Yes, this is correct. (up to the typos that "so each bit is occurred at" in 1. should read "so each 128-bit value occurs at", and that the unit "bit" is missing at the end of that sentence; as well as the not-mentioned assumption that every time a 128-bit value is randomly picked, its value is independent of the choices take before). If the state of a cryptographically secure PRG is exactly 128 bit, then it's not allowed to "loose" any entropy during operation to be 128-bit secure, and it has to be seeded by a perfectly uniform random source.

The problem is how to choose the initial state. An attacker should have only a chance of $2^{-128}$ to guess the initial state, as (s)he could otherwise just calculate the output of the PRG (after guessing the initial state) to predict its output. So you have to find a way to pick a uniformly distributed random 128-bit value for the initial value, which is a real problem: you need a random source (that cannot be observed by the attacker) and a way to extract 128 bit entropy.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I appreciate the detail answer, I learn something from that. I have a quick follow question. If I make it to 256bit entropy support PRNG. So I need to do two things. First, I need to modify my PRNG to support 256-bit data structure, that is to use 8 32-bit integers to hold data block. Second, I need to pick 8 32-bit random integers as initial state. For example, picking those numbers in memory at random address or extract those numbers from current mouse location (similar to sshkeygen use mouse action to generate initial seed). Do you think that is the good way? Thanks again for your help. $\endgroup$
    – user1285419
    Jan 17, 2017 at 20:22

Your Answer

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

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