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

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 16Sorting Comparisons Time All 1000Sorting Comparisons Time All 10000Sorting Comparisons Time All 100000Sorting Comparisons Time All 1000000

Sorting Comparisons Source Code

https://code.msdn.microsoft.com/windowsdesktop/Tests-of-Six-Sorting-94aa6fd0?redir=0

 

Selected Exercises for the Feynman Lectures on Physics by Richard Feynman, Et Al. Chapter 27 Quantum Behavior: Waves, Particles, and Photons – Detailed Work by James Pate Williams, Jr. BA, BS, MSwE, PhD

Computerized solutions to Exercises 27.3 to 27.6:

Exercise 27.3 Main

Exercise 27.3

Exercise 27.4

Exercise 27.5

Exercise 27.6

Partial source code for the preceding C# application:

Exercise 27.3

Detailed solutions to Exercises 27.3 to 27.7 in a Portable Document File (PDF):

Feynman Exercises Chapter 27

 

Excerpt from My Memoirs “Clinging onto the Edge of the Abyss” by James Pate Williams, Jr. BA, BS, MSwE, PhD

I believe in late spring quarter of 1978, Mr. P.M. Hicks, a chemistry and physics professor at LaGrange College, introduced me to a large desktop Texas Instruments (TI) programmable calculator. I immediately became immersed in the manual and I learned the rudiments of calculator programming on this machine.

I advanced onto LaGrange College’s new Data General Eclipse minicomputer in the summer of 1978. I taught myself Dayton BASIC (Beginner’s All Purpose Symbolic Instruction Code) using the book “BASIC Programming” by Paul W. Murrill and Cecil L. Smith of which I still own a copy and it is copyrighted 1971. I seem to recall I special ordered the textbook from the LaGrange College library. This self-study put me many steps in front of my peers in the Fall Quarter of 1978 when I took a course under Professor Kenneth Cooper on BASIC programming. I taught Professor Cooper how to perform matrix and vector calculations using the Data General BASIC interpreter.

I also was taking my first course in physical chemistry in the fall of 1978. During the week of Monday, November 6, 1978 my physical chemistry partner Chuck H. Pitts (now Dr. Chuck H. Pitts, a prominent dentist in LaGrange, GA) did an experiment whose lab report title was “Determination of Molecular Size and Avogadro’s Number”. I seem to recall the division of labor was that I perform the calculations with the aid of a BASIC computer and Chuck and I would write up the experiment and I believe someone in the Callaway Foundation office or Chuck did the actual typing of the document at the Callaway Foundation office on Broome Street in LaGrange, GA. Well it took a lot of persuasion by Chuck to get me to do my part, since back in that era I was prone to destructive perfectionism. (Incidentally, I did not give up on being a perfectionist until Professor Felton at Georgia Tech in 1981 stated categorically “There is no room for perfectionism in science.”)

In the Winter Quarter of 1979 I took a FORTRAN (Formula Translator) IV course under Professor Kenneth Cooper. That quarter I also had Professor Cooper for Physical Chemistry II and Biochemistry. I did well in the computer programming course and I can remember helping several fellow students to pass the course. Professor Brooks Shelhorse then of the Math Department was one of my fellow classmates that I tutored. Biochemistry was an 8:00 AM course. I spent a lot of late nights in the computer lab, so I would sometimes fall asleep during the biochemistry lectures. I distinctly remember Dr. Cooper hurling an eraser near me to wake me up one morning. I made B’s in the two chemistry courses.

Spring Quarter of 1979 was my final quarter as a chemistry student at LaGrange College. I took Quantitative Analysis II, an Independent Study in Chemistry, General Physics III, and Angling. I made all A’s that quarter. The independent study was an introductory course to architecture and programming of the Intel 8085 microprocessor. Dr. Cooper in his time as a computer engineering student at Auburn University had built two very nice and unique computers, a rather large analog computer and a digital computer that consisted of an Intel 8085 microprocessor in a wooden box with hexadecimal keypad, two seven segment red light emitting diode displays, EEPROM, and RAM memory.  I used the digital computer in my independent study. Professor Cooper taught me about the instruction set for the microprocessor and I would hand assemble my assembly language programs into two hexadecimal digit strings of machine code and manually enter the machine code via the keypad. One of my first assignments was to count down from 0xFF = 255 decimal to 0x00 = 0 decimal. I had a delay of about a ¼ second built into the program, so it took me one minute and four seconds to count down to zero. I was the only student in my independent study, therefore, it sometimes felt funny to have Professor Cooper give a whole one-hour lecture to an audience of one.

I bought the IBM book “Sorting and Sort Systems” by Harold Lorin in the summer of 1979. I proceeded to implement most of the sorting and merge algorithms in the book. I first translated the IBM PL/I (Programming Language I) code to BASIC and later for FORTRAN IV. Professor Cooper had developed a large BASIC program for the LaGrange College Registrar, Jimmy Herring. This program used a slow sorting algorithm which was either Shell sort of Bubble sort. I implemented a very fast sorting algorithm named Singleton’s sort in BASIC and was able to dramatically cut the time required to sort all the students by their Social Security Administration numbers which many colleges and universities then used as their primary flat-file or database key. I also began teaching myself the Data General Advanced Operating System (AOS) macro-assembly language. Like many computer programmers before I became infatuated with all the control over an operating system that assembly language afforded a knowledgeable programmer.

I convinced my parents to pay for me to audit Calculus and Analytic Geometry IV under Professor Shelhorse during the Fall Quarter of 1979, so I would have an excuse to be on campus to use my favorite computer, the LaGrange College Data General Eclipse minicomputer. That quarter I re-implemented my fast sorting algorithm in assembly language and set a new sorting time record with a program that sorting about 1000 student data records. Since the code was in AOS macro-assembly language it could not be readily integrated with the existing registrar’s system.

In 1980 I bummed around the college using the computer system until I was accepted to chemistry graduate school at the Georgia Institute of Technology for the Fall Quarter of 1980. I taught myself Data General Pascal and furthered my work with macro-assembly language, BASIC, and FORTRAN IV in the Winter, Spring, and Summer Quarters of 1980 at LaGrange College. I was unpaid computer programming teaching assistant for those three quarters which allowed me to earn my keep so to speak.

http://www.lagrange.edu/index.html

https://social.technet.microsoft.com/Profile/james%20pate%20williams%20jr

https://www.facebook.com/pg/JamesPateWilliamsJrConsultant/posts/

https://www.linkedin.com/in/james-williams-1a5b1370/

 

 

 

Selected Exercises for the Feynman Lectures on Physics by Richard Feynman, Et Al. Chapter 4 Kinematics – Detailed Work by James Pate Williams, Jr. BA, BS, MSwE, PhD

Exercises 4.1 to 4.7:

Feynman Exercises Chapter 04

Computer solution output of Exercise 4.6:

Exercise 4.6

C# source code for the computer solution of Exercise 4.6, sorry about the naming confusion in the file:

Exercise 4.6

Computer solution of Exercise 4.7 using a velocity square drag function (velocity retardation function is the term used in exterior ballistics). I wrote a baseball ballistics program based on my numeric work (Runge-Kutta Fifth Order) and analytic solutions found in the paper:

Click to access 04-LAJPE-782_Chudinov.pdf

The first picture is the main form interface for the program with the parameters initial velocity in meters per second and the initial angle which is in degrees. We use a velocity of 25 meters per second which is approximately 56 miles per hour and the angle is 90 degrees to the horizontal which is throwing the ball straight up into the air.

BB Main Exercise 4.7

First we show the classical ballistics without atmospheric drag:

BB CB Exercise 4.7

Next we show the invalid (due to a singularity in one of the equations) analytic and numeric solutions:

BB AN Exercise 4.7

The analytic solution is not valid for theta0 = 90 degrees. The numeric solution shows a time to apogee of 2.28 seconds and time of flight 4.66 seconds. The difference is 4.66 – 2.28 seconds = 2.38 seconds so the time to return from apogee is greater than the time to reach apogee. The analytic solution becomes valid at 88 degrees of inclination.

BB AN 88 Exercise 4.7

Next we move onto an inclination of 15 degrees:

BB CB 15 Exercise 4.7

BB AN 15 Exercise 4.7

Finally for the maximum distance traveled by the ball classically we select 45 degrees:

BB CB 45 Exercise 4.7

BB AN 45 Exercise 4.7

We find that with drag the maximum distance traveled (range) is achieved around 43 degrees:

BB CB 43 Exercise 4.7

BB AN 43 Exercise 4.7

 

 

Test Implementation of SHA-3 Secure Hash Algorithm 3 by James Pate Williams, Jr. BA, BS, MSwE, PhD

The primary source for this C# implementation was FIPS 202:

Click to access NIST.FIPS.202.pdf

The first test of my implementation consists of the 5 bits 11001 = 16 + 8 + 1 = 25. The output from my test application is given below:

SHA-3 Test

Message Digest SHA3-224
FF BA D5 DA 96 BA D7 17 89 33 02 06 DC 67 68 EC 
AE B1 B3 2D CA 6B 33 01 48 96 74 AB

Message Digest SHA3-256
7B 00 47 CF 5A 45 68 82 36 3C BF 0F B0 53 22 CF 
65 F4 B7 05 9A 46 36 5E 83 01 32 E3 B5 D9 57 AF

Message Digest SHA3-384
73 7C 9B 49 18 85 E9 BF 74 28 E7 92 74 1A 7B F8 
DC A9 65 34 71 C3 E1 48 47 3F 2C 23 6B 6A 0A 64 
55 EB 1D CE 9F 77 9B 4B 6B 23 7F EF 17 1B 1C 64

Message Digest SHA3-512
A1 3E 01 49 41 14 C0 98 00 62 2A 70 28 8C 43 21 
21 CE 70 03 9D 75 3C AD D2 E0 06 E4 D9 61 CB 27 
54 4C 14 81 E5 81 4B DC EB 53 BE 67 33 D5 E0 99 
79 5E 5E 81 91 8A DD B0 58 E2 2A 9F 24 88 3F 37

See the following NIST generated files:

Click to access SHA3-224_Msg5.pdf

Click to access SHA3-256_Msg5.pdf

Click to access SHA3-384_Msg5.pdf

Click to access SHA3-512_Msg5.pdf

New 30-bit test string: 110010100001101011011110100110.

SHA-3 Test 30-Bit

Message Digest SHA3-224
D6 66 A5 14 CC 9D BA 25 AC 1B A6 9E D3 93 04 60 
DE AA C9 85 1B 5F 0B AA B0 07 DF 3B

Message Digest SHA3-256
C8 24 2F EF 40 9E 5A E9 D1 F1 C8 57 AE 4D C6 24 
B9 2B 19 80 9F 62 AA 8C 07 41 1C 54 A0 78 B1 D0

Message Digest SHA3-384
95 5B 4D D1 BE 03 26 1B D7 6F 80 7A 7E FD 43 24 
35 C4 17 36 28 11 B8 A5 0C 56 4E 7E E9 58 5E 1A 
C7 62 6D DE 2F DC 03 0F 87 61 96 EA 26 7F 08 C3

Message Digest SHA3-512
98 34 C0 5A 11 E1 C5 D3 DA 9C 74 0E 1C 10 6D 9E 
59 0A 0E 53 0B 6F 6A AA 78 30 52 5D 07 5C A5 DB 
1B D8 A6 AA 98 1A 28 61 3A C3 34 93 4A 01 82 3C 
D4 5F 45 E4 9B 6D 7E 69 17 F2 F1 67 78 06 7B AB

See Secure Hashing FIPS 202 SHA-3 on the NIST webpage:

https://csrc.nist.gov/projects/cryptographic-standards-and-guidelines/example-values

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

In this first installment of Chapter 9 Hash Functions and Data Integrity of the Handbook, we concentrate on the unkeyed hash functions mentioned in the Chapter which are:

  1. Matyas-Meyer-Oseas Hash 9.41 Algorithm page 341
  2. Davies-Meyer Hash 9.42 Algorithm page 341
  3. Miyaguchi-Preneel Hash 9.43 Algorithm page 341
  4. MDC-2 (DES Based) 9.46 Algorithm page 342
  5. MDC-4 (DES Based) 9.47 Algorithm page 343
  6. MD4 9.49 Algorithm page 346
  7. MD5 9.51 Algorithm page 347
  8. SHA-1 (Secure Hash Algorithm 1) 9.53 Algorithm page 348-349
  9. RIPMD-160 9.55 Algorithm pages 350-351

The first five algorithms are based on the IBM-NIST-NSA encryption algorithm DES (Data Encryption Standard).

Chapter 9 Unkeyed 1

Matyas-Meyer-Oseas DES Hash Function
abcdefghijklmnopqrstuvwxyz
IV = 01ad27b0 75851f2a
H1 = 62af6ffa e32867a0
Zbcdefghijklmnopqrstuvwxyz
IV = 01ad27b0 75851f2a
I1 = 567f7eaf 7420eb6f
number of changed bits by a five bits input change = 27

Davies-Meyer DES Hash Function
abcdefghijklmnopqrstuvwxyz
IV = 464f95ff 30d042d1
H1 = be1c30f4 2f6fc905
Zbcdefghijklmnopqrstuvwxyz
IV = 464f95ff 30d042d1
I1 = e56ec4b7 ffd98172
number of changed bits by a five bits input change = 33

Miyaguchi-Preneel DES Hash Function
abcdefghijklmnopqrstuvwxyz
IV = 164502df 2264bd00
H1 = d866343a 137eee2a
Zbcdefghijklmnopqrstuvwxyz
IV = 164502df 2264bd00
I1 = becbad0e 0ca8fa64
number of changed bits by a five bits input change = 32

Chapter 9 Unkeyed 2

MDC_2 DES Hash Function
abcdefghijklmnopqrstuvwxyz
G0 = a2a9a035 554856b1
G0T = ed24d012 d536f455
Zbcdefghijklmnopqrstuvwxyz
H0 = 5a79b365 970b3216
H0T = 2694dd17 0d93ddb1
number of changed bits by a five bits input change = 55

MDC-4 DES Hash Function
abcdefghijklmnopqrstuvwxyz
IV = 3cd408f2 528789b6
IVT = 0ac7b125 5a8a8729
G0 = 80140bb0 e49cc013
G0T = 80140bb0 e49cc013
Zbcdefghijklmnopqrstuvwxyz
IV = 3cd408f2 528789b6
IVT = 0ac7b125 5a8a8729
H0 = 37d40179 ce50bcc9
H0T = 37d40179 ce50bcc9
number of changed bits by a five bits input change = 62

Chapter 9 MD4

MD4

0x31d6cfe0 
0xd16ae931 
0xb73c59d7 
0xe0c089c0

a
0xbde52cb3 
0x1de33e46 
0x245e05fb 
0xdbd6fb24

abc
0xa448017a 
0xaf21d852 
0x5fc10ae8 
0x7aa6729d

abcdefghijklmnopqrstuvwxyz
0xd79e1c30 
0x8aa5bbcd 
0xeea8ed63 
0xdf412da9

Chapter 9 MD5

MD5

0xd41d8cd9 
0x8f00b204 
0xe9800998 
0xecf8427e

a
0x0cc175b9 
0xc0f1b6a8 
0x31c399e2 
0x69772661

abc
0x90015098 
0x3cd24fb0 
0xd6963f7d 
0x28e17f72

abcdefghijklmnopqrstuvwxyz
0xc3fcd3d7 
0x6192e400 
0x7dfb496c 
0xca67e13b

Chapter 9 SHA

SHA-1

0xda39a3ee 
0x5e6b4b0d 
0x3255bfef 
0x95601890 
0xafd80709

a
0x86f7e437 
0xfaa5a7fc 
0xe15d1ddc 
0xb9eaeaea 
0x377667b8

abc
0xa9993e36 
0x4706816a 
0xba3e2571 
0x7850c26c 
0x9cd0d89d

abcdefghijklmnopqrstuvwxyz
0x32d10c7b 
0x8cf96570 
0xca04ce37 
0xf2a19d84 
0x240d3a89

Chapter 9 RIPEMD

RIPEMD-160

0x9c1185a5 
0xc5e9fc54 
0x61280897 
0x7ee8f548 
0xb2258d31

a
0x0bdc9d2d 
0x256b3ee9 
0xdaae347b 
0xe6f4dc83 
0x5a467ffe

abc
0x8eb208f7 
0xe05d987a 
0x9b044a8e 
0x98c6b087 
0xf15a0bfc

abcdefghijklmnopqrstuvwxyz
0xf71c2710 
0x9c692c1b 
0x56bbdceb 
0x5b9d2865 
0xb3708dbc

Test vectors for MD4, MD5, SHA-1, and RIPEMD-160 can be found in Table 9.6 of the Handbook on page 345.