9.6. $RANDOM: генерация псевдослучайных целых чисел
$RANDOM — внутренняя функция Bash (не константа), которая возвращает псевдослучайные целые числа в диапазоне 0 — 32767. Функция $RANDOM не должна использоваться для генераци ключей шифрования.
Пример 9-23. Генерация случайных чисел
Пример 9-24. Выбор случайной карты из колоды
Jipe подсказал еще один способ генерации случайных чисел из заданного диапазона.
Насколько случайны числа, возвращаемые функцией $RANDOM? Лучший способ оценить «случайность» генерируемых чисел — это написать сценарий, который будет имитировать бросание игрального кубика достаточно большое число раз, а затем выведет количество выпадений каждой из граней.
Пример 9-25. Имитация бросания кубика с помощью RANDOM
Как видно из последнего примера, неплохо было бы производить переустановку начального числа генератора случайных чисел RANDOM перед тем, как начать работу с ним. Если используется одно и то же начальное число, то генератор RANDOM будет выдавать одну и ту же последовательность чисел. (Это совпадает с поведением функции random() в языке C.)
Пример 9-26. Переустановка RANDOM
Системный генератор /dev/urandom дает последовательность псевдослучайных чисел с более равномерным распределением, чем $RANDOM. Команда dd if=/dev/urandom of=targetfile bs=1 count=XX создает файл, содержащий последовательность псевдослучайных чисел. Однако, эти числа требуют дополнительной обработки, например с помощью команды od (этот прием используется в примере выше) или dd (см. Пример 12-42).
Есть и другие способы генерации псевдослучайных последовательностей в сценариях. Awk имеет для этого достаточно удобные средства.
Пример 9-27. Получение псевдослучайных чисел с помощью awk
Источник
Understanding random number generators, and their limitations, in Linux
Random numbers are important in computing. TCP/IP sequence numbers, TLS nonces, ASLR offsets, password salts, and DNS source port numbers all rely on random numbers. In cryptography randomness is found everywhere, from the generation of keys to encryption systems, even the way in which cryptosystems are attacked. Without randomness, all crypto operations would be predictable and hence insecure.
When computer algorithms are fed with the same input they should always give the same output; they are predictable and therefore not a good source of random numbers. A good random numbers generator consists of two parts: a source of entropy and a cryptographic algorithm.
A source of entropy (RNG)
Entropy is the measurement of uncertainty or disorder in a system. Good entropy comes from the surrounding environment which is unpredictable and chaotic. You can think of entropy as the amount of surprise found in the result of a randomized process: the higher the entropy, the less the certainty found in the result. Random number generators or RNGS are hardware devices or software programs which take non-deterministic inputs in the form of physical measurements of temperature or phase noise or clock signals etc and generate unpredictable numbers as its output.
A hardware RNG could use hard-to-predict values such as wind speed or atmospheric pressure, or exploit intrinsically random (quantum) processes such as photon transmission/reflection through a semi-transparent mirror. In computers we can use the attached hardware to harvest entropy like movement on the mouse pointer, keys typed on the keyboard, and disk and/or network I/O. Such systems are a good source of entropy, however they are slow to yield data (for example the CPU jitter generator). Also they are dependent on external triggers in order to generate random numbers and are often not reliable when large amount of random numbers are required.
There are algorithms to produce pseudo-random values from within an ideal, deterministic computing environment. However, there is no algorithm to produce unpredictable random numbers without some sort of additional non-deterministic input.
A cryptographic algorithm (PRNG)
Pseudo random number generators, or PRNGs, are systems that are efficient in reliably producing lots of artificial random bits from a few true random bits. For example, a RNG which relies on mouse movements or keyboard key presses would stop working once the user stops interacting with the mouse or the keyboard. However a PRNG would use these random bits of initial entropy and continue producing random numbers.
PRNGs maintain a large memory buffer called the entropy pool. The bytes received from the entropy sources (RNG) are stored there. Often the PRNG mixes the entropy pool bytes in order to remove statistical biases in the entropy data. Random bits are generated by running a deterministic random bit generator (DRBG) on the entropy pool data bits. This algorithm is deterministic (it always produces the same output given the same input). The trick is to ensure that the DRBG is never fed the same value input twice!
Real working PRNG’s
Most operating systems have built-in crypto PRNGs. Most of them are software based, but some can be pure hardware as well. In Linux, the device files /dev/random and /dev/urandom are the userland interfaces to the crypto PRNG which can reliably generate random bits.
The kernel maintains an entropy pool which is used to store random data generated from events like inter-keypress timings, inter-interrupt timings, etc. Randomness from these interfaces are fixed with the entropy pool using a sort of cyclic redundancy check-like function. This is not cryptographically strong but tries to ensure that any maliciously introduced randomness is eliminated and is also fast enough. The kernel also keeps an estimate of how many bits of randomness has been stored into the random number generator’s internal state via the /proc/sys/kernel/random/entropy_avail file.
When random numbers are desired they are obtained by taking SHA-1 hash of the contents of the entropy pool. The SHA hash is chosen because it is cryptographically strong: it does not expose the contents of the entropy pool, and it is computationally infeasible to reverse the SHA output to obtain its input. Thus, the confidentiality of the entropy pool is preserved. On each generation of random numbers, the kernel decreases its estimate of true randomness which are contained in the entropy pool.
The kernel provides two character devices /dev/random and /dev/urandom . The /dev/random device is suitable for use when very high-quality randomness is desired (for example, for key generation or one-time pads), as it will only return a maximum of the number of bits of randomness (as estimated by the random number generator) contained in the entropy pool.
The /dev/urandom device does not have this limit and will return as many bytes as are requested. As more and more random bytes are requested without giving time for the entropy pool to recharge, this will result in random numbers that are «merely» cryptographically strong. For many applications, however, this is acceptable.
The biggest problem with /dev/random is that it is blocking. Once the kernel’s entropy pool is exhausted, reads from /dev/random will pause until sufficient entropy is replenished. Such pauses are typically unacceptable and can constitute a denial-of-service attack against the application or even the system as a whole.
Boot time randomness
In 2012 security researchers scanned the internet and harvested public keys from TLS certificates and SSH hosts. They found a few systems had identical public keys and in some cases very similar RSA keys with shared prime factors. It was found that many of these systems generated their keys very early after boot. At this point very little entropy is collected in the entropy pool. Therefore despite having a good PRNG, because the entropy pool is almost identical, the random numbers generated are similar on different systems. In Linux you can carry the information in the entropy pool across shutdowns and start-ups.
To do this, you can use this as a script to run during the boot sequence:
and use this as a script which is run as the system is shut down:
For example, for older systems which use System V init scripts, such code fragments would be found in /etc/rc.d/init.d/random . The script causes the contents of the entropy pool to be saved at shutdown time and reloaded into the entropy pool at start-up. (The dd , in addition to the bootup script, is to make sure that /etc/random-seed is different for every start-up)
Newer systems (for example Red Hat Enterprise Linux 7) which use systemd already have the systemd-random-seed.service installed by default. This service restores the random seed of the system at early boot and saves it at shutdown which has the same effect as the script listed above.
Hardware based PRNG
The Intel Digital Random Number Generator is a hardware random generator which was introduced in Intel CPUs in 2012 as a part of Intel Ivy Bridge microarchitecture and is based on NIST’s SP 800-90 guidelines. Intel provides RDRAND assembly instructions which can be used to access this PRNG and is much faster than any software PRNGs.
RDRAND has a single entropy source and provides a stream of entropy data as zeros and ones. It is essentially a hardware circuit which jumps between 0 and 1 based on thermal noise fluctuations within the CPU. Though Intel’s PRNG is only partially documented it is audited by a company called Cryptography Research. There are, however, some concerns about the security of this type of random number generator, mainly since PRNGs are a very good target for cryptographic backdoors. These issues can normally be avoided by mixing the output from RDRAND with other sources of entropy in the entropy pool (unless of course the CPU itself is malicious). This should prevent any possible bias, if they exist.
Providing random numbers on virtual machines
Generating a good amount of entropy can be a problem for virtual machines because by default there are no attached hardware devices which can seed the entropy pool. Red Hat Enterprise Linux 7 includes virtio-rng, a virtual hardware random number generator device that can provide the guest with fresh entropy on request.
On the host physical machine, the hardware RNG interface creates a chardev at /dev/hwrng , which can be opened and then read to fetch entropy from the host physical machine. In co-operation with the rngd daemon, the entropy from the host physical machine can be routed to the guest virtual machine’s /dev/random, which is the primary source of randomness. The virtual random number generator device allows the host physical machine to pass through entropy to guest virtual machine operating systems.
Non-crytographic random number generators
Finally, let us look at a good source of non-cryptographic random number generator on Linux, namely glibc’s random() function. Glibc provides a simple linear congruential generator (LCG), defined by the following equation:
This generator is referred to as TYPE_0 in the glibc source. (LCG random generators have the useful property that they are very fast and they have a very small amount of state — the same size as the random value that is returned. This means that once a particular (31-bit) value is produced, it will not be seen again until the function has been called enough times to produce every other value in its range.)
Glibc also provides a slightly more advanced, additive feedback generator. That generator has a number of states, unlike the above described LCG. You can get the same number twice (or more times) during the same period. This generator is called the TYPE_1 , TYPE_2 , TYPE_3 or TYPE_4 in the glibc source.
Which generator is used depends on the size of the initial state set with the initstate() function. The first (LCG) generator is used only when state size is 8 bytes. When it is bigger, the second generator is used. When you set your seed using srand() the size of the state is 128 bytes by default, so the second generator is used. While not cryptographically strong, these generators are useful for monte-carlo methods and testing, where it may be desirable to repeat exactly the same pseudo-random stream on a subsequent run. As long as srand() or initstate() is called with the same value each time your program starts, it will obtain the same random numbers.
Conclusion:
Random numbers are the lifeline of any cryptographic operation in modern computing. It is important for developers to understand what interface to use, and how to handle random numbers correctly in their code. It is also important for users to understand the limitations of such code. This post provides a basic insight into how random number generators actually work in Linux and what are their limitations.
Источник
How to ‘randomize()’ random numbers in C(Linux)?
Trying to generate random numbers in C, rand() doesn’t generate different numbers each time i compile the code, can anyone tell me how to use srand() or tell any other method for generating.
4 Answers 4
In order to generate a sequence of pseudorandom numbers, the generator needs to be seeded. The seed fully determines the sequence of numbers that will be produced. In C, you seed with srand , as you indicate. According to the srand(3) man page, no explicit seeding implies that the generator will use 1 as a seed. This expains why you always see the same numbers (but do remember that the sequence itself is pretty random, with quality depending on the generator used, even though the sequence is the same each time).
User mzabsky points out that one way to get a seed that feels random to a human user is to seed with time. Another common method (which I just saw that mzabsky also points out — sorry) is to seed the generator with the contents of the system’s random number generator, which draws from an entropy pool fed by things such as mouse movement, disk timings etc. You can’t draw a lot of randomness from the system generator, as it won’t be able to gather enough entropy. But if you just draw a seed from it, you’ll have chosen at random a sequence of random numbers in your program. Here’s an example of how to do that in C on Linux:
In light of Conrad Meyer’s answer, I thought I’d elaborate a bit more. I’d divide the use of random numbers into three categories:
Variation. If you use random numbers to create seemingly random or varied behavior in for example a game, you don’t need to think very hard about the topic, or about choosing a proper seed. Seed with time, and look at some other solution if this turns out not to be good enough. Even relatively bad RNGs will look random enough in this scenario.
Scientific simulations. If you use random numbers for scientific work, such as Monte Carlo calculations, you need to take care to choose a good generator. Your seed should be fixed (or user-changeable). You don’t want variation (in the sense above); you want deterministic behavior but good randomness.
Cryptography. You’ll want to be extremely careful. This is probably out of the scope of this thread.
