320 A Boolean function based pseudo random number generator (PRNG)

320 : A Boolean function based pseudo random number generator (PRNG)

  • Author: SEAL, CSE Department, IIT Kharagpur
  • Description: Boolean function based pseudo random number generator implemented using finite field
  • GitHub repository
  • Clock: 10000000 Hz

How it works

Principle of operation of Boolean function based pseudo random number generator (PRNG)
This implementation of a PRNG contains linear mappings to and from the following blocks:

  • one $GF(2^4)$ normal base,
  • three instances of $GF(2^4)$ multipliers,
  • one $GF(2^4)$ inverter, and
  • one square scaler.
    The input and output strings of the PRNG are split into five and three shares, respectively. Our PRNG generates random values based on the five input bytes or variables. Instead of relying solely on a single seed or input, it takes several inputs thereby introducing more control over the randomness of the generated values. Thus, the multiple input bytes are used as seeds. The seeds are generated from external factors like time, user-provided data, and environmental conditions. Additionally, previous random values produced by our PRNG design can also be considered as a valid seed. This results in a more tailored or context-aware randomness, which finds its application in simulations, games, cryptography, or data generation. The operation of the Boolean function based PRNG can be classified into three phases, namely, Affine transformation ($1^{st}$ phase), Finite field inversion ($2^{nd}$ phase) and the combination of Finite field multiplication and inverse linear mapping ($3^{rd}$ phase) as evident from the block diagram in Figure 1. The working procedure of these phases are discussed as follows:

First phase- Affine transformation
In the first phase, three shares are processed by the linear input mapping and afterwards fed into a multiplier. Similarly, a uniform reduction to two shares is fed into the square scaler.
$(a,b,c)\mapsto(a,b \oplus c)\ \ \ \ (1)$ The output of the multiplier is partially re-masked by 8 bits of randomness while the square scaler output is left as it is. We use fresh randomness at the end of the first phase to satisfy uniformity during the combination of the square scaler’s and the multiplier’s outputs. The result is saved in a register, $P_1$ as illustrated in the block diagram.

Second phase- Finite field inversion
In the second phase, the overall five shares are combined into four shares. Due to the previous remasking, this can be done uniformly as such:

$(x,y,a,b,c)\mapsto(x,y \oplus (r_1 \oplus r_2),a \oplus (b \oplus r_1),c \oplus r_2)\ \ \ \ (2)$

In the above equation, $x,y$ denote the square scaler output, while $a,b,c$ denote the multiplier output. Note that a register needs to hold all five shares before recombination to prevent leakage. After recombination, the four shares are fed into the inverter and re-masked with 8 bits of randomness. A register stage named $P_2$, preventing glitches, follows this inverter.

Third phase- Finite field multiplication and inverse linear mapping
In the final stage, the re-masked outputs are reduced to three shares uniformly by the following function.

$(a,b,c,d)\mapsto(a \oplus (b \oplus r_3),c \oplus r_4,d \oplus r_3 \oplus r_4)\ \ \ \ (3)$

Subsequently, these shares are fed into two multipliers. Finally, the inverse linear mapping follows. With this construction, it is enough to have three input shares to the generator since the multiplier block requires only three shares. At this stage, we again add a randomness after the inverter to break the dependency between the inputs of the multipliers in the third phase.
In general, we need to reduce the number of shares from five to four at the end of the first phase as the inverter in the second phase can process four input strings. Moreover, the multipliers in the final stage is capable of processing three shares of input thus enforcing the reduction of shares from four to three at the end of the second phase.
A working example is presented below for a better understanding:

In this example, the five input bytes are assigned values of $0x62, 0x04, 0x05, 0xf8$ and $0x95$, respectively. Preliminarily, the 'ena', an active high input signal is assigned a logic '0'. After the power on reset, the 'ena' is pulled up to logic '1', thus enabling the input data loading. The five input bytes are loaded sequentially into an input buffer which is $40$ bits wide. As soon as the buffer is populated, the 'ena' signal is set to active low. This marks the end of the data loading procedure. After the data loading stage, the input values are then processed by linear mapping and three shares of data are produced which are $IN1=0xa8$, $IN2=0x81$ and $IN3=0x7e$. In the first and second phase, the remaining two input values of $R_0=0xf8$ and $R_1=0x95$ are utilized for introducing randomness.

The two inputs to the square scaler are $SQ_{IN1}=0x2$ and $SQ_{IN2}=0x0$. Our design acquires $SQ_{IN1}$ by XOR-ing the first and last $4$ bits of $IN1$ , whereas $SQ_{IN2}$ is acquired by XOR-ing the first and last $4$ bits of $IN2 \oplus IN3$. The strings $IN1[7:4],IN2[7:4],IN3[7:4],IN1[3:0],IN2[3:0]$, and $IN3[3:0]$ are given as inputs to the multiplier and represented by $MUL_{IN1}, MUL_{IN2}, MUL_{IN3}, MUL_{IN4}, MUL_{IN5}$ and $MUL_{IN6}$, respectively. The signals, $r_1$ and $r_2$ are $4$ bits wide, the values of which are obtained by slicing $R_0$. At the end of the first phase, five shares of data are produced along with the randomness, namely, $SQ_{OUT1}, SQ_{OUT2}, MUL_{OUT1}, MUL_{OUT2}, MUL_{OUT3}$ and $r$, respectively. The values of the individual signals are summarized below:
Inputs:
$r_1 \gets 0xf$, $r_2 \gets 0x8$,
$MUL_{IN1} \gets 0xa$, $MUL_{IN2} \gets 0x8$, $MUL_{IN3} \gets 0x7$, $MUL_{IN4} \gets 0x8$, $MUL_{IN5} \gets 0x1$, $MUL_{IN6} \gets 0xe$
Outputs:
$r \gets 0x7$,
$SQ_{OUT1} \gets 0x0$, $SQ_{OUT2} \gets 0x6$,
$MUL_{OUT1} \gets 0xf$, $MUL_{OUT2} \gets 0xe$, $MUL_{OUT3} \gets 0x8$
In the second phase, the corresponding input values, $INV_{IN1}, INV_{IN2}, INV_{IN3}$ and $INV_{IN4}$ to the inverter are $0x0, 0x1, 0xe$ and $0x0$. The subsequent outputs, $INV_{OUT2}$ and $INV_{OUT3}$ are again combined with the random values $r_3$ and $r_4$, whereas the outputs, $INV_{OUT1}$ and $INV_{OUT4}$ are left as is. The values of $r_3$ and $r_4$ are acquired by slicing $R_1$. At the end of this phase, there are four shares of data along with the randomness bits, $r$. The remaining input and output values of this stage are summarized below:
Inputs:
$r_3 \gets 0x9$, $r_4 \gets 0x5$,
Outputs:
$r \gets 0xc$,
$INV_{OUT1} \gets 0x6$, $INV_{OUT2} \gets 0xb$, $INV_{OUT3} \gets 0x2$, $INV_{OUT4} \gets 0x0$

In the final stage, $MUL_{IN1}, MUL_{IN2}$ and $MUL_{IN3}$ are given as inputs to each of the multipliers (see Equation 3). The corresponding outputs of the two multipliers, $MUL_{OUT1}, MUL_{OUT2}, MUL_{OUT3}, MUL_{OUT4}, MUL_{OUT5}$ and $MUL_{OUT6}$ are concatenated to form three strings of eight bits each and fed to the inverse linear mapping module. Thus, we acquire the final output bytes, $OUT1, OUT2$ and $OUT3$. These values are outlined below:
Inputs:
$MUL_{IN1} \gets 0x4$, $MUL_{IN2} \gets 0x7$, $MUL_{IN3} \gets 0xc$,
Outputs:
${MUL_{OUT1},MUL_{OUT4}} \gets 0xbb$, ${MUL_{OUT2},MUL_{OUT5}} \gets 0xa6$, ${MUL_{OUT3},MUL_{OUT6}} \gets 0x68$,
$OUT1 \gets 0x55$, $OUT2 \gets 0xa2$, $OUT3 \gets 0x0c$

How to test

After reset, the ena signal is set to logic '1'. This enables the device to load input values in multiple shares. After loading all the input shares, the ena signal is reset. After two clock cycles, the output ready (uio_out) is set to logic '1' and the multiple output shares are generated.

Picture

IO

#InputOutputBidirectional
0input bitoutput bitoutput ready
1input bitoutput bit
2input bitoutput bit
3input bitoutput bit
4input bitoutput bit
5input bitoutput bit
6input bitoutput bit
7input bitoutput bit

Chip location

Controller Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux tt_um_chip_rom (Chip ROM) tt_um_factory_test (TinyTapeout 05 Factory Test) tt_um_loopback (TinyTapeout 05 Loopback Test Module) tt_um_Leaky_Integrate_Fire_nfjesifb (Leaky Integrate and Fire Neuron Model) tt_um_topModuleKA (Time Multiplexed Neuron Ckt) tt_um_sap_1 (SAP-1 Computer) tt_um_lif (Leaky Integrate-and-Fire Neuron (Verilog Demo)) tt_um_jleugeri_ticktocktokens (TickTockTokens) tt_um_LSNN (Spiking LSTM Network) tt_um_if (Integrate-and-Fire Neuron. (Verilog Demo)) tt_um_mihailocode_neural_network (Neural network on chip) tt_um_hls_lfi (Simple Leaky Integrate and Fire (LIF) Neuron) tt_um_diadatp_spigot_e (e Spigot) tt_um_kskyou (Continued Fraction Calculator) tt_um_wokwi_380005495431181313 (Water Pump Controller) tt_um_EventFilter (Event Denoising Circuit) tt_um_wokwi_380416099936681985 (7 segment seconds (Verilog Demo)) tt_um_freq_hcohensa (Frequency Encoder/Decoder) tt_um_wokwi_380410498092232705 (UART Greeter with RNN Module) tt_um_wokwi_380120751165092865 (WS2812B LED strip driver) tt_um_wokwi_380408486941145089 (Tiny Tapeout 5 Workshop) tt_um_wokwi_380409169798008833 (Tiny Tapeout 1) tt_um_wokwi_380409488188706817 (Supercon Workshop) tt_um_matrix_multiplier (Matrix Multiplier) tt_um_wokwi_380408594272345089 (Clock Divider) tt_um_wokwi_380408784463076353 (Binary Counter) tt_um_wokwi_380408396356749313 (ring osc test) tt_um_7segx4_clock_abhishek_top (7 segment clock with 4 digits) tt_um_wokwi_380409481852161025 (test001) tt_um_hodgkin_huxley (Hodgkin-Huxley Chip Design) tt_um_wokwi_380408823952452609 (Character Selector) tt_um_wokwi_380409904919056385 (Intructouction to PRBS) tt_um_wokwi_380409081067502593 (tto5 Supercon Project) tt_um_jmadden173_delta_modulation (Delta Modulation Spike Encoding) tt_um_wokwi_380409086743445505 (GameOfLife) tt_um_reflex_game (Reflex Game) tt_um_wokwi_380409019830656001 (Logic Gates Tapeout) tt_um_Fiona_CMU (Stream Cipher w/ LSR) tt_um_wokwi_380409532780455937 (tt5modifyd) tt_um_alu_chip (ALU Chip) tt_um_wokwi_380408936929183745 (Tapeout Test) tt_um_rjmorgan11_calculator_chip (Calculator chip) tt_um_wokwi_380409369220404225 (Shifty Snakey) tt_um_synth_GyanepsaaS (Synth) tt_um_wokwi_380408774591779841 (Sawtooth Generator) tt_um_wokwi_380197591775930369 (Blinking A) tt_um_wokwi_380409393770716161 (Supercon 2023) tt_um_mvm (Sparsity Aware Matrix Vector Multiplication) tt_um_wokwi_380408455148316673 (Ring Oscillator and Clock Source Switch) tt_um_mv_mult_alrdelcr (Matrix Vector Multiplication (Verilog Demo)) tt_um_wokwi_380416361853146113 (IDK WHAT TO DO) tt_um_wokwi_379319062779062273 (7-segment display logic system ) tt_um_wokwi_380409568391147521 (Hardware Trojan Example) tt_um_wokwi_379824923824476161 (Analog Clock) tt_um_wokwi_380145600224164865 (7 segment display) tt_um_wokwi_379889284755158017 (W_Li_10/28) tt_um_wokwi_380408409844584449 (Supecon Gate Play) tt_um_manjushettar (ECE 183 - Integrate and Fire Network Chip Design) tt_um_wokwi_380409236812508161 (tto5) tt_um_rebel2_balanced_ternary_ALU (REBEL-2 Balanced Ternary ALU) tt_um_wokwi_380229599886002177 (Stochastic Multiplier) tt_um_jeffdi_seven_segment_seconds (7 segment seconds - count down) tt_um_wokwi_380416616536542209 (TT05 Submission) tt_um_lif_n (Leaky Integrate-and-Fire Neuron) tt_um_wokwi_379764885531576321 (Count via LFSR) tt_um_dlmiles_tt05_i2c_bert (I2C BERT) tt_um_loopback_ericsmi (tt05-loopback tile with input skew measurement) tt_um_flappy_vga_cutout1 (Flappy VGA) tt_um_async_proc_paulschulz (Asynchronous Parallel Processor Demonstrator) tt_um_wokwi_380055891603379201 (Hex Countdown) tt_um_nickjhay_processor (Matrix multiply coprocessor (8x8 1bit)) tt_um_htfab_cell_tester (Standard cell generator and tester) tt_um_wta (Winner-Take-All Network (Verilog Demo)) tt_um_muncherkin_lioncage (Lion cage) tt_um_seven_segment_seconds_ksandov4 (Brain Inspired Random Dropout Circuit) tt_um_seanvenadas (Event-Based Denoising Circuit) tt_um_wokwi_378231665807713281 (RAM cell test) tt_um_rejunity_ay8913 (Classic 8-bit era Programmable Sound Generator AY-3-8913) tt_um_rnn (RNN (Demo)) tt_um_gharenthi_top (STDP Neuron) tt_um_SNN (Basic Spiking Neural Network) tt_um_btflv_8bit_fp_adder (8 bit floating point adder) tt_um_perceptron (Perceptron Hardcoded) tt_um_jkprz (Cheap and quick STDP) tt_um_topLevel_derekabarca (Brain-Inspired Oscillatory Network) tt_um_uwuifier (UART uwuifier) tt_um_perceptron_connorguzi (Perceptron and basic binary neural network) tt_um_hadirkhan10_lif_neuron (Leaky Integrate-and-Fire Neuron) tt_um_wokwi_380119282165535745 (7 segment seconds) tt_um_uabc_electronica_2023 (UABC-ELECTRONICA) tt_um_proppy_bytebeat (bytebeat) tt_um_meriac_play_tune (Super Mario Tune on A Piezo Speaker) tt_um_wrapper_inputblackboxoutput (Byte Computer) tt_um_vhdl_seven_segment_seconds (7 segment seconds (VHDL Demo)) tt_um_cejmu (4-Bit ALU) tt_um_rejunity_sn76489 (Classic 8-bit era Programmable Sound Generator SN76489) tt_um_minipit_stevej (Miniature Programmable Interrupt Timer) tt_um_gchenfc_seven_segment_gerry (7-segment Name Display) tt_um_supertails_tetris (Tetris) tt_um_mabhari_seven_segment_seconds (Simple_Timer-MBA) tt_um_njzhu_uart (UART Receiver) tt_um_wokwi_376553022662786049 (AGL CorticoNeuro-1) tt_um_adaptive_lif (Leaky-Integrated Fire Neuron) tt_um_myuart (MyUART) tt_um_wokwi_380438365946734593 (UART test) tt_um_tkmheart (Heart Rhythm Analyzer) tt_um_stdp (Spike-timing dependent plasticity (Verilog Demo)) tt_um_wokwi_380465686251921409 (Tiny Tapeout 5 TM project1) tt_um_thermocouple (Thermocouple-to-temperature converter (digital backend)) tt_um_wokwi_380412382001715201 (Naive 8-bit Binary Counter) tt_um_asinghani_tinyscanchain_tt05 (tinyscanchain Test Design) tt_um_carlosgs99_cro_udg (6 digit chronometer.) tt_um_suhrojo (Convolutional Network Circuit Chip Design) tt_um_mvm_ (Matrix Vector Multiplication Accelerator) tt_um_perceptron_neuromeme (Perceptron (Neuromeme)) tt_um_czlucius_alu (4 Bit ALU) tt_um_BNNNeuron (Binary Neural Network (Verilog Demo)) tt_um_urish_skullfet (SkullFET) tt_um_ja1tye_sound_generator (Wavetable Sound Generator) tt_um_jaylennee_wta_pwm (PWM signal generation with Winner-Take-All selection) tt_um_joerdsonsilva_top (Multimode Modem) tt_um_toivoh_synth (Analog emulation monosynth) tt_um_tiny_game_of_life (Tiny Game of Life) tt_um_mingkaic1_stack_machine (Stack Machine) tt_um_morningjava_top (ChipTune) tt_um_urish_silife (Game of Life 8x8 (siLife)) tt_um_tt05_analog_test (TT05 Analog Testmacro (Ringo, DAC)) tt_um_wokwi_380409528895479809 (RBUART) tt_um_mattngaw_fp8 (8-bit Floating-Point Adder) tt_um_chip_inventor_music__6_bit_count (6 bit Counter and Piano Music created by Chip Inventor) tt_um_4_bit_pipeline_multiplier (4 Bit Pipelined Multiplier) tt_um_wokwi_380477805171811329 (2-Bit ALU + Dice) tt_um_wokwi_380490286828784641 (TT02 Wokwi 7seg remake) tt_um_wokwi_380361576213660673 (ping pong asic) tt_um_prg (A Boolean function based pseudo random number generator (PRNG)) tt_um_digital_clock_sellicott (Digital Desk Clock) tt_um_haozhezhu_top (4-bit FIFO/LIFO) tt_um_top_mole99 (One Sprite Pony) tt_um_GrayCounter_ariz207 (4 bit Sync Gray Code Counter) tt_um_clkdiv (Clock and Random Number Gen) tt_um_matt_divider_test (TT05 Analog Test) tt_um_tomkeddie_a (VGA Experiments) tt_um_rejunity_rule110 (Rule110 cell automata) tt_um_no_time_for_squares_tommythorn (No Time for Squares) tt_um_urish_silife_max (Game of Life 8x32 (siLife)) tt_um_gfg_development_tros (TROS) tt_um_chatgpt_snn_mtomlin5 (ChatGPT designed Spiking Neural Network) tt_um_ks_pyamnihc (Karplus-Strong String Synthesis) tt_um_dinogame (VGA Dino Game) tt_um_himanshu5_prog_chipTop (Dual Compute Unit) tt_um_rtfb_collatz (Collatz conjecture brute-forcer) tt_um_retospect_neurochip (Field Programmable Neural Array) tt_um_urish_dffram (DFFRAM Example (128 bytes)) tt_um_rejunity_snn (Chonky SNN) tt_um_hh (Hodgkin-Huxley Neuron) tt_um_wokwi_377426511818305537 (PRBS Generator) tt_um_devinatkin_stopwatch (Stop Watch) tt_um_algofoogle_vga_spi_rom (vga_spi_rom) tt_um_blink (RO and counter) tt_um_ttl74hc595_v2 (8-Bit Shift Register with Output Latches 74HC595) tt_um_psychogenic_neptuneproportional (Neptune guitar tuner (proportional window, version b, debug output on bidir pins, larger set of frequencies)) tt_um_urish_simon (Simon Says game) tt_um_kianV_rv32ima_uLinux_SoC (KianV uLinux SoC) tt_um_urish_ringosc_cnt (Ring oscillator with counter) tt_um_sunaofurukawa_cpu_8bit (cpu_8bit) tt_um_vga_clock (VGA clock) tt_um_seven_segment_seconds (7 segment seconds (Verilog Demo)) tt_um_frequency_counter (Frequency counter) tt_um_rgb_mixer (RGB Mixer) tt_um_MichaelBell_spi_peri (SPI Peripheral) tt_um_multiplexed_clock (Multiplexed clock) tt_um_psychogenic_shaman (Shaman: SHA-256 hasher) tt_um_yubex_metastability_experiment (metastability experiment) Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available