15,498,398 members
Articles / Programming Languages / C#
Article
Posted 5 Mar 2010

252K views
191 bookmarked

# Classical Encryption Techniques

Rate me:
Implementation of famous Ciphering algorithms

## 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 recognized  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)

C#
```namespace EncryptionAlgorithms
{
using System;
using System.Collections.Generic;
using System.Linq;
using System.ComponentModel.Composition;

public class Ceaser : SecurityAlgorithm
{

#region Constructor

public Ceaser(int key)
{
this.key = key;
}

#endregion

#region Public Methods

public override string Encrypt(string plainText)
{
return Process(plainText, Mode.Encrypt);
}

public override string Decrypt(string cipher)
{
return Process(cipher, Mode.Decrypt);
}

#endregion

#region Private Methods

private string Process(string message, Mode mode)
{
string result = string.Empty;

foreach (char c in message)
{
var charposition = alphabet[c];
var res = Common.GetAlphabetPosition(charposition, key, mode);
result += alphabet.Keys.ElementAt(res % 26);
}

return result;
}

#endregion
}
}		```

#### 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. Example:

Key:

Plain text: ifwewishtoreplaceletters

Cipher text: WIRFRWAJUHYFTSDVFSFUUFYA

#### Cryptanalysis

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:

C#
```namespace EncryptionAlgorithms
{
using System;
using System.Collections.Generic;
using System.Linq;

public class Monoalphabetic : SecurityAlgorithm
{

public Monoalphabetic()
{
_alphabetShuffledReverse = new Dictionary<char, char>();
_alphabetShuffled = new Dictionary<char, char>();
ShuffleAlphabet();
}

#region Public Methods

public override string Encrypt(string plainText)
{
return Process(plainText, Mode.Encrypt);
}

public override string Decrypt(string cipherText)
{
return Process(cipherText, Mode.Decrypt);
}

#endregion

#region Private Methods

private string Process(string token, Mode mode)
{
string result = "";

for (int i = 0; i < token.Length; i++)
{
switch (mode)
{
case Mode.Encrypt:
result += _alphabetShuffled[token[i]];
break;
case Mode.Decrypt:
result += _alphabetShuffledReverse[token[i]];
break;
}
}

return result;
}

private void ShuffleAlphabet()
{
Random r = new Random(DateTime.Now.Millisecond);
var alphabetCopy = alphabet.Keys.ToList();

foreach (var character in alphabet.Keys)
{
int characterPosition = r.Next(0, alphabetCopy.Count);
char randomCharacter = alphabetCopy[characterPosition];
alphabetCopy.RemoveAt(characterPosition);
}
}

#endregion
}
}```

### 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:

 P L A Y F I R E X M B C D G H K N O Q S T U V W Z

• Plaintext encrypted two letters at a time
• If a pair is a repeated letter, insert a filler like 'X', ex: “Communication" encrypts as “Com x munication"
• If the letters appear on the same row of your table, replace them with the letters to their immediate right respectively (wrapping around to the left side of the row if a letter in the original pair was on the right side of the row).

XM becomes MI

• If the letters appear on the same column of your table, replace them with the letters immediately below respectively (again wrapping around to the top side of the column if a letter in the original pair was on the bottom side of the column).

NU becomes UL

• If the letters are not on the same row or column, replace them with the letters on the same row respectively but at the other pair of corners of the rectangle defined by the original pair. The order is important – the first letter of the encrypted pair is the one that lies on the same row as the first letter of the plaintext pair.
TH becomes  ZB
• To decrypt, use the INVERSE (opposite) of the last 3 rules, and the 1st as is (dropping any extra "X"s that don't make sense in the final message when you finish).

Encrypting the message "Hide the gold in the tree stump":

Cipher Text: BM OD ZB XD NA BE KU DM UI XM MO UV IF

• The Playfair cipher is a great advance over simple monoalphabetic ciphers, due to:
• The identification of digrams is more difficult than individual letters:

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.

• The relative frequencies of individual letters exhibit a much greater range than that of digrams, making frequency analysis much more difficult.
C#
```namespace EncryptionAlgorithms
{
using System.Collections.Generic;
using System.Linq;
using System.ComponentModel.Composition;

public class PlayFair : SecurityAlgorithm
{
string key;

public PlayFair(string key)
{
this.key = key;
}

#region Public Methods

public override string Encrypt(string plainText)
{
return Process(plainText, Mode.Encrypt);
}

public override string Decrypt(string cipherText)
{
return Process(cipherText, Mode.Decrypt);
}

#endregion

#region Private Methods

private string Process(string message, Mode mode)
{
//Key:Charcater
//Value:Position
Dictionary<char, string> characterPositionsInMatrix = new Dictionary<char, string>();

//Key:Position
//Value:Charcater
Dictionary<string, char> positionCharacterInMatrix = new Dictionary<string, char>();

FillMatrix(key.Distinct().ToArray(), characterPositionsInMatrix, positionCharacterInMatrix);

if (mode == Mode.Encrypt)
{
message = RepairWord(message);
}

string result = "";

for (int i = 0; i < message.Length; i += 2)
{
string substring_of_2 = message.Substring(i, 2);//get characters from text by pairs
//get Row & Column of each character
string rc1 = characterPositionsInMatrix[substring_of_2[0]];
string rc2 = characterPositionsInMatrix[substring_of_2[1]];

if (rc1[0] == rc2[0])//Same Row, different Column
{
int newC1 = 0, newC2 = 0;

switch (mode)
{
case Mode.Encrypt://Increment Columns
newC1 = (int.Parse(rc1[1].ToString()) + 1) % 5;
newC2 = (int.Parse(rc2[1].ToString()) + 1) % 5;
break;
case Mode.Decrypt://Decrement Columns
newC1 = (int.Parse(rc1[1].ToString()) - 1) % 5;
newC2 = (int.Parse(rc2[1].ToString()) - 1) % 5;
break;
}

newC1 = RepairNegative(newC1);
newC2 = RepairNegative(newC2);

result += positionCharacterInMatrix[rc1[0].ToString() + newC1.ToString()];
result += positionCharacterInMatrix[rc2[0].ToString() + newC2.ToString()];
}

else if (rc1[1] == rc2[1])//Same Column, different Row
{
int newR1 = 0, newR2 = 0;

switch (mode)
{
case Mode.Encrypt://Increment Rows
newR1 = (int.Parse(rc1[0].ToString()) + 1) % 5;
newR2 = (int.Parse(rc2[0].ToString()) + 1) % 5;
break;
case Mode.Decrypt://Decrement Rows
newR1 = (int.Parse(rc1[0].ToString()) - 1) % 5;
newR2 = (int.Parse(rc2[0].ToString()) - 1) % 5;
break;
}
newR1 = RepairNegative(newR1);
newR2 = RepairNegative(newR2);

result += positionCharacterInMatrix[newR1.ToString() + rc1[1].ToString()];
result += positionCharacterInMatrix[newR2.ToString() + rc2[1].ToString()];
}

else//different Row & Column
{
//1st character:row of 1st + col of 2nd
//2nd character:row of 2nd + col of 1st
result += positionCharacterInMatrix[rc1[0].ToString() + rc2[1].ToString()];
result += positionCharacterInMatrix[rc2[0].ToString() + rc1[1].ToString()];
}
}

return result;
}

private string RepairWord(string message)
{
string trimmed = message.Replace(" ", "");
string result = "";

for (int i = 0; i < trimmed.Length; i++)
{
result += trimmed[i];

if (i < trimmed.Length - 1 && message[i] == message[i + 1])
//check if two consecutive letters are the same
{
result += 'x';
}
}

if (result.Length % 2 != 0)//check if length is even
{
result += 'x';
}

return result;
}

private void FillMatrix(IList<char> key,  Dictionary<char, string>
characterPositionsInMatrix,  Dictionary<string, char> positionCharacterInMatrix)
{
char[,] matrix = new char[5, 5];
int keyPosition = 0, charPosition = 0;
List<char> alphabetPF = alphabet.Keys.ToList();
alphabetPF.Remove('j');

for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
if (charPosition < key.Count)
{
matrix[i, j] = key[charPosition];//fill matrix with key
alphabetPF.Remove(key[charPosition]);
charPosition++;
}

else//key finished...fill with rest of alphabet
{
matrix[i, j] = alphabetPF[keyPosition];
keyPosition++;
}

string position = i.ToString() + j.ToString();
//store character positions in dictionary to avoid searching everytime
}
}
}

private int RepairNegative(int number)
{
if (number < 0)
{
number += 5;
}

return number;
}

#endregion
}
}		 ```

### 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 = EK (P) = KP mod 26

P = DK (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

C#
```namespace EncryptionAlgorithms
{
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.ComponentModel.Composition;

public class Hill : SecurityAlgorithm
{

public Hill(int[,] matrix)
{
key = matrix;
}

#region Public Methods

public override string Encrypt(string plainText)
{
return Process(plainText, Mode.Encrypt);
}

public override string Decrypt(string cipher)
{
return Process(cipher, Mode.Decrypt);
}

#endregion

#region Private Methods

private string Process(string message, Mode mode)
{
MatrixClass matrix = new MatrixClass(key);

if (mode == Mode.Decrypt)
{
matrix = matrix.Inverse();
}

int pos = 0, charPosition;
string substring, result = "";
int matrixSize = key.GetLength(0);

while (pos < message.Length)
{
substring = message.Substring(pos, matrixSize);
pos += matrixSize;

for (int i = 0; i < matrixSize; i++)
{
charPosition = 0;

for (int j = 0; j < matrixSize; j++)
{
charPosition += (int)matrix[j, i].Numerator * alphabet[substring[j]];
}

result += alphabet.Keys.ElementAt(charPosition % 26);
}
}

return result;
}

#endregion
}
}	  ```

### 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.

This 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

C#
```namespace EncryptionAlgorithms
{
using System;
using System.ComponentModel.Composition;

public class RailFence : SecurityAlgorithm
{

public RailFence(int key)
{
this.key = key;
}

#region Public Methods

public override string Encrypt(string plainText)
{
return Process(plainText, Mode.Encrypt);
}

public override string Decrypt(string cipherText)
{
return Process(cipherText, Mode.Decrypt);
}

#endregion

#region Private Methods

private string Process(string message, Mode mode)
{
int rows = key;
int columns = (int)Math.Ceiling((double)message.Length / (double)rows);
char[,] matrix = FillArray(message, rows, columns, mode);
string result = "";

foreach (char c in matrix)
{
result += c;
}

return result;
}

private char[,] FillArray(string message, int rowsCount, int columnsCount, Mode mode)
{
int charPosition = 0;
int length = 0, width = 0;
char[,] matrix = new char[rowsCount, columnsCount];

switch (mode)
{
case Mode.Encrypt:
length = rowsCount;
width = columnsCount;
break;
case Mode.Decrypt:
matrix = new char[columnsCount, rowsCount];
width = rowsCount;
length = columnsCount;
break;
}

for (int i = 0; i < width; i++)
{
for (int j = 0; j < length; j++)
{
if (charPosition < message.Length)
{
matrix[j, i] = message[charPosition];
}
else
{
matrix[j, i] = '*';
}

charPosition++;
}
}

return matrix;
}

#endregion
}
}```

### 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.

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

 4 3 1 2 5 6 7 a t t a c k p o s t p o n e d u n t i l t w o a m * * *

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

C#
```namespace EncryptionAlgorithms
{
using System;
using System.Collections.Generic;

public class RowTransposition : SecurityAlgorithm
{

public RowTransposition(int[] key)
{
this.key = key;
}

#region Public Methods

public override string Encrypt(string plainText)
{
int columns = 0, rows = 0;
Dictionary<int, int> rowsPositions = FillPositionsDictionary(plainText, ref columns, ref rows);
char[,] matrix2 = new char[rows, columns];

//Fill Matrix
int charPosition = 0;
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < columns; j++)
{
if (charPosition < plainText.Length)
{
matrix2[i, j] = plainText[charPosition];
}
else
{
matrix2[i, j] = '*';
}

charPosition++;
}
}

string result = "";

for (int i = 0; i < columns; i++)
{
for (int j = 0; j < rows; j++)
{
result += matrix2[j, rowsPositions[i + 1]];
}

result += " ";
}

return result;
}

public override string Decrypt(string cipherText)
{
int columns = 0, rows = 0;
Dictionary<int, int> rowsPositions = FillPositionsDictionary(cipherText, ref columns, ref rows);
char[,] matrix = new char[rows, columns];

//Fill Matrix
int charPosition = 0;
for (int i = 0; i < columns; i++)
{
for (int j = 0; j < rows; j++)
{
matrix[j, rowsPositions[i + 1]] = cipherText[charPosition];
charPosition++;
}
}

string result = "";

foreach (char c in matrix)
{
if (c != '*' && c != ' ')
{
result += c;
}
}

return result;
}

#endregion

#region Private Methods

private Dictionary<int, int> FillPositionsDictionary(string token, ref int columns, ref int rows)
{
var result = new Dictionary<int, int>();
columns = key.Length;
rows = (int)Math.Ceiling((double)token.Length / (double)columns);
/*  we need something to tell where to start
*        4  3  1  2  5  6  7               Key
*
*        0  1  2  3  4  5  6               Value
*/
//attack postponed until two am xyz
for (int i = 0; i < columns; i++)
{
}

return result;
}

#endregion
}
}```

### 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

Written By
Software Developer
Egypt
Enthusiastic programmer/researcher, passionate to learn new technologies, interested in problem solving, data structures, algorithms, AI, machine learning and nlp.

Amateur guitarist/ keyboardist, squash player.

 First PrevNext
 how to run this Member 1358277913-Jun-20 4:40 Member 13582779 13-Jun-20 4:40
 My vote of 5 Frank R. Haugen27-Aug-15 4:28 Frank R. Haugen 27-Aug-15 4:28
 need approval to use your source code Komal Dhobe4-Jan-15 7:03 Komal Dhobe 4-Jan-15 7:03
 Re: need approval to use your source code Omar Gameel Salem6-Jan-15 19:07 Omar Gameel Salem 6-Jan-15 19:07
 Ukraine Member 112189829-Nov-14 5:28 Member 11218982 9-Nov-14 5:28
 Re: Ukraine Omar Gameel Salem13-Nov-14 15:51 Omar Gameel Salem 13-Nov-14 15:51
 Need fixed length encrypted string output algorithm in c# ? Manivignesh20-May-14 2:33 Manivignesh 20-May-14 2:33
 can't run source code thyanx2-Apr-14 10:00 thyanx 2-Apr-14 10:00
 Doubt Member 1046890823-Dec-13 18:00 Member 10468908 23-Dec-13 18:00
 Re: Doubt Yvan Rodrigues19-Jan-14 6:24 Yvan Rodrigues 19-Jan-14 6:24
 Re: Doubt Member 1199799420-Sep-15 9:26 Member 11997994 20-Sep-15 9:26
 My vote of 5 SagarRS12-Jun-13 21:31 SagarRS 12-Jun-13 21:31
 My vote of 5 StianSandberg21-Apr-13 22:51 StianSandberg 21-Apr-13 22:51
 My vote of 5 Sudhakar Shinde19-Mar-13 23:02 Sudhakar Shinde 19-Mar-13 23:02
 Examples with explanation of Advance Encryption and Data encryption and Decryption..Reg, Master Blaster13-Dec-12 20:18 Master Blaster 13-Dec-12 20:18
 Javascript version? Karakaya9-Dec-12 3:03 Karakaya 9-Dec-12 3:03
 Re: Javascript version? Omar Gameel Salem9-Dec-12 3:13 Omar Gameel Salem 9-Dec-12 3:13
 My vote of 5 Monjurul Habib2-Dec-12 10:55 Monjurul Habib 2-Dec-12 10:55
 Excellent Zaf Khan1-Dec-12 16:09 Zaf Khan 1-Dec-12 16:09