, , , , , , , , , , , , ,

Here’s the basic problem I was trying to solve: The RSA encryption software must use keys derived from two very large numbers that must be co-prime. I’ll explain in a later post exactly where this fits in. In the real world, they’ll be somewhere around 60 digits in length, so obviously it’s impractical to expect the user to set these numbers.
The numbers could be built into the program, but that would defeat the principle that a cipher should be fully distributable without compromising security. That leaves us with the option of generating the keys randomly, so they’ll be unique for each session. For this a Pseudo-Random Number Generator (PRNG) is needed.

I started off by copying a simple C++ example from a site, which basically uses the system clock and the rand() function.

Defining the Output Range
With most applications we might want only values within a defined range. For example, a dice program would have a range between 1 – 6.
For the RSA program, we’re using a much bigger range, both numbers having a specific number of digits. For now, I’ve set this as 1000000 – 999999 by declaring values LowerLimit and UpperLimit as constants, but it should really be much larger as FirstRandomInt and SecondRandomInt have been declared as long integers in my program (meaning a lot of unused buffer space).

The following is what generates both numbers:
FirstRandomInt = rand() % (UpperLimit - LowerLimit + 1) + time(NULL);
SecondRandomInt = rand() % (UpperLimit - LowerLimit + 1) + time(NULL);

The larger the numbers, the harder it’ll be to predict in advance the values generated, and consequently the keys also become harder to guess.

Relative Primes
Thanks to the Cryptology lectures, I’ve not only found a way to generate a pair of pseudo-random numbers with the right number of digits, but also values that are relative primes. This is what I had problems with when developing the RSA part of the XeroCrypt software last year. In this case it’s a simple matter of dropping the random number generator code into an earlier program, then making it loop.

The modified code works roughly like this: The program generates a pair of pseudo-random numbers using rand() and the system clock, passes them to a function that calculates their greatest common denominator (using the Eclidean algorithm), and repeats the entire process until the GCD is exactly 1 (indicating the numbers are co-prime). The pseudo-code looks something like:

FindGCD(FirstRandomInt, SecondRandomInt)
Calculate GCD of the two numbers
Pass GCD to Main()

While GCD > 1
Generate two random numbers
Pass RandomInt1 and RandomInt2 to FindGCD()
Print FirstRandomInt
Print SecondRandomInt

Adventures with Crypto++
While the basic PRNG that does what I need, it’s a bit crap. A real-world RSA system would use a Cryptographically Secure Pseudo-Random Number Generator (CSPRNG). Without this, we potentially have a flaw that enables an attacker to derive the keys. A suitable PRNG must meet several criteria:
* The output should be impossible to predict, beyond the fact the numbers are co-prime and within a certain range.
* The PRNG’s output must be independent of external factors, that is an attacker cannot influence the numbers it generates. For example, by changing the room temperature or causing a power surge.
* Ideally the output would be checked to ensure all the output values are uniformly distributed. There shouldn’t be any tendency to generate certain values.

Using one of the PRNGs that came with Crypto++ (such as the Mersenne Twister) would have been an excellent way of getting started with it, I wanted it done with fewer lines of code. The first step was to copy a very simple program to check whether the IDE was linking to the Crypto++ library. It wasn’t.

The program compiled okay, but attempts to build it threw up several ‘undefined reference’ errors. Basically it meant the compiler doesn’t know where the relevant Crypto++ libraries are. A quick Google (actually an IXquick) search revealed that numerous others had experiencing the same problem.
The problem’s sorted by appending -lcrypto++ to g++ compile and build commands, so the compiler knows what it’s supposed to link to. It also turns out headers in the program must be defined in the form: ‘#include "cryptopp/randpool.h"‘.

While I haven’t got the PRNG code itself working yet using Crypto++, I kind of got sidetracked into building another program that uses the AES function to encrypt any 256-character message.