LCD Display Inverter

Among various encryption algorithms to ensure Internet security, random number generation is very important. There are several ways to generate random numbers, of which the oscillator sampling method is most suitable for building the random number generator required for SoC designs. This article describes how the oscillator sampling method works and outlines the considerations when using this oscillator specifically.

Demand for virtual private network (VPN) devices has also begun to rise as many enterprise network applications expand from the intranet to the public Internet. To serve this market, semiconductor manufacturers have introduced specialized products that integrate all the necessary security functions into a single device.

AES and 3DES type encryption/decryption algorithms dedicated to Internet Protocol Security (IPsec) and hashing algorithms such as SHA1 and MD5 are well known and appreciated, however, the key to securing a VPN system is the ability to generate random numbers, but this But it is often ignored.

Random numbers are the basis of many cryptographic applications, and their role is to generate public/private key pairs required for algorithms such as Diffie-Hellman, Rivest-Shamir-Adelman, and digital signatures, and to generate initial vectors and initial vectors for bulk encryption algorithms and IPsec, respectively. Instant random numbers, and many other types of security protocols also rely on the unpredictability of random number generators to prevent systems from being cracked. Some complex mathematical functions are commonly used to generate high-quality pseudo-random number generator (PRNG) bitstreams, but it turns out that there are many ways to attack systems encrypted with PRNGs, so cryptographically secure systems need to use higher-quality random number generators.

With these requirements clarified, is there a true random number generator that can generate random numbers from non-deterministic noise sources and is especially suitable for system-on-chip (SoC) designs? Most random number generator schemes generally fall into three broad categories, namely direct amplification, discrete-time chaos, and oscillator sampling. The first two methods are more suitable for custom cell designs, where the designer can control the layout of the actual circuit; while the oscillator sampling technique can be used as part of the standard cell design flow, so it is popular in SoC design. However, even if a designer chooses oscillator technology, there are still many implementation issues that need to be carefully considered.

Random Number Generation Technology

Direct amplification techniques use high-gain, high-bandwidth amplifiers to handle voltage variations caused by thermal or scattered noise. For example, an N-well resistor pair can be used to convert its thermal noise into a voltage-varying signal, which is then input into the random number generator module microsystem in the form of jitter (Figure 1). Designers must consider other factors when using this approach. System thermal noise is often coupled with local characteristics such as noise floor and supply voltage fluctuations, which can make thermal noise sources random if the circuit is not properly shielded. affected. The way to overcome this phenomenon is to sample a pair of adjacent resistors and then difference the results to reduce the effect of other noise sources.

Discrete-time chaos methods use analog signal processing techniques to generate random bit streams. In this way, randomness is not obtained from thermal noise sources, but from very stable dynamics, and the system design is similar in nature to analog-to-digital converters. In a traditional A/D converter, the residual signal is sampled and held and fed to the input of the A/D converter (Figure 2). In general, this technique alone is not sufficient to generate random sequences, because circuit inaccuracies limit A/D conversion resolution and reduce the system’s ability to generate random sequences. Therefore, to obtain non-deterministic randomness, this technique is often used in conjunction with other techniques.

At present, the most popular method in random number generator (RNG) design is the oscillator sampling method (Fig. 3). The basic design idea is to use the relative relationship between two independently working high and low frequency oscillators to obtain non-deterministic A source of noise, a high-frequency oscillator is sampled with a high-jitter low-frequency oscillator, resulting in a sequence of random numbers. In digital circuits, a low-frequency square-wave source can be used as a positive-edge-triggered D flip-flop clock, and a high-frequency square-wave source can be used as the data input of the flip-flop, which is sampled on the rising edge of the clock pulse.

In this system, the key element for generating random numbers is the low frequency oscillator, because it is designed with frequency instability, or jitter, and the ratio of low frequency to high frequency is carefully selected to meet certain conditions. The most important thing in the design is the amount of jitter in the LFO, which is the source of randomness. Frequency instability can be a function of such oscillators, or it can be “implanted” directly by another non-deterministic noise source, so it can be said that it is the phase change of the sampling clock relative to the high frequency data input that ensures that random bitstream.

If neither oscillator drifts during operation, the sampled bit stream is periodic and predictable, and this periodicity is related to a frequency ratio commonly referred to as the beat frequency. In addition, the frequency ratio of the two oscillators has a very important effect on the resulting bit stream. Several studies have shown that in order to ensure a high degree of randomness, the ratio of twice the standard deviation of the low frequency oscillator period variation to the high frequency oscillator period should be greater than 3:2, otherwise there will be a significant correlation between the bit codes, so that the The bits that follow will be more predictable than the bits that precede it.

Using the oscillator sampling method

Designers choosing oscillator sampling to design random number generators must also consider other implementation issues, and the type of oscillator chosen can also affect the inherent randomness of the overall system design. In addition, to ensure that correlated noise sources do not degrade system randomness, the oscillator must be chosen carefully, which in turn complicates the circuit layout of the device. As a compensation, digital post-processing techniques can be employed to reduce design risk and preserve the randomness of the system.

When considering implementing oscillator sampling, designers can choose from several different types of oscillators, including differential, single-ended, and hybrid oscillators, each with varying susceptibility to different noise sources. Different. Obviously, the comparison of the characteristics of different oscillators requires a wealth of knowledge, which is only briefly discussed in this article.

In general, differential oscillators are less sensitive to power supply and noise floor than single-ended oscillators. This is because the power and ground points of the differential amplifier pair simultaneously experience voltage swings, so the difference between the two inputs is consistent and the output is consistent, exhibiting a high common-mode rejection ratio (CMRR). Differential logic is often used in analog logic VCO designs, such as oscillators in phase-locked loops, because phase-locked loops require high CMRR, so the differential oscillator scheme is not particularly suitable for those designs that require non-deterministic noise sources . On the other hand, single-ended inverting oscillators are highly susceptible to voltage swings or DC components in the input signal, and any fluctuations in the level caused by noise will affect the oscillator’s jitter. In addition, differential, capacitive and relaxation oscillator designs require custom circuit layouts and cannot be integrated into standard cell SoC designs. Therefore, the most straightforward solution in SoC design is usually a single-ended ring oscillator (Figure 4).

Despite the advantages of a single-ended ring oscillator, there are some complications that must be considered when choosing. Due to the switching action of high-speed digital systems, thermal noise is generally negligible compared to supply/floor noise. Power supply and floor noise are the main causes of noise coupling, and a noise-coupled oscillator will cause a delta delay in an inverting circuit. Supply voltage variations or noise coupled from the substrate can change the capacitance of each stage’s output node, causing the overall oscillator frequency to change continuously. Also, in addition to thermal noise, the power supply and noise floor in all ring oscillator delay circuit stages are correlated, so designers do not want to have two oscillator circuits too close together without a solid ground ring protection circuit . If the masking is not very good, it will cause random correlation between the two bitstream sources. All of these factors must be considered in the final oscillator design.

Furthermore, even with the best intentions of the designer, an implementation may not produce a truly random bit stream. Designers may need to resort to some costly additional testing to ensure that the random number generator system produces the desired results. As mentioned earlier, the randomness comes mainly from the coupling of power supply and floor noise to the oscillator circuit, and since these oscillators will couple to the same noise source, designers do not want to place them too close together. Further, if two oscillators are locked to the same noise source and coupled to each other, the correlation between them also increases, correlating the random outputs of the two sources. If the two oscillators are separated in the final layout, the related effects of power supply and noise floor can be mitigated.

A common practice with oscillator sampling is to design an additional pair of oscillators, which also reduces the risk of the RNG system being free of non-deterministic noise sources in case the primary source of randomness fails, and then passes the sampling through a strong mixing function. The bitstreams are mixed in order to preserve the randomness inherent in each source, as will be described later. In order to obtain better randomness from mixed bit streams, each oscillator must be selected with a unique main nominal frequency, or its frequency must be adjustable, which minimizes cross-correlation between multiple sources. Of course, the designer must make a trade-off between accepting the extra cost or taking the risk of not being able to generate truly random numbers.

Bias Corrector

The oscillator sampling method works based on the fact that the high frequency oscillator maintains a 50% duty cycle all the time, while the low frequency oscillator varies significantly from cycle to cycle. If this is not the case (although it is in most cases), the bit code obtained will be skewed, either “1” or “0”, which is called offset. Fortunately, we can take effective post-processing methods to correct the bias and produce a more evenly distributed bit stream in a deterministic way. Two of the simplest techniques are called parity generation and transform mapping, but there are more complex bias correction methods, including the use of fast Fourier transform functions and more complex bit shuffling techniques, which typically employ delay elements and feedback paths combined to remove bit-to-bit correlation.

The goal of bias correction is to evenly distribute the bitstream so that “1”s and “0s” are produced with equal probability, basically by extracting more random values ​​from the biased bit sequence. This post-processing capability is not unique to oscillator sampling techniques, its application does not require the original noise source, and it is not complicated to implement. A simple method is parity generation, which has the advantage of being robust to a wider range of biased distributions. Implementing a fixed-length sequence of bit samples in hardware is generally very simple, for example a simple cascaded XOR chain can effectively function as a parity generator with proper bias correction (Figure 5).

A transformation map, also called a von Neumann corrector, converts a pair of sampled input bits into an output bit, e.g.[0，1]Convert to 1, put[1，0]converted to 0, while the input is[0，0]or[1，1]nothing is output. This technique removes the bias completely, but at the cost of having to create an indeterminate amount of delay between the input bits and produce an arbitrary number of output bits long.

mix function

Even with all of the above techniques employed, there are concerns that the inherent randomness of the system may be compromised due to the presence of multiple non-random data sources (such as the aforementioned multiple oscillator source combinations). The randomness of a random source is ensured by the use of powerful mixing functions that combine two or more sampled bits to produce an output bit that is a complex nonlinear function of the previous input bits. Of course, the output random number of bits obtained in this way cannot be more than the input number of bits. The expected functionality of this function is that any change in the input bits will cause a change in about half of the output bits, and these mixing functions can also be used as more sophisticated bias correction methods to remove bias in the bit stream, as discussed earlier.

In general, the stronger the function of the mixing function, the larger the chip area it occupies. The cascaded XOR mentioned above is a very simple example. The DES encryption/decryption algorithm is a more complex example because it requires 120 input bits and produces 64 output bits, each output bit depends on a complex non-linear function involving all input bits, other encryption/decryption algorithms have It works similarly. Shuffle functions can also be used as powerful mixing functions, which take input bits of arbitrary length and produce a digest of information of a certain length. Again, the design engineer needs to make a trade-off between the extra overhead and the inability of the generated bitstream to achieve the desired randomness.

Statistical evaluation

The U.S. Department of Commerce has created a variety of standards for evaluating the randomness of random number generators in cryptographic applications, and the National Institute of Standards and Technology (NIST) “Special Issue 800-22” recommends a comprehensive statistical test methods, and strictly specify measures to satisfy various degrees of randomness. Test engineers can use this test method, or other similar tests, during verification to verify that the design has non-random characteristics and thus determine whether a certain degree of randomness has been achieved. There are 16 different types of tests specified in the NIST Statistical Test Suite so that defects in the random number generator under test can be found.

NIST FIPS 140-2 is another document issued by the U.S. Department of Commerce that defines a set of requirements that designers must follow when implementing cryptographic devices in security applications. One of the most important requirements is that any real-time cryptographic module using a random number generator must provide power-up capability and continuous real-time testing of the RNG function to ensure that it does not fail during operation, if in the prescribed statistical tests On any failure, the RNG module must enter an error state. For SoC designs, this means that the tester module that does the testing must be integrated into the device itself and meet the specified requirements if the final product is to be licensed under US government safety standards.

Some techniques that generate non-deterministic noise sources may not be applicable, depending on whether a standard cell design or a custom layout design is used. It is true that a design is guaranteed to achieve the desired degree of randomness, but this guarantee comes at the expense of increasing die size to allow for redundant structures or more complex post-processing functions. Even a well-planned design must be validated by a statistical test suite at the final stage, only then can the design be said to achieve the desired degree of randomness.