randomness extractors embedded with physical random number generators

June 3, 2015

1 abstract

Figure 1: A simple flowchart of physical random numebr generation process

2 drawings

Figure 2: A more detailed flowchart of physical random numebr generation process

Figure 4: A 63-bit Galois-type LFSR Figure 5: Example of a Fibonacci-type randomness extractor, serial input/output

Figure 6: Example of a Galois-type randomness extractor, serial input/output

3 Invention background

The invention introduced in this material generally relates to methods used for generating random numbers used in communication and encryption processes. In particular, the invention introduces different randomness extraction processes used to convert biased random data into unbiased pure random bits. These randomness extraction processes are necessary in high speed randomness generation schemes.

3.1 Random number generation

Various applications require random numbers to be generated at high speed. In particular, when information security is of concern, the quality of the generated random numbers must meet certain requirements:the generated random numbers should have good statistical properties without bias and correlations, and these numbers should be intrinsically unpredictable.

There exists two categories of randomness generators: pseudo-random number generators and physical random number generators(also sometimes known as hardware random number generators).

Pseudo-random number generators make use of complex algorithmic functions to produce seemingly random output streams. They are high-speed and in general easy to implement. However, due to the deterministic nature of these functions, the generated numbers cannot be treated as unpredictable despite that they have nice statistical properties. The pseudo-random number generators, as such, are often used for computational purposes such as Monte-Carlo Simulations. Physical random number should be used for security sensitive cases instead of pseudo-random number generators. Physical random number generators whose output is based on intrinsically unpredictable physical processes are good countermeasures to potential third-party attacks.

Different implementations of physical random number generators have been investigated. Typical physical randomness sources includes radioactive counters, human behaviours(key strokes, mouse movements, etc), electrical/optical noises, etc. Physical random number generation typically involves making repeated measurements on the randomness sources and converting the outcomes into binary bits.

Typically the output quality of physical random number generators are trusted to be more random compare to pseudo-random number generator due to the intrinsic unpredictability. However, one drawback of physical random number Figure 7: Example of a Fibonacci-type randomness extractor, serial type

Figure 8: Example of a Fibonacci-type randomness extractor, serial type

generators is that they generally have slower output rates. One fact responsible to the slow output rate is that measurements on physical randomness sources are very often slower than the computation speed of processors, thus limit the output rate. Another important fact is that the direct output data from physical measurements cannot be treated as good random numbers, as these data usually do not have good statistical properties. Post-processing is needed in general for a physical random number generator to ensure the quality of the output numbers. This post-processing, also known as randomness extraction, generally involves performing logic operations on the raw random data and will introduce further time delay in the final output stage.

3.2 Randomness extraction

Randomness extraction is an algorithmic process typically involved in physical random number generators. Raw data generated from measuring physical randomness sources is in general statistically weak. The target of a randomness extractor is to eliminate the statistical weaknesses such as bias and correlations and produce an output stream that is indistinguishable from a true random stream. From an information-theory point of view, a randomness extractor is a process that converts a stream with Shannon entropy of less than 1 per bit into a statistically random stream of entropy 1 per bit. The process should be, in principle, irreversible such that the raw data cannot be recovered from the output.

Different implementations of practical randomness extractors have been proposed. One well-known example is the so called Von-Neumann extractor. This specific extractor operates by grouping the raw bit stream into pairs and map them into individual bits. The Von-Neumann extractor is proven useful to eliminate bias of the bit stream, but not effective against other correlations. Moreover, it is not considered efficient as the output rate is reduced by more than half of the input rate of the extractor.

Some more recent approaches of randomness extraction use cryptographically secure hash functions. These implementations involves using complex arithmetic functions to process the input raw data, and generate high quality random number output. These methods are generally shown to be effective against almost all kinds of statistical weaknesses, and the output quality is usually satisfactory for information security purposes. The drawback of using these hashing functions is typically a trade-off between output speed and computational resources. A faster output rate generally requires more memory space and faster processing units, thus compact implementations of such algorithms are difficult to achieve.

The applicant came to notice another feature of importance regarding randomness extraction, known as the conservation of entropy. From an information-theory point of view, in input stream of a randomness extractor, each bit contains less than 1 bit of Shannon entropy due to the statistical weaknesses. If the extractor were to output a binary stream of entropy 1 per bit, the length of the output stream must be shorter than the input so that the total entropy conserves. This proposition can be understood as such: from an theoretical angle, the entropy at the input/output need to be conserved as the randomness extractor introduced is a deterministic function that does not input new entropy into the system, hence an increase in the entropy at the output is not favoured in this case. Another point of view from a cryptographic angle is that a shorter output stream require dropping certain portion of output bits, which makes the entire extraction process practically irreversible. As such, potential attackers can not recover the raw random data and hence the security of the system is ensured. The applicant observes that implementing such a entropy conversation process helps improves the output quality of the randomness extractors.

3.3 Prior arts

Prior arts to be quoted?(saw several other patents did that...) some possible quotes US 8219602 US 6581078 US 8364977

4 Summary of the disclosure

The applicant proposes a efficient implementation of a randomness extractor that processes raw random data from a physical randomness source and produces high quality random number at the output.

The applicant observes that a simple and compact structure commonly known as a Linear Feedback Shift Registers(LFSR) is suitable to be used to build such randomness extractors due to some nice properties such as spectrum whitening and distribution uniformizing of its output streams.

The applicant proposes a modification to the LFSR structure such that instead of a deterministic structure, the LFSR receives a random serial input from a physical source, performs a series of logic operations and output a extracted random stream. The extracted random stream is at the same time, used to update the internal state of the LFSR and prepare for next rounds of operation.

The applicant proposes two different structures of such extractor implementations, namely the serial version, Fibonacci type and the Galois type randomness extractors.

The applicant also proposes two additional structures, namely the parallel version, Fibonacci type and Galois type randomness extractors. The two parallel version extractors may have much faster output rate compare to their corresponding serial version, with a acceptable increase in the computational resources requirement.

The applicant makes use of the entropy conservation process mentioned earlier and apply a bit-dropping step to all the extractors introduced to ensure a shorter output stream and a conserved input/output entropy. The portion of dropped bits is decided by first statistically measure the entropy of the raw random data, and then match the output stream length to the amount of entropy measured.

The applicant claims that the proposed structure to be a high speed, efficient randomness extraction scheme, and can be implemented in compact and efficient designs. The proposed structures may possibly be implemented on information security systems where local memory is limited and power consumption is of concern, such as cell-phones, tablets, and other small portable devices.

5 Description of the drawings

Fig.1 shows a general flow chart of the random number generation process from a physical randomness source. The process includes a physical randomness source, a measurement/sampling unit, and a randomness extractor unit. Fig.2 shows a more detailed example of the physical randomness generator. The physical randomness source is a measurement of optical noise, and the uniformizing property of the randomness extractor is shown. Fig.3 schematically shows the common structure of a Fibonacci-type Linear Feedback Shift Register. Fig.4 schematically shows the common structure of a Galois-type Linear Feedback Shift Register. Fig.5 shows a possible implementation of a serial version, Fibonacci-type randomness extractor Fig.6 shows a possible implementation of a serial version, Galois-type randomness extractor Fig.7 shows a possible implementation of a parallel version, Fibonacci-type randomness extractor Fig.8 shows a possible implementation of a parallel version, Galois-type randomness extractor

6 Description of the invention

6.1 Randomness from physical sources

A physical random number generator is based on measurements of physical randomness sources. Possibilities of using different physical processes as randomness sources have been intensitivly investigated. Commonly used randomness sources includes radioactive counters, electrical/optical noises, etc. A physical randomness source is usually quantum mechanical or chaotic, thus ensure the unpredictability of the measurement outcome.

An example of such a randomness source and measuement is shown in Fig.2. The applicant makes use of optical noises to generate the raw random data. Optical noises are in general believed to be originated from quantum mechanical fluctuations and are truly unpredictable. Also, measurements of optical noises can be conducted at high speed, and have a compact physical design of the device.

In the measurement, an analog/digital convertor(ADC) is used to digitize the measurement outcomes. Each outcome is now represented by a binary number of certain bit length, determined by the choice of the ADC. It is easy to see that for randomness source measured with a n-bit ADC, there are 2^{n} possible outcomes. The statistically weak raw data from the measurements will be distributed among these possible outcomes with a non-uniform distribution.

6.2 Shannon entropy of a randomness source

The quality of a randomness source can be described by its Shannon entropy. It can be understood as a measurement of how random the source is. Higher entropy suggests more randomness while zero entropy suggests that the source is perfectly predictable.

Before the randomness extraction process, it is important to first charactise the entropy of the randomness source such that one may estimate the amount entropy be extracted later.

Each outcome of measurement with n-bit ADC can be considered as a randomness variable X with 2^{n} possible values. For such a random variable, its Shannon entropy is defined as:

H(X) = − ∑_{x_{i}} P (X = x_{i})logP (X = x_{i})

where ∑_{x_{i}} means summing over all possible values of X, and P (X = x_{i}) is the

probability of the variable taking the value x_{i}. The probability of each outcome P (X = x_{i}) can be statistically measured. One may simply collect a sample of outcomes and count the number of occurance of each outcome. If the sample size is large enough, the above expression can be considered as a good estimation of entropy. For a n-bit ADC, the value of H(X) is between 0 and n, with 0 being perfectly non-random and n being perfectly random. A perfectly random case corresponds to a uniform distribution of outcomes among all 2^{n} possibilities.

6.3 Linear Feedback Shift Register(LFSR)

A brief introduction of the so called Linear Feedback Shift Register is necessary before introducing the proposed randomness extractors.

An Linear Feedback Shift Register(LFSR) is an arithmetic structure consists of a shift register and XOR gates. The shift register is of length n and stores n bits of data at any instant. The length of the shift register is commonly referred as the length of the LFSR. The bit content stored in the shift register at a certain clock cycle is referred as the state of the LFSR at the moment.

Fig.3 and Fig.4 shows two possible structures of LFSR, namely the Fibonaccitype and the Galois-type.

As its name suggests, an LFSR operates by XORing the bits inside the shift register and the bit at its output end. The addresses in the shift register that take part in the XOR operations are commonly called the LFSR taps.

Fig.3 is an example of a 63-bit Fibonacci-type LFSR. Addresses 1 and 2 are chosen as taps. At each clock cycle, the bits stored in addresses 1 and 2 are XORed to produce an output bit, which is simoutaneously sent back to address 63 of the shift register. All other bits in the LFSR shift one step upwards in the process. Fig.4 is an example of a 63-bit Galois-type LFSR. Addresses 1 and 2 are chosen as taps. At each clock cycle, the bits stored in addresses 63 is shifted to address 1. Simoutaneously the same bit is XORed with the bit originally stored in address 1, and their outcome occupies address 2. All other bits in the LFSR shift one step downwards in the process. It is obvious that an LFSR is a deterministic structure. Despite that the LFSR state is constantly updated at each clock cycle, eventually it will return to its state at the beginning. It is pointed out that an LFSR of length n can maximally have 2^{n} − 1 states. For any LFSR(any length, any tap-combinations), the zero state(with all bits being zero in the shift register), is not considered as an operational state, since its output will be nothing but zero.

In principle, the taps of an LFSR can be arbitrarily chosen addresses. In practice, given a fixed LFSR length, certain sets of taps are of more interest. These are the so called maximum period taps. As the name suggests, some particular sets of taps allow the LFSR to iterate through all the 2^{n} − 1 possible states before repeating itself. In the examples in Fig.3 and Fig.4, addresses 1 and 2 forms such a set of taps. The example LFSR will go through 2^{63} − 1 different states before repeating outcomes start to occur. Mathematically, an LFSR can be described finite Galois field algebra. It can be shown that both Fibonacci-type and Galois-type LFSR can be described by the same arithmetics, and the solutions of maximum period taps can be analyzed with the same mathematics.

The output binary sequence of a LFSR with maximum period taps possess nice statistical properies. The occurance of 0s and 1s are almost identical and so do the two-bit pairs(00,01,10,11) and 3-bit triplets(000,001,010...) and so on. A discrete Fourier transform of the stream shows a white spectrum. Although the stream is deterministic in nature, its repetition period will be sufficiently long even for a moderate length LFSR(2^{63} − 1 for a 63-bit length LFSR). As such, the output stream of such a LFSR is often used as a pseudo-random number generator. However, it should be noted that despite its good statistical properties, such pseudo-random stream cannot be considered as good random numbers and used for information security purposes. There does exist certain possible methods to distinguish such a stream from a good random stream.

The randomness extractor proposed by the applicant can be considered as a combination of a physical randomness source and a LFSR structure. The applicant proposes to make use of the statistical properties of an LFSR output, and meanwhile introduce the unpredictablity of a physical randomness source to construct an efficient randomness extraction scheme.

6.4 LFSR based randomness extractors

In this invention, the applicant makes use of the LFSR structures to build randomness extractors. Four different designs are presented in this material: serial/parallel version of both Fibonacci type and Galois type extractors. Unlike a conventional LFSR, a LFSR based extractor receives an input stream(several streams in parallel case) from measurement of the randomness source, and output a random stream of shorter length depends on the entropy of the source.

6.4.1 Serial version extractors: Fibonacci type

Fig.5 shows the basic structure of a serial version, Fibonacci-type extractor. The central part is a Fibonacci type LFSR, with the its taps chosen to give a maximal period(addresses 1 and 2). The extractor has a serial input and output. On each clock cycle, the following operations take place:

1. One bit is read from the physical RNG to input.

2. The input bit is XORed with the bits from the LFSR taps, generating one new bit. The operation can be expressed as: X_{output} = X_{1} ⊕ X_{2} ⊕ X_{input}

3. The LFSR shifts, all bits move 1 step upwards, the vacated bottom position is occupied by the newly generated bit. The new bit is at the same time sent to output.

4. A portion of bits are dropped to conserve entropy.

The applicant notes that the structure described is very similar to the so called scramblers, normally used in telecommunications. A difference between the two is that a scrambler does not allow any bit losses in the output while in an extractor one deliberately drops bits to conserve entropy.

The example in Fig.5 makes use of a 63-bit LFSR. The reason for choosing a length 63 is that a 63-bit LFSR has a set of maximal period taps with only two addresses, which minimizes the number of XOR gates required. In general, a longer LFSR provides more complexity to the system and improves the statistical properties of the output. The applicant also observed that a shorter LFSR length (¡ 32-bits) may reduce the quality of the output random numbers.

In this example, each measurement outcome is a 16-bit number(a 16-bit ADC is used). An entropy measurement of the physical randomness source yields 12 bits of entropy in each outcome. In order to fulfil the entropy conservation condition, for every 16 output bits, 4 are dropped.

6.4.2 Serial version extractors: Galois type

Fig.6 shows the basic structure of a serial version, Galois-type extractor. The central part is a Galois type LFSR, with the LFSR taps chosen to give a maximal period(addresses 1 and 2). The extractor has a serial input and output. On each clock cycle, the following operations take place:

1. One bit is read from the physical RNG to input.

2. The input bit is XORed with the output bit(bit from address 63) of the LFSR, generating one new bit.

3. The LFSR shifts, all bits move one ste downwards. The vacated top position is occupied by the newly generated bit. Bit from address 63(bottom) is sent as output. The XOR operation can be expressed as: X_{1} = X_{input} ⊕ X_{63}, X_{2} = X_{1} ⊕ X_{63}

4. A portion of the output bits are dropped to conserve entropy

A Galois-type LFSR is mathematically equivalent to a Fibonacci-type LFSR. Both structures can be described using Galois algebra of finite field. However, the Galois-type LFSR extractor has one significant advantage: all the XOR operation in such structure can take place simultaneously and send one bit output in one clock cycle. The Fibonacci-type LFSR extractor, on the other hand, need at least two clock cycles to generate one bit output. If the output rate of the system is of concern, Galois-type extractor should be chosen as it provides a faster processing scheme.

The entropy conservation condition and the LFSR length considerations remains the same as the Fibonacci type.

6.4.3 Parallel version extractors: Fibonacci type

Fig.7 shows an example of a parallel version, Fibonacci-type extractor. The addresses of the shift register are labelled in numbers. The arrows indicate the shift directions of bits at each clock cycle. To generate an output of 63 bits in parallel, 63 × 2 = 126 cells of memory are needed. Cells 1 ∼ 63 store the state of the LFSR, and are to be sent to output at next clock cycle; cells 64 ∼ 126 are used to store the next 63 bits that are newly generated by the XOR(Exclusive OR) module. Similar to the serial extractor, the operations in one clock cycle are as following:

1. 63 bits are read from the physical RNG to the input.

2. XOR operations are performed between the input 63 bits and the bits stored in the shift register. Following the truth table below:

XOR module X_{64} = X_{1} ⊕ X_{2} ⊕ X_{input1}

X_{63} = X_{2} ⊕ X_{3} ⊕ X_{input2}
⋮
X_{126} = X_{63} ⊕ X_{64} ⊕ X_{input63}

this step will generate 63 new bits. It’s worth noting here that all these XOR operations are performed in parallel, thus no extra operating time is required compare to the serial extractor.

3. The parallel LFSR shifts. All bits shift 63 addresses forward: 64 → 1, 65 → 2, etc. Bits originally stored in addresses 1 ∼ 63 are sent to output; the vacated addresses 64 ∼ 126 accommodate the newly generated 63 bits from the XOR operations.

4. A portion of bits are dropped to conserve entropy.

The parallel structured extractor will speed up processing speed at a cost of requiring more memory space and more XOR gates compare to its serial version. To build a parallel Fibonacci-type extractor using a n-bit LFSR that has k bit parallel output, k must be less or equal to n. The number of memory cells needed is simply n + k.

The entropy conservation condition and the LFSR length considerations remains the same.

6.4.4 Parallel version extractors: Galois type

Fig.8 shows an example of a parallel version, Galois-type extractor. The addresses of the shift register are labelled in numbers. The arrows indicate the shift directions of bits at each clock cycle. To generate an output of 63 bits in parallel, 63 × 3 = 189 cells of memory are needed. Cells 1 ∼ 63 store the state of the LFSR, and are to be sent to output at next clock cycle; cells 64 ∼ 189 are used to store the 126 bits that will undergo the XOR operations.

Similar to the serial extractor, the operations in one clock cycle are as following:

1. 63 bits are read from the physical RNG to the input.

2. XOR operations are performed on two modules between the input 63 bits, output 63 bits and the bits stored in the shift register. Following the truth table below:

XOR module 1 XOR module 2 X_{64′} = X_{1} ⊕ X_{input1} X_{64} = X_{64′} ⊕ X_{2}

X_{65′} = X_{2} ⊕ X_{input2} X_{65} = X_{65′} ⊕ X_{3}
⋮  ⋮
X_{64′} = X_{1} ⊕ X_{input1} X_{64} = X_{64′} ⊕ X_{2}

this step will generate 63 new bits. It’s worth noting here that all these XOR operations are performed simultaneously in the same clock cycle.

3. The parallel LFSR shifts. All bits shift 63 addresses forward: 64′ → 64, 64 → 1, 65′ → 65, 65 → 2, etc. Bits originally stored in addresses 1 ∼ 63 are sent to output; the results from XOR circuit 1 occupy addresses 64′ ∼ 126′; results from XOR circuit 2 occupy addresses 64 ∼ 126

4. A portion of bits are dropped to conserve entropy.

The Galois-type parallel extractor will speed up processing speed at a cost of more memory space and more XOR gates compare to its serial version. To build a parallel Galois-type extractor using a n-bit LFSR that has k bit parallel output, k must be less or equal to n. The number of memory cells needed would be n + m × k where m is the number of taps of the chosen LFSR.

The entropy conservation condition and the LFSR length considerations remains the same.