A few years ago, I implemented the LLL lattice reduction algorithm found in two references: “Handbook of Applied Cryptography” Edited by Alfred J. Menezes et al and “A Course in Computational Algebraic Number Theory” by Henri Cohen. My new implementation in C# uses 64-bit integers and BigIntegers. Here are some results.
The five pseudorandom number generators are:
Five stream ciphers were created using 1 to 5. Screenshots of the C# application follow:
The pass phrase optimally should consist of 147 ASCII characters. If the number of pass phrase ASCII characters is less than 147 then more random ASCII characters are added using the standard C# pseudorandom number generator seeded with the parameter named Seed. The user defined parameter k is used by RSA, Micali-Schnorr, and Blum-Blum-Shub pseudorandom number generators. It is the approximate bit length of the large composite number composed of two large probable prime numbers. The real key lengths of all the stream ciphers is about 1024-bits for 1, 3, 4, and 5 and 296-bits for 2. I’d strongly suggest using 1 and/or 5.
This blog explores six pseudorandom number generators which are enumerated as follows:
Here is the order in terms of run-times from the fastest to the slowest: 1, 2, 3, 6, 5, 4.
This blog post is dedicated to Section 5.3.1 ANSI X9.17 generator page 173 with 5.11 Algorithm and Section 5.4.4 Five basic tests pages 181-183 especially 5.32 Note of the Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. I developed a PRNG test program for three PRNGs namely, Triple-AES, Triple-DES, and the C# built-in PRNG.
Each time an algorithm is run a randomly generated key is generated based on the time of day and the C# built-in PRNG with a key space of 2147483647 possible seeds. Triple-AES requires a 147 7-bit ASCII key and part of a similar key is used to construct the 296-bit Triple-DES key material. Now onto my C# Windows Forms application’s screenshots.
We use the five basic statistical tests of Chapter 5 Section 5.4.4 which are as follows:
Below is a copy of a recent email of mine concerning Secret Key Exchange or Distribution:
The linchpin and point of greatest vulnerability in any secret key cryptographic system is the key exchange mechanism. Now suppose that we are living in a post quantum computer world. This means that traditional public key cryptosystems such as RSA (integer factorization problem based) and elliptic curve public key cryptography (discrete logarithm problem based) are effectively broken. That implies that any public key based cryptographic key exchange is compromised over communication channels where Eve, the classical eavesdropper, is listening in on the key exchange between Alice and Bob. Quantum cryptography over fiber optic channels allows the communication endpoints to detect the eavesdropper and thus abort a potentially compromised key exchange. However, quantum cryptography is not readily available everywhere on the vast Internet. The rest of this email missive is devoted to other more exotic means of secret key exchange.
Human to human key exchange is optimal provided that all human beings in the loop are trustworthy. A good way to exchange secret keys is via a diplomatic courier with a diplomatic pouch and the key bits are concealed by a steganographic means.
Now suppose an adversary of an English speaking and reading country has two agents or human intelligence operatives that have infiltrated the country. Further both agents have the same 1024-bit seeded pseudorandom number generator-based stream cipher on their desktops and/or laptops for secure communications. That means they must somehow pass 147 secret 7-bit printable ASCII characters of information between one another for each quasi-one-time pad message. Each character represents 7 bits of the key and there are 5 bits left over after construction of each key. Also, suppose an actual face-to-face meeting between the two spies is inadvisable. Enter the text based social media or library book code. Now suppose the two spies are connected to one another via Facebook but are afraid to use text messaging for direct key exchange or clandestine communication. The solution is to use a shared Facebook page of text to construct the secret key. One spy shares a Facebook post containing at least 147 English characters and the other spy looks up the post. Both spies cut and paste the first 147 English characters of the post into a key constructing application. Voila, now both spies can communicate using their handy dandy stream cipher and email and/or cell phone text messaging of encrypted data in the form of three-digit decimal numbers. An alternative key exchange could be by the classic and readily available book code. Assume both spies have access to the same library, but not concurrent access. Both somehow agree to go and copy 147 characters from the same book in the library’s reference section. They write down the passage and take it home to enter the text into the key generator. Again, we have a means of clandestine key exchange.
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.
Optimally we would like to 0 index of coincidence, but 0.00222 is reasonably acceptable.
In this blog post we give some information about my implementation of a C# triple-DES stream cipher using the ANSI X9.17 pseudorandom number generator of 5.11 Algorithm in the Handbook of Applied Cryptography by Alfred J. Menezes, ET AL. page 173. This is about as close as I can come to a one time pad (perfect security) utilizing a triple-DES based function for key generation. I suspect the security is pretty tight as long as one does not stupidly reuse a key. Recall from my previous blogs on the ANSI X9.17 matrix cipher that key space is 168-bits for triple-DES in E-D-E mode and an additional 128-bits in other key parameters for a total of 296-bits.
It would be nice if the index of coincidence was 0, but this index is probably satisfactory.
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.
Below is a histogram of the plaintext characters.
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.
Next we display part of the key material (upper triangular matrix elements), the ASCII encoded plaintext and the last column is the resulting ciphertext.
We now display a histogram of the ciphertext.
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.
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!
Numerical Explorations 