Chapter - Two

Fundaments of Cryptography

1
 Outline

• Cryptography
• Symmetric and asymmetric encryption
• Caesar cipher, Vigenère encryption
• Cryptanalysis
• Block vs Stream Ciphers
• Substitution-Permutation Ciphers
• Cryptographic Algorithms

2
 Cryptography
• Cryptography, a word with Greek origins, means “secret writing.”
• However, we use the term to refer to the science and art of
transforming messages to make them secure and immune to
attacks.

• Cryptanalysis: the art and science of decrypting messages.

• Cryptology (from the Greek kryptós, "hidden," and lógos, "word")

is the science of secure or secret communication.
– Cryptology: cryptography + cryptanalysis

Source: Britannica (www.britannica.com)

A similar definition can be found on Wikipedia: http://en.wikipedia.org/wiki/Cryptography 3
 Purpose of Cryptography

• Secure stored information - regardless if access

obtained

• Secure transmitted information - regardless if

transmission has been monitored

• Secure computed information – regardless if

processing devices have been compromised

4
 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
5
 Relevance of Cryptography
• The applications of Cryptography
– Cash machines ATM, money transfer between
banks
– Electronic cash, online banking, secure email
– Phone cards, cell phones, remote controls
– Cloud, IoT
– Crypto currency
– Electronic Signature
– Secure communication
– End-to-end encryption
– Military communications
– Electronic commerce
– Computer Passwords
6
 Cryptography Components
• Cryptography has five components:
- Plaintext: This is what you want to encrypt.
- Ciphertext: The encrypted output.
- Enciphering or encryption: The process by which plaintext is
converted into ciphertext.
- Encryption algorithm: The sequence of data processing steps
that go into transforming plaintext into ciphertext.
- Secret Key: is used to set some or all of the various parameters
used by the encryption algorithm.
- Deciphering or decryption: Recovering plaintext from
ciphertext.
- Decryption algorithm: The sequence of data processing steps that
go into transforming ciphertext back into plaintext. 7
 Keys
• A key can be thought of as 010100111
simply a collection of bits 0
• The more bits, the stronger the 101111011
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

8
 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 9
information that can be used later to prove its authenticity
 Encryption
• Encryption is the process of
taking some data and a key
and feeding it into a function
and getting encrypted data
out
Encryption
• Encrypted data is, in
Function
principle, unreadable unless
decrypted

10
 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

11
 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. Decrypt
• Strength of encryption technique
depends on key length
12
 Encryption Techniques…
• Secret Key (Symmetric)
– Known symmetrical algorithms
• Data Encryption Standard (DES)
– 56 bit key
• Triple DES, Double DES
– 168 bit key
• Advanced Encryption Standard (AES)
- 128, 192,256
• RC2, RC4, RC5
– variable length up to 2048 bits
• IDEA - basis of PGP
– 128 bit key
• Blowfish, Two fish
– variable length up to 448 bits 13
 Encryption Techniques…
Asymmetric Encryption
• Encryption and decryption
algorithms that use a key
pair are called asymmetric
• E.g. RSA, DH

14
 ENCRYPTION DECRYPTION

Message 1 Encrypted Message 1

Central to the growth of e-commerce and e- 9a46894335be49f0b9cab28d755aaa9cd98571b
governance is the issue of trust in electronic 275bbb0adb405e6931e856ca3e5e569edd13528
environment. 5482

Encrypted Message 1 Message 1

9a46894335be49f0b9cab28d755aaa9cd985 Central to the growth of e-commerce and e-
71b275bbb0adb405e6931e856ca3e5e569e governance is the issue of trust in electronic
dd135285482 environment.

Same Key
Message 2 SYMMETRIC
The Internet knows no geographical boundaries. Encrypted Message 2
It has redefined time and space. Advances in a520eecb61a770f947ca856cd675463f1c95a9a2b
computer and telecommunication technologies 8d4e6a71f80830c87f5715f5f59334978dd7e97da
have led to the explosive growth of the Internet. 0707b48a1138d77ced56feba2b467c398683c7db
This in turn is affecting the methods of eb86b854f120606a7ae1ed934f5703672adab0d7
communication, work, study, education, be66dccde1a763c736cb9001d0731d541106f50b
interaction, leisure, health, governance, trade b7e54240c40ba780b7a553bea570b99c9ab3df13
and commerce. d75f8ccfdddeaaf3a749fd1411
Encrypted Message 2 Message 2
a520eecb61a770f947ca856cd675463f1c95 The Internet knows no geographical boundaries. It has
a9a2b8d4e6a71f80830c87f5715f5f5933497 redefined time and space. Advances in computer and
8dd7e97da0707b48a1138d77ced56feba2b4 telecommunication technologies have led to the
67c398683c7dbeb86b854f120606a7ae1ed9 explosive growth of the Internet. This in turn is
Different Keys
34f5703672adab0d7be66dccde1a763c736c affecting the methods of communication, work, study,
b9001d0731d541106f50bb7e54240c40ba7 education, interaction, leisure, health, governance,
[Keys of a pair – Public and Private]
80b7a553bea570b99c9ab3df13d75f8ccfddd trade and commerce.
ASYMMETRIC
eaaf3a749fd1411

[PKI] 15
 Encryption Techniques…

• One-Way Function
– non-reversible “quick” encryption
– produces a fixed length value called a hash or message
digest
– used to authenticate contents of a message
– Common message digest functions
• MD4 and MD5
– produces 128 bit hashes
• SHA
– produces 160 bit hashes

16
 Cryptographic Services Allow
• Digital Signatures
– sign messages to validate source and integrity of the contents
• Digital Envelopes (combination of symmetric/asymmetric)
– secure delivery of secret keys
• Message Digests
– short bit string hash of message
• Digital Certificates
– used to authenticate: users, web sites, public keys of public/private
pair, and information in general
• Secure Channels
– Encryption can be used to create secure channels over private or
public networks 17
 Cryptanalysis

• Objective is to recover key not just the message.

• General approaches:
– cryptanalytic attack
– brute-force attack
• if either succeed, all key use will be compromised.

18
 Cryptanalysis…
• Cryptanalysis:
– relies on the nature of the algorithm plus
– some knowledge of the general characteristics of the plaintext or
– even some sample plaintext - ciphertext pairs.
• This type of attack exploits the characteristics of the algorithm to
attempt to:
– deduce a specific plaintext or
– to deduce the key being used.

• Brute-force attacks:
– try every possible key on a piece of ciphertext until an intelligible
translation into plaintext is obtained.
– On average, half of all possible keys must be tried to achieve success.
– WHY?
19
 Cryptanalysis…

• If either type of attack succeeds in deducing the key, the effect

is catastrophic:
– All future and past messages encrypted with that key will be
compromised.

• Defense method
– Use longer keys and
– stronger encryption algorithm

20
 Cryptanalytic Attacks
• Known ciphertext only
– only know algorithm & ciphertext, know or can identify plaintext

• Known plaintext
– know/suspect plaintext & ciphertext to get keys or algorithms

• Chosen plaintext
– Here, the attacker, chooses the plaintext for any cipher and
understands the 'key' and the algorithm.

• Chosen ciphertext
– select ciphertext and obtain plaintext and key
21
 Brute Force Search
• always possible to simply try every key
• most basic attack, proportional to key size

Key Size (bits) Number of Time required at 1 Time required at 106

Alternative Keys decryption/µs decryptions/µs

32 232 = 4.3  109 231 µs = 35.8 minutes 2.15 milliseconds

56 256 = 7.2  1016 255 µs = 1142 years 10.01 hours

128 2128 = 3.4  1038 2127 µs = 5.4  1024 5.4  1018 years
years

168 2168 = 3.7  1050 2167 µs = 5.9  1036 5.9  1030 years
years

26 characters 26! = 4  1026 2  1026 µs = 6.4  1012 6.4  106 years

(permutation) years

22
 Steganography

Steganography is
the art and science
of writing hidden
message in images,
audios, or videos.

23
 Cryptography + Steganography
• Enciphering on source side

24
Cryptography + Steganography
Deciphering

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

26
 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
27
• stream
 Cryptography example: Caesar cipher
Caesar encryption (Julius Caesar, 100 - 44 B.C.)
• mono-alphabetic substitution 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 28
 Cryptography example
Caesar cipher
• If we represent each letter of the alphabet by an integer that
corresponds to its position in the alphabet, the formula for replacing
each character ’P’ of the plaintext with a character ’C’ of the
ciphertext can be expressed as
C = E( 3, P) = (P + 3) mod 26
• A more general version of this cipher that allows for any degree of
shift would be expressed by
C = E( k, P) = (P + k) mod 26
• The formula for decryption would be
P = D( k, C ) = (C - k) mod 26
• In these formulas, ’k’ would be the secret key.
• The symbols ’E’ and ’D’ represent encryption and decryption. 29
 Weakness of the Caesar Cipher

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

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

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

31
 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. 32
 Vigenère encryption
(poly-alphabetic substitution cipher)
• Vigenère encryption (Blaise de Vigenère, 1523-1596)
• French diplomat, cryptographer, translator, and alchemist
• Encryption with a keyword using a key table
• Example Plaintext Ciphertext

• Keyword: CHIFFRE
• Encrypting: VIGENERE becomes XPOJSVVG
• The plaintext character (V) is replaced by the character in the
corresponding row and in the column of the first keyword character (C).
• The next plaintext character (I) is replaced by the character in the
corresponding row and in the column of the next keyword character (H),
and so on.
• If all characters of the keyword have been used, then the next keyword
character is the first key character. 33
 Vigenère Keyword character

encryption …
• Example
• Keyword:
CHIFFRE
• Encrypting:
VIGENERE Plaintext
becomes
XPOJSVVG

Ciphertext

Plaintext character Encrypted character 34

 Vigenère encryption…
• This algorithm uses different cipher letters for different
occurrences of same plaintext letter (poly-alphabetic substitution).
• Make cryptanalysis harder with more letters to guess.

• The encryption formula is defined as

Ci = Ek(Pi) = (Pi + Ki mod m) mod 26
• while the decryption formula is
Pi = Dk(Ci) = (Ci - Ki mod m) mod 26
• where m is the length of the key string.

35
 Plaintext

Plaintext: THANKYOU
Key: COVERCOVER…
Cipher: VVVRBACP

Given ciphertext and

key, How to get back
the plaintext?
Cipher: VVVRBACP Key

Key: COVERCOVER…
Plaintext ?
36
 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, AES, Blowfish, RC2, RC5, IDEA…

• Asymmetric: different keys are used to encrypt and

decrypt the data
– Example: RSA, DH…

37
 Requirements
• Two requirements for secure use of symmetric
encryption:
– a strong encryption algorithm
– a secret key known only to sender / receiver
C = DK [EK (P)]

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
38
 Key Distribution Problem
• Key distribution for symmetric encryption methods
• If 2 persons communicate with each other using symmetric
encryption, they need one common secret key.
• If n persons communicate with each other, then they need
Sn = n * (n-1) / 2 keys. Number of required keys

That is: n = 100 persons require

S100 = 4,950 keys; and

n = 1,000 persons require Number of keys

S1000 = 499,500 keys.

A factor of 10 more persons means a

factor of 100 more keys.

39

Number of persons
 Cryptography – Important Insights - 1
Solving the key distribution problem through asymmetric
cryptography.
• Asymmetric cryptography
– For centuries it was believed that sender and receiver need to
know the same secret.
– New idea: Every person needs a key pair (which solves the key
distribution problem).
• Asymmetric encryption
– MIT, 1977: Leonard Adleman, Ron Rivest, Adi Shamir (well known
as RSA)
• Key distribution
– Stanford, 1976: Whitfield Diffie, Martin Hellman, Ralph Merkle
(Diffie-Hellman key exchange)
40
 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.
Security in open networks (such as the Internet) would be extremely expensive
and complex without asymmetric cryptography!
41
 Cryptography – Important Insights (2)

• Increasing relevance of mathematics and information technology.

• Modern cryptography is increasingly based on mathematics.
– There are still new symmetric encryption methods, such as AES; these
often feature better performance and shorter key length compared to
asymmetric methods that are based purely on mathematical problems.
• The security of encryption methods heavily depends on the current
state of mathematics and information technology (IT).
– Computation complexity (meaning processing effort in relation to key
length, storage demand, and data complexity).
– RSA-1024, RSA-2048
• Major topics in current research:
– Factorization of very large numbers, quantum computers, protocol weaknesses
A combination of symmetric and asymmetric cryptosystem make todays
security more efficient than before. 42
 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

43
Block vs Stream Ciphers

44
 Substitution-Permutation Ciphers
• In his 1949 paper, Shannon introduced the idea
of substitution-permutation (S-P) networks,
which now form the basis of modern block
ciphers.

• an S-P network is the modern form of a

substitution-transposition product cipher.

• S-P networks are based on the two primitive

cryptographic operations we have seen before

45
 Substitution-Permutation Ciphers…
• Substitution Operation
– a binary word is replaced by some other binary word
– the whole substitution function forms the key
– if use n bit words, the key is 2n ! bits, grows rapidly
– will call them S-Boxes

• Permutation Operation
– a binary word has its bits reordered (permuted)
– the re-ordering forms the key
– if use n bit words, the key is n! bits, which grows more slowly, and
hence is less secure than substitution
– will call these P-Boxes 46
 Substitution-Permutation Ciphers…
• Shannon combined these two primitives
• he called these mixing transformations
• Shannon's mixing transformations are a special form of product
ciphers where
• S-Boxes
– provide confusion of input bits
• P-Boxes
– provide diffusion across S-box inputs

47
Substitution-Permutation Ciphers…

Basic elements of product ciphers.

(a) P-box. (b) S-box. (c) Product.

48
Cryptography – Important Insights (3)
• Kerckhoffs’ principle (first stated in 1883)
– Separation of algorithm (method) and key e.g. Caesar encryption:
• Algorithm: “Shift alphabet by a certain number of positions to the left”
• Key: The “certain number of positions”
– Kerckhoffs’ principle: The secret lies within the key and not within
the algorithm; “security through obscurity” is invalid
• Shannon’s concepts: Confusion and Diffusion
– Relation between M, C, and K should be as complex as possible
(M=message, C=cipher, K=key)
– Every ciphertext character should depend on:
• as many plaintext characters and
• as many characters of the encryption key as possible
– “Avalanche effect” (small modification, big impact) 49
 Cryptographic Algorithms

• Block ciphers (secret/symmetric key, DES, AES)

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

50