CHAPTER TWO

Fundaments of Cryptography

•1
Outline
• Basic Security techniques
• Cryptography
• Symmetric and asymmetric encryption
• Cryptanalytic Attacks
• Caesar cipher
• Block vs Stream Ciphers
• Cryptographic Algorithms
• Symmetric Block Cipher Algorithms
– DES (Data Encryption Standard)
– Double DES
– 3DES (Triple DES)
• DES strength/weakness
• AES

•2
Purpose of Cryptography
• Secure stored information - regardless if access
obtained

• Secure transmitted information - regardless if

transmission has been monitored

•3
Services Provided by Cryptography
• Confidentiality
– provides privacy for messages and stored data by hiding
• Message Integrity
– provides assurance to all parties that a message remains
unchanged
• Non-repudiation
– Can prove a document came from X even if X denies it
• Authentication
– identifies the origin of a message
– verifies the identity of person using a computer system

•4
Cryptography
• Terminologies
 Plaintext - the original message
 Ciphertext - the coded message
 Cipher - algorithm for transforming plaintext to ciphertext
 Key - info used in cipher known only to sender/receiver
 Encipher (encrypt) - converting plaintext to ciphertext
 Decipher (decrypt) - recovering plaintext from ciphertext
 Cryptography - study of encryption principles/methods
 Cryptanalysis (codebreaking) - the study of principles/
methods of deciphering ciphertext without knowing key
 Cryptology - the field of both cryptography and
cryptanalysis

•5
Keys
• A key can be thought of as 010100111
simply a collection of bits 0
• The more bits, the stronger 101111011
the key 101100101
• Keys are tied to specific
encryption algorithms
• Lengths vary depending on
the encryption algorithm
– e.g. 128 bits is long for
some algorithms, but short
for others

•6
Cryptography
• Encryption Overview
– Plain text is converted to cipher text by use of an
algorithm and key.
• Algorithm is publicly known
• Key is held private
– Three Main Categories
• Secret Key
– single key is used to encrypt and decrypt information
• Public/Private Key
– two keys are used: one for encryption (public key) and one for
decryption (private key)
• One-way Function
– information is encrypted to produce a “digest” of the original
information that can be used later to prove its authenticity •7
Encryption
• Encryption is the process of
taking some data and a key
and feeding it into a
function and getting
encrypted data out
• Encrypted data is, in Encryption
principle, unreadable unless Function
decrypted

•8
Decryption
• Decryption is the process
of taking encrypted data
and a key and feeding it
into a function and
getting out the original
data
– Encryption and decryption
functions are linked Decryption
Function

•9
Encryption Techniques
Symmetric Encryption
• Encryption and decryption
algorithms that use the same
key are called symmetric
Encrypt
– In this case everyone wanting to
read encrypted data must share
the same key
• Sender and receive have the
same secret key that will
encrypt and decrypt plain text.
• Strength of encryption Decrypt
technique depends on key
length
•10
Encryption Techniques…
Asymmetric Encryption
• Encryption and decryption
algorithms that use a key
pair are called asymmetric
– Keys are mathematically
linked
• Most common algorithm
is the RSA (Rivest Shamir
Adelman) algorithm with
key lengths from 512 to
1024 bits.

•11
Building Blocks of Encryption Techniques
• Two building blocks of all classical encryption techniques are
substitution and transposition.

• Substitution means replacing an element of the plaintext with

an element of ciphertext.
– each element in the plaintext (bit, letter, group of bits or
letters) is mapped into another element

• Transposition means rearranging the order of appearance of

the elements of the plaintext.

• Transposition is also referred to as permutation.

•12
Cryptography…
• Cryptographic systems can be characterized along these
three independent dimensions.
– type of encryption operations used
• substitution
• transposition
• product
– number of keys used
• single-key, secret-key, symmetric or private
• two-key, asymmetric or public-key

– way in which plaintext is processed

• block
• stream
•13
Cryptography...
• Simplified Encryption Model:

•14
Cryptography...
Description
• A sender S wants to transmit message M to a
receiver R.
• To protect the message M, the sender first encrypts
it into an intelligible message M’.
• After receipt of M’, R decrypts the message to obtain
M.
• M is called the plaintext
 What we want to encrypt
• M’ is called the ciphertext
 The encrypted output
•15
Cryptanalytic Attacks
• Types of attacks
- An attacker has only the ciphertext and his goal is to find
the corresponding plaintext.
- An attacker has a ciphertext and the corresponding
plaintext and his goal is to find the key.

• A good cryptosystem protects against all types of

attacks.

• Attackers use both Mathematics and Statistics.

•16
Cryptanalytic Attacks…
• Intruders
• Eavesdropping (listening/spying the message)
 An intruder may try to read the message
 If it is well encrypted, the intruder will not know the content
 However, just the fact the intruder knows that there is
communication may be a threat (Traffic analysis)

• Modification
 Modifying a plaintext is easy, but modifying encrypted messages
is more difficult

• Insertion of messages
 Inserting new message into a ciphertext is difficult
•17
Cryptography example:
Caesar cipher
• This is the earliest known example of a substitution cipher.
• Each character of a message is replaced by a character
three position down in the alphabet.

• Shift of letters:
Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher: DEFGHIJKLMNOPQRSTUVWXYZABC

Example
plaintext: are you ready
ciphertext: duh brx uhdgb
•18
Cryptography example:
Caesar cipher
Example: Encipher the message
THIS MESSAGE IS TOP SECRET
• using the ordinary alphabet and a Caesar cipher with a shift of 3.
• When each letter is converted to a number, and we group into
blocks of length 5, we get

19 7 8 18 12 4 18 18 0 6 4 8 18 19 14 15 18 4 2 17 4 19

• Here, we group the items in blocks for readability. After applying

the enciphering transformation, each number becomes
22 10 11 21 15 7 21 21 3 9 7 11 21 22 17 18 21 7 5 20 7 22
• and the ciphertext message is sent as
WKLVP HVVDI HLVWR SVHFU HW
•19
WEAKNESSES OF THE CAESAR
CIPHER
• The Caesar Cipher is a secret key cryptosystem;
– that is, revealing the enciphering key makes decryption
simple.

• In the Caesar cipher, the shift value is the enciphering

key.
• Anyone knowing it can immediately decrypt, so it must
be protected from unauthorized persons.

•20
WEAKNESSES OF THE CAESAR CIPHER

• Exhaustive Key Search. There is yet another method for

breaking the Caesar cipher:
• simply try all the possible keys!
– After all, there are only 26 viable keys in the ordinary alphabet, and
only 255 useful keys in the ASCII alphabet! This kind of attack is
called an exhaustive search.
• An exhaustive search is rarely effective against all but the
simplest of cryptosystems.
• Seeing that the Caesar cipher is so vulnerable, we attempt
to see stronger cryptosystems.

•21
Ciphering with Transposition
• So far we have seen ciphering with substitution.
• We will now talk about a different notion in classical
cryptography: permuting the plaintext.

• This is how a pure permutation cipher could work:

– You write your plaintext message along the rows of a matrix of
some size.
– You generate ciphertext by reading along the columns.
– The order in which you read the columns is determined by the
encryption key.

•22
Ciphering with Transposition…

Key: 4 1 3 6 2 5

Plaintext: m e e t m e
a t s q u a
r e g u a r
d e n f o r
g o o d d i
n n e r o k

Ciphertext: tqufdrmardgnesgnoeearriketeeonmuaodo
The cipher can be made more secure by performing multiple
rounds of such permutations. •23
Symmetric and Asymmetric ciphering

• Symmetric: the same key is used to encrypt the

data
– Both sides of the communication must have the
same key
– Examples: DES, Blowfish, RC2, RC5, IDEA…

• Asymmetric: different keys are used to encrypt

and decrypt the data
– Example: RSA, DH…

•24
Symmetric and Asymmetric ciphering...
• Symmetric Cryptography
• Also called secret-key/private-key cryptosystem
• The same key is used to encrypt and decrypt a message
C = DK [EK (P)]

• Have been used for centuries in a variety of forms

• The key has to be kept secret

• The key has to be communicated using a secure channel

• They are still in use in combination with public-key

cryptosystems due to some of their advantages

•25
Requirements
• Two requirements for secure use of symmetric
encryption:
– a strong encryption algorithm
– a secret key known only to sender / receiver
• mathematically have:
C = E(K, P ) done by sender side
P = D(K, C ) receiver side
• assume encryption algorithm is known
• implies a secure channel to distribute key

•26
Asymmetric ciphering

• Asymmetric Cryptography

• Also called public-key cryptosystem

 keys for encryption and decryption are different but form a unique pair

C = DKD [EKE (P)]

 Only one of the keys need to be private while the other can be public.

• Invented by Diffie and Hellman in 1976.

• It is a revolutionary concept since it avoids the need of using a
secure channel to communicate the key.
• It has made cryptography available for the general public and
made many of today’s on-line application feasible.
•27
Block vs Stream Ciphers

• Block ciphers process messages into blocks,

each of which is then en/decrypted
• like a substitution on very big characters
– 64-bits or more
• Stream ciphers process messages a bit or byte
at a time when en/decrypting
• many current ciphers are block ciphers

•28
Cryptographic Algorithms

• Block ciphers (secret/symmetric key, DES)

• Hashes (digital signature)
• Diffie-Hellman key exchange
• RSA (public key encryption and digital
signature)
• ElGamal digital signature
• IDEA, RC2, RC5, Blowfish, and many more

•29
Symmetric Block Cipher Algorithms

• DES (Data Encryption Standard)

• 3DES (Triple DES)
• AES (Advanced Encryption Standard)

•30
N D
E