RAJAGIRI SCHOOL OF
ENGINEERING & TECHNOLOGY
RAJAGIRI VALLEY, KAKKANAD, COCHIN – 682 039
DIVISION OF COMPUTING SCIENCES
SECURITY IN COMPUTING – MODULE III
Index
1. Cryptography…………………………………………………………………….1
2. Fiestel Networks………………………...………………………………………10
3. Data Encryption Standard……………………………………………………..12
4. Modes of operation of DES……………………………...……………………..20
5. Public key Cryptography………………………………………………………26
6. RSA Algorithm……………………………………………………………….....28
7. Diffie Hellman Key Exchange………………………………………………….31
8. MAC and HASH function………………………………………………….….33
9. Digital Signature…………………………………………………………….…35
10. Questions……………………………………………………………………..…37
1. Cryptography
1.1 Introduction
Definitions
Plaintext / "The original message before it is encoded."Encoding/Encryption / "The process of disguising the plaintext."
Ciphertext / "The enciphered version of the plaintext."
Decoding/Decryption / "The process of reverting the cipher text back to the plain text."
Cryptography / "The science of keeping messages secret and of ensuring authentication."
Cryptanalysis / "The science (and art) of deciphering encoded messages without the knowledge of the used key."
Cryptology / Greek: kryptós = hidden, lógos=science. "The combination of cryptography and cryptanalysis "The science of hidden, disguised information."
1.2 Types of Cryptography
1.2.1 Conventional Encryption/Private-key Cryptography
In a "One-Key-Encryption" or "Conventional Encryption", the sender and the recipient share the same key as their common secret
(source: www.PGPi.com):
At some earlier point in time the two correspondents, the sender and the recipient, must have agreed on that key. If they are in different locations, they must trust a courier or a phone system to transmit the secret key in a secure manner. Surely, this is not very practical, particularly when many (new) parties are involved.
However, the major problem is the total number of keys involved. 2 correspondents use 1 key, 3 use 3 keys, 4 use 6 keys, 5 use 10 keys, 100 use 4950 keys, 1000 use 499500 keys, etc. And each key must be stored in a secure manner. Key management is enough of a difficult task that a name was invented for it: The Key Distribution Problem. It is the reason why One-Key-Cryptography is not appropriate for today's secure electronic data transfers between many parties involved.
Every Cipher is made up of two ingredients: an encryption method (the "algorithm") and the set of all possible keys (the "key space"). The sender may now choose from the number of possible keys to encode his secret message. The security of the cryptosystem shall not be based on keeping the algorithm secret, but solely keeping the key secret.
Private Key Cryptography means that the knowledge of the encoding key yields the decoding key. Such Ciphers are therefore also called "Symmetric Ciphers". If a Cipher only offers a small number of keys (i.e. the Caesar Cipher) it can be broken by simply testing the possible keys. A huge number of keys assures the security of a cipher
Private Key Cryptography provides "high-security" ciphers, however, their usage is not practical because of the key distribution problem. It describes the difficulty of exchanging and handling a large number of keys. I.e. 1000 correspondents have to handle a total of 499500 keys. The number of keys increases with the square of the number of correspondents.
1.2.2 Two-key/Public-key Cryptography
The "Two-Key Cryptography" or "Public-Key Cryptography" was a major breakthrough in 1976. It makes the inconceivable reality: A Public Key is used to encode the plain text, its corresponding Private Key is used to decode the cipher text. The clue: Although the encoding key available to the whole world, nobody is capable of figuring out the decoding key. The figure below shows the how "Two-Key Cryptography" is performed.
(source: www.PGPi.com):
The primary benefit of public key cryptography is that it allows people who have no preexisting security arrangement to exchange messages securely. The need for sender and receiver to share secret keys via some secure channel is eliminated; all communications involve only public keys, and no private key is ever transmitted or shared.
1.2.3 Transposition and Substitution Ciphers
Substitution and Transposition Ciphers are two categories of ciphers used in classical cryptography. Substitution and Transposition differ in how chunks of the message are handled by the encryption process. Substitution ciphers encrypt plaintext by changing the plaintext one piece at a time.
The Ceasar Cipher was an early substitution cipher. In the Caesar Cipher, each character is shifted three places up. Therefore, A becomes D and B becomes E, etc...
This table shows "VOYAGER" being encrypted with the Caesar substution cipher:
Plaintext / V / O / Y / A / G / E / RKey / +3 / +3 / +3 / +3 / +3 / +3 / +3
Ciphertext / Y / R / B / D / J / H / U
Transposition ciphers encrypt plaintext by moving small pieces of the message around.
This table shows "VOYAGER" being encrypted with a primitive transposition cipher where every two letters are switched with each other:
V / O / Y / A / G / E / RO / V / A / Y / E / G / R
1.2.4 Stream and Block Ciphers
Block and Stream Ciphers are two categories of ciphers used in classical cryptography. Block and Stream Ciphers differ in how large a piece of the message is processed in each encryption operation. Block ciphers encrypt plaintext in chunks. Common block sizes are 64 and 128 bits. Stream ciphers encrypt plaintext one byte or one bit at a time. A stream cipher can be thought of as a block cipher with a really small block size. Generally speaking, block ciphers are more efficient for computers and stream ciphers are easier for humans to do by hand.
1.3 Caesar Substitution
The simplest of all substitution ciphers is the one in which the cipher letters results from shifting plain letters by the same distance. Among those, the best known is called "Caesar Cipher", used by Julius Caesar, in which each A is encrypted as D, B as E, C as F,... etc. Here key is 3
Mathematically, the encryption and decryption functions can be described as follows:
The sender encodes each plain text letter P using the key b as follows:
C= (P+b) mod 26
The recipient decodes each cipher text letter C using the key b as follows:
P=(C-b) mod 26
1.4 Playfair Cipher
The best known substitution cipher that encrypts pairs of letters is the Playfair Cipher invented by Sir Charles Wheatstone but championed at the British Foreign Office by Lyon Playfair, the first Baron Playfair of St. Andrews, whose name the cipher bears. Here, a 5 x 5-square matrix containing the 26 letters of the alphabet (I and J are treated as the same letter) is used to carry out the encryption. A key word, MONARCHY in this example, is filled in first, and the remaining unused letters of the alphabet are entered in their lexicographic order.
Pairs of plaintext letters are encrypted with the matrix by first locating the two plaintext letters in the matrix. They are
(1) in different rows and columns or
(2) in the same row or
(3) in the same column or
(4) alike.
The corresponding encryption (replacement) rules are the following:
1. If the pair of letters are in different rows and columns, each letter is replaced by the letter that is in the same row but in the other column; i.e., to encrypt WE, W is replaced by U and E by G.
2. If two letters are in the same row simply shift both one position to the right. I.e. A and R are in the same row. A is encrypted as R and R (reading the row cyclically) as M.
3. Similarly, if two letters are in the same column shift both one position down. I.e. I and S are in the same column. I is encrypted as S and S as X.
4. If a double letter occurs, a spurious symbol, say Q, is introduced so that the MM in SUMMER would encrypt into NL for MQ and CL for ME.
5. An X is appended to the end of the plaintext if necessary to cause the plaintext to have an even number of letters.
1.5 Monoalphabetic substitution
The Caesar Cipher, the Multiplication Cipher and the Linear Cipher have one property in common. They all fall in the category of Monoalphabetic Ciphers: "Same plain letters are encoded to the same cipher letter." i.e. in the Caesar Cipher each "a" turned into "d", each "b" turned into "e", etc.
The reason why such Ciphers can be broken is the following: Although letters are changed the underlying letter frequencies are not! If the plain letter "a" occurs 10 times its cipher letter will do so 10 times. Therefore, any monoalphabetic Cipher can be broken with the aid of letter frequency analysis.
1.6 Polyalphabetic Substitution
Polyalphabetic substitution cipher is simply a substitution cipher with an alphabet that changes. For example one could have two alphabets:
Plain Alphabet: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Cipher Alphabet #1: B D F H J L N P R T V X Z A C E G I K M O Q S U W Y
Cipher Alphabet #2: Z Y X W V U T S R Q P O N M L K J I H G F E D C B A
Now to encrypt the message ``The quick brown fox jumped over the lazy dog" we would alternate between the two cipher alphabets, using #1 for every first letter and #2 for every second, to get: ``Msj joxfp dicda ucu tfzkjw ceji msj xzyb hln". Polyalphabetic substitution ciphers are useful because they cannot be broken using frequency analysis.The number of letters encrypted before a polyalphabetic substitution cipher returns to its first cipher alphabet is called its period. The larger the period, the stronger the cipher.
Vigenere Cipher
The polyalphabetic substitution cipher involves the use of two or more cipher alphabets. Instead of there being a one-to-one relationship between each letter and its substitute, there is a one-to-many relationship between each letter and its substitutes.
The Vigenere Cipher , proposed by Blaise de Vigenere is a polyalphabetic substitution based on the following tableau:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y
Note that each row of the table corresponds to a Caesar Cipher. The first row is a shift of 0; the second is a shift of 1; and the last is a shift of 25.
The Vigenere cipher uses this table together with a keyword to encipher a message. For example, enciphering the plaintext message:
TO BE OR NOT TO BE THAT IS THE QUESTION
using the keyword RELATIONS. We begin by writing the keyword, repeated as many times as necessary, above the plaintext message. To derive the ciphertext using the tableau, for each letter in the plaintext, one finds the intersection of the row given by the corresponding keyword letter and the column given by the plaintext letter itself to pick out the ciphertext letter.
Keyword: RELAT IONSR ELATI ONSRE LATIO NSREL
Plaintext: TOBEO RNOTT OBETH ATIST HEQUE STION
Ciphertext: KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY
Decipherment of an encrypted message is equally straightforward. One writes the keyword repeatedly above the message:
Keyword: RELAT IONSR ELATI ONSRE LATIO NSREL
Ciphertext: KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY
Plaintext: TOBEO RNOTT OBETH ATIST HEQUE STION
This time one uses the keyword letter to pick a column of the table and then traces down the column to the row containing the ciphertext letter. The index of that row is the plaintext letter.