Entropy Extractor Based High-Throughput Post-Processing for True Random Number Generators

Repository for the paper: Entropy extractor based high-throughput post-processings for True Random Number Generators, published in TCHES 2025 Issue 4.

🔍 Paper Abstract

In cryptographic systems, true random number generation is essential, as a compromised TRNG could lead to a security catastrophe. The raw random numbers are discrete values that are derived at discrete points in time from a noise source of a TRNG. These values often exhibit statistical defects that require post-processing, also called conditioner, to improve uniformity. The two main types of post-processing are algorithmic post-processing and cryptographic post-processing, both of which have pros and cons in theories and applications. However, another type of post-processing existing between these two types, named entropy extractor, has often been overlooked by the applied cryptographic community. Therefore, we implement two information-theoretically provable entropy extractors: Toeplitz extractor and Trevisan extractor catering to various performance requirements and applications of high-throughput TRNG post-processing. This paper proposes a combination of matrix chunking and FFT acceleration to boost the performance of the Toeplitz extractor, along with a modified Toeplitz matrix design to decrease the hardware consumption. In addition, we introduce a lightweight single-bit extractor to implement an efficient Trevisan extractor. Both algorithms are devised and verified through FPGA hardware simulations. The enhanced Toeplitz extractor achieves a throughput of 42 Gbps, while the Trevisan extractor attains 1.82 Gbps, representing an 84% and 73% improvement in throughput-to-area ratio over the previous best-performing design for each extractor. The standard statistical test suites, such as NIST SP800-22, NIST SP800-90B, and AIS-31, are adopted to evaluate the effectiveness of the proposed post-processing techniques. Naturally, this approach can only serve as a supplementary measure, as modern standards, such as AIS-31, necessitate formal analysis and stochastic models to account for randomness.

👨‍💻 Authors & Affiliations

• Yifan Dang - BNRist, SIC, Tsinghua University, Beijing, China
• Milos Grujic - KU Leuven, Belgium
• Bohan Yang - BNRist, SIC, Tsinghua University, Beijing, China
• Wenping Zhu - BNRist, SIC, Tsinghua University, Beijing, China
• Hanning Wang - BNRist, SIC, Tsinghua University, Beijing, China
• Min Zhu - MUCSE, Wuxi, China
• Ingrid Verbauwhede - KU Leuven, Belgium
• Leibo Liu - BNRist, SIC, Tsinghua University, Beijing, China

📂 Repository Structure

.
├── Toeplitz/
│   ├── bitstream_file/ # Bitstream file
│   ├── src/            # RTL source code
│   ├── tb/             # Testbench
│   ├── Toeplitz.tcl    # Tcl file
│   └── xdc/            # Constraint file
│
├── Trevisan/
│   ├── bitstream_file/ # Bitstream file
│   ├── src/            # RTL source code
│   ├── tb/             # Testbench
│   ├── Trevisan.tcl    # Tcl file
│   └── xdc/            # Constraint file
│
├── LICENSE.md          # License file
└── Readme.md           # Project documentation

🚀 Code Execution

Both projects are designed for FPGAs using the following development environment:

• 💻 System：Windows 11

• 💻 Software: Xilinx Vivado 2018.3

• 🛠️ Hardware Platform: Digilent Nexys A7-100T

Installation Guide

Vivado 2018.3 installation

• Visit the official website(https://www.xilinx.com/support/download.html) to obtain the installation package:

  

• Click Vivado Archive

• Click 2018.3 version

• Choose Vivado HLx 2018.3: All OS installer Single-File Download

• You may need to log in to your AMD account

• Unzip the installation package

• Open the xsetup installation wizard

• Click "Next"

• Check the box to agree to the agreement and click "Next"

• Choose Vivado HL System Edition

• Choose based on the actual chip model used, but Artix-7 must be selected

  

• Select installation path

  

• Click "Yes"

  

• Confirm installation information and click "Install"

  

• Waiting...

  

• Choose "30 Day Trial"

  

• Then exit the license manager and wait

  

• Then install the winpcap

  

  

  

  

• If you choose the Vivado HL System Edition version, a MATLAB import wizard will pop up (if you don't have MATLAB installed, just click OK or exit)

• Complete!

Installing the board files

There is a little bit of setup needed to get started. This comes in the form of "board files" containing parameters for a particular type of FPGA development board. Digilent provides board files in a github repository.

Locate the directory where you installed Vivado and check for this subdirectory <Vivado_dir>/<version>/data/boards/board_files. If you already have a nexys-a7-100t sub folder located there, you do not need to do anything. But if not you should grab the board files from Digilent github, unzip the archive and locate nexys-a7-100t directory. This directory will be under a subdirectory called new/board_files.

Toeplitz Extractor

📜 RTL Source Code

The SystemVerilog source code is located in the Toeplitz/src/ directory.

Modules:

1. Toeplitz.sv: The top module with parameters N=2304 (input length), M=1728 (output length), T=64 (rows of sub-matrix), and K=64 (columns of sub-matrix).
2. seed.sv: Uses LFSRs to simulate the update of the random seed.
3. fifo.sv: Manages the input stream for processing.
4. butterfly.sv & fft128.sv: Core components for the FFT operation.
5. fft.sv: Performs the FFT of the input sub-matrix and sub-vector.
6. ifft.sv: Performs the Inverse FFT of the multiplication results.
7. sum.sv: Accumulates intermediate results to produce the final output.
8. XORchain.sv: Performs a reduction XOR operation on an input vector.
9. And.sv: Performs a bitwise AND operation.
10. Assign.sv: Assigns the input vector to the output vector when enabled.

The structure of RTL source code is shown as follows:

All modules are described as follows:

1. parameter N=2304: input length; M=1728: output length; T=64: rows of sub-matrix; K=64: columns of sub-matrix. The Toeplitz module is the top module.
2. The seed module uses LFSRs to simulate the update of the random seed. As described in the paper, the random seed can be kept constant over $2^{50}$ rounds of post-processing. Every two consistent $m\times k$ sub-matrices have only one subblock of size $t\times k$ that is not the same due to the property of the Toeplitz matrix. Therefore, we only simulate the generation of this subblock of size $t\times k$ in the seed module.
3. The fifo module takes out the first $m$ bits of the input and transmits them to the sum module. The remaining $n-m$ bits are output to the fft module in chunks of $k$ bits per cycle.
4. The butterfly module and fft128 module achieve the FFT with input length of $t+k=128$.
5. The fft module performs the FFT of the input sub-matrix and input sub-vector and multiplies the transform results.
6. The ifft module performs the IFFT of the multiplication results.
7. The sum module accumulates all the intermediate results to get the final output.
8. The XORchain module performs the reduction XOR operation of all bits in input vector.
9. The And module performs bitwise AND operation on two inputs.
10. The Assign module assigns the input vector to the output vector when enabled.

Note: The main interfaces of my design is clock signal, reset signal, input signal(raw random numbers, which is fixed in simulation architecture), output signal(internal random numbers). We should point out that the open source portion of the code contains only the core functionality of the entropy extractor and not the overall simulation architecture. The PRESENT module used to simulating the generation of the raw random numbers and uart module used to transforming the internal random numbers are excluded is excluded from the open RTL source code.

🧪 Testbench

The testbench of this design can be found in ./tb. Since there are not enough input pins on the FPGA to match the input length N, testbench simply applies the clock and reset signals to the design to verify the timing of the extractor. The correct functionality of the design can be verified by simulating the input data on the input ports and adding a uart transfer module to the output ports, and then verifying the correct functionality of the design by statistical randomness test on the PC.

Specially, users need to use the raw random numbers output by the entropy source as input for post-processing, and connect a commercial UART module to the output end of the post-processing. The UART module transmits the post-processing output data to the computer. Finally, statistical tests are run on the collected data on the computer to verify its randomness. We should point out that the open source portion of the code contains only the core functionality of the post-processing without the other modules for simulation purpose. Therefore, the input module used to simulate the raw random numbers and the UART module used to transmit data are not included in the artifact.

⚙️ Implementation Flow

• Open vivado and click on Create Project.

  

• Click on "Next"

  

• Make up a name for the project and pick a location for the project related files. Check the Create project subdirectory checkbox. Click next to move on to the next setting.

  

• Next up select Project Type. The type to use here is RTL Project and also click the Do not specify sources at this time checkbox. Then click next.

• The next step is to select the FPGA board to use as target. Locate the two tabs Parts and Boards and switch to tab Boards.

• Project configuration is now completed and you will see a summary of your settings.

• After a brief pause the GUI starts up and you will be looking at something similar to this.

• In the Project Manager locate the Sources pane and right click within it. This brings up a list of choices, click on Add Sources. We are going to add a design source and click next.

• Click on the Add File button and select all the modules in ./Toeplitz/src. Then click Finish in the Add Sources window.

  

• Click on Add Sources. We are going to add constraints and click next.

• Click on the Add File button and select all the constraint file in ./Toeplitz/xdc. Then click Finish in the Add Sources window.

• Click on Run Synthesis and click on OK.

• Waiting for circuit synthesis to finish and select Run Implementation. Click OK.

• Click OK.

• After implementation, click Cancel.

• Check Timing(clock cycle is 4.5 ns in xdc file) and Dynamic Power reports

  

• Click on Open Implemented Design

  

• Click on Report Utilization

  

• Click on OK

  

• Check Utilization

Other ancillary components are shown as follows:

1. A project generation script Toeplitz.tcl can be found in ./src to make the FPGA project reproducible.
2. A generated bitstream file is also offered in ./bitstream_file.

Trevisan Extractor

📜 RTL Source Code

The SystemVerilog source code is located in the Trevisan/src/ directory.

Modules:

1. Trevisan.sv: The top module with parameters N (input length), M (output length), L (seed length of single-bit extractor), and K (seed length of Trevisan extractor).
2. seed.sv: Uses LFSRs to simulate random seed updates.
3. weak_design.sv: Divides the random seed into segments for the extraction process.
4. extract.sv: Connects the single-bit extractors in series.
5. datasel.sv: Selects the appropriate input sequence for the first extraction process.
6. dot.sv: Performs the circular shift inner product.
7. XORchain.sv: Performs a reduction XOR operation.
8. Assign.sv: Assigns the input vector to the output vector when enabled.

The structure of RTL source code is shown as follows:

All modules are described as follows:

1. parameter N: input length; M: output length; L: seed length of single-bit extractor; K: seed length of Trevisan extractor. The Trevisan module is the top module.
2. The seed module uses LFSRs to simulate the update of the random seed. As described in the paper, the random seed can be kept constant over $2^{50}$ rounds of post-processing.
3. The weak_design module divides the random seed into segments for two extraction processes in each single-bit extractor.
4. The extract module inputs each segment of the seed to a corresponding single-bit extractor and connects the outputs of each single-bit extractor in series.
5. The datasel module implements the selection from the input that corresponds to the first extraction process of the single-bit extractor.
6. The dot module performs the circular shift inner product between the selected sequence and the second section seed.
7. The XORchain module performs the reduction XOR operation of all bits in input vector.
8. The Assign module assigns the input vector to the output vector when enabled.

Note: Similar to the Toeplitz extractor, this code contains only the core functionality.

🧪 Testbench

The testbench in Trevisan/tb/ is minimal for the same reasons as the Toeplitz extractor. Functional verification should be performed via statistical testing on the hardware output like the Toeplitz extractor.

⚙️ Implementation Flow

The implementation flow is same as the Toeplitz extractor. The performance results of the Trevisan extractor are slightly faster than those reported in the paper, but the area is also slightly larger. This is because we made slight modifications.

Other ancillary components are shown as follows:

1. A project generation script Trevisan.tcl can be found in ./src to make the FPGA project reproducible.
2. A generated bitstream file is also offered in ./bitstream_file.

📩 Contact

Please contact Yifan Dang ([email protected]) for:

• Technical questions about the paper
• Bug reports
• Potential research extensions

📄 License

Copyright (c) 2025, Yifan Dang, Leibo Liu. All rights reserved.

Please see the LICENSE.md file for further license instructions.