Obtaining and converting random numbers.
There are two main ways to obtain random numbers:
1) Random numbers are generated by a special electronic attachment (random number sensor) installed on the computer. The implementation of this method requires almost no additional operations other than accessing the random number sensor.
2) Algorithmic method - based on the generation of random numbers in the machine itself through a special program. The disadvantage of this method is the additional consumption of computer time, since in this case the machine performs the operations of the electronic set-top box itself.
A program for generating random numbers using a given distribution law can be cumbersome. Therefore, random numbers with a given distribution law are usually obtained not directly, but by transforming random numbers that have some standard distribution. Often this standard distribution is the uniform distribution (easy to obtain and easy to convert to other laws).
It is most advantageous to obtain random numbers with a uniform law using an electronic set-top box, which frees the computer from additional costs of computer time. Obtaining a purely uniform distribution on a computer is impossible due to the limitations bit grid. Therefore, instead of a continuous set of numbers on the interval (0, 1), a discrete set of numbers is used 2n numbers, where n– bit depth of the machine word.
The law of distribution of such a population is called quasi-uniform . At n³20, the differences between the uniform and quasi-uniform laws become insignificant.
To obtain quasi-uniform random numbers, two methods are used:
1) generating random numbers using an electronic set-top box by modeling some random processes;
2) obtaining pseudorandom numbers using special algorithms.
For getting n-digit binary random number using the first method, a sequence of independent random variables z i, taking the value 0 or 1. The resulting sequence is 0 and 1, if we consider it as a fractional number, and represents a random variable of quasi-uniform distribution on the interval (0, 1). Hardware methods for obtaining these numbers differ only in the way they obtain the implementation z i.
One of the methods is based on counting the number of radioactive particles over a certain period of time Dt, if the number of particles is beyond Dt even, then z i=1 , and if odd, then z i=0 .
Another way is using a noise effect vacuum tube. By recording the value of noise voltage at certain points in time t i, we obtain the values of independent random variables U(t i), i.e. voltage (Volts).
Magnitude z i determined by law:
Where a– a certain value of the threshold voltage.
Magnitude a usually selected from the condition:
The disadvantage of the hardware method is that it does not allow the use of the double-run method to control the operation of the algorithm for solving any problem, since repeated runs cannot obtain the same random numbers.
Pseudorandom call numbers generated on a computer using special programs recurrent method: each random number is obtained from the previous one using special transformations.
The simplest of these transformations is the following. Let there be some n– bit binary number from the interval nО (0, 1). Let's square it, and we get 2n digit number. Let's highlight the averages n discharges. Obtained in this way n– digit number will be the new value of the random number. We square it again, etc. This sequence is pseudorandom, because from a theoretical point of view, it is not random.
The disadvantage of recurrent algorithms is that sequences of random numbers may degenerate (for example, we will receive only a sequence of zeros or a sequence of ones, or periodicity may appear).
Deterministic PRNGs
No deterministic algorithm can generate completely random numbers, it can only approximate some properties of random numbers. As John von Neumann said, " anyone who has a weakness for arithmetical methods of obtaining random numbers is sinful beyond any doubt».
Any PRNG with limited resources sooner or later goes in cycles - it starts repeating the same sequence of numbers. The length of PRNG cycles depends on the generator itself and on average is about 2 n/2, where n is the size internal state in bits, although linear congruent and LFSR generators have maximum cycles of the order of 2n. If a PRNG can converge to cycles that are too short, the PRNG becomes predictable and unusable.
Most simple arithmetic generators, although very fast, suffer from many serious disadvantages:
- The period/periods are too short.
- Consecutive values are not independent.
- Some bits are "less random" than others.
- Uneven one-dimensional distribution.
- Reversibility.
In particular, the mainframe algorithm turned out to be very poor, which raised doubts about the validity of the results of many studies that used this algorithm.
PRNG with entropy source or RNG
Just as there is a need to generate easily repeatable sequences of random numbers, there is also a need to generate completely unpredictable or simply completely random numbers. Such generators are called random number generators(RNG - English) random number generator, RNG). Since such generators are most often used to generate unique symmetric and asymmetric keys for encryption, they are most often built from a combination of a cryptographic PRNG and external source entropy (and it is precisely this combination that is now commonly understood as RNG).
Almost all major chip manufacturers supply hardware RNGs with various sources entropy using various methods to clear them of inevitable predictability. However, on this moment the speed at which random numbers are collected by all existing microchips (several thousand bits per second) does not correspond to the speed of modern processors.
In personal computers, software RNG authors use much faster sources of entropy, such as sound card noise or processor clock cycle counter. Before it became possible to read clock counter values, entropy collection was the most vulnerable point of the RNG. This problem is still not fully resolved in many devices (eg smart cards), which thus remain vulnerable. Many RNGs still use traditional (outdated) methods of collecting entropy, such as measuring user reactions (mouse movement, etc.), as in, for example, or interaction between threads, as in Java secure random.
Examples of RNG and entropy sources
A few examples of RNGs with their entropy sources and generators:
| Source of entropy | PRNG | Advantages | Flaws | |
|---|---|---|---|---|
| /dev/random on Linux | CPU clock counter, however only collected during hardware interrupts | LFSR, with output hashed via | It “heats up” for a very long time, can “get stuck” for a long time, or works like a PRNG ( /dev/urandom) | |
| Yarrow by Bruce Schneier | Traditional (outdated) methods | AES-256 and | Flexible crypto-resistant design | Takes a long time to “heat up”, very small internal state, depends too much on the cryptographic strength of the selected algorithms, slow, applicable exclusively for key generation |
| Generator by Leonid Yuryev | Sound card noise | ? | Most likely a good and fast source of entropy | No independent, known crypto-strong PRNG, available exclusively as Windows |
| Microsoft | Built into Windows, doesn't get stuck | Small internal state, easy to predict | ||
| Communication between threads | There is no other choice in Java yet, there is a large internal state | Slow entropy collection | ||
| Chaos by Ruptor | Processor clock counter, collected continuously | Hashing 4096-bit internal state based on a non-linear variant of the Marsaglia generator | Until the fastest of all, the big internal state, gets “stuck” | |
| RRAND from Ruptor | CPU cycle counter | Encrypting internal state with a stream cipher | Very fast, internal state of arbitrary size to choose from, no “stuck” |
PRNG in cryptography
A type of PRNG are PRBGs - generators of pseudo-random bits, as well as various stream ciphers. PRNGs, like stream ciphers, consist of an internal state (usually ranging in size from 16 bits to several megabytes), a function to initialize the internal state with a key or seed(English) seed), internal state update functions, and output functions. PRNGs are divided into simple arithmetic, broken cryptographic and cryptographic strong. Their general purpose is to generate sequences of numbers that cannot be distinguished from random by computational methods.
Although many strong PRNGs or stream ciphers offer much more "random" numbers, such generators are much slower than conventional arithmetic generators and may not be suitable for any kind of research that requires the processor to be free for more useful calculations.
For military purposes and field conditions Only secret synchronous cryptographic strong PRNGs (stream ciphers) are used; block ciphers are not used. Examples of well-known crypto-strong PRNGs are ISAAC, SEAL, Snow, the very slow theoretical algorithm of Bloom, Bloom and Shub, as well as counters with cryptographic hash functions or strong block ciphers instead of an output function.
Hardware PRNG
Apart from the legacy, well-known LFSR generators that were widely used as hardware PRNGs in the 20th century, unfortunately, very little is known about modern hardware PRNGs (stream ciphers), since most of them were developed for military purposes and are kept secret. Almost all existing commercial hardware PRNGs are patented and also kept secret. Hardware PRNGs are limited by strict requirements for consumable memory (most often the use of memory is prohibited), speed (1-2 clock cycles) and area (several hundred FPGA - or
Due to the lack of good hardware PRNGs, manufacturers are forced to use the much slower, but well-known block ciphers available at hand (Computer Review No. 29 (2003)
The software of almost all computers has a built-in function for generating a sequence of pseudo-random quasi-uniformly distributed numbers. However, for statistical modeling, increased requirements are placed on random number generation. The quality of the results of such modeling directly depends on the quality of the generator of uniformly distributed random numbers, because these numbers are also sources (initial data) for obtaining other random variables with a given distribution law.
Unfortunately, there are no ideal generators, and a list of them known properties is replenished with a list of shortcomings. This leads to the risk of using a bad generator in a computer experiment. Therefore, before conducting a computer experiment, it is necessary to either evaluate the quality of the random number generation function built into the computer, or select an appropriate random number generation algorithm.
To be used in computational physics, the generator must have the following properties:
Computational efficiency is the shortest possible calculation time for the next cycle and the amount of memory for running the generator.
Large length L random sequence of numbers. This period must include at least the set of random numbers necessary for a statistical experiment. In addition, even approaching the end of L poses a danger, which can lead to incorrect results of a statistical experiment.
The criterion for a sufficient length of a pseudorandom sequence is chosen from the following considerations. The Monte Carlo method consists of repeated calculations of the output parameters of a simulated system under the influence of input parameters that fluctuate with given distribution laws. The basis for implementing the method is the generation of random numbers with uniform distribution in the interval from which random numbers with given distribution laws are formed. Next, the probability of the simulated event is calculated as the ratio of the number of repetitions of model experiments with a successful outcome to the number of total repetitions of experiments under given initial conditions (parameters) of the model.
For a reliable, in a statistical sense, calculation of this probability, the number of repetitions of the experiment can be estimated using the formula:
Where 
- function inverse to the normal distribution function, 
- confidence probability of error 
Probability measurements.
Therefore, in order for the error not to go beyond the confidence interval with confidence probability, for example =0.95 it is necessary that the number of repetitions of the experiment be no less than:
(2.2)
For example, for a 10% error (
=0.1) we get 
, and for a 3% error (
=0.03) we already get 
.
For other initial conditions of the model, a new series of repetitions of experiments should be carried out on a different pseudo-random sequence. Therefore, either the pseudo-random sequence generation function must have a parameter that changes it (for example, R 0 ), or its length must be at least:
Where K - number of initial conditions (points on the curve determined by the Monte Carlo method), N - number of repetitions of the model experiment under given initial conditions, L - length of the pseudorandom sequence.
Then each series of N repetitions of each experiment will be carried out on its own segment of the pseudo-random sequence.
Reproducibility. As stated above, it is desirable to have a parameter that changes the generation of pseudo-random numbers. Usually this is R 0 . Therefore, it is very important that the change 0 did not spoil the quality (ie statistical parameters) of the random number generator.
Good statistical properties. This is the most important indicator of the quality of a random number generator. However, it cannot be assessed by any one criterion or test, because There are no necessary and sufficient criteria for the randomness of a finite sequence of numbers. The most that can be said about a pseudorandom sequence of numbers is that it “looks” random. No single statistical test is a reliable indicator of accuracy. At a minimum, it is necessary to use several tests that reflect the most important aspects of the quality of the random number generator, i.e. the degree of its approximation to an ideal generator.
Therefore, in addition to testing the generator, it is extremely important to test it using standard problems that allow independent assessment of the results by analytical or numerical methods.
It can be said that the idea of the reliability of pseudo-random numbers is created in the process of using them, with careful verification of the results whenever possible.
09/19/2017, Tue, 13:18, Moscow time , Text: Valeria Shmyrova
The Security Code company, the developer of the Continent cryptographic complex, received a patent for a biological random number sensor. This is precisely a biological sensor, since randomness is based on the user’s reaction to the image shown to him. The company assures that such technologies have not been patented in the world before.
Obtaining a patent
The Security Code company received a patent for biological random number sensor technology. According to the developers, when creating the technology, “a new approach to solving the problem of generating random numbers using a computer and a person” was used. The development is already used in a number of products, including Continent-AP, Secret Net Studio, Continent TLS and Jinn, as well as in the SCrypt cryptographic library.
As company representatives explained to CNews, work on the sensor has been going on for three years now. It consists of a scientific part, an implementation part and an experimental part. Three people are responsible for the scientific part of the company; the entire team of programmers took part in the development, and testing and experiments were carried out by the entire team, which amounts to several hundred people.
Technology capabilities
The new sensor can generate random sequences on personal devices - no additional devices or hardware add-ons are required. It can be used in data encryption and in any area where there is a need for random binary sequences. According to the developers, with its help, encryption keys are created much faster on mobile devices. This property can be used to encrypt data or generate electronic signature.
As explained Alisa Koreneva, a “Security Code” system analyst, the company’s sensor generates random sequences based on the speed and accuracy of the user’s hand response to changes in the image on the PC or tablet screen. A mouse or touchscreen is used for input. It looks like this: circles move chaotically across the screen, some of their parameters change over time. At some points in time the user reacts to changes in the image. Taking into account the peculiarities of his motor skills, this is reflected in the random mass of bits.
Generate random number sequences can be based on spontaneous human reactions
Outside of cryptography, the sensor can be used to generate random numbers in computer games or to select competition winners.
Scientific novelty
As the company explained to CNews, many known methods The construction of random number sensors is based either on physical laws and phenomena, or on deterministic algorithms. Sequences can be generated using a computer - in this case, the instability of some parts of the computer and the uncertainty of hardware interference are taken as the basis for randomness.
The novelty of the Security Code technology lies in the fact that the source of randomness is a person’s reaction to a changing image that is displayed on the device’s display. That is why the name of the invention contains the word “biological”. The company reports that neither it nor Rospatent have found patented analogues of the technology in Russia or in the world. However, in general such techniques are known: for example, a sequence can be generated based on user actions such as clicks or movements of the mouse or keystrokes on the keyboard.
According to Koreneva, the development team analyzed different ways generating random sequences. As it turned out, in many cases there are no reasonable estimates of the generation performance, or the statistical properties of the generated sequences, or both. This is due to the difficulty of justifying an already invented technology. Security Code claims that its research has produced reasonable estimates of the generation rate, was able to justify good probabilistic characteristics and statistical properties, and has estimated the entropy contributed by human actions.
Products that use technology
"Continent" is hardware software package, designed for data encryption. Used in the Russian public sector, for example, in the Treasury. Consists of a firewall and tools for creating a VPN. It was created by the NIP Informzashita company, and is now being developed by Security Code LLC.
Specifically, the “Continent” access server and the “Continent-AP” information cryptographic protection system are a module for secure remote access using GOST algorithms, and “Continent TLS VPN” is a system for providing secure remote access to web applications also using GOST encryption algorithms.
Secret Net Studio is a comprehensive solution for protecting workstations and servers at the data, application, network, operating system and peripheral equipment, which also develops a "Security Code". Jinn-Client is designed for cryptographic information protection for creating an electronic signature and trusted visualization of documents, and Jinn-Server is a software and hardware complex for building legally significant electronic document management systems.
The SCrypt cryptographic library, which also uses the new sensor, was developed by Security Code to make it easier to apply cryptographic algorithms in various products. This is a single program code that has been checked for errors. The library supports cryptographic hashing, electronic signature, and encryption algorithms.
What does the “Security Code” do?
"Security code" - Russian company, which develops software and hardware. Was founded in 2008. Product scope: protection information systems and bringing them into compliance with international and industry standards, including the protection of confidential information, including state secrets. "Security Code" has nine licenses Federal service for Technical and Export Control (FSTEC) of Russia, the Federal Security Service (FSB) of Russia and the Ministry of Defense.
The company's staff consists of about 300 specialists; products are sold by 900 authorized partners in all regions of Russia and the CIS countries. The Security Code client base includes about 32 thousand government and commercial organizations.
Lesson 15. Chance is the soul of the game
You have already taught the turtle a lot. But she also has others, hidden possibilities. Can a turtle do anything on its own that will surprise you?
It turns out yes! There are turtles in the list of sensors random number sensor:
random
We often encounter random numbers: when throwing dice in a children's game, listening to a fortune teller cuckoo in the forest, or simply “guessing any number.” The random number sensor in LogoWorlds can take the value of any positive integer number from 0 to the value limit specified as a parameter.
The number itself, specified as a parameter of the random number sensor, never appears.
For example, a random sensor 20 can be any integer from 0 to 19, including 19, a random sensor 1000 can be any integer from 0 to 999, including 999.
You might be wondering where the game is - just numbers. But don’t forget that in LogoWorlds you can use numbers to set the shape of the turtle, the thickness of the writing pen, its size, color, and much more. The main thing is to choose the right limit of values. The limits of change in the basic parameters of the turtle are shown in the table.
The random number generator can be used as a parameter to any command, for example forward, right and so on.
Task 24. Using the Random Number Sensor
Organize one of the games suggested below using the random number sensor and launch the turtle.
Game 1: Colorful Screen
1. Place the turtle in the center of the screen.
2. Enter commands in the Backpack and set the mode Many times:
new_color random 140 paint wait 10
Team paint performs the same actions as the Fill tool in the graphics editor.
3. Voice the plot.
Game 2: “The Cheerful Painter” 1. Modify game #1 by drawing lines on the screen into random areas with continuous boundaries:
2. Complete the instructions in the Turtle Backpack with random turns and movements:
right random 360
forward random 150
Set instructions in the Backpack to move the turtle ( forward 60) with a 60 thick nib of random color (0-139) lowered at a slight angle ( new_course 10).Game 4: "Hunt"
Develop a plot in which a red turtle hunts a black one. The black turtle moves along a random trajectory, and the direction of movement of the red turtle is controlled by a slider.
Questions for self-control
1. What is a random number generator?
2. What is the parameter of the random number sensor?
3. What does the value limit mean?
4. Does the number specified as a parameter ever come up?