"Human" entropy for a random number generator

Only because of our weakness, because of our ignorance, does an accident exist for us

A. Poincare

The more people learned the secrets of the universe, the closer they came to the point of ignorance in which their ancestors attributed everything to the gods. Now it is called - an accident. And although Einstein did not believe in chance - he said, “God does not play dice,” he is among the first on the list: Einstein, Schrodinger, Laplace ...

In our age of digital technology and the huge role of information in the development of mankind, the protection of information is the most urgent task. Technological solution of this problem involves the involvement of "randomness", namely, the generation of random numbers. At the same time, the quality of the results obtained directly depends on the quality of the generators used. This circumstance emphasizes the well-known aphorism of Robert R. Kavu from ORNL: “the generation of random numbers is too important to leave it to chance.”

Sources of real random numbers, for example, physical noise - detectors of ionizing radiation events, shot noise in a resistor, cosmic radiation, etc. - used in security applications rarely. An alternative solution is to create a set of a large number of random numbers and publish it in a dictionary. However, such sets provide a very limited source of numbers compared to the required one: these sets do provide statistical randomness, but they are not random enough.
')
Cryptographic applications use special algorithms to generate random numbers. These algorithms are predefined and, therefore, generate a sequence of numbers that cannot theoretically be statistically random. At the same time, if you choose a good algorithm, the resulting numerical sequence will pass most random tests. Such numbers are called pseudo-random numbers.

No deterministic algorithm can generate completely random numbers, it can only approximate some of their properties. As John von Neumann said, "anyone who has a weakness for arithmetic methods for obtaining random numbers is a sinner without a doubt."

Most simple arithmetic generators, although they are fast, suffer from many serious flaws:

- Too short period / periods.
- Sequential values ​​are not independent.
- Some bits are "less random" than others.
- Uneven one-dimensional distribution.
- Reversibility.

How to make such a RNG, the results of which will be unpredictable to the extent possible? What is one of the most unpredictable phenomena in nature and practically defies formalization, and therefore modeling? Human behavior: an individual, not the masses (crowds, groups, organizations, clubs, etc.).

It is proposed to construct the RNG on the idea of ​​the unpredictability of the behavior of an individual. To implement the project, the integrated development environment Microsoft Visual Studio 2010 and the language Visual Basic .NET were chosen.

On the form of the project are placed next to each other 56 buttons-squares. Each button is associated with a MouseEnter system event.



In the event handler of each button is the code that receives the system time in milliseconds. When you hover the cursor over a button, a certain number within 0 ÷ 999 is stored in the memory. When the cursor is repeated over the same button, a new number is saved. Thus, the user randomly holds the cursor over the field of buttons, forming a series of numbers. It is recommended to “work” (hold the cursor over the buttons) at least 1/2 of the field to get the “best” sequence (with a smaller number, the program will not allow to get a series of numbers).

Regardless of how many squares the cursor was held, as a result we will always get 56 digits. "Missing" numbers appear as follows:

- Creates 2 arrays b and c with dimension of 56 elements each. Alternately randomly (built-in function) are filled with arrays b and c; each time, before the next item is filled, a randomization counter reset is initiated, otherwise each subsequent value would depend on the previous one.
- The fragment of the program code (presented below) illustrates the algorithm for filling the array:

Randomize() znak = Rnd() * 5 If znak = 0 Then a(ii) = b(ii) + c(ii) If a(ii) > 999 Then While a(ii) > 999 a(ii) = (a(ii) / 3.14) + Rnd() * 42 End While End If ElseIf znak = 1 Then a(ii) = b(ii) - c(ii) If a(ii) < 0 Then a(ii) = a(ii) * (-1) End If ElseIf znak = 2 Then a(ii) = b(ii) * c(ii) If a(ii) > 999 Then While a(ii) > 999 a(ii) = (a(ii) / 3.14) + Rnd() * 42 End While End If ElseIf znak = 3 Then a(ii) = b(ii) / (c(ii) + Rnd() * 9) If c(ii) = 0 Then c(ii) = Rnd() * 99 + 1 End If If a(ii) > 999 Then While a(ii) > 999 a(ii) = (a(ii) / 3.14) + Rnd() * 42 End While End If ElseIf znak = 4 Then a(ii) = Now.Millisecond End If 

Each time, with the next “backup” array filling, the Randomize () function is called, which takes as its initial point the value of the system timer, rather than the previous value of Rnd. That is, each time, generating the next sequence, the user initiates filling the arrays b and c anew, with different values ​​that do not depend on each other.
After the user has “poeled” enough across the field, he clicks on the corresponding button and gets the result.
The program will allow the user to see the result of the work only if he has “engaged” at least half of the field buttons, otherwise he will receive a message about the need to “activate” a larger number of “responsive” buttons. The implemented program allows you to copy the data to the clipboard. The user can also receive statistical data on the generated sequence, such as the number of generation starts, the distribution of numbers by intervals, the sum of this series of numbers, by clicking the corresponding button.

Buttons-squares are arranged in an absolutely chaotic order, that is, the first button (if you use it with the cursor) does not necessarily determine the first number of the sequence, etc., which additionally improves the “randomness”, so even if you move along the field line by line, with an admissible high speed it will be impossible to determine the consistency of the resulting sequence. It is impossible to predict how the user will behave, in what sequence he will lead the cursor over the squares, which will involve, which are not. It should be noted that when repeating the same algorithm of cursor movements, we will get different numbers: it is impossible to get into the same time interval in which the previous cursor trajectory was “drawn”, since human reaction is simply not capable of such. Thus, the quality of the proposed generator is due, inter alia, to an external source of entropy:

- arbitrariness of the buttons on the form;
- arbitrariness of their choice by the user;
- unpredictability of the time interval of this choice.
This generator was tested for quality of work:
- accident;
- uniform distribution;
- statistical independence.

Testing was carried out repeatedly, by different people, at different times. Tests were used: peak criterion, uniform distribution testing: expectation, variance, standard deviation, frequency test, Chi-square test, statistical independence test, no auto-correlation. Most of the tests showed the reliability of this generator (at least 90%), the Chi-square test showed 99% reliability, testing of individual statistics always showed results close to the benchmark for uniform distribution.

UPD:
If software implementation is interesting, then download it here . I wrote more than a year ago, I dare to hope that since then the programming skill has improved :)