C/C++ – Page 4 – Numerical Explorations

Triple-AES Stream Cipher Using the ANSI X9.17 Pseudorandom Number Generator (PRNG) by James Pate Williams, Jr. BA, BS, MSwE, PhD

The Advanced Encryption Standard (AES) is fully described in the National Institute of Standards and Technology (NIST) publication:

Click to access NIST.FIPS.197.pdf

AES is a secret key block cipher with a block length of 128-bits and variable key lengths of 128-bits, 192-bits, and 256-bits.

The ANSI X9.17 pseudorandom number generator is described by Alfred J. Menezes, ET AL. in the Handbook of Applied Cryptography on page 176 5.11 Algorithm.

We use triple-AES with three 256-bit keys in Encryption-Decryption-Encryption mode. Also we utilize two 128-bit numbers. The total key space is (768 + 256)-bits = 1024-bits.

We now illustrate in the following screenshots our C# implementation of a stream cipher using the preceding algorithms.

We use the following dialog to allow under certain circumstances the application to randomly generate the seed material for our PRNG. Unfortunately, the built-in C# PRNG only has 2^31 -1 = 2147483647 different seeds. This cuts down on the amount of thought and typing required but is inherently dangerous due to the relatively small number of seeds. If you want true security the requisite sixteen 64-bit numbers must be random.

AES3 Stream Cipher 0

AES3 Stream Cipher 1

AES3 Stream Cipher Encrypt 0

AES3 Stream Cipher Encrypt 1

AES3 Stream Cipher Decrypt 0

AES3 Stream Cipher Decrypt 1

Optimally we would like to 0 index of coincidence, but 0.00222 is reasonably acceptable.

ANSIX9_17 Source Code

Some Statistics for Another Matrix Cipher by James Pate Williams, Jr. BA, BS, MSwE, PhD

We first encipher the string “This is a test of the emergency broadcasting system!” which is a English language sample of length 52 ASCII characters.

New Matrix Cipher Encrypt 0

Below is a histogram of the plaintext characters.

New Matrix Cipher Encrypt 1

Here are the counts of the different plaintext characters and the statistic known as the index of coincidence. English has an index of coincidence of approximately 0.065, so this short sample is in that ballpark at 0.06067.

New Matrix Cipher Encrypt 2

Next we display part of the key material (upper triangular matrix elements), the ASCII encoded plaintext and the last column is the resulting ciphertext.

New Matrix Cipher Encrypt 3

We now display a histogram of the ciphertext.

New Matrix Cipher Decrypt 1

New Matrix Cipher Decrypt 2

The index of coincidence is 0. Each of the 52 plaintext characters map to a different ciphertext number in the range 2 to 977 inclusive. Now we show the decryption matrix, ciphertext, and plaintext.

New Matrix Cipher Decrypt 3

We now say a few more words about the cryptanalysis of this matrix cipher. Since the PRNG has a large key space, a direct brute force attack on the PRNG would probably be futile in a milieu without a quantum computer. We can guess values of N and we know that key matrix inverse has n * (n + 1) / 2 elements instead of n * n elements since it is an upper triangular matrix. In our sample the key matrix inverse has 52 * 53 / 2 = 26 * 53 = 1,378 matrix elements. Each matrix element is in the inclusive range 0 to 996 or 997 values. So we would need to brute force test N * n * (n + 1) / 2 possible key matrix inverses. In our case the number is 997 * 1,378 = 1,373,866 which is not a very large number by cryptanalytic standards but how many of those decryptions would make perfectly good sense? A reasonably adept adversary would not reuse the PRNG key and N for a new 52 ASCII character string so each message would require a new cryptanalytic attack.

Using the upper triangular nature of the key matrix inverse and a further assumption that the plaintext is in the range 32 to 127 or 96 different values, we can reduce the brute force attack to 96 * 1,378 = 132,288 possibilities. Again the adversary could somewhat thwart these cryptanalytic efforts by choosing a much larger N and n.

However, all of this mental masturbation amounts to a mute point since no modern and sane adversary would utilize such an easy cipher to break. Just use a one time pad based on the ANSI X9.17 PRNG utilizing triple-AES instead of triple-DES with three 256-bit E-D-E keys or an astounding 768-bits of key material for the cipher core alone plus 256 bits in additional secret information. The final keyspace of such a scheme would be 1024-bits!

Another Matrix Cipher by James Pate Williams, Jr. BA, BS, MSwE, PhD

This is perhaps an improvement on the matrix cipher of a previous blog post of mine. In that post I introduced a matrix cipher whose keys were generated by selection of a seed such that 1 <= seed <= 2147483647, a number N such that 2 <= N <= 1000, and plaintext of length n such that 1 <= n <= N -1.

This matrix cipher relies on the ANSI X9.17 pseudorandom number generator (PRNG) of 5.11 Algorithm of the Handbook of Applied Cryptography by Alfred J. Menezes, et al. The PRNG uses triple-DES with a potential 168-bit (56 * 3 = 168) key space using E-D-E (Encryption key 1 – Decryption key 2 – Encryption key 3). Also, a 64-bit date related number and a 64-bit random seed are needed to initialize the PRNG.

The key space for the algorithm is (168 + 128) bits which is 296 bits. Here is the encryption and decryption of the ASCII ten characters string “ATTACK NOW”.

New Matrix Cipher 0

New Matrix Cipher 1

New Matrix Cipher 2

New Matrix Cipher 3

New Matrix Cipher 4

The first step in the cryptanalysis of this cipher would be to determine the modulus of the matrix and vector calculations N. I don’t know how many ciphertexts would be necessary to perform this task. From the preceding known ciphertext we find that N is at least 991. From traffic analysis we may have determined that the maximum value of N is 1000. That means would we only need to try 10 values of N.

Two of My Many Sorting Algorithms Implementations by James Pate Williams, Jr. BA, BS, MSwE, PhD

A recurring theme in my life has been to implement and re-implement the sorting algorithms found in Harold Lorin’s treatise Sorting and Sort Systems and Thomas H. Corman et al.’s Algorithms. I purchased a copy of Lorin’s book in the summer of 1979 and Corman’s textbook in 1999 or 2000. This has been good exercise in translating from one computer language to a later and greater newer computer language. I began in BASIC and FORTRAN IV and transitioned to C, C++, C#, Common LISP, Java, Modula-2, Pascal, and Scheme in alphabetic not chronological order. In this blog we cover two C# applications, one from October 26, 2010, named Sorting Comparisons and the other from January 17, 2015, with the moniker Sorting.

In the Sorting Comparisons application, we compare the sorting algorithms: Heap Sort, Quick Sort, and Singleton’s Sort. The first two algorithms are from the Algorithms tome and Singleton’s Sort is from Lorin’s treatment. These are some of the fastest general purpose sorting algorithms available in my particular arsenal.

Sorting Comparisons Test All 16 Sorting Comparisons Time All 1000