## Introduction

The problems of using certain constants in pseudo-random number generators (PRNG) is a problem that is still not very known among developers. Recent events regarding the NSA and their presumable attempt to weaken the `Dual_EC `

DRBG algorithm have shown one of the major flaws in modern days cryptography.

This example will demonstrate the effects of choosing a weak parameter in the Logistic Map, a mathematical function that is known from chaos theory and which can be used to implement a PRNG.

## Background

The Logistic map is a simple non-linear equation that is defined as:

`x_n+1 = a * x_n* (1- x_n)`

The parameter `a `

determines the behaviour of the map. If `a > 3.57`

, the map shows chaotic properties which means that even a slight change of the original input value `x_0`

leads to a complete different set of output values. The closer `a `

gets to `4`

, the greater the chaotic effect will become (i.e., if `a >= 3.9`

, then the logistic map is considered to be very chaotic).

This effect can be used to design a PRNG.

## Using the Code

```
package chaoticprng;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;
public class ChaoticPRNG {
static double logisticMap(double a, double x) {
double retVal = a * x * (1 - x);
return retVal;
}
static int flipBit(int n, int pos) {
return (n | (1 << pos));
}
public static void main(String[] args) throws IOException {
double x = Math.random();
double y = Math.random();
Writer wr = new FileWriter("C:\\tmp\\DiehardSuite\\prng397");
for (int i = 0; i < 5000000; i++) {
Integer number = 0;
for (int k = 0; k < 32; k++) {
x = logisticMap(3.9, x);
y = logisticMap(3.9, y);
Long xToLong = Double.doubleToLongBits(x);
Long yToLong = Double.doubleToLongBits(y);
int bitCount = Long.bitCount(xToLong ^ yToLong);
//System.out.println(bitCount);
if (bitCount % 2 == 1) {
number = flipBit(number, k);
}
}
wr.write(number);
}
wr.close();
System.out.println("Finished");
}
}
```

## Statistical Tests using the Diehard Battery

We implement a simple Java method that calculates two long numbers `x `

and `y `

using the Logistic map with parameter `a=3.9`

(the seed is provided by the `Math.random() `

method).

From `x `

and `y`

, we determine an integer number using the bit operator (^) and write it into a file.

For statistical purposes, we want to create 5 million of theses integer values and store them in a file called *logmap.dat*.

// Logistic map

The Diehard battery of tests is a toolkit to determine the quality of a random number sequence. It is publicly available and uses a set of statistical tests to check whether a given sequence of integer numbers shows specific patterns. Using this tool, we get the following result file (the following output is just one of the 15 tests of the suite):

```
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:: The OVERLAPPING SUMS test ::
:: Integers are floated to get a sequence U(1),U(2),... of uni- ::
:: form [0,1) variables. Then overlapping sums, ::
:: S(1)=U(1)+...+U(100), S2=U(2)+...+U(101),... are formed. ::
:: The S's are virtually normal with a certain covariance mat- ::
:: rix. A linear transformation of the S's converts them to a ::
:: sequence of independent standard normals, which are converted ::
:: to uniform variables for a KSTEST. The p-values from ten ::
:: KSTESTs are given still another KSTEST. ::
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Test no. 1 p-value 1.000000
Test no. 2 p-value 1.000000
Test no. 3 p-value 1.000000
Test no. 4 p-value 1.000000
Test no. 5 p-value 1.000000
Test no. 6 p-value 1.000000
Test no. 7 p-value 1.000000
Test no. 8 p-value 1.000000
Test no. 9 p-value 1.000000
Test no. 10 p-value 1.000000
Results of the OSUM test for prng
KSTEST on the above 10 p-values: 1.000000
```

A `p`

-value of `1.0`

means that the sequence shows strong non-random patterns, each of the other 14 tests fail the same way. So we can deduce that the Logistic map with `a=3.90 `

simply does not generate enough entropy although mathematicians consider it to be „highly chaotic“.

However, if we change the parameter to `a= 3.97 `

(instead of `3.90`

) it seems that the amount of entropy becomes sufficient. The nature of non-linear maps is that their behaviour is hard to grasp even when the algorithms are Open Source. By modifying these constants, a backdoor can be implemented that is somehow „hidden“ even though the source code is public.