Tag: Cryptography

Blog Entry Wednesday, July 10, 2024, © James Pate Williams, Jr. My Dual Interests in Cryptography and Number Theory

I became fascinated with secret key cryptography as a child. Later, as an adult, in around 1979, I started creating crude symmetric cryptographic algorithms. I became further enthralled with cryptography and number theory in 1996 upon reading Applied Cryptography, Second Edition: Protocols, Algorithms, and Source Code in C by Bruce Schneier and later the Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. After implementing many of the algorithms in both tomes, I communicated my results to two of the authors namely Bruce Schneier and Professor Alfred J. Menezes. In 1997 I developed a website devoted to constraint satisfaction problems and their solutions, cryptography, and number theory. I posted legal C and C++ source code. Professor Menezes advertised my website along with his treatise. See the following blurb:

In the spirit of my twin scientific infatuations, I offer yet another C integer factoring implementation utilizing the Free Large Integer Package (known more widely as lip) which was created by Arjen K. Lenstra (now a Professor Emeritus). This implementation includes Henri Cohen’s Trial Division algorithm, the Brent-Cohen-Pollard rho method, the Cohen-Pollard p – 1 stage 1 method, and the Lenstra lip Elliptic Curve Method. If I can get the proper authorization, I will later post the source code.

total time required for initialization: 0.056000 seconds
enter number below:
2^111+2
== Menu ==
1 Trial Division
2 Pollard-Brent-Cohen rho
3 p - 1 Pollard-Cohen
4 Lenstra's Elliptic Curve Method
5 Pollard-Lenstra rho
1
2596148429267413814265248164610050
number is composite
factors:
total time required factoring: 0.014000 seconds:
2
5 ^ 2
41
397
2113
enter number below:
0

total time required for initialization: 0.056000 seconds
enter number below:
2^111+2
== Menu ==
1 Trial Division
2 Pollard-Brent-Cohen rho
3 p - 1 Pollard-Cohen
4 Lenstra's Elliptic Curve Method
5 Pollard-Lenstra rho
2
2596148429267413814265248164610050
number is composite
factors:
total time required factoring: 1.531000 seconds:
2
5 ^ 2
41
397
2113
415878438361
3630105520141
enter number below:
0

total time required for initialization: 0.055000 seconds
enter number below:
2^111+2
== Menu ==
1 Trial Division
2 Pollard-Brent-Cohen rho
3 p - 1 Pollard-Cohen
4 Lenstra's Elliptic Curve Method
5 Pollard-Lenstra rho
3
2596148429267413814265248164610050
number is composite
factors:
total time required factoring: 0.066000 seconds:
2
5 ^ 2
41
838861
415878438361
3630105520141
enter number below:
0

total time required for initialization: 0.056000 seconds
enter number below:
2^111+2
== Menu ==
1 Trial Division
2 Pollard-Brent-Cohen rho
3 p - 1 Pollard-Cohen
4 Lenstra's Elliptic Curve Method
5 Pollard-Lenstra rho
4
2596148429267413814265248164610050
number is composite
factors:
total time required factoring: 0.013000 seconds:
2
5
205
838861
415878438361
3630105520141
enter number below:
0

Five Stream Ciphers Created from Five Pseudorandom Number Generators Built Using the Tests of FIPS 140-1 by James Pate Williams, BA, BS, MSwE, PhD

The five pseudorandom number generators are:

  1. Triple-AES based ANSI X9.17 PRNG
  2. Triple-DES based ANSI x9.17 PRNG
  3. RSA based PRNG
  4. Micali-Schnorr PRNG
  5. Blum-Blum-Shub PRNG

Five stream ciphers were created using 1 to 5. Screenshots of the C# application follow:

sc aessc dessc rsasc mssc bbs

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.

Tests of Six Pseudorandom Number Generators (PRNGs) Using the Now Superseded FIPS 140-1 by James Pate Williams, Jr. BA, BS, MSwE, PhD

This blog explores six pseudorandom number generators which are enumerated as follows:

  1. Standard C# PRNG
  2. Triple-AES PRNG
  3. Triple-DES PRNG
  4. RSA Based PRNG
  5. Micali-Schnorr PRNG
  6. Blum-Blum-Shub PRNG

PT 00PT 01PT 02PT 03PT 04PT 05

Here is the order in terms of run-times from the fastest to the slowest: 1, 2, 3, 6, 5, 4.

 

PRNG Tests Using the Now Superseded FIPS 140-1 by James Pate Williams, Jr., BA, BS, MSwE, PhD

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.

PRNGTests AES Key

PRNG Tests AES

PRNG Tests DES Key

PRNG Tests DES

PRNG Tests C#

PRNG Tests Other AES

PRNG Tests Other AES Data

PRNG Tests Other DES Key

PRNG Tests Other DES Data

PRNG Tests Other C#

We use the five basic statistical tests of Chapter 5 Section 5.4.4 which are as follows:

  1. Monobit Test also Known as the Single Bit Frequency Test
  2. Serial Test also as the Two-Bit Frequency of Occurrence Test
  3. Poker Test
  4. Runs Test (Not to be confused with Montezuma’s Revenge)
  5. Autocorrelation Test

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.

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

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

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.

DES3 SC Encrypt

DES3 SC Encrypt Histogram

DES3 SC Encrypt Statistics

DES3 SC Decrypt Histogram

DES3 SC Decrypt Statistics

It would be nice if the index of coincidence was 0, but this index is probably satisfactory.

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.

 

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

Suppose you have a n vector of ASCII encoded characters, arbitrarily choose 1 <= n <= 1000. Choose a modulus N such that 128 <= N <= 1000. Also choose a pseudo-random number seed 1 <= s <= 2147483647. Next find a random n x n matrix that is invertible by Gaussian elimination over the integer field consisting of N elements. Suppose this matrix is M and its tridiagonal form is M’. Now suppose the plaintext is the n vector P and the ciphertext is the n vector C then we have for encryption:

C = M’P

Further assume the inverse of M’ is N’. For decryption we use the equation:

P = N’C

Where

M’N’ = N’M’ = I

Such that I is the n x n identity matrix.

This cipher is related to the classic Hill Cipher. This cipher is polyalphabetic. We show the results of one encryption and decryption using 10 ASCII ‘A’ characters, N = 999, and s = 1. As you can see each occurrence of the letter ‘A’ which is encoded as the decimal number 65 leads to different integer in the range 0 to 998 which has a maximum of 10 bits. The key consists of the 100 integers in the original 10 x 10 matrix. The application was implemented in C# using a Gaussian elimination over a number field algorithm from Henri Cohen’s A Course in Computational Algebraic Number Theory.

Matrix Cipher 0

Matrix Cipher 1

Matrix Cipher 2

Chapter 8 of the Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone Highlights by James Pate Williams, Jr. BA, BS, MSwE, PhD

Chapter 8 of the Handbook is devoted to the public key encryption systems available in the late 1990s. The most interesting algorithms in my humble opinion are:

  1. RSA (Rivest, Shamir, and Adleman) Public Key Algorithm
  2. Rabin Public Key Encryption Public Key Algorithm
  3. Generalized ElGamal Public Key Encryption Algorithm

My original C implementations that were created in the period 1996 to 1998 utilized the Free LIP (Free Large Integer Package) which was designed and implemented by Arjen K. Lenstra. Later, this particular  Professor Lenstra helped in the development of the General and Special Number Field Sieve. He is also of factoring large integers fame. I used the C# language again in my testing implementations.

First we display the RSA results using an artificially small bit size of 256 bits.

RSA Chapter 8

Key Generation

k :
256
n :
 71748965933911640426880165731135238544415795986802264097926042451628661227723
d :
17534201656439215903029293361854099060868747295577796745436087467699018441853
e :
46435195294099703737718314333558788184905780513774200544498948302189056810037

Encryption

plaintext :
Now is the time for all good men to come to the aid of the party
4e 6f 77 20 69 73 20 74 68 65 20 74 69 6d 65 20 66 6f 72 20 61 6c 6c 20 67 6f 6f 64 20 6d 65 6e 20 74 6f 20 63 6f 6d 65 20 74 6f 20 74 68 65 20 61 69 64 20 6f 66 20 74 68 65 20 70 61 72 74 79

bytes per block = 32
number blocks = 3

plaintext :
Now is the time for all good men to come to the aid of the party

ciphertext :
37 97 74 00 91 d6 09 6e f6 92 c0 7d 2b 55 27 3f 49 4c 8f 56 a0 3a 2e fb 24 9d cc a7 f4 6e c5 88 a3 5b 1c 5c 9e d3 c8 2e dd 4e f0 1a 4c 13 03 ec 88 ea 84 19 56 bc 8e b1 00 04 1f 16 cf 26 16 0a 68 75 69 03 21 fe 9f bd f0 0b 41 9b 6d 42 0f bc 3a c2 cc 81 08 5f 88 8c 55 f3 ac 63 03 00 73 23

Decryption

4e 6f 77 20 69 73 20 74 68 65 20 74 69 6d 65 20 66 6f 72 20 61 6c 6c 20 67 6f 6f 64 20 6d 65 6e 20 74 6f 20 63 6f 6d 65 20 74 6f 20 74 68 65 20 61 69 64 20 6f 66 20 74 68 65 20 70 61 72 74 79

plaintext :
Now is the time for all good men to come to the aid of the party

Rabin Chapter 8

Next we illustrate the Rabin public key cryptosystem using a 12-bit key.

Key Generation

k = 128
n = 211556863392599022339215233849307913121
p = 13935902955925754761
q = 15180707275422140761

Encryption

plaintext = Now is the time for all good men to come to the aid of the party
4e 6f 77 20 69 73 20 74 68 65 20 74 69 6d 65 20 66 6f 72 20 61 6c 6c 20 67 6f 6f 64 20 6d 65 6e 20 74 6f 20 63 6f 6d 65 20 74 6f 20 74 68 65 20 61 69 64 20 6f 66 20 74 68 65 20 70 61 72 74 79 
bytes per block = 16
number blocks = 5
a7 f3 64 45 7e 4d 63 7a fc 6f f4 58 05 2a 00 13 4c ea 0f 35 f2 a9 06 a0 18 84 7f f8 e0 1a ab 29 dd f7 77 7d a3 e0 5e fa 38 91 b3 43 f0 3b 45 38 20 82 df 81 56 28 eb fc d6 fd 1a 02 4b c4 6f 6b 00 40

Decryption

plaintext = Now is the time for all good men to come to the aid of the party

Now we move onto the generalized ElGamal public key cryptosystem.

ElGamal Chapter 8

Key Generation

k = 128
p = 461570115794525767856064295512031627189
a = 65681037355098887145615950726949326919
alpha = 329715121991374833383052968963601528401
alpha-a = 112278742131178183966835822395003469140

Encryption

plaintext = Now is the time for all good men to come to the aid of the party
4e 6f 77 20 69 73 20 74 68 65 20 74 69 6d 65 20 66 6f 72 20 61 6c 6c 20 67 6f 6f 64 20 6d 65 6e 20 74 6f 20 63 6f 6d 65 20 74 6f 20 74 68 65 20 61 69 64 20 6f 66 20 74 68 65 20 70 61 72 74 79 
bytes per block = 16
number blocks = 5

Decryption

plaintext = Now is the time for all good men to come to the aid of the party