Random Number Generation and Windows Forms Encryption via C# Parallel Programming


Introduction

Sometimes the terms concurrency and parallelism are used interchangeably. But a multi-threaded application can have threads execute simultaneously while residing on one physical chip. Parallelism, however, is achieved only when those concurrent threads are executing on separate cores of a multi-core chip. When we write an algorithm to use concurrency, our most important design choice should be to figure out how to partition the original problem into individual sub-parts. Most programs spend a lot of their execution time running loops over an iteration range, so parallelizing those loops enables concurrency.

The purpose of this article to show how to use parallel programming to build a Windows Forms application that is able to use a random number generator to implement an encryption of a quote. The reader will find that when the parallel check box is checked, the number of random number generations is much greater than if done sequentially. Apart from the Windows designer code that is generated by IDE while building form, there is a program file that contains the main function of source execution. The complicated part is understanding the two classes: the TextMatchGeneticAlgorithm.cs and the ThreadSafeRandom.cs algorithm. The ThreadSafeRandom file contains objects that are constructed in the TextMathGeneticAlgorithm file. Both of these files are mutually inclusive to the main form files and the Program.cs files.

Because we are dealing with random number generation of certain types, I am going to begin this article explaining the .NET provisions for these mechanisms. After exemplifying the basics about random number generator (RNGCryptoServiceProvider), the downloadable source ThreadSafeRandom.cs should not appear too complicated. The TextMatchGeneticAlgorithm.cs follows after these parallel patterns. An excellent source of information regarding parallel programming resides at the MSDN Parallel Programming Center. Most of the articles are must reads and useful for both reference and developing your own content.

The .NET Framework has two ways of generating random numbers. Most programs will instantiate a System.Random object instance and call one of the member functions to get random numbers. The numbers returned aren't truly random, but rather pseudo random. But they're good enough for most applications that call for randomness. But the pseudo random nature of the numbers returned by System.Random objects is not good enough for cryptographic purposes. The algorithm used by System.Random to generate random numbers is actually generating a sequence in which the next number generated is dependent on the previous number generated. The algorithm is deterministic and predictable. Somebody who knows how the algorithm works can use that information to trivially break any encryption based on the pseudorandom numbers. Cryptographic applications require truly random sequences that can't be predicted. In .NET, the System.Security.Cryptography.RandomNumberGenerator abstract class serves as the base class for all cryptographic random number generators. System.Security.Cryptography.RNGCryptoServiceProvider provides an implementation of that abstract class.

Generating Secure Random Values

The first step in generating truly random values is to create an instance of the RNGCryptoServiceProvider class. Then, allocate an array of bytes and pass that array to the GetBytes method. The random number generator will fill the byte array with a sequence of random values. Here's how to do it in C#:

using System;

using System.Security;

using System.Security.Cryptography;

public class Program

{

    public static void Main()

    {

        RNGCryptoServiceProvider random = new RNGCryptoServiceProvider();

        byte[] randomBytes = new byte[1024];

        random.GetBytes(randomBytes);

        foreach (var b in randomBytes)

        {

            Console.Write("{0:X2} ", b);

        }

    }

}

Here is the output:

7D 96 7D EB C3 A1 81 64 52 7E 80 57 7D 3B 10 2C 8E 7D 27 D8 4F 38 29 99 2E

32 BB 23 74 4E 61 65 43 45 EB 15 53 9B 50 F2 74 A5 83 9E C0 AF CB 72 53 86

75 7F 6A 83 D7 74 8A B5 CF D1 B8 F8 BF 2A 7D A6 62 44 6F E9 8B F8 26 C4 CE

D2 A7 F0 29 94 A9 F8 F6 E6 95 58 6F DF 4F DE 60 2D 56 A4 93 35 3A CA B3 17

E9 E6 19 C3 41 D7 C6 D1 9E E6 A3 94 C8 A3 20 14 4F F5 83 30 EB 08 C7 39 D2

65 B3 F1 65 6B 23 1E 61 D9 AA 22 D0 59 BC 02 B5 CC 06 D2 48 0E 14 CD FC D2

5F 77 17 26 79 40 C6 F9 FE 00 69 EF 9A 3F E4 BE E5 9D FB 89 1D 7F E6 1E A1

F7 DF BA B6 CC 9F B4 F9 5A 37 FE 58 B5 2F 9F 51 86 FE 69 57 7E F8 45 16 34

52 3C 8E 87 AF 59 5E 9B EF 61 79 59 AC 73 81 52 7A C9 F4 3F EC E0 C9 5B FE

30 E8 E9 00 7B DC E6 C5 F4 88 30 93 48 80 B2 0E D9 F5 B4 1F 1D E7 F4 A1 DA

DA CD CE 26 5F 30 A0 D1 9E 73 01 8D 2D 70 34 51 80 97 08 39 3B C8 0F EC 2A

18 BD C1 06 95 20 3D F7 3F 79 8A 9C 26 76 10 22 47 01 38 3A 94 04 30 BB A4

DB A1 FD 3D 43 45 EA F3 0D 1C 87 77 DC C3 41 AC 0D 82 28 05 54 61 42 F5 BC

1D 92 AC BD 36 53 C7 1F E9 F3 D4 9C 51 B3 69 77 E3 A5 92 52 FF 18 E7 5C 11

95 09 C2 EE 53 D9 E7 D9 D4 6A 6B 5F D8 B6 08 36 6C 5B 95 A6 24 49 BD 1F B6

5A 18 1D C5 30 54 33 9B 3C 30 95 83 C3 48 B2 AB 21 92 65 35 E9 86 EC 26 71

65 5A 94 05 CA 1D FB DE 81 B3 ED 7F 04 20 16 A5 68 2D E2 EC 46 B5 6D 00 17

2F 81 76 3A 86 11 05 31 ED BA BF 1D 3D D6 69 8F AD 3F 18 94 61 E2 CE B3 08

2D 6A E7 AF 17 02 75 48 60 00 7D 9B 92 0B A1 A3 62 D6 46 D0 C9 6A E9 FB D5

03 1C 43 4A 6A 76 1D 45 90 0D D8 6B 64 3A 2C 38 F1 42 4F 98 79 2C 6C 77 69

3B 87 A4 7E 00 87 15 92 02 67 5C C0 20 1C 81 E7 DF F7 7A 28 6F 7F 70 10 51

8A 17 67 2C 75 9C 2E 20 C2 5E 80 98 11 CC 46 87 FB 4A 85 65 99 58 06 6D 86

E2 50 2C FB EA 69 47 DE 3E B2 39 B0 E4 5D B3 63 F3 70 C6 52 67 F1 09 C8 AC

and so on . . . . . . . .

Generating Random Integers

In general, applications that require the use of truly random values don't typically need random integers or random floating point numbers. They just need random bytes. But if you really want random integers or other multi-byte values, you'll have to construct them yourself from the bytes returned by GetBytes. The code below generates 256 random positive integers from the random bytes returned by GetBytes.

using System;

using System.Security.Cryptography;

public class Program

{

    public static void Main()

    {

        RNGCryptoServiceProvider random = new RNGCryptoServiceProvider("testo");

        byte[] randomBytes = new byte[256 * sizeof(int)];

        random.GetBytes(randomBytes);

        for (int i = 0; i < 256; ++i)

        {

            int val = BitConverter.ToInt32(randomBytes, i * 4);

            val &= 0x7fffffff;

            Console.WriteLine(val);

        }

    }

}

And the output is:


317550161

422861278

526562124

449336275

991713816

1652487604

880619295

633790643

1397989797

696122560

2081704890

338459605

1023259457

903093930

630767348

554883809

809901421

685484127

1992278417

1651570395

1606911073

1970878803

1813967620

1119285127

1545465870

1674136843

212937010

1301413975

1144306793

997391586

234662339

1345235759

1055049749

914349757

1286666161

506392153

1768422944

914725219

335875720

720919927

1278360239

1362332549

270292310

1587219133

403765394

1192342225

597086276

802359086

864984234

and so on . . . . .

BitConverter.ToInt32 gets the next four bytes in the array and returns a 32 bit integer. The next line of code just makes sure that the number is positive. If you don't mind getting negative numbers, then you can skip that. Or, you can get unsigned integers by calling BitConverter.ToUInt32.

The Two Class Library Files

Here is ThreadSafeRandom.cs:

using System;

using System.Security.Cryptography;

namespace System.Threading

{

    public class ThreadSafeRandom : Random

    {

        private static readonly RNGCryptoServiceProvider _global =

                                      new RNGCryptoServiceProvider();

        private ThreadLocal _local = new ThreadLocal(() =>

        {

            var buffer = new byte[4];

            _global.GetBytes(buffer);         // RNGCryptoServiceProvider is

            // thread-safe for use in this manner

            return new Random(BitConverter.ToInt32(buffer, 0));

        });

        public override int Next()

        {

            return _local.Value.Next();

        }

        public override int Next(int maxValue)

        {

            return _local.Value.Next(maxValue);

        }

        public override int Next(int minValue, int maxValue)

        {

            return _local.Value.Next(minValue, maxValue);

        }

        public override double NextDouble()

        {

            return _local.Value.NextDouble();

        }

        public override void NextBytes(byte[] buffer)

        {

            _local.Value.NextBytes(buffer);

        }

    }

}

And here is the TextMatchGeneticAlgorithm.cs file:

using System;

using System.Linq;

using System.Text;

using System.Threading;

using System.Threading.Tasks;

using System.Security.Cryptography;

namespace ShakespeareanMonkeys

{

    public class TextMatchGeneticAlgorithm

    {

        private static ThreadSafeRandom _random = new ThreadSafeRandom();

        private static char[] _validChars;

        private string _targetText;

        private GeneticAlgorithmSettings _settings;

        private TextMatchGenome[] _currentPopulation;

        private bool _runParallel;

        static TextMatchGeneticAlgorithm()

        {

            // Initialize the valid characters to newlines plus

            // all the alphanumerics and symbols

            _validChars = new char[2 + (127 - 32)];

            _validChars[0] = (char)10;

            _validChars[1] = (char)13;

            for (int i = 2, pos = 32; i < _validChars.Length; i++, pos++)

            {

                _validChars[i] = (char)pos;

            }

        }

        public TextMatchGeneticAlgorithm(bool runParallel,

               string targetText, GeneticAlgorithmSettings settings)

        {

            if (settings == null) throw new ArgumentNullException("settings");

            if (targetText == null) throw new ArgumentNullException("targetText");

            _runParallel = runParallel;

            _settings = settings;

            _targetText = targetText;

        }

        public void MoveNext()

        {

            // If this is the first iteration, create a random population

            if (_currentPopulation == null)

            {

                _currentPopulation = CreateRandomPopulation();

            }

            // Otherwise, iterate

            else _currentPopulation = CreateNextGeneration();

        }

        public TextMatchGenome CurrentBest { get { return _currentPopulation[0]; } }

        private TextMatchGenome[] CreateRandomPopulation()

        {

            return (from i in Enumerable.Range(0, _settings.PopulationSize)

                    select CreateRandomGenome(_random)).ToArray();

        }

        private TextMatchGenome CreateRandomGenome(Random rand)

        {

            var sb = new StringBuilder(_targetText.Length);

            for (int i = 0; i < _targetText.Length; i++)

            {

                sb.Append(_validChars[rand.Next(0, _validChars.Length)]);

            }

            return new TextMatchGenome { Text = sb.ToString(), TargetText = _targetText };

        }

        private TextMatchGenome[] CreateNextGeneration()

        {

            var maxFitness = _currentPopulation.Max(g => g.Fitness) + 1;

            var sumOfMaxMinusFitness = _currentPopulation.Sum

                       (g => (long)(maxFitness - g.Fitness));

            if (_runParallel)

            {

                return (from i in ParallelEnumerable.Range

                               (0, _settings.PopulationSize / 2)

                        from child in CreateChildren(

                            FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness),

                            FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness))

                        select child).

                        ToArray();

            }

            else

            {

                return (from i in Enumerable.Range(0, _settings.PopulationSize / 2)

                        from child in CreateChildren(

                            FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness),

                            FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness))

                        select child).

                        ToArray();

            }

        }

        private TextMatchGenome[] CreateChildren(

            TextMatchGenome parent1, TextMatchGenome parent2)

        {

            // Crossover parents to create two children

            TextMatchGenome child1, child2;

            if (_random.NextDouble() < _settings.CrossoverProbability)

            {

                Crossover(_random, parent1, parent2, out child1, out child2);

            }

            else

            {

                child1 = parent1;

                child2 = parent2;

            }

            // Potentially mutate one or both children

            if (_random.NextDouble() < _settings.MutationProbability)

                Mutate(_random, ref child1);

            if (_random.NextDouble() < _settings.MutationProbability)

 

                Mutate(_random, ref child2);

            // Return the young'ens

            return new[] { child1, child2 };

        }

        private TextMatchGenome FindRandomHighQualityParent

                       (long sumOfMaxMinusFitness, int max)

        {

            long val = (long)(_random.NextDouble() * sumOfMaxMinusFitness);

            for (int i = 0; i < _currentPopulation.Length; i++)

            {

                int maxMinusFitness = max - _currentPopulation[i].Fitness;

                if (val < maxMinusFitness) return _currentPopulation[i];

                val -= maxMinusFitness;

            }

            throw new InvalidOperationException("Not to be, apparently.");

        }

        private void Crossover(Random rand, TextMatchGenome p1,

        TextMatchGenome p2, out TextMatchGenome child1, out TextMatchGenome child2)

        {

            int crossoverPoint = rand.Next(1, p1.Text.Length);

            child1 = new TextMatchGenome

            {

                Text = p1.Text.Substring(0, crossoverPoint) +

                    p2.Text.Substring(crossoverPoint),

                TargetText = _targetText

            };

            child2 = new TextMatchGenome

            {

                Text = p2.Text.Substring(0, crossoverPoint) +

                    p1.Text.Substring(crossoverPoint),

                TargetText = _targetText

            };

        }

        private void Mutate(Random rand, ref TextMatchGenome genome)

        {

            var sb = new StringBuilder(genome.Text);

            sb[rand.Next(0, genome.Text.Length)] = _validChars[rand.Next

                               (0, _validChars.Length)];

            genome.Text = sb.ToString();

        }

    }

    public struct TextMatchGenome

    {

        private string _targetText;

        private string _text;

        public string Text

        {

            get { return _text; }

            set

            {

                _text = value;

                RecomputeFitness();

            }

        }

        public string TargetText

        {

            get { return _targetText; }

            set

            {

                _targetText = value;

                RecomputeFitness();

            }

        }

        private void RecomputeFitness()

        {

            if (_text != null && _targetText != null)

            {

                int diffs = 0;

                for (int i = 0; i < _targetText.Length; i++)

                {

                    if (_targetText[i] != _text[i]) diffs++;

                }

                Fitness = diffs;

            }

            else Fitness = Int32.MaxValue;

        }

        public int Fitness { get; private set; }

    }

    public class GeneticAlgorithmSettings

    {

        public int PopulationSize

        {

            get { return _populationSize; }

            set

            {

                if (value < 1 ||

                    value % 2 != 0)

                    throw new ArgumentOutOfRangeException("PopulationSize");

                _populationSize = value;

            }

        }

        public double MutationProbability

        {

            get { return _mutationProbability; }

            set

            {

                if (value < 0 || value > 1)

                    throw new ArgumentOutOfRangeException("MutationProbability");

                _mutationProbability = value;

            }

        }

        public double CrossoverProbability

        {

            get { return _crossoverProbability; }

            set

            {

                if (value < 0 || value > 1)

                    throw new ArgumentOutOfRangeException("CrossoverProbability");

                _crossoverProbability = value;

            }

        }

        private int _populationSize = 30;

        private double _mutationProbability = .01;

        private double _crossoverProbability = .87;

    }

}

Those files are downloadable as a zip file. When you open the zip file, press Ctrl-A to select all of the files (or the initial folder) and then extract to a new folder in the Projects folder of the Visual Studio 2010 folder. Visual Studio 2010 is an easy download as an ISO file and is easy to burn to a DVD. Once the files are exposed, click the solution file, build the solution, and then choose "run without debugging".

1.png

Now we run the application first in sequential mode (i.e., we don't check the parallel check box). Take care to note the number of generations per second, as well as the number of generations altogether:

2.png

Parts of this article have been referenced from MSDN's Parallel Computing Center


Similar Articles