Classical Encryption Techniques

• Download Code - 207.36 KB
• Download Demo - 63.26 KB

Introduction

Basic Encryption algorithms and their implementation in C# 

Overview

The two basic building blocks of all encryption techniques are:

Substitution      

•          Letters of plain text are replaced by other letters or by numbers or symbols

•          If the plain text is viewed as a sequence of bits, then substitution involves replacing plain text bit patterns with cipher text bit patterns

Transposition/Permutation 

•          The letters/bytes/bits of the plaintext are rearranged without altering the actual letters used

•          can be easily recognised  since the ciphertext have the same frequency distribution as the original plain text. 

Substitution Algorithms

Caesar Cipher  

Earliest known substitution cipher by Julius Caesar

It involves replacing  each letter in the plaintext by a shifted letter in the alphabet used.

Example: If the shift value is (3) then we can define transformation as: 

so the message "meet me after the toga party" becomes:  

PHHW PH DIWHU WKH WRJD SDUWB

Mathematical Model 

mathematically give each letter a number:   

then the Caesar cipher  is expressed as:

C = E(p) = (p + k) mod (26)

     p = D(C) = (C – k) mod (26)     

private string Ceaser(string strText, Mode mode)
        {
            int nKey = Convert.ToInt32(nm_Key.Value);
            int nchar_position, nRes;
            string strReturn = "";
            for (int i = 0; i < strText.Length; i++)
            {
                nchar_position = m_DicAlphabetSorted[strText[i]];
                nRes = GetAlphabetPosition(nchar_position, nKey, mode);
                strReturn += m_DicAlphabetSorted.Keys.ElementAt(nRes % 26);
            }
            return strReturn;
        }
		

Cryptanalysis 

Can try each of the keys (shifts) in turn, until we recognize the original message,   Therefore using a Brute Force Attack we can have only 26 trials !! 

Example:  

breaking cipher text "GCUA VQ DTGCM” is: “ easy to break", with a shift of 2  

Mono-alphabetic Cipher 

Each plaintext letter maps to a different random cipher text letter ,  Hence the key size is 26 letters long   

Plain text: ifwewishtoreplaceletters

Cipher text: WIRFRWAJUHYFTSDVFSFUUFYA

Now the Brute Force attack to this cipher requires exhaustive search of a total of 26! = 4 x 1026 keys, but the cryptanalysis makes use of the language characteristics, the Letter that is commonly used in English is the letter e , then T,R,N,I,O,A,S other letters are fairly rare Z,J,K,Q,X There are tables of single, double & triple letter frequencies:

for (int i = 0; i < strPlainText.Length; i++)
                    {
                        nchar_position = m_DicAlphabetSorted[strPlainText[i]];
                        strCypher += m_DicAlphabetRandom[nchar_position];
                    }
		

Playfair Cipher  

One approach to improving security was to encrypt multiple letters, Playfair Key Matrix: A 5X5 matrix of letters based on a keyword Fill in letters of keyword (sans duplicates),  Fill rest of matrix with other letters.

Example: Using "playfair example" as the key, the table becomes:

XM becomes MI 

 NU becomes UL 

TH becomes  ZB 

i) In the Monoalphabetic cipher, the attacker searches in 26 letters only.

ii) But using the Playfair cipher, the attacker is searching in 26 x 26 = 676 digrams.

Hill Cipher 

Each letter is first encoded as a number. Often the simplest scheme is used: A = 0, B =1, ..., Z=25, but this is not an essential feature of the cipher. The encryption takes m successive plaintext letter and substitutes them for m ciphertext letters. In case m = 3 , the encryption can be expressed in terms of the matrix multiplication as follows:

Mathematical Model: 

C = E_K (P) = KP mod 26

P = D_K (C ) = K^-1 C mod 26 = K^-1 KP = P
K is the key matrix and K^-1 is the matrix inverse.
The inverse matrix can be calculated as K.K^-1 = I where I is the identity matrix. 

Encryption example: Plaintext: “paymoremoney”

Key:

Cipher text :LNSHDLEWMTRW 

Decryption example 

For decryption use the inverse key matrix P = C mod 26

private string Hill(string strText, Mode mode)
        {
            MatrixClass m = new MatrixClass(m_frmMatrix.m_arrMatrix);
            if (mode == Mode.Decrypt)
                m = m.Inverse();
            int npos = 0, nchar_position;
            string strSubstring, strReturn = "";
            while (npos < strText.Length)
            {
                strSubstring = strText.Substring(npos, (int)nm_Key.Value);
                npos += (int)nm_Key.Value;

                for (int i = 0; i < nm_Key.Value; i++)
                {
                    nchar_position = 0;
                    for (int j = 0; j < nm_Key.Value; j++)
                    {
                        nchar_position += (int)m[j, i].Numerator * m_DicAlphabetSorted[strSubstring[j]];
                    }
                    strReturn += m_DicAlphabetSorted.Keys.ElementAt(nchar_position % 26);
                }
            }
            return strReturn;
        }
		  

Polyalphabetic Ciphers 

Another approach to improving security is to use multiple cipher alphabets Called polyalphabetic substitution ciphers. Makes cryptanalysis harder with more alphabets to guess and flatter frequency distribution.

Use a key to select which alphabet is used for each letter of the message.

Example: the Vigenère Cipher: 

1. Write the plain text 
2. Write the keyword repeated below it 
3. Use each key letter as a caesar cipher key
4. Encrypt the corresponding plaintext letter.

Decryption works in the opposite way

Cryptanalysis:

The problem in repeating the key so frequently, is that there might be repetitions in the ciphertext. This helps in the cryptanalysis process as it gives a clue on the key period.

Ideally we want a key as long as the message, this is done in  Autokey Cipher.

Autokey Cipher  

Vigenère proposed the autokey cipher to strengthen his cipher system. With keyword is prefixed to message as key But still have frequency characteristics to attack.

key: deceptivewearediscoveredsav

plaintext: wearediscoveredsaveyourself 

ciphertext: ZICVTWQNGKZEIIGASXSTSLVVWLA 

notice how we completed the key with characters from plain text. 

One-Time Pad 

is a system that uses a truly random key as long as the message in the decryption and encryption processes. It is unbreakable since ciphertext bears no statistical relationship to the plaintext since for any plaintext & any ciphertext there exists a key mapping one to other.

This system is practically infeasible since its impractical to generate large quantities of random keys. The key distribution and protection is a big problem in this case. 

Transposition Ciphers   

Rail Fence cipher  

Write the message letters out diagonally over a number of rows then read off cipher row by row. 

Example: Encrypting the following message using rail fence of depth 2:

“Meet me after the Graduation party” 

Write message out as: 

m e m a t r h g a u t o p r y

e t e f e t e r d a i n a t 

Cipher text: MEMATRHGAUTOPRY ETEFETERDAINAT 

private string RailFence(string strText, Mode mode)
        {
            int nRows = Convert.ToInt32(nm_Key.Value);
            int nColumns = (int)Math.Ceiling((double)strText.Length / (double)nRows);
            char[,] arrResult = FillArray(strText, nRows, nColumns, mode);
            string strReturn = "";
            foreach (char c in arrResult)
            {
                strReturn += c;
            }
            return strReturn;
        } 

Row Transposition  

A more complex scheme. Write letters of message out in rows over a specified number of columns. Then reorder the columns according to some key before reading off the rows.

Ex:using key 4,3,1,2,5,6,7  and plain text "attack postponed until two am" 

cipher text:  TTNA APTM TSUO AODW COI* KNL* PET* 

int nColumns = 0, nRows = 0;
                        Dictionary<int,> dicRows_Positions = FillPositionsDictionary(strPlainText.Length, ref nColumns, ref nRows);
                        char[,] Matrix_2 = new char[nRows, nColumns];

                        //Fill Matrix
                        for (int i = 0; i < nRows; i++)
                        {
                            for (int j = 0; j < nColumns; j++)
                            {
                                if (nchar_position < strPlainText.Length)
                                    Matrix_2[i, j] = strPlainText[nchar_position];
                                else
                                    Matrix_2[i, j] = '*';
                                nchar_position++;
                            }
                        }

                        for (int i = 0; i < nColumns; i++)
                        {
                            for (int j = 0; j < nRows; j++)
                            {
                                strCypher += Matrix_2[j, dicRows_Positions[i + 1]];
                            }
                            strCypher += " ";
                        }</int,>

Product Ciphers  

Ciphers using substitutions or transpositions are not secure because of language characteristics. Hence consider using several ciphers in succession to make cryptanalysis harder, two substitutions make a more complex substitution,  two transpositions make more complex transposition but a substitution followed by a transposition makes a new much harder cipher. 

This is a bridge from classical to modern ciphers 

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)