Classical Encryption Techniques
4.80/5 (91 votes)
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)
namespace EncryptionAlgorithms
{
using System;
using System.Collections.Generic;
using System.Linq;
using System.ComponentModel.Composition;
public class Ceaser : SecurityAlgorithm
{
readonly int key;
#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:
namespace EncryptionAlgorithms
{
using System;
using System.Collections.Generic;
using System.Linq;
public class Monoalphabetic : SecurityAlgorithm
{
readonly Dictionary<char, char> _alphabetShuffled;
readonly Dictionary<char, char> _alphabetShuffledReverse;
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];
_alphabetShuffled.Add(character, randomCharacter);
_alphabetShuffledReverse.Add(randomCharacter, character);
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.
-
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).
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.
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
characterPositionsInMatrix.Add(matrix[i, j], position);
positionCharacterInMatrix.Add(position, matrix[i, j]);
}
}
}
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
namespace EncryptionAlgorithms
{
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.ComponentModel.Composition;
public class Hill : SecurityAlgorithm
{
readonly int[,] key;
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:
- Write the plain text
- Write the keyword repeated below it
- Use each key letter as a Caesar cipher key
- 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
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
namespace EncryptionAlgorithms
{
using System;
using System.ComponentModel.Composition;
public class RailFence : SecurityAlgorithm
{
readonly int key;
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*
namespace EncryptionAlgorithms
{
using System;
using System.Collections.Generic;
public class RowTransposition : SecurityAlgorithm
{
readonly int[] key;
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++)
{
result.Add(key[i], 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