- Introduction
- An Overview of Common Cryptosystems
- Data Encryption Standard
- Advanced Encryption Standard
- Enciphering
- SubBytes()
- ShiftRows()
- MixColumns()
- AddRoundKey()

- Deciphering
- Generating Keys

- References & External Links
- History

Cryptology is a field that deals with providing security and privacy. This field includes many cryptosystems, each one consisting of a set of algorithms that aims to provide data security. Nowadays, cryptosystems are widely used in all areas of digital technology. Digital signatures, electronic mails, and internet banking are just a few applications that cryptosystems are used in. This work briefly explains the common cryptosystems, and details the two most popular private-key ciphers: DES ,which is probably the most widely used, and AES, which is intended to replace DES. Now, let's begin with an overview of the common cryptosystems.

Three cryptosystems are the base of many security applications: symmetric cryptosystems, asymmetric cryptosystems, and hashing.

Symmetric cryptosystems use the same key in both the encryption and decryption operations. These two operations are usually similar. However, some parts of these operations follow the reverse order of each other (e.g., for AES, the decryption algorithm follows the reverse order of the encryption algorithm, with a little modification on some other methods).

Symmetric cryptosystems divide data into small blocks and encrypt them one by one using a secret key. Then, the blocks are combined and sent to the recipient as a whole. At the recipient side, the decryption operation is applied using the same key, which yields the restored data.

Symmetric algorithms are extremely fast compared to asymmetric cipher algorithms, and are well suited for performing cryptographic transformations on large streams of data. The most popular symmetric cipher algorithms are DES, AES, and TripleDES. TripleDES uses DES three times in a sequence with different keys. DES and AES will be covered in detail later.

Block diagram of symmetric cryptosystems

Plain text is encrypted with the private key, transmitted, then decrypted with the same private key.

private void buttonEncrypt_Click(object sender, EventArgs e)
{
string password = textBoxKey.Text;
string salt = textBoxSalt.Text;
string plainText = textBoxInput.Text;
byte[]plainBytes=Encoding.ASCII.GetBytes(plainText);
Rfc2898DeriveBytes rfc = new Rfc2898DeriveBytes(password,
Encoding.ASCII.GetBytes(salt));
SymmetricAlgorithm Alg = GetSelectedAlgorithm();
Alg.Key = rfc.GetBytes(Alg.KeySize / 8);
Alg.IV = rfc.GetBytes(Alg.BlockSize / 8);
MemoryStream strCiphered = new MemoryStream();
CryptoStream strCrypto = new CryptoStream(strCiphered,
Alg.CreateEncryptor(), CryptoStreamMode.Write);
strCrypto.Write(plainBytes, 0, plainBytes.Length);
strCrypto.Close();
textBoxCiphered.Text = Convert.ToBase64String(strCiphered.ToArray());
strCiphered.Close();
}
private SymmetricAlgorithm GetSelectedAlgorithm()
{
SymmetricAlgorithm Alg = null;
if (comboBoxAlgorithm.SelectedIndex == 0)
Alg = new DESCryptoServiceProvider();
else if (comboBoxAlgorithm.SelectedIndex == 1)
Alg = new RijndaelManaged();
else if (comboBoxAlgorithm.SelectedIndex == 2)
Alg = new TripleDESCryptoServiceProvider();
else
Alg = new RC2CryptoServiceProvider();
return Alg;
}

Asymmetric cryptosystems perform encryption and decryption operations via public-private key pairs which are mathematically linked with each other. Unlike symmetric cryptosystems, when a public key is used to encrypt data, it becomes impossible to restore that data without using a private key. More simply, if you use a private key to encrypt data, then you use a public key to decrypt that data, and vice versa.

Asymmetric cipher algorithms are based on heavy mathematical operations, thus they are not efficient at processing large blocks of data. They are often used to safely exchange small session keys. Asymmetric ciphers can be used for authentication and confidentially. The most popular asymmetric cipher algorithm is RSA, which requires a strong mathematical background to be understood. Here is the structure of RSA:

//Generating Public-Private Keys
Select p,q that p and q are two different large prime numbers
Let n=p*q
Let m=(p-1)*(q-1)
Select e that 1<e<m and gcd(m,e)=1 (e is coprime to m)
Calculate d such that (d*e)mod(m) = 1
Public Key: {e,n}
Private Key:{d,n}
//Encryption
PlainText : M (M<n)
CipherText: C = M<sup>e</sup> Mod(n)
//Decryption
CipherText : C
PlainText : M = C<sup>d</sup> Mod(n)

Block diagram of asymmetric cryptosystems

Plain text is encrypted [by Bob] with Alice's public key, transmitted, then decrypted [by Alice] with Alice's private key.

private void GenerateKeyPairs()
{
rsaCipher = new RSACryptoServiceProvider();
textBoxPublicKey.Text = rsaCipher.ToXmlString(false);
textBoxPrivateKey.Text = rsaCipher.ToXmlString(true);
}
private void buttonEncrypt_Click(object sender, EventArgs e)
{
rsaCipher = new RSACryptoServiceProvider();
string publicKey = textBoxPublicKey.Text;
rsaCipher.FromXmlString(publicKey);
string plainText = textBoxPlain.Text;
byte[] plainBytes = Encoding.ASCII.GetBytes(plainText);
byte[] cipheredBytes = rsaCipher.Encrypt(plainBytes, true);
string cipheredText = Convert.ToBase64String(cipheredBytes);
textBoxCiphered.Text = cipheredText;
}

Hashing is the operation of taking the fingerprint of data. Thus, the purpose of this method is to produce a constant size unique key [from input data] that no different data can produce, thereby making it impossible to produce the data from the key. A very useful application of hashing is used in database systems. Think about a database that stores the passwords of users. Keeping the passwords clear is not as safe as keeping the hash values of passwords in tables. Even though any hash value in a database is enclosed, it is impossible to restore the original password from this value. This method provides the same functionality for authorization processes. The only difference is that the hash of the user's password is compared with the value in the database instead of comparing the password itself.

private void buttonComputeHash_Click(object sender, EventArgs e)
{
byte[] input = Encoding.ASCII.GetBytes(textBoxInput.Text);
HashAlgorithm Alg = GetSelectedAlgorithm();
Alg.ComputeHash(input);
textBoxHash.Text = Convert.ToBase64String(Alg.Hash);
}
private HashAlgorithm GetSelectedAlgorithm()
{
Rfc2898DeriveBytes rfc = new Rfc2898DeriveBytes(textBoxKey.Text,
Encoding.ASCII.GetBytes(textBoxSalt.Text));
HashAlgorithm Alg = null;
if (comboBoxAlgorithm.SelectedIndex == 0)
Alg = new MD5CryptoServiceProvider();
else if (comboBoxAlgorithm.SelectedIndex == 1)
Alg = new RIPEMD160Managed();
else if (comboBoxAlgorithm.SelectedIndex == 2)
Alg = new SHA1CryptoServiceProvider();
else if (comboBoxAlgorithm.SelectedIndex == 3)
Alg = new SHA256Managed();
else if (comboBoxAlgorithm.SelectedIndex == 4)
Alg = new SHA384Managed();
else if (comboBoxAlgorithm.SelectedIndex == 5)
Alg = new SHA512Managed();
else if (comboBoxAlgorithm.SelectedIndex == 6)
Alg = new MACTripleDES(rfc.GetBytes(16));
else if (comboBoxAlgorithm.SelectedIndex == 7)
Alg = new HMACSHA1(rfc.GetBytes(29));
return Alg;
}

Digital signature applications are based on two cryptographic methods: public key cryptosystem and hashing. These two are covered above, and we are now concerned with how to use these two in a simple application.

Think about a case where you want to send a message to your recipient in a way that s/he can certainly be sure that the message is sent by you and no one has modified the content during transmission. Sending the message with its hash will allow the recipient to check whether the hash belongs to the message or not. If the message is modified, the hash of the message will be the same as the attached hash. But what if someone else modifies both the message and the hash during transmission? Then we have to care about this case.

The figure below depicts the block diagram of a digital signature system which is constructed in two phases: signing document (left side) and verifying document (right side). Both phases use a public-key cryptosystem to encrypt and decrypt data. On the signing phase, the hash of the message is encrypted with the private key of the sender. This value (encrypted hash) becomes the signature and is sent to the recipient with the original message. Then, on the verifying phase, the recipient decrypts the signature (encrypted hash) with the public key of the sender. This operation yields the hash value which the sender has already computed. The recipient also computes the hash of the received message and compares it with the sender's hash. If these two hash values are the same, the documents are verified, otherwise not.

Block diagram of a digital signature application

DES has been the most widely used private-key cipher. It exhibits the classic Feistel structure which consists of a number of identical rounds of processing. DES uses 64-bit block and 54-bit key size. The key is used in both encryption and decryption. The encryption operation on DES follows the rounds on the figure.

Block diagram of DES encryption

The figure depicts the encryption operation. However, just reversing the order of keys applied would yield the decryption operation. Before applying this figure, sixteen keys are generated from the secret key. These phases are explained next.

Here is the algorithm for the encryption operation which is also depicted on the figure above. Three phases are the base of this algorithm: an initial permutation, an `F()`

function, and a final permutation.

private Bit[] Encrypt64Bit(Bit[] block)
{
InitialPermutation(block);
Bit[] Left = block[0 - 31];
Bit[] Right = block[31 - 63];
for (int i = 1; i <= 16; i++)
{
Temp = Left;
Left = Right;
Right = (Temp) Xor (F(Right, Keys[i - 1]));
}
block[0 - 31] = Right;
block[32 - 63] = Left;
RevInitialPermutation(block);
return block;
}

This operation takes a 64 bit input and permutes a different block in the order of the IP table. For example, the first element of the IP table is 58, which means the first element of the new block has the 58^{th} element of the input block. Thus, the second element of the new block has the 50^{th} element of the input block and the last element of the new block has the 7^{th} element of the input block.

IP = new byte[8 * 8] { 58, 50, 42 ..... 15, 7 };

This method takes two parameters: the right block (32 bit) and the current key (48 bit). It first expands the right block in the order of E selection table which yields a 48-bit block. Then, applies the Exclusive-OR operation on this new block and the current key. Then, divides the XORed block into 8 pieces (the first 6 bits become the first piece, the second 6 bits become the second piece, and so on). Now, there are 8 blocks, each having 6 bits. Then, from each 6-bit block, a 4-bit block is produced according to the following rule:

(There are eight S tables namely S1, S2, S3... S8. The maximum element in these tables is 15, meaning that the maximum element's bit number is 4). Let the first 6 bits be abcdef, then compute B1 = S1[2*a+f, 8*b+4*c+2*d+e]. Let the second 6 bits be asdfgh, then compute B2 = S2[2*a+h, 8*s+4*d+2*f+g]. Let the eighth 6 bits be zxcvbn, then compute B8 = S8[2*z+n, 8*x+4*c+2*v+b].

Each one of these 8 blocks has 4 bits. This yields a 4*8=32 bit block (B1 B2 B3 B4 B5 B6 B7 B8) which is finally permuted in the order of P table as demonstrated in the following code segment:

private BitArray F(BitArray R, BitArray K)
{
R = Table(E, R);
BitArray B = R.Xor(K);
BitArray S = new BitArray(8 * 4);
int x, y;
BitArray Temp;
for (int i = 0; i < 8; i++)
{
x = (B[i * 6 + 0] ? 2 : 0) + (B[i * 6 + 5] ? 1 : 0);
y = (B[i * 6 + 1] ? 8 : 0) + (B[i * 6 + 2] ? 4 : 0) +
(B[i * 6 + 3] ? 2 : 0) + (B[i * 6 + 4] ? 1 : 0);
Temp = new BitArray(new byte[] { Ss[i, 16 * x + y] });
Copy(Temp, 0, S, i * 4, 4);
}
S = Table(P, S);
return S;
}

Block diagram of F function

This method just takes two bit arrays and applies an Exclusive-OR operation to each bit of the input array. Then it stores the eXOR-ed bits to a new bit array. An implementation of this method would be like this:

Bit[] Xor(Bit[] Left, Bit[] Right)
{
Bit[] Result = new Bit[Right.Length];
for (int i = 0; i < Right.Length; i++)
Result[i] = Left[i] ^ Right[i];
return Result;
}

This method is just like the Initial Permutation method except that the input is permuted in the order of IP-1 table.

The decryption algorithm on DES is similar to the encryption algorithm except that it applies the reverse order of keys as shown below:

private Bit[] Decrypt64Bit(Bit[] block)
{
InitialPermutation(block);
Bit[] Left = block[0 - 31];
Bit[] Right = block[31 - 63];
for (int i = 1; i <= 16; i++)
{
Temp = Left;
Left = Right;
Right = (Temp)Xor(F(Right, **Keys[16 - i]**));
}
block[0 - 31] = Right;
block[32 - 63] = Left;
RevInitialPermutation(block);
return block;
}

This operation takes a 56-bit key and produces 16 different 48-bit keys. First, the input key is permuted in the order of PC1 table, which yields a 56-bit block. Then, divide this new block into two parts, yielding two 28-bit blocks, namely C0 and D0. Then follows the 16 rounds. At each round, C(n+1) and D(n+1) are permuted by applying a left shift to C(n) and D(n). Finally, permuting (Cn)(Dn) in the order of PC-2 table yields the n^{th} Key (C0 D0 in the order of PC-2 table yields the first key, C1 D1 in the order of PC-2 table yields the second key ... C15 D15 in the order of PC-2 table yields the fifteenth key). The number of left shifts differ at each round. This means C1 D1 is obtained from C0 D0 by one left shift, C2 D2 is obtained from C1 D1 by one left shift, C3 D3 is obtained from C2 D2 by two left shift, and so on. A single left shift means a rotation of the bits one place to the left, so that after one left shift, the bits in the 28 positions are the bits that were previously in positions 2, 3,..., 28, 1.

LeftShifts = new byte[16] { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 };

Block diagram of the DES key generation

AES (known as Rijndael) is also a block cipher, but it does not use a Feistel structure. The block size of AES is 128-bit, but the key size may differ as 128, 192, or 256 bits.

Block diagram of AES encryption/decryption

As the figure depicts, the encryption operation consists of four separate functions: byte substitution, permutation, arithmetic operations over a finite field, and XOR with a key.

protected byte[] Encrypt128Bit(byte[] block)
{
AddRoundKey(block, 0);
for (int i = 1; i < Nr; i++)
{
SubBytes(block);
ShiftRows(block);
MixColumns(block);
AddRoundKey(block, i);
}
SubBytes(block);
ShiftRows(block);
AddRoundKey(block, Nr);
return block;
}

This method substitutes each byte of the block in the order of `Sbox`

. It provides an invertible transformation of blocks during encryption, with the reverse during decryption. Implementation of this method is very easy, as depicted:

private void SubBytes(byte[] block)
{
for (int i = 0; i < 16; i++)
{
block[i] = Sbox[i];
}
}

The `ShiftRows`

operation performs left circular shifts of rows 1, 2, and 3 by 1, 2 and 3, as depicted:

void ShiftRows(byte[] state)
{
byte[] t = new byte[4];
for (int r = 1; r < 4; r++)
{
for (int c = 0; c < 4; c++)
t[c] = state[r * 4 + ((c + r) % 4)];
for (int c = 0; c < 4; c++)
state[r * 4 + c] = t[c];
}
}

This method multiplies each column of the input block with a matrix. The multiplication operation is just like matrix multiplication, except that it uses a Finite Field to multiply two elements and performs an XOR operation instead of addition.

Here is the result for the multiplication of the column above (dots denote FF multiplication, pluses in circle denote eXOR operation):

private void MixColumns(byte[] block)
{
byte[,] t = new byte[4, 4];
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
t[i, j] = block[i * 4 + j];
}
}
for (int i = 0; i < 4; i++)
{
block[00 + i] = (byte)(M(2, t[0, i]) ^ M(3, t[1, i]) ^ t[2, i] ^ t[3, i]);
block[04 + i] = (byte)(t[0, i] ^M(2, t[1, i])^ M(3, t[2, i]) ^ t[3, i] );
block[08 + i] = (byte)(t[0, i] ^ t[1, i] ^ M(2, t[2, i]) ^ M(3, t[3, i]));
block[12 + i] = (byte)(M(3, t[0, i]) ^ t[1, i] ^ t[2, i] ^ M(2, t[3, i]));
}
}

This operation just applies an eXOR operation to each byte of the input block and the current weight (key) matrix.

private void AddRoundKey(byte[] block, int round)
{
for (int i = 0; i < 16; i++)
{
block[i] = (byte)(block[i] ^ Keys[(round * 4 + i )]);
}
}

The following reverses the steps of the encryption algorithm with some modifications on the methods, yielding the decryption algorithm:

protected byte[] Decrypt128Bit(byte[] block)
{
AddRoundKey(block, Nr);
for (int i = Nr - 1; i > 0; i--)
{
InvShiftRows(block);
InvSubBytes(block);
AddRoundKey(block, i);
InvMixColumns(block);
}
InvShiftRows(block);
InvSubBytes(block);
AddRoundKey(block, 0);
return block;
}

Here is how the method differs from the encryption operation:

- The
`InvShiftRows`

operation performs **right** (left in `ShiftRows`

) circular shifts of rows 1, 2, and 3 by 1, 2, and 3.
`InvSubBytes`

differs from `SubBytes`

as it uses `InvSbox`

instead of `Sbox`

.
`InvMixColumns`

multiplies each column with a different matrix (available in the source).

This method is also known as key expansion. It takes a matrix in [4,Nk] (Nk = 4, 6, or 8) dimensions and expands it to [4,4*(Nr+1)] (Nr = 10, 12 or 14) dimensions. Here is the algorithm for this method as described in Fips-197:

KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk)
begin
word temp
i = 0
while (i < Nk)
w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3])
i = i+1
end while
i = Nk
while (i < Nb * (Nr+1)]
temp = w[i-1]
if (i mod Nk = 0)
temp = SubWord(RotWord(temp)) xor Rcon[i/Nk]
else if (Nk > 6 and i mod Nk = 4)
temp = SubWord(temp)
end if
w[i] = w[i-Nk] xor temp
i = i + 1
end while
end

- October 28, 2007: Initial release.