Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have a potentially infinite stream of data originating in some physical phenomena that may expose random behavior (due to quantum effects, thermal noise, the butterfly effect in chaotic dynamical systems, etc). The stream may carry some amount of entropy (true randomness), but it may be distributed unevenly throughout the stream and its density is unknown.

I have a limited storage space (say, 1GB). I need a procedure that can collect as much entropy as possible from the stream to the storage provided, and, when required, generate (in a reasonable time) a single file containing the collected entropy. It is preferable to make the resulting file as small as possible without reducing the amount of entropy it contains.

How can I implement such a procedure?

share|improve this question
    
Does the stream have essentially unlimited length? $\:$ Can you use significantly more space than the file's size? –  Ricky Demer Feb 7 at 22:26
    
Yes, the stream is potentially infinite, but the total available storage is limited, and a need to produce the resulting file may occur at any moment. I updated the problem statement to explain this better. –  Vladimir Reshetnikov Feb 8 at 0:29
    
If the entropy level of the stream is unknown or uneven, I would take large chunks (16KB or more) and run it through SHA-512 to produce your output, possibly encrypting each hash with with independent keys (I have used this method and it seems to produce well distributed data from poor entropy sources, my key generator was SHA256 with a nonce and incrementing counter, cipher Twofish). Do you have entropy estimates of the stream? –  Richie Frame Feb 8 at 12:13

1 Answer 1

up vote 2 down vote accepted

Partition the file into blocks of almost-equal size, and let $B$ denote the maximum block size (in bits). $\:$ Choose a randomness extractor whose outputs are long enough to
sample from the blocks and still have $B$ bits of the output left over.
Choose a seed for the extractor (unless you choose an extractor that doesn't actually use one).

For each [extractor's source's size] bits from the stream, apply the extractor to those bits,
use the output to sample a block as described before, let $s$ be the number of bits in that block,
set that block equal to its old value plus the left-most $s$ bits of the remaining extractor output
(both interpreted as unsigned integers) mod 2$^s$, then if any of the extractor's
output is still unused, continue as if those were the next bits from the stream.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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