Simple Cryptographer - Simple DES/AES Implementation in C#

Download SimpleCryptographer.zip - 147.3 KB

Introduction

It's Simple DES/AES Enctypt and Decrypt Program that using string data type. If it helps someone need to get some practical source code, it'll be my honor.

Caution : I'm not good at writing in English, so be careful on some inappropriate sentences. Thanks you. hahaha.

Background

Background? Understanding about C#2.0 and string data type and ,of course, Cryptography.

I got so many(???) complain about tell-you-nothing post.:)
So I will describe some implementation of The Simple Cryptographer.

But it's too stupid that reinvent the wheel, so I recommend read some good articles about DES and AES.

I read these articles when I implement The Simple Cryptographer.

DES : The DES Algorithm Illustrated by J. Orlin Grabbe

AES : rijndael - Encryption Process Flash Animation by Enrique Zabala and CONXX

And "Cryptography and Network Security, 4th edition, William Stallings", it's very good.:),

How DES works in SimpleCryptographer

First, All the permutation tables in DES and the S-BOXes are declared like this,

public static readonly int[] pc_1 ={ 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 
                                          42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 
                                          27, 19, 11, 3, 60, 52, 44, 36, 63, 55, 
                                          47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 
                                          30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 
                                          13, 5, 28, 20, 12, 4 };
public static readonly int[,] s1 ={ { 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9,
                                           0, 7 }, 
                                         { 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9,
                                           5, 3, 8 }, 
                                         { 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3,
                                           10, 5, 0 }, 
                                         { 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10,
                                           0, 6, 13 } };

All the other methods in the ProcessDES class except EncryptionStart, DecryptionStart, DoPermutation, SetAllKeys, FinalEncription, f, P, sBox_Transform, E_Selection are just helper method, so just focus on DES-process.

And it starts with make 16-sub keys.

string hex_key = this.FromTextToHex(key);
string binary_key = this.FromHexToBinary(hex_key);
string key_plus = this.DoPermutation(binary_key, DESData.pc_1);
string C0 = "", D0 = "";
C0 = this.SetLeftHalvesKey(key_plus);
D0 = this.SetRightHalvesKey(key_plus);
Keys keys = this.SetAllKeys(C0, D0);

The key input is hexa decimal, so convert it to binary decimal for bit permutations and transformations.

And permutate the key by permutation table PC-1, and split this key into left and right halves, C0 and D0.

And make 16 sub-keys.

        public Keys SetAllKeys(string C0, string D0)
        {
            Keys keys = new Keys();
            keys.Cn[0] = C0;
            keys.Dn[0] = D0;
            for (int i = 1; i < keys.Cn.Length; i++)
            {
                keys.Cn[i] = this.LeftShift(keys.Cn[i - 1], DESData.nrOfShifts[i]);
                keys.Dn[i] = this.LeftShift(keys.Dn[i - 1], DESData.nrOfShifts[i]);
                keys.Kn[i - 1] = this.DoPermutation(keys.Cn[i] + keys.Dn[i], 
                    DESData.pc_2);
            }          
            return keys;
        }

It's just implementation of create 16-subkeys in DES.

Please reference good explanation in linked DES article above.

And now, encrypt data block process.

binaryText = this.setTextMutipleOf64Bits(binaryText);
StringBuilder EncryptedTextBuilder = new StringBuilder(binaryText.Length);
for (int i = 0; i < (binaryText.Length / 64); i++)
{
    string PermutatedText = this.DoPermutation(binaryText.Substring(i * 64, 64),
        DESData.ip);
    string L0 = "", R0 = "";
    L0 = this.SetLeftHalvesKey(PermutatedText);
    R0 = this.SetRightHalvesKey(PermutatedText);
    string FinalText = this.FinalEncription(L0, R0, keys, false);
    EncryptedTextBuilder.Append(FinalText);
}

First, set the total data size to multiple of 64bit.

Because, DES is block cipher that encrypt 64bit data block at once.

I use StringBuilder for reduce string garbage, but I think string is not good choice for performance but good for implementation.(easy:))

public string FinalEncription(string L0, string R0, Keys keys, bool IsReverse)
        {
            string Ln = "", Rn = "", Ln_1 = L0, Rn_1 = R0;
            int i = 0;
            if (IsReverse == true)
            {
                i = 15;
            }
            while (this.IsEnough(i, IsReverse))
            {
                Ln = Rn_1;
                Rn = this.XOR(Ln_1, this.f(Rn_1, keys.Kn[i]));
                //Next Step of L1, R1 is L2 = R1, R2 = L1 + f(R1, K2), hence,

                //value of Step1's Ln, Rn is Rn_1, Ln_1 in Step2.

                Ln_1 = Ln;
                Rn_1 = Rn;
                if (IsReverse == false)
                {
                    i += 1;
                }
                else
                {
                    i -= 1;
                }
            }
            string R16L16 = Rn + Ln;
            string Encripted_Text = this.DoPermutation(R16L16, DESData.ip_1);
            return Encripted_Text;
        }

It's final process of encryption.

The "IsReverse" flag is for using same method for encryption and decryption.

How AES works in SimpleCryptographer

It's hard to describe AES in detail for me.

But I think flash animation that i linked above will be a great help.:)

So I describe basic building blocks of the Simple Cryptographer.

In AES, it use matrix-like data structure, state, so I designed matrix-like class.

class Matrix
    {
        #region Private Fields
        private string[,] matrix;
        private int rows = 0;
        private int columns = 0;
        #endregion
        #region Constructor        
        public Matrix(int rows, int columns)
            : this("", rows, columns)
        {
        }
        public Matrix(string text)
            : this(text, 4, 4)
        {
        }
        public Matrix(string text, int rows, int columns)
        {
            if (text.Length != columns * rows * 8)
            {
                text = text.PadRight(columns * rows * 8 - text.Length, '0');
            }
            matrix = new string[rows, columns];
            int count = 0;
            this.rows = rows;
            this.columns = columns;
            for (int i = 0; i < columns; i++)
            {
                for (int j = 0; j < rows; j++)
                {
                    matrix[j, i] = text.Substring(count * 8, 8);
                    count++;
                }
            }
        }
        #endregion
        #region Properties, Indexer
        public int Rows
        {
            get
            {
                return rows;
            }
        }
        public int Columns
        {
            get
            {
                return columns;
            }
        }
        public string this[int i, int j]
        {
            get
            {
                return matrix[i, j];
            }
            set
            {
                //If it gets hexa decimal, convert it to binary decimal.

                if (value.Length == 2)
                {
                    matrix[i, j] = BaseTransform.FromHexToBinary(value);
                }
                else if (value.Length == 8)
                {
                    matrix[i, j] = value;
                }
            }
        }
        #endregion
        #region Overrided ToString method
        public override string ToString()
        {
            StringBuilder text = new StringBuilder(128);
            if (matrix != null)
            {
                for (int j = 0; j < columns; j++)
                {
                    for (int i = 0; i < rows; i++)
                    {
                        text.Append(matrix[i, j]);
                    }
                }
            }
            return text.ToString();
        }
        #endregion
        #region one row operation
        public string[] getRow(int rowindex)
        {
            string[] row = new string[this.columns];
            if (rowindex > this.rows)
            {
                throw new IndexOutOfRangeException("It's out of index.");
            }
            for (int i = 0; i < this.columns; i++)
            {
                row[i] = matrix[rowindex, i];
            }
            return row;
        }
        public void setRow(string[] row, int rowindex)
        {
            if (rowindex > this.rows)
            {
                throw new IndexOutOfRangeException("It's out of index.");
            }
            for (int i = 0; i < this.columns; i++)
            {
                matrix[rowindex, i] = row[i]; 
            }
        }
        #endregion
        #region one column operation
        public string[] getWord(int wordindex)
        {
            string[] word = new string[this.rows];
            if (wordindex > this.rows)
            {
                throw new IndexOutOfRangeException("It's out of index.");
            }
            for (int i = 0; i < this.rows; i++)
            {
                word[i] = matrix[i, wordindex];
            }
            return word;
        }
        public void setWord(string[] word, int wordindex)
        {
            if (wordindex > this.rows)
            {
                throw new IndexOutOfRangeException("It's out of index.");
            }
            for (int i = 0; i < this.rows; i++)
            {
                matrix[i, wordindex] = word[i];
            }
        }
        #endregion
    }

It's implemented one row calculation, one column(one word in AES) calculation and indexer and I use it all of code in AES implemention like the code below.

public static Matrix XOR(Matrix a, Matrix b)
        {
            Matrix c = new Matrix(a.Rows, a.Columns);
            for (int i = 0; i < c.Rows; i++)
            {
                for (int j = 0; j < c.Columns; j++)
                {
                    c[i, j] = MultiplicativeInverse.XOR(a[i, j], b[i, j]);
                }
            }
            return c;
        }

And the module that calculate bit as polynomial that has binary coefficient is multiplicativeinverse class. In AES, it uses multiplication on GF(2⁸).

public static string GetInverse(string text1, string text2, string mx, int n)
        {
            string[] multiplyTable = new string[n];
            if (text1.IndexOf('1') > text2.IndexOf('1'))
            {
                string temp = text2;
                text2 = text1;
                text1 = temp;
            }
            multiplyTable[0] = text1;
            for (int i = 1; i < n; i++)
            {
                multiplyTable[i] = MultiplicativeInverse.LeftShift2(multiplyTable[i - 1],
                    n);
                if (multiplyTable[i - 1][text1.Length - n].Equals('1'))
                {
                    multiplyTable[i] = MultiplicativeInverse.XOR(multiplyTable[i], mx);
                }
            }
            string Mul_Inverse = "";
            for (int i = 0; i < text2.Length; i++)
            {
                if (text2[i].Equals('1'))
                {
                    if (Mul_Inverse.Equals(""))
                    {
                        Mul_Inverse = multiplyTable[(text2.Length - 1/*2*/) - i];
                    }
                    else
                    {
                        Mul_Inverse = MultiplicativeInverse.XOR(Mul_Inverse,
                            multiplyTable[(text2.Length - 1/*2*/) - i]);
                    }
                }
            }
            if (Mul_Inverse.Equals(""))
            {
                Mul_Inverse = "00000000";
            }
            return Mul_Inverse;
        }

Mx is reduction modulo, n is greatest degree of a polynomial.

If bit string of 1byte "01000100" convert to polynomial on GF(2⁸), x⁷ + x².

Detail process of AES and calcultate multiplication on GF(2⁸) is better see book or web site.

(recommend wikipedia)

Very Very Very simple elasped time checking(Appended)

DateTime start = DateTime.Now;
this.StartSelectedProcess();
DateTime end = DateTime.Now;
TimeSpan result = end - start;
lblProgress.Text = "Elapsed Time : " + result.ToString();

That's it. :)

Using the code

It has two core classes, ProcessDES, ProcessAES. As you can see, these classes are process encryption and decryption using DES and AES.

These classes are derived from ,abstract class, CommonProcess that has EncryptionStart, DecryptionStart. These methods are common interface for ProcessDES, ProcessAES. If i don't misunderstanded, changing algorithm between DES and AES in this program is implemented by Factory Pattern. Using the common interface CommonProcess.

And other classes are some buliding blocks of DES and AES, transform from text to hexadecimal, hexadecimal to text, to binary , and some core building block like multiplication on GF(2⁸), matrix transformation....etc....

All of these algorithm is implemented by string data. It's bad for many times of transformation because it's immutable. If you change value, original value replaced by new one, and the old one is being garbage. It's reason for using StringBuilder in many times roop like for and while. I minded it while i write program but i don't assure about performance.

Points of Interest

I started learning Cryptography two weeks ago, and i made this program. It really helps me understanding detail implemetation about DES and AES

History

- The progressbar for Encryption and Decryption has appended. (2007/5/3)

- Count elapsed time has appended. (2007/5/8)

- Count detailed elasped time that more than second that just show result time at the end of the process has appended. (2007/5/9)

- Fix bug that it cut some texts out when decryption. (2007/5/10)

- Check a input key whether hexadecimal or not. (2007/5/21)