RSA and Random Bitstream Generators

At the core of our online security is randomness. Within this we provide want to reveal none of the original data. A hash method will look…

RSA and Random Bitstream Generators

At the core of our online security is randomness. Within this, we provide want to reveal none of the original data. A hash method will look like random bits, and where a single change in one of the input bits, will cause a change in around half of the outputs. But we need to generate encryption keys, and to keep these secure, we need them to be as near random as possible. While pseudorandom number generators are good, they are not as good as true random sources. But it must be said, that there are no random sources that have actually been proven to be truly random.

The usage of random numbers can cause many problems, as developers often just link to standard libraries which do not quite generate a proper random number, or which repeat in every time they are called.

True or pseudo?

Within cryptography, random numbers are used to generate things like encryption keys. If the generation of these keys could be predicted in some way, it may be possible to guess them. The two main types of random number generators are:

Pseudo-Random Number Generators (PRNGs). This method repeats the random numbers after a given time (periodic). They are fast and are also deterministic, and are useful in producing a repeatable set of random numbers.
True Random Number Generators (TRNGs). This method generates a true random number and uses some which is random. One approach is to monitor the movements of a mouse pointer on a screen or from the pauses in key-strokes. Overall the method is generally slow, especially if it involves human interaction, but is non-deterministic and aperiodic.

Normally simulation and modelling applications use PRNG, so that the values generated can be repeated for different runs, while cryptography, lotteries, gambling and games use TRNG, as each value which is selected at random should not repeat or be predictable. Eve could thus guess the key created by the method that Bob uses to generate a key. So, in the generation of encryption keys for public-key encryption, user’s are typically asked to generate some random activity. The random number is then generated based on this activity.

Computer programs, though, often struggle to generate TRNG, and hard-ware generators are often used within highly secure applications. One method is to generate a random number based on low-level, statistically random “noise” signals. This includes things like thermal noise and from the photoelectric effect.

Within cryptography, it is important that we are generating values which are as near-random, so that Eve cannot guess the random numbers that Bob and Alice are used. With randomness, we cannot determine how random the values are by just taking a few samples. For this, we need a large number of samples and make an estimation of the overall randomness.

RSA Random Bit Stream Generator

So let’s look at a random number generator which uses the RSA method, and which is defined as a CGPRBG (Cryptographically Secure PseudoRandom Bit Generator). Initially, we generate two prime numbers (p and q). We then generate:

n=p×q

ϕ=(p−1)×(q−1)

Next, we generate a random value of e which is between [1,ϕ], and x_0 is selected between [1,n−1]. We then generate the random bit stream from for each bit (i) in the following iteration:

The coding is here:

import random

from Crypto.Util.number import *

import Crypto

import sys

primebits=64
bitsize=128

if (len(sys.argv)>1):
  primebits=int(sys.argv[1])

p = Crypto.Util.number.getPrime(primebits, randfunc=Crypto.Random.get_random_bytes)
q = Crypto.Util.number.getPrime(primebits, randfunc=Crypto.Random.get_random_bytes)

n = p*q
PHI=(p-1)*(q-1)

x=random.randint(1,n)

e=random.getrandbits(72)

print ("Prime number size:",primebits)
print ("Prime (p):",p)
print ("Prime (q):",q)
print ("Prime (n):",n)
print ("Prime (PHI):",PHI)
print ("x:",x)
print ("e:",e)
print("Random stream:\n")

for i in range(0,bitsize):
  x = pow(x,e,n)
  print (x & 1,end='')

The code:

A sample run:

Prime number size: 16
Prime (p): 65027
Prime (q): 50207
Prime (n): 3264810589
Prime (PHI): 3264695356
x: 1136516735
e: 52861013072681202620
Random stream:

00110001011001100011100111111111101001111010000001010101010110101101101000110010011010001100010010001001110011011110000010101110

Conclusions

The cryptography, even gaining information of a few bits can drastically change the overall security of a given implement, so we need to make sure the methods we are using are sound.