For example, if to the skewed main signal c p _x0 = 0.3 (entropy ???) add a strongly skewed complement with p _y0 = 0.? we obtain the result p _r0 = ??? with an entropy of ???.
 
 
So, the entropy can not be spoiled, but it is not yet certain. Therefore, we need a second attempt. However, it is also possible to carry out proof through entropy. Scheme (all steps are simple enough, 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 p _r0 can not be farther from 1/2 than p _x0 .
 
 
The second attempt to prove. Through the ability to guess. Let's say an attacker has a priori some information about the main and additional sequences. The possession of information is expressed in the ability to guess with some probability the values ​​of in advance. x , y and, as a consequence, r . Probabilities of guessing are x and y will be denoted as [/b] ? respectively. g _x [/b] and g _y (from the word guess). The bit of the resulting sequence is guessed either when both values ​​are correctly guessd, or when both are incorrect, so the guessing probability is:
 
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 the perfect guesser, we have [i] g = 1. If we do not know anything, g is equal to no, not zero, but 1/2. It is this probability of guessing that is obtained if we make a decision by throwing a coin. Very interesting case when g <1/2. С одной стороны, такой угадыватель где-то внутри себя обладает данными об угадываемой величине, но зачем-то инвертирует свою выдачу, и таким образом становится worse coin . Remember, please, the phrase "worse coin", it will be useful below. From the point of view of the mathematical theory of communication (and, as a consequence, the usual quantitative theory of information), this situation is absurd, since this will not be a theory of information but a theory of disinformation, but in life this state of affairs is much more frequent than we would like .
 
 
Let us consider the limiting cases:
 
 
 
g _x = 1 , that is, the sequence x fully predictable:
 
g _r = g _x g _y + (1-g _.x ) (1-g _Y ) = 1 g _y + (1-1) (1-g ? y [/sub] ) = G _y
 
That is, the probability of guessing the result is equal to the probability of guessing the additional sequence.
 
[i] g _y = 1 : Same as above. The probability of guessing the result is equal to the probability of guiding the main sequence.
 
g _x = 1/2 , that is, the sequence x 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, adding any additional sequence does not worsen 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 additional sequence to the main one does not help an attacker, we need to find out under what conditions g _r can be more than g _x , that is
 
2 g _x g _y G _x G _y + 1> g _x
 
We 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 carry out in the left part 2g _x for the brackets:
 
2 g _x (g ? y [/sub] -1)> g _y - 1
 
Since we have g _y is less than unity (the limiting case when g _y = ? we have already considered), then turn g _y -1 in 1-g _y , not forgetting to change "more" to "less":
 
2 g _x (1-g ? y [/sub] ) < 1 − g _y
 
We shorten "1-g _y "And get the condition that adding an additional sequence will improve the intruder's guessing situation:
 
2 g _x < 1
 
g _x < 1/2
 
That is [i] g _r can be more than [i] g _x Only when guessing the main sequence worse coin . Then, when our predictor is engaged in conscious sabotage.
 
 
A few additional considerations about entropy.
 
 
 
Entropy is an extremely mythological concept. Information - including. This is very disturbing. Often information entropy is presented as a kind of subtle matter, which is either objectively present in the data, or not. In fact, information entropy is not something that is present in the signal itself, but a quantitative estimate of the a priori awareness of the recipient of the message relative to the message itself. That is, it is not only about the signal, but also about the recipient. If the receiver does not know anything about the signal in advance, the information entropy of the transmitted binary one is exactly 1 bit, regardless of how the signal was received and what it is.
 
We have a theorem on the addition of entropies, according to which the total entropy of independent sources is equal to the sum of the entropies of these sources. If we connected the basic sequence with the complementary sequence through concatenation, we would preserve the entropy 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, in terms of a separate bit. The concatenation of sources gives us the specific entropy of the result, equal to the average arithmetic entropy 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 part of the entropy, but we are guaranteed to have the resulting entropy not worse than the maximum entropy of the terms.
 
Cryptographers have a dogma: the use of pseudo-random number generators is unpardonable presumption. Because these generators have a small specific entropy. But we just found out that if we do it right, entropy becomes a barrel of honey, which can not be ruined by any amount of tar.
 
If we have only 10 bytes of real entropy,Data per kilobyte 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 smeared qualitatively, and besides bruteforce there is no way to calculate these 10 bytes, everything looks not so bad. 10 bytes is 2 ⁸⁰ , and if our brute force per second looks at a trillion options, we will need an average of 19 thousand years to learn how to guess the next sign.
 
 
As was said above, the information entropy is a relative quantity. Where, for one entity, the specific entropy is ? for another, it may well be 0. Moreover, one who has 1 may not have any opportunity to know the true state of affairs. The system RNG produces a stream that is indistinguishable from the really random, but that it is really random for all , we can only hope. And believe. If paranoia suggests that the quality of the main RNG can suddenly turn out to be unsatisfactory, it makes sense to insure yourself with an additional one.
 
 

The 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.
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." ""
######## In fact, all this for the sake of this line:
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
[/code]
Пример использования:
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[/code]
В качестве основного потока взят считающийся правильным SystemRandom, а в качестве дополнительного – стандартный ГПСЧ Random. Смысла в этом, конечно, не очень много. Стандартный ГПСЧ – точно не та добавка, ради которой всё это стоило затевать. Можно вместо этого поженить между собой два системных ГСЧ:
myrandom2 = random_xe.CompoundRandom(SystemRandom(), SystemRandom())[/code]
Смысла, правда в этом ещё меньше (хотя именно такой приём почему-то рекомендует Брюс Шнайер в «Прикладной криптографии»), потому что приведённые выше выкладки справедливы только для независимых источников. Если системный ГСЧ скомпрометирован, результат также получится скомпрометированным. В принципе, полёт фантазии в деле поиска источника дополнительной энтропии ничем не ограничен (в нашем мире беспорядок встречается намного чаще, чем порядок), но в качестве простого решения предложу ГПСЧ HashRandom, также реализованный в библиотеке «random_xe».

ГПСЧ на основе потокового циклического хеширования

В простейшем случае можно взять некоторое относительно небольшое количество начальных данных (например, попросить пользователя побарабанить по клавиатуре), вычислить их хеш, а потом циклически доливать хеш на вход алгоритма хеширования и брать следующие хеши. Схематически это можно изобразить так:

Криптостойкость этого процесса основывается на двух предположениях:
1. Задача восстановления исходных данных по значению хеша невыносимо сложна.
2. По значению хеша невозможно восстановить внутреннее состояние хеширующего алгоритма.
Посовещавшись с внутренним параноиком, признал второе предположение лишним, и поэтому в чистовой реализации ГПСЧ схема немножко усложнена:

Теперь если злоумышленнику удалось получить значение «Хеш 1r», он не сможет вычислить следующие за ним значение «Хеш 2r», так как у него нет значения «Хеш 2h», которое он не сможет узнать, не вычислив функцию хеширования «против шерсти». Таким образом, криптостойкость этой схемы соответствует криптостойкости применяемого хеширующего алгоритма.
Пример использования:
# Создаём объект, проинициализировав HashRandom лучшим в мире паролем '123':
myrandom3 = random_xe.CompoundRandom(SystemRandom(), random_xe.HashRandom('123'))
# Используем как обычный Random:
myrandom3.random()
0.8257149881148604[/code]
По умолчанию используется алгоритм SHA-256. Если хочется чего-то другого, можно в конструктор вторым параметром передать желаемый тип алгоритма хеширования. Для примера сделаем составной ГСЧ, суммирующий в кучу следующее:
1. Системный ГСЧ (это святое).
2. Пользовательский ввод, обрабатываемый алгоритмом SHA3-512.
3. Время, затраченное на этот ввод, обрабатываемое 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[/code]
Выводы:
1. Если мы не уверены в своём генераторе случайных чисел, мы можем легко и потрясающе дёшево решить эту проблему.
2. Решая эту проблему, сделать хуже мы не сможем. Только лучше. И это математически доказано.
3. Нужно не забыть постараться сделать так, чтобы использованные источники энтропии были независимыми.
Исходники библиотеки – на GitHub.