The NIST Frequency Monobit test in Ruby

The NIST Frequency Monobit test in Ruby | Nevada Start

In some symmetric key systems pseudorandom number generators (PNRG) are used to create a keystream for encrypting plaintext. An important part of cryptography is key generation, and a strong key is as close to random as possible (PNRG sequences aren’t truly random, as they are generated from a seed, but that’s for another day).

We won’t get into the actual key generation in this post, but we are going to look at how to evaluate the randomness of the key. The National Institute of Standards and Technology (NIST) created a suite of 15 tests to check for randomness in binary sequences generated by PNRGs.

We’re going to implement the first test, The Frequency (Monobit) Test, in Ruby!

The Frequency (Monobit) Test

Given a sequence of bits, the test checks the proportions of zeroes and ones in the sequence, with the purpose of determining if the number of ones and zeros in the input is close to what we would expect for a random sequence. It’s important to note that the NIST also recommends a minimum length of 100 for the input, but I’ve chosen a small input for simplicity’s sake.

The test has a few (relatively) straightforward steps:

First given a sequence of bits, we have to change the 0’s to -1, and sum the result

To simplify the implementation, we’ll use an array to hold the sequence.

input =  [0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0]

Then convert it:

  def converted_input(input)
    input.map { |n| n.zero? ? -1 : n }
  end

  #=> [-1, 1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, -1]

Sum the result from step 1, and take the absolute value

  [-1, 1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, -1].sum.abs 
  #=> 2

Calculate the test statistic S_obs, here’s the formula:

Where S is the sum from step 1, and n the number of elements in the original input: S_obs = S/√n

def calculate_test_statistic(s, n)
    s / Math.sqrt(n)
end

#=> 0.5345224838248488

With the value for S_obs, we compute the P-value. For this we’ll need the complementary error function (erfc), which luckily for us is included in Ruby!

P-value = erfc(S_obs/2)

def p_value(s_obs)
    Math.erfc(s_obs / Math.sqrt(2))
end

#=> 0.5929800980174267

Interpreting the results

As a threshold for the randomness test, the NIST specifies a minimum value of 1%. So if the result from step 3 is greater or equal to 0.01, we can conclude the sequence is random. So for the example above, we could conclude that our test sequence with a value of 0.59, passes the test! ———

A more complete implementation in Ruby could look something like this:

class FrequencyMonobitTest
  
  DECISION_RULE = 0.01
  RECOMMENDED_INPUT_LENGTH = 100

  attr_reader :input, :length

  def initialize(input)
    @input = input
    @length = input.length
  end

  def random?
    @p_value ||= calculate
    @p_value >= DECISION_RULE
  end

  private

  def calculate
    input_warning if length < RECOMMENDED_INPUT_LENGTH
    calculate_test_statistic(converted_input)
    p_value
  end

  def input_warning
    puts "Warning! The length of the input: #{length}, is less than the recommended #{RECOMMENDED_INPUT_LENGTH}"
  end

  def converted_input
    input.map { |n| n.zero? ? -1 : n }
  end

  def calculate_test_statistic(values)
    @test_statistic = values.sum.abs / Math.sqrt(length)
  end

  def p_value
    @p_value = Math.erfc(@test_statistic / Math.sqrt(2))
  end
end

The Frequency (Monobit) Test

Interpreting the results

A more complete implementation in Ruby could look something like this:

Further reading