Increase the randomness of the fact that it is [probably] [almost] random

random numbers are tastier if they are slightly peppered

We will combine theory with practice - we will show that it is possible to improve the entropy of random sequences, after which we will look at the source codes that do this.

I really wanted to write about the fact that high-quality, that is, highly entropic, random number generation is critically important in solving a huge number of problems, but this is probably superfluous. I hope everyone knows this very well.
')
In pursuit of qualitative random numbers, people invent very ingenious devices (see, for example, here and here ). In principle, quite good sources of randomness are built into the API of operating systems, but this is a serious matter, and we are always a little bit worried about the worm of doubt: is the RNG good enough that I use, and is it not spoiled by third parties?

Little theory

To begin, let us show that with the right approach, the quality of the existing RNG cannot be degraded. The simplest correct approach is to overlay any other main sequence through the XOR operation. The main sequence may be, for example, a systemic RNG, which we already consider to be quite good, but there are still some doubts, and we have a desire to make sure. An additional sequence can be, for example, a pseudo-random number generator, the output of which looks good, but we know that its real entropy is very low. The resulting sequence is the result of applying the XOR operation to the bits of the main and additional sequences. Significant nuance: the main and additional sequences must be independent of each other. That is, their entropy must be taken from fundamentally different sources, the interdependence of which cannot be calculated.

Denote as x the next bit of the main sequence, and y - the corresponding bit of the additional sequence. Bit of the resulting sequence is denoted as r :
r = x⊕y

The first attempt to prove. Let's try to go through the informational entropy x , y and r . The probability of zero x is denoted as p _x0 , and the probability of zero y as p _y0 . Informational entropies x and y are calculated using the Shannon formula:

H _x = - (p _x0 log ₂ p _x0 + (1 − p _x0 ) log ₂ (1 − p _x0 ))
H _y = - (p _y0 log ₂ p _y0 + (1 − p _y0 ) log ₂ (1 − p _y0 ))

A zero in the resulting sequence appears when the input has two zeroes or two ones. The probability of zero r:

p _r0 = p _x0 p _y0 + (1 − p _x0 ) (1 − p _y0 )
H _r = - (p _r0 log ₂ p _r0 + (1 − p _r0 ) log ₂ (1 − p _r0 ))

In order to prove the non-deterioration of the main sequence, it is necessary to prove that
Hr - Hx ≥ 0 for any values ​​of p _x0 and p _y0 . I failed to prove this analytically, but the visualized calculation shows that the increase in entropy forms a smooth surface, which is not going anywhere to go to minus:


For example, if we add a strongly skewed additional with p _y0 = 0.1 to the skewed main signal c p _x0 = 0.3 (entropy 0.881), we get the result p _r0 = 0.66 with entropy 0.925.

So, entropy cannot be spoiled, but this is not yet accurate. Therefore, we need a second attempt. However, through entropy, it is also possible to carry out the proof. Scheme (all the steps are quite simple, you can do it yourself):

1. We prove that the entropy has a maximum at the point p ₀ = 1/2.
2. We prove that for any p _x0 and p _{y0, the} value of p _r0 cannot be further from 1/2 than p _x0 .

The second attempt to prove. Through the ability to guess. Suppose an attacker has a priori some information about the main and additional sequences. The possession of information is expressed in the ability with some probability to guess in advance the values ​​of x , y and, as a result, r . The probabilities of guessing x and y are denoted respectively by g _x and g _y (from the word guess). Bit of the resulting sequence is guessed either when both values ​​are guessed correctly, or when both are wrong, therefore the probability of guessing is as follows:
g _r = g _x g _y + (1 − g _x ) (1 − g _y ) = 2 g _x g _y - g _x - g _y + 1

When we have a perfect guessler, we have g = 1. If we don’t know anything, g is ... no, not zero, but 1/2. It is this probability of guessing is obtained if we make a decision by tossing a coin. A very interesting case is when g <1/2. On the one hand, such a diviner somewhere inside of itself has data about the predictable value, but for some reason it inverts its output, and thus it becomes worse than a coin . Please remember the phrase “worse than a coin,” it will be useful to us below. From the point of view of the mathematical theory of communication (and, as a consequence, the quantitative information theory we are used to), this situation is absurd, since it will no longer be information theory, but disinformation theory, but in life we ​​have this situation more often than we would like .

Consider the limiting cases:

• g _x = 1 , that is, the sequence x is completely predictable:
  g _r = g _x g _y + (1 − g _x ) (1 − g _y ) = 1 g _y + (1 - 1) (1 − g _y ) = g _y
  That is, the probability of guessing the result is equal to the probability of guessing the additional sequence.
• g _y = 1 : Same as above. The probability of guessing the result is equal to the probability of guessing the main sequence.
• g _x = 1/2 , that is, the sequence x is completely unpredictable:
  g _r = 2 g _x g _y - g _x - g _y + 1 = 2/2 g _y - 1/2 - g _y +1 = g _y - g _y + 1/2 = 1/2
  That is, the addition of any additional sequence does not impair the overall unpredictability of the main one.
• g _y = 1/2 : Same as above. Adding a completely unpredictable extra sequence makes the result completely unpredictable.

In order to prove that adding an extra sequence to the main one doesn’t help an attacker, we need to find out under what conditions g _r can be greater than g _x , that is,

2 g _x g _y - g _x - g _y + 1> g _x

Transfer g _x from the right to the left and g _y and 1 to the right:

2 g _x g _y - g _x - g _x > g _y - 1
2 g _x g _y - 2 g _x > g _y - 1
We put in the left part 2g _x for the brackets:
2 g _x (g _y - 1)> g _y - 1
Since we have g _y less than unity (we have already considered the limiting case when g _y = 1), we will turn g _y −1 into 1 − g _y , not forgetting to change “more” to “less”:
2 g _x (1 - g _y ) <1 - g _y

We reduce “1 − g _y ” and obtain the condition under which adding an additional sequence improves the guessing situation for an attacker:

2 g _x <1
g _x <1/2

That is, g _r can be greater than g _x only when guessing the main sequence is worse than a coin . Then, when our predictor is busy conscious sabotage.

A few additional considerations about entropy.

1. Entropy is an extremely mythologized concept. Informational - including. It really hinders. Often, informational entropy is represented as some subtle matter that is either objectively present in the data or not. In fact, informational entropy is not something that is present in the signal itself, but a quantitative assessment of the a priori awareness of the message recipient regarding the message itself. That is, it is not only about the signal, but also about the recipient. If the recipient knows nothing about the signal in advance, the information entropy of the transmitted binary unit is exactly 1 bit regardless of how the signal was received and what it is.
2. We have an entropy addition theorem, according to which the total entropy of independent sources is equal to the sum of the entropies of these sources. If we connected the main sequence with the additional one through concatenation, we would save the entropies of the sources, but we would get a bad result, because in our problem we need to estimate not the total entropy, but the specific entropy, in terms of a separate bit. The concatenation of sources gives us the specific entropy of the result, which is equal to the arithmetic mean of the sources, and the entropy weak additional sequence naturally worsens the result. The use of the XOR operation leads to the fact that we lose some of the entropy, but we are guaranteed to have a resultant entropy no worse than the maximum entropy of the terms.
3. Cryptographers have a dogma: the use of pseudo-random number generators is an unforgivable arrogance. Because these generators have a small specific entropy. But we just found out that if you do everything right, entropy becomes a barrel of honey, which cannot be spoiled by any amount of tar.
4. If we have only 10 bytes of real entropy, spread out over kilobytes of data, from a formal point of view, we have only 1% of specific entropy, which is very bad. But if these 10 bytes are spread out qualitatively, and apart from brute force there is no way to calculate these 10 bytes, everything does not look so bad. 10 bytes is 2 ⁸⁰ , and if our brute force per second goes through a trillion variants, we will need an average of 19 thousand years to learn how to guess the next sign.

As mentioned above, informational entropy is a relative value. Where for one subject the specific entropy is 1, for another it may well be 0. Moreover, the one from whom 1 may have no way of knowing the true state of affairs. Systemic RNG issues a stream that is indistinguishable for us from a truly random one, but we can only hope that it is really random for everyone . And believe. If paranoia suggests that the quality of the main RNG may suddenly turn out to be unsatisfactory, it makes sense to err with the help of an extra.

Implementation of the summing RNG on Python

from random import Random, SystemRandom from random import BPF as _BPF, RECIP_BPF as _RECIP_BPF from functools import reduce as _reduce from operator import xor as _xor class CompoundRandom(SystemRandom): def __new__(cls, *sources): """Positional arguments must be descendants of Random""" if not all(isinstance(src, Random) for src in sources): raise TypeError("all the sources must be descendants of Random") return super().__new__(cls) def __init__(self, *sources): """Positional arguments must be descendants of Random""" self.sources = sources super().__init__() def getrandbits(self, k): """getrandbits(k) -> x. Generates an int with k random bits.""" ########         : return _reduce(_xor, (src.getrandbits(k) for src in self.sources), 0) def random(self): """Get the next random number in the range [0.0, 1.0).""" ########  ,   SystemRandom   .  ... return self.getrandbits(_BPF) * _RECIP_BPF 

Usage example:

 >>> import random_xe # <<<    >>> from random import Random, SystemRandom >>> #  : >>> myrandom1 = random_xe.CompoundRandom(SystemRandom(), Random()) >>> #    Random: >>> myrandom1.random() 0.4092251189581082 >>> myrandom1.randint(100, 200) 186 >>> myrandom1.gauss(20, 10) 19.106991205743107 

The main stream is taken as the SystemRandom considered correct, and the standard PRNG Random is taken as an additional stream. The meaning of this, of course, is not very much. A standard PRNG is definitely not the supplement for which all this was worth starting up. You can instead marry two system RNGs together:

 >>> myrandom2 = random_xe.CompoundRandom(SystemRandom(), SystemRandom()) 

There is even less sense in this (although this is the reason why Bruce Schneier recommends this in Applied Cryptography), because the above calculations are valid only for independent sources. If the system’s RNG is compromised, the result will also be compromised. In principle, the flight of fantasy in the search for a source of additional entropy is not limited by anything (in our world, confusion occurs much more often than order), but as a simple solution I will offer the PRNG HashRandom, also implemented in the random_xe library.

PRNG based stream cyclic hashing

In the simplest case, you can take a relatively small amount of initial data (for example, ask the user to drum on the keyboard), calculate their hash, and then cyclically add a hash to the input of the hashing algorithm and take the following hashes. Schematically, this can be represented as:



The cryptoresistance of this process is based on two assumptions:

1. The task of restoring the original data to the hash value is unbearably difficult.
2. According to the hash value, it is impossible to restore the internal state of the hashing algorithm.

After consulting with the internal paranoid, he recognized the second assumption as superfluous, and therefore in the final implementation of the PRNG scheme the scheme is a bit complicated:



Now if an attacker managed to get the value of Hash 1r, he will not be able to calculate the next value of Hash 2r, since he does not have the value of Hash 2h, which he cannot find out without calculating the counter-hashing function. Thus, the crypto-resistance of this scheme corresponds to the crypto-resistance of the hashing algorithm used.

Usage example:

 >>> #  ,  HashRandom     '123': >>> myrandom3 = random_xe.CompoundRandom(SystemRandom(), random_xe.HashRandom('123')) >>> #    Random: >>> myrandom3.random() 0.8257149881148604 

The default algorithm is SHA-256. If you want something else, you can transfer the desired type of hashing algorithm to the constructor by the second parameter. For example, let's make a composite RNG, summing up the following:

1. Systemic RNG (this is holy).
2. User input processed by the SHA3-512 algorithm.
3. The time spent on this input processed by SHA-256.

 >>> from getpass import getpass >>> from time import perf_counter >>> from hashlib import sha3_512 #    : >>> def super_myrandom(): t_start = perf_counter() return random_xe.CompoundRandom(SystemRandom(), random_xe.HashRandom( getpass('  :'), sha3_512), random_xe.HashRandom(perf_counter() - t_start)) >>> myrandom4 = super_myrandom()   : >>> myrandom4.random() 0.35381173716740766 

Findings:

1. If we are not sure of our random number generator, we can easily and incredibly cheaply solve this problem.
2. Solving this problem, we can’t do worse. Only better. And it is mathematically proven.
3. One should not forget to try to make the used sources of entropy independent.

The sources of the library are on GitHub .