Chapter Three:

Cryptography and
Encryption Techniques
 Security Techniques:
Cryptography
Terminology
Terminology

Cryptography:
Cryptography: Schemes
Schemes for
for encryption
encryption
and
and decryption
decryption

Encryption:
Encryption: The The process
process by by which
which
plaintext
plaintext is
is converted
converted into
into cipher
cipher text.
text.

Decryption:
Decryption: Recovering
Recovering plaintext
plaintext from
from
the
the cipher
cipher text
text

Secret
Secret key:
key: Used
Used toto set
set some
some oror all
all of
of the
the
various
various parameters
parameters used
used by
by the
the
encryption
encryption algorithm.
algorithm. In In aa classical
classical
(symmetric
(symmetric key)key) cryptography,
cryptography, the the same
same
secret
secret key
key is is used
used for
for encryption
encryption and and
decryption
decryption
 Cryptography

Cryptography
Cryptography has has five
five ingredients:
ingredients:
•• Plaintext
Plaintext
•• Encryption
Encryption algorithm
algorithm
•• Secret
Secret Key
Key
•• Cipher
Cipher text
text
•• Decryption
Decryption algorithm
algorithm
Security
Security depends
depends on on the
the secrecy
secrecy of
of
the
the key,
key, not
not the
the secrecy
secrecy of of the
the
algorithm
algorithm
 Cryptography
Simplified
Simplified Encryption
Encryption Model:
Model:
 Cryptography
Description:
Description:
A
A sender
sender S S wanting
wanting to to transmit
transmit
message
message M M to
to aa receiver
receiver RR
To
To protect
protect thethe message
message M, M, the
the
sender
sender first
first encrypts
encrypts it it into
into an
an
unintelligible
unintelligible message
message M’M’
After
After receipt
receipt ofof M’,
M’, R
R decrypts
decrypts the
the
message
message to to obtain
obtain M M
M
M is
is called
called the
the plaintext
plaintext

What
What we
we want
want to
to encrypt
encrypt
M’
M’ is
is called
called the
the cipher
cipher text
text
 Cryptography
Notation:
Notation:


Given
Given

P=Plaintext
P=Plaintext

C=CipherText
C=CipherText
C
 C=
=EEKK (P)
(P) Encryption
Encryption
P
 P == DDKK (( C)
C)
Decryption
Decryption
 Cryptography
Cryptographic
Cryptographic systems
systems are
are characterized
characterized along
along three
three
independent
independentdimensions:
dimensions:
1.1. The
The type
type of
of operations
operations used
used for
for transforming
transforming plaintext
plaintext to
to
ciphertext.
ciphertext. All
All encryption
encryption algorithms
algorithms are
are based
based on
on two
two general
general
principles:
principles: substitution,
substitution, in
in which
which each
each element
element in
in the
the plaintext
plaintext
(bit,
(bit, letter,
letter, group
group of
of bits
bits or
or letters)
letters) isis mapped
mapped into
into another
another
element,
element,and
andtransposition,
transposition,in
inwhich
whichelements
elementsin
inthe
theplaintext
plaintextare
are
rearranged.
rearranged. The
The fundamental
fundamental requirement
requirement isis that
that no
no information
information
be
be lost
lost (that
(that is,
is, that
that all
all operations
operations are
are reversible).
reversible). Most
Most systems,
systems,
referred
referred to
to as
as product
product systems,
systems, involve
involve multiple
multiple stages
stages of
of
substitutions
substitutionsand
andtranspositions.
transpositions.
 Cryptography
2.2. The
Thenumber
numberof
ofkeys
keys used.
used. IfIfboth
bothsender
senderand
andreceiver
receiveruse
usethe
the
same
same key,
key, the
the system
system isis referred
referred to
to as
as symmetric,
symmetric, single-key,
single-key,
secret-key,
secret-key, or
or conventional
conventional encryption.
encryption. IfIf the
the sender
sender and
and
receiver
receiver use
use different
different keys,
keys, the
the system
system isis referred
referred to
to as
as
asymmetric,
asymmetric,two-key,
two-key,or
orpublic-key
public-keyencryption.
encryption.
3.3. The
The way
way in
in which
which the
the plaintext
plaintext isis processed.
processed. AAblock
blockcipher
cipher
processes
processesthe
theinput
inputone
oneblock
blockof
ofelements
elementsatataatime,
time,producing
producing
an
an output
output block
block for
for each
each input
input block.
block. AA stream
streamcipher
cipher
processes
processes the
the input
input elements
elements continuously,
continuously, producing
producing output
output
one
oneelement
elementatataatime,
time,as
asititgoes
goesalong.
along.
 Cryptography/Cipher
classification:
Cipher
Cipher classification:
classification:
 Cipher classification /classical
Ciphers/substitution
Caesar
Caesar Cipher
Cipher -- early
early example:
example:
Caesar
Caesar Cipher:
Cipher: The The earliest
earliest
known
known example
example of of aa substitution
substitution
cipher
cipher in
in which
which each
each character
character of
of
aa message
message is is replaced
replaced byby aa
character
character three
three position
position down
down inin
the
the alphabet.
alphabet.
 Plaintext: are
Plaintext: are you
you ready
ready
 Ciphertext: duh
Ciphertext: duh brx
brx uhdgb
uhdgb
 Cipher classification /classical
Ciphers/substitution

If
If we
we represent
represent each
each letter
letter of
of the
the
alphabet
alphabet byby anan integer
integer thatthat
corresponds
corresponds to
to its
its position
position in
in the
the
alphabet:
alphabet:

The
The formula
formula for
for replacing
replacing each
each
character
character ‘p’
‘p’ of
of the
the plaintext
plaintext with
with aa
character
character ‘c’
‘c’ of
of the
the ciphertext
ciphertext can
can
be
be expressed
expressed as:as:
cc =
 =EE33(p
(p )) =
= (p
(p +
+ 3)
3) mod
mod 26
26
 Cipher classification/classical
Ciphers/substitution

A
A more
more general
general version
version of
of this
this
cipher
cipher that
that allows
allows for
for any
any degree
degree of
of
shift:
shift:
cc =
 =EEkk(p
(p )) =
= (p
(p +
+ k)
k) mod
mod 26
26
The
The formula
formula for
for decryption
decryption would
would
be
be
p
 p=
=DDkk(c
(c )) =
= (c
(c -- k)
k) mod
mod 26
26
In
In these
these formulas
formulas

 ‘k’
‘k’ is
is the
the secret
secret key.
key. The
The symbols
symbols ’E’
’E’
and
and ’D’
’D’ stand
stand for
for Encryption
Encryption and
and
Decryption
Decryption respectively,
respectively, and
and pp and
and cc
 Cipher classification/classical
Ciphers/substitution

Properties
Properties of
of encryption
encryption
function
function

It
It is
is computationally
computationally infeasible
infeasible to
to
find
find the
the key
key K K when
when given
given the
the
plaintext
plaintext P
P and
and associated
associated
ciphertext
ciphertext C=C= EEKK (p)
(p)

It
It should
should also
also be
be computationally
computationally
infeasible
infeasible toto find
find another
another key
key k’
k’
such
such as
as EEKK(p)
(p) ==EEKK’(p).
(p). Uniqueness.
Uniqueness.
’
 Cipher classification/classical
Ciphers/substitution
Caesar
Caesar Cipher
Cipher substitution
substitution is
is
based
based on on aa monoalphabetic
monoalphabetic
substitution
substitution and
and plyalphatic
plyalphatic
substitution
substitution
Monoalphabetic:
Monoalphabetic:
●
●ItIt only
only uses
uses one
one alphabet.
alphabet.
Plyalphatic:
Plyalphatic:
●
●An
An advanced
advanced substitution
substitution ciphers
ciphers
use
use two
two or
or more
more alphabets
alphabets
●
●The
The plaintext
plaintext of
of each
each letter
letter is
is
transformed
transformed into
into its
its corresponding
corresponding
letters based on its order of
 Cipher classification/classical
Ciphers/substitution
Example
Example let
let us
us see
see how
how the
the word
word TEXT
TEXT
is
is changed
changed
Plaintext:
Plaintext:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Substitution
Substitution cipher
cipher 11
DEFGHIJKLMNOPQRSTUVWXYZABC
DEFGHIJKLMNOPQRSTUVWXYZABC
Substitution
Substitution cipher
cipher 22
GHIJKLMNOPQRSTUVWXYZABCDEF
GHIJKLMNOPQRSTUVWXYZABCDEF
Substitution
Substitution cipher
cipher 33
JKLMNOPQRSTUVWXYZABCDEFGHI
JKLMNOPQRSTUVWXYZABCDEFGHI
Substitution
Substitution cipher
cipher 44
MNOPQRSTUVWXYZABCDEFGHIJKL
 Cipher classification/classical
Ciphers/substitution
Vigenere
Vigenere ciphers-
ciphers- early
early example:
example:
Uses
Uses aa keyword
keyword or or phrase
phrase in
in
conjunction
conjunction with
with aa lookuptable
lookuptable
(known
(known as as Vigenere
Vigenere Tableau)
Tableau) toto
encrypt
encrypt aa message
message
●● For
For example
example

 Plaintext
Plaintext message:
message:
•• BIG
BIG SECRET
SECRET

 Keyword
Keyword
•• Lock
Lock

 Keyword
Keyword extended
extended to
to match
match length
length of
of
message
message
•• Loc
Loc klockl
klockl
•• BIG
BIG SECRET
SECRET

 The
The plaintext
plaintext letter
letter and
and its
its associated
associated key
key
Cipher classification/classical
Ciphers/substitution
 Cipher classification/classical
Ciphers/Transposition
Columnar
Columnar Transposition
Transposition ciphers-
ciphers- early
early
example:
example:
Transposition
Transposition (permutation)
(permutation)
ciphers
ciphers
●
●The
The order
order of
of the
the characters
characters in
in the
the
original
original message
message is
is rearranged
rearranged
CIPHER
CIPHER might
might become
become REHPIC
REHPIC
In
In aa columnar
columnar transposition,
transposition, aa
plaintext
plaintext message
message is is transposed
transposed into
into
several
several columns
columns
Ciphertext
Ciphertext isis produced
produced byby reading
reading the
the
resulting
resulting rows
rows in
in sequence
sequence
 Cipher classification/classical
Ciphers/Transposition
Example
Example with with 22 columns:
columns:
●● Plainaintext:
Plainaintext: SECRET
SECRET
●● Plaintext
Plaintext arranged
arranged into
into 22 columns:
columns:
•• SR
SR
•• EE
EE
•• CT
CT
●● Ciphertext:
Ciphertext: sreect
sreect
●● The
The key
key in
in aa columnar
columnar transposition
transposition is is
the
the number
number of of columns!
columns!
•• In
In the
the example
example above,
above, the
the key
key is
is 22
 Cipher classification/classical
Ciphers/Transposition
Rail-Fece
Rail-Fece Transposition
Transposition ciphers-
ciphers- early
early
example:
example:
In rail-fence transposition, a plaintext
In rail-fence transposition, a plaintext
message
message isis transposed
transposed into
into several
several rows
rows
Ciphertext
Ciphertext is is produced
produced by by reading
reading the
the
resulting
resulting columns
columns inin sequence
sequence

Example
Example with
with 22 rails
rails (rows):
(rows):
●● Plaintext:
Plaintext: THEBIGBANGTHEORY
THEBIGBANGTHEORY
●● Plaintext
Plaintext arranged
arranged into
into 22 rows:
rows:

THEBIGBA
THEBIGBA

NGTHEORY
NGTHEORY
●● Ciphertext:
Ciphertext: tnhgetbhiegobray
tnhgetbhiegobray
 Ciphers/Attack

Types
Types of
of attacks
attacks

The
The attacker
attacker has has only
only the the
ciphertext
ciphertext and and his
his goal
goal is
is to
to find
find
the
the corresponding
corresponding plaintext
plaintext

The
The attacker
attacker has has aa ciphertext
ciphertext and
and
the
the corresponding
corresponding plaintext
plaintext and
and
his
his goal
goal is
is to
to find
find the
the key
key
A
A good
good cryptosystem
cryptosystem protects
protects
against
against all
all types
types of of attacks
attacks
Attackers
Attackers use use both
both Mathematics
Mathematics
and
and Statistics
Statistics
 Ciphers/Attack
Intruders
Intruders

Eavesdropping
Eavesdropping (listening/spying
(listening/spying the
the
message)
message)

An intruder
An intruder may may try try to
to read
read the
the
message
message

If
If it
it is
is well
well encrypted
encrypted thethe intruder
intruder will
will
not
not know
know thethe content
content

However
However,, just just the
the fact
fact the
the intruder
intruder
knows
knows that that there
there is
is communication
communication may may
be
be aa threat
threat (Traffic
(Traffic analysis)
analysis)

Modification
Modification

Modifying
Modifying aa plaintext
plaintext is
is easy,
easy, but
but
modifying
modifying encrypted
encrypted messages
messages is
is more
more
 Ciphers/Attack

Intruders
Intruders
Cipher classification /Modern Ciphers

There
There are
are two
two fundamentally
fundamentally
different
different cryptographic
cryptographic
systems
systems

Symmetric
Symmetric cryptosystem/
cryptosystem/ Private
Private
key
key

Asymmetric
Asymmetric cryptosystem/
cryptosystem/ Public
Public
key
key
Cipher classification /Modern
Ciphers
Symmetric
Symmetric Cryptosystem
Cryptosystem
Also
Also called
called secret-key/private-key
secret-key/private-key
cryptosystem
cryptosystem
The
The same
same keykey is
is used
used to
to encrypt
encrypt and
and
decrypt
decrypt aa message
message
P
 P=
=DDKK [E
[EKK (P)
(P) ]]
Have
Have been
been used
used forfor centuries
centuries in
in aa variety
variety
of
of forms
forms
The
The key
key has
has to
to bebe kept
kept secret
secret
The
The key
key has
has to
to bebe communicated
communicated using
using aa
secure
secure channel
channel
They
They are
are still
still in
in use
use in
in combination
combination with
with
Cipher classification /Modern
Ciphers
Asymmetric
Asymmetric Cryptosystem
Cryptosystem
Also
Also called
called public-key
public-key cryptosystem
cryptosystem

keys
keys for
for encryption
encryption and
and decryption
decryption are
are different
different but
but
form
form aaunique
unique pair
pair
PP =
 =DDKD [E
KD
[EKE (P)
KE (P) ]]

Only
Only one
one of
of the
the keys
keys need
need to
to be
be private
private while
while the
the
other
other can
can be
be public
public
Invented
Invented by by Diffie
Diffie and
and Hellman
Hellman in in 1976
1976
Uses
Uses Mathematical
Mathematical functions
functions whose
whose inverse
inverse isis not
not
known
known by by Mathematicians
Mathematicians of of the
the day
day
It
It is
is aa revolutionary
revolutionary concept
concept since
since itit avoids
avoids the
the
need
need of of using
using aa secure
secure channel
channel to to communicate
communicate
the
the key
key
It
It has
has made
made cryptography
cryptography available
available forfor the
the general
general
public
public and and made
made many
many of of today’s
today’s on-line
on-line
 Cipher classification /Modern
Ciphers
Public-key
Public-key Cryptosystem
Cryptosystem
Which
Which one
one ofof the
the encryption
encryption or
or
decryption
decryption key
key is is made
made public
public
depends
depends on
on the
the use
use of
of the
the key
key

If
If Hana
Hana wants
wants to
to send
send aa confidential
confidential
message
message to
to Ahmed
Ahmed

She encrypts
She encrypts thethe message
message using
using Ahmed’s
Ahmed’s
public
public key
key

Send
Send the
the message
message

Ahmed
Ahmed willwill then
then decode
decode it
it using
using his
his own
own
private
private key
key

On
On the
the other
other hand,
hand, if
if Ahmed
Ahmed needs
needs to
to
make
make sure
sure that
that aa message
message sent
sent by
by Hana
Hana
 Cipher classification /Modern
Ciphers
Public-key
Public-key Cryptosystem
Cryptosystem
Using
Using digital
digital signature
signature

Hana
Hana has
has to
to first
first encrypt
encrypt aa digital
digital
signature
signature using
using her
her private
private key
key

Then
Then encrypt
encrypt the
the message
message (signature
(signature
included)
included) with
with Ahmed’s
Ahmed’s public
public key
key

Sends
Sends the
the encrypted
encrypted message
message to
to Ahmed
Ahmed

Ahmed
Ahmed decrypts
decrypts the
the message
message using
using his
his
private
private key
key

Ahmed
Ahmed then
then decrypts
decrypts the
the signature
signature using
using
Hana’s
Hana’s public
public key
key

IfIf successful,
successful, he
he insures
insures that
that it
it comes
comes
 Cipher classification /Modern
Ciphers
Public-key
Public-key Cryptosystem:
Cryptosystem: Example
ExampleRSA
RSA
RSA
RSA is is from
from R. R. Rivesh,
Rivesh, A. A. Shamir
Shamir and and L.L.
Aldermen
Aldermen
Principle:
Principle: No No mathematical
mathematical method
method is is yet
yet known
known
to
to efficiently
efficiently find
find the
the prime
prime factors
factors ofof large
large
numbers
numbers
In
In RSA,RSA, the the private
private and
and public
public keyskeys areare
constructed
constructed from from veryvery large
large prime
prime numbers
numbers
(consisting
(consisting of of hundred
hundred of of decimal
decimal digits)
digits)
One
One of
of the
the keys
keys can
can be
be made
made public
public
Breaking
Breaking RSA RSA is is equivalent
equivalent toto finding
finding the
the prime
prime
factors:
factors: this
this is is know
know to to bebe computationally
computationally
infeasible
infeasible
It
It is
is only
only the
the person
person who
who has
has produced
produced the the keys
keys
from
from thethe prime
prime number
number whowho can
can easily
easily decrypt
decrypt
 Cipher classification /Modern
Ciphers
Public-key Cryptosystem: Average
Public-key Cryptosystem: Average time
time
required
required for
for exhaustive
exhaustive key
key search
search

Key Number of Time

Size Alternative required at
(bits) Keys 106
Decryption/µs
32 232 = 4.3 x 2.15
109 milliseconds
56 256 = 7.2 x 10 hours
1016
 Cipher classification /Modern
Ciphers
Public-key
Public-key Cryptosystem
Cryptosystem

Summary
Summary

AA pair
pair of
of keys
keys (private,
(private, public)
public)

If
If you
you have
have the
the private
private key,
key, you
you
can
can easily
easily decrypt
decrypt whatwhat is
is
encrypted
encrypted byby the
the public
public key
key

Otherwise,
Otherwise, itit is
is computationally
computationally
infeasible
infeasible to
to decrypt
decrypt what
what has
has
been
been encrypted
encrypted by by the
the public
public key
key
 Cipher classification /Modern
Ciphers
Hash
Hash functions
functions

One
One application
application of of cryptography
cryptography in in
distributed
distributed systems
systems isis the
the use
use ofof hash
hash
functions
functions
AA hash
hash function
function H H takes
takes aa message
message m m of
of
arbitrary
arbitrary length
length and
and produces
produces aa bit
bit string
string
h,
h, h=
h= HH (m)
(m)
When
When thethe hash
hash value
value hh is
is sent
sent with
with the
the
message
message m, m, itit enables
enables to to determine
determine
whether
whether m m has
has been
been modified
modified or
or not
not
It
It is
is similar
similar toto cyclic-redundancy
cyclic-redundancy checkcheck
(CRC)
(CRC) and
and Check
Check sum
sum
 Cipher classification /Modern
Ciphers
Hash
Hash functions
functions

Properties
Properties of
of hash
hash functions
functions

 One-way
One-way function:
function: It
It is
is computationally
computationally
infeasible
infeasible to
to find
find m
m that
that corresponds
corresponds to
to
aa known
known output
output ofof hh

 Collision
Collision resistance
resistance

 Weak-collision resistance: It is
Weak-collision resistance: It is
computationally
computationally infeasible,
infeasible, given
given mm and
and H,
H, to
to
find
find m’
m’ ≠
≠mm such
such that
that H(m)
H(m) = = H(m’)
H(m’)

 Strong-collision
Strong-collision resistance:
resistance: Given
Given H, H, it
it is
is
computationally
computationally infeasible
infeasible to
to find
find any
any two
two
different
different input
input values
values m m and
and m’,
m’, such
such that
that
H(m)
H(m) == H(m’)
H(m’)
 Cipher classification /Modern
Ciphers
DES
DES--Popular
PopularExample
Exampleof
of Symmetric
SymmetricCryptosystem
Cryptosystem
In
In 1973,
1973, the
the NBS
NBS (National
(National Bureau
Bureau of of Standards,
Standards, now
now
called
called NIST
NIST -- National
National Institute
Institute of
of Standards
Standards and
and
Technology)
Technology) published
published aa request
request for
for anan encryption
encryption
algorithm
algorithm that
that would
would meet
meet the
the following
following criteria:
criteria:
have
haveaahigh
highsecurity
securitylevel
level
be
beeasily
easilyunderstood
understood
not
notdepend
dependononthe
thealgorithm's
algorithm'sconfidentiality
confidentiality
be
beadaptable
adaptableand
andeconomical
economical
be
beefficient
efficientand
andexportable
exportable
In
In late
late 1974,
1974, IBM
IBM proposed
proposed "Lucifer",
"Lucifer", which
which
was
was then
then modified
modified byby NSA
NSA (National
(National Security
Security
Agency)
Agency) in in 1976
1976 toto become
become the
the DES
DES (Data
(Data
Encryption
Encryption Standard).
Standard). The
The DES
DES was
was approved
approved
by
by thethe NBS
NBS in in 1978.
1978. The
The DESDES waswas
standardized
standardized by by the
the ANSI
ANSI under
under the
the name
name of
of
 Cipher classification /Modern
Ciphers
DES-
DES- Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem…
…

DES
DES Utilizes
Utilizes block
block cipher,
cipher, which
which meansmeans thatthat
during
during thethe encryption
encryption process,
process, thethe plaintext
plaintext is is
broken
broken into
into fixed
fixed length
length blocks
blocks ofof 64
64 bits.
bits.
The
The key
key is
is 56
56 bits
bits wide.
wide. 8-bit
8-bit out
out of
of the
the total
total 64-
64-
bit
bit block
block key key isis used
used for for parity
parity check
check (for(for
example,
example, each
each byte
byte has
has anan odd
odd number
number of of bits
bits set
set
to
to 1).
1).
56-bit
56-bit keykey gives
gives 2256 (
56
( 7.2*10
7.2*1016)) possible
16
possible key key
DES
DES
variationsalgorithm
algorithm involves
involves carrying
carrying out
out
variations
combinations,
combinations, substitutions
substitutions and and permutations
permutations
between
between the the text
text to
to bebe encrypted
encrypted and and the
the key,
key,
while
while making
making sure sure the the operations
operations can can be be
performed
performed in in both
both directions
directions (for
(for decryption).
decryption).
The
The combination
combination of
of substitutions
substitutions and
and
 Cipher classification /Modern
Ciphers
DES-
DES- Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem…
…

DES
DES was
was best
best suited
suited for
for implementation
implementation in in
hardware,
hardware, probably
probably to
to discourage
discourage
implementations
implementations in in software,
software, which
which tend
tend toto
be
be slow
slow by
by comparison
comparison during
during that
that time.
time.
Modern
Modern computers
computers are are so so fast
fast that
that
satisfactory
satisfactory software
software implementations
implementations for for
DES
DES are
are possible.
possible.
DES
DES is is the
the most
most widely
widely used
used symmetric
symmetric
algorithm
algorithm despite
despite claims
claims whether
whether 56 56 bits
bits is
is
long
long enough
enough toto guarantee
guarantee security.
security.
Using
Using current
current technology,
technology, 56-bit
56-bit key
key size
size is
is
vulnerable
vulnerable toto aa brute
brute force
force attack.
attack.
 Cipher classification /Modern
Ciphers
DES-
DES- Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem…
…

DES
DES Encryption
Encryption starts
starts with
with an
an initial
initial
permutation
permutation (IP) (IP) of
of the
the 64
64 input
input bits.
bits. These
These bits
bits
are
are then
then divided
divided into
into two
two 32-bit
32-bit halves
halves called
called LL
and
and R.R. The
The encryption
encryption then
then proceeds
proceeds through
through 16 16
rounds,
rounds, eacheach using
using the
the LL andand R R parts,
parts, andand aa
subkey.
subkey.
The
The R R and
and subkeys
subkeys areare processed
processed in in the
the so
so called
called
f-function,
f-function, andand exclusive-or
exclusive-or of of the
the output
output of of the
the
f-function
f-function with
with the
the existing
existing LL partpart to
to create
create thethe
new
new R R part.
part. The
The new
new LL part
part isis simply
simply aa copy
copy ofof
the
the incoming
incoming R R part.
part.
In
In the
the final
final round,
round, the
the LL and
and R R parts
parts are
are swapped
swapped
once
once more
more before
before the
the final
final permutation
permutation (FP) (FP)
producing
producing the the output
output block.
block.
Cipher classification /Modern
Ciphers

DES
DESAlgorithm
Algorithm--Overall
Overalland
andDetail
Detail
 Cipher classification /Modern
Ciphers
DES-
DES- Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem…
…

The
The f-function
f-function mixes
mixes the
the bits
bits of
of the
the R
R portion
portion
using
using the
the Subkey
Subkey for for the
the current
current round.
round. First
First
the
the 32-bit
32-bit R R value
value is is expanded
expanded to to 48
48 bits
bits
using
using aa permutation
permutation E. E. That
That value
value is
is then
then
exclusive-or'ed
exclusive-or'ed with
with the
the subkey.
subkey.
The
The 48
48 bits
bits are
are then
then divided
divided into
into eight
eight 6-bit
6-bit
chunks,
chunks, each
each of of which
which is is fed
fed into
into an
an S-Box
S-Box
that
that mixes
mixes the the bits
bits and
and produces
produces aa 4-bit
4-bit
output.
output. AA little
little bit
bit funny
funny operation!!
operation!!
Those
Those 4-bit
4-bit outputs
outputs areare combined
combined intointo aa 32-
32-
bit
bit value,
value, andand permuted
permuted once once again
again to to
produce
produce the
the f-function
f-function output.
output.
 Cipher classification /Modern
Ciphers
S-Box
TheS-Box
The

IfIf SS1 isis the

the function
function defined
definedininthis
thistable
tableand
and BBisisaablock
blockofof66bits,
bits,then
then SS1(B) is determined as
1 1(B) is determined as

follows:
follows:The
Thefirst
firstand
andlast
lastbits
bitsofof BBrepresent
representininbase
base22aanumber
numberininthe
thedecimal
decimalrange
range00toto33(or
(or
binary
binary0000toto11).
11).Let
Letthat
thatnumber
numberbe bei.i.The
Themiddle
middle44bits
bitsofofBBrepresent
representininbase
base22aanumber
numberininthe
the
decimal
decimalrange
range00toto15
15(binary
(binary0000
0000toto1111).
1111).Let
Letthat
thatnumber
numberbe bej.j.Look
Lookupupininthe
thetable
tablethe
thenumber
number
ininthe
thei-th
i-throw
rowand
andj-th
j-thcolumn.
column.ItItisisaanumber
numberininthe
therange
range00toto15
15andandisisuniquely
uniquelyrepresented
representedby
byaa
44bit
bitblock.
block.That
Thatblock
blockisisthe
theoutput
output SS1(B) of S1 for the input B. For example, for input block B =
1(B) of S1 for the input B. For example, for input block B =

011011
011011the
thefirst
firstbit
bitisis"0"
"0"and
andthe
thelast
lastbit
bit"1"
"1"giving
giving01
01as
asthe
therow.
row.This
Thisisisrow
row1.1.The
Themiddle
middlefour
fourbits
bits
are
are"1101".
"1101".This
Thisisisthethebinary
binaryequivalent
equivalentofofdecimal
decimal13,
13,so
sothe
thecolumn
columnisiscolumn
columnnumber
number13.
13.InInrow
row
1,1,column
column13
13appears
appears5.5.This
Thisdetermines
determinesthe
theoutput;
output;55isisbinary
binary 0101,
0101,so
sothat
thatthe
theoutput
outputisis0101.
0101.
Hence S (011011) = 0101.
DES-
DES-Algorithm,
Algorithm,the f-function
thef-function
Ciphers
Cipher classification /Modern
 Cipher classification /Modern
Ciphers
DES-
DES- Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem…
…

To
To generate
generate the
the subkeys,
subkeys, start
start with
with the
the 56-
56-
bit
bit key
key (64
(64 bits
bits if if you
you include
include the
the parity
parity
bits).
bits). These
These are
are permuted
permuted and and divided
divided into
into
two
two halves
halves called
called C C and
and D.
D.
For
For each
each round,
round, CC and
and D D are
are each
each shifted
shifted left
left
circularly
circularly one
one or
or two
two bits
bits (the
(the number
number of of bits
bits
depending
depending on on the
the round).
round).
The
The 48-bit
48-bit subkey
subkey is is then
then selected
selected from
from the
the
current
current CC and
and DD bits.
bits.
Cipher classification /Modern
Ciphers

DES-
DES-Algorithm
Algorithm--Key
KeySchedule
Scheduleand
andSubkey
SubkeyGeneration
Generation
 Cipher classification /Modern
Ciphers
DES-
DES-Permutation
Permutationprinciples
principles
Initial Permutation (IP) Final Permutation(FP)

IP IP-1
58 50 42 34 26 18 10 2 40 8 48 16 56 24 64 32
60 52 44 36 28 20 12 4 39 7 47 15 55 23 63 31
62 54 46 38 30 22 14 6 38 6 46 14 54 22 62 30
64 56 48 40 32 24 16 8 37 5 45 13 53 21 61 29
57 49 41 33 25 17 9 1 36 4 44 12 52 20 60 28
59 51 43 35 27 19 11 3 35 3 43 11 51 19 59 27
61 53 45 37 29 21 13 5 34 2 42 10 50 18 58 26
63 55 47 39 31 23 15 7 33 1 41 9 49 17 57 25
“First Bit of the output is taken from the 58th bit of the input, etc...”
 Cipher classification /Modern
Ciphers
DES-
DES-Permutation
Permutationprinciples
principles
Expansion/Permutation Contraction/Permuted Choice (PC-2)

The 32-bit half-block of data is expanded Selects/Extracts the 48-bit subkey for each
to 48 bits. round from the 56-bit key-schedule state.
E PC-2
32 1 2 3 4 5 14 17 11 24 1 5
4 5 6 7 8 9 3 28 15 6 21 10
8 9 10 11 12 13 23 19 12 4 26 8
12 13 14 15 16 17 16 7 27 20 13 2
16 17 18 19 20 21 41 52 31 37 47 55
20 21 22 23 24 25 30 40 51 45 33 48
24 25 26 27 28 29 44 49 39 56 34 53
28 29 30 31 32 1 46 42 50 36 29 32
DES-Algorithm,
DES- Algorithm,GGeneral
eneral depiction (W.
depiction (W.
Stallings)
Stallings)
Ciphers
Cipher classification /Modern
 Cipher classification /Modern
Ciphers
DES-
DES- Single
Singleround
roundof
ofDES
DESAlgorithm
Algorithm(W.
(W.Stallings)
Stallings)
 Cipher classification /Modern
Ciphers
DES-
DES- Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem…
…

Cracking:
Cracking: The The most
most basic
basic method
method of of attack
attack
for
for any
any cypher
cypher is is brute
brute force
force -- trying
trying every
every
possible
possible keykey in
in turn.
turn.
The
The length
length ofof the
the key
key determines
determines the the number
number
of
of possible
possible keys,
keys, and
and hence
hence the
the feasibility
feasibility of
of
the
the approach.
approach.
DES
DES is is not
not adequate
adequate withwith this
this regard
regard duedue to
to
its
its key
key size
size
In
In academia,
academia, various
various proposals
proposals for for aa DES-
DES-
cracking
cracking machine
machine were
were advanced.
advanced.
In
In 1977,
1977, Diffie
Diffie and
and Hellman
Hellman proposed
proposed aa machine
machine
costing
costing anan estimated
estimated US$20US$20 million
million which
which could
could
find
find aa DES
DES key
key in
in aa single
single day.
day.
By 1993, Wiener had proposed a key-search
 Cipher classification /Modern
Ciphers
DES-
DES- Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem…
…

The
The vulnerability
vulnerability of of DES
DES was was practically
practically
demonstrated
demonstrated in in 1997,
1997, where
where RSARSA Security
Security
sponsored
sponsored aa series
series ofof contests,
contests, offering
offering aa
$10,000
$10,000 prize
prize to
to the
the first
first team
team that
that broke
broke aa
message
message encrypted
encrypted with
with DES
DES for
for the
the contest.
contest.
That
That contest
contest was
was won
won by
by the
the
DESCHALL
DESCHALL Project,
Project, ledled by by Rocke
Rocke Verser,
Verser,
Matt
Matt Curtin,
Curtin, and
and Justin
Justin Dolske,
Dolske, using
using idle
idle
cycles
cycles of
of thousands
thousands of of computers
computers across
across the
the
Internet.
Internet.
The
The feasibility
feasibility of
of cracking
cracking DES DES quickly
quickly was
was
demonstrated
demonstrated in in 1998
1998 when
when aa custom
custom DES-DES-
cracker
cracker was
was built
built by
by the
the
 Cipher classification /Modern
Ciphers
DES-
DES- Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem…
…
The EFF's
US$250,000
DES cracking machi
ne
contained 1,856
custom chips and
could brute force a
DES key in a matter
of days - the photo
shows a DES Cracker
circuit board fitted
with several Deep
Crack chips.
 Cipher classification /Modern
Ciphers
DES-
DES- Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem…
…

AA variant
variant of
of DES,
DES, Triple
Triple DES
DES (3-DES),
(3-DES), provides
provides enhanced
enhanced
security
security by
by executing
executing the
the core
core algorithm
algorithm three
three times
times in
in aa
row.
row.
With
With triple
triple length
length key
key of
of three
three 56-bit
56-bit keys
keys K1,
K1, K2
K2 &
& K3,
K3,
encryption
encryption is:is:

 Encrypt
Encryptwith
withK1
K1

 Decrypt
Decryptwith
withK2
K2

 Encrypt with K3
Encrypt with K3
Decryption
Decryption is
is the
the reverse
reverse process:
process:

 Decrypt
Decryptwith
withK3
K3

 Encrypt with K2
Encrypt with K2
Setting

 K3
Decrypt
Setting equal
K3with
Decrypt K1
equal
with K1to
toK1
K1in
inthese
theseprocesses
processesgives
givesus
usaadouble
double
length
lengthkey
keyK1,
K1,K2.
K2.
Setting
SettingK1,
K1,K2K2and
andK3K3all
allequal
equaltotoKKhas
hasthe
thesame
sameeffect
effectas
as
using
usingaasingle-length
single-length(56-bit
(56-bitkey).
key).
Thus
Thus it
it is
is possible
possible for
for aa system
system using
using triple-DES
triple-DES toto be
be
compatible with a system using single-DES.
 Cipher classification /Modern
Ciphers
AES
AES--Popular
PopularExample
Exampleof
of Symmetric
SymmetricCryptosystem
Cryptosystem

What
What is
is AES?
AES?
●
●The
The AES
AES algorithm
algorithm (known
(known as
as Rijndael
Rijndael
algorithm)
algorithm) is
is aa symmetric
symmetric block
block cipher
cipher
algorithm
algorithm that
that takes
takes aa block
block size
size of
of 128
128 bit
bit
and
and converts
converts them
them into
into ciphertext
ciphertext using
using
key
key of
of 128,192,
128,192, and
and 256
256 bits.
bits.
●
●ItIt implemented
implemented in
in software
software and
and hardware
hardware
to encrypt sensitive data throughout the
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem

What
What is
is feature
feature of
of AES?
AES?
●
●ItIt uses
uses permutation
permutation and
and substitution
substitution
●
●AA single
single key
key expanded
expanded to
to bebe used
used in
in
multiple
multiple rounds.
rounds.
●
● AES
AES performs
performs on
on byte
byte data,
data, instead
instead of of bit
bit
data.
data.
●
●Number
Number ofof rounds
rounds depend
depend on
on key
key length
length
128-bit
128-bit key
key length
length ----------->
-----------> 10
10
round
round
192-bit
192-bit key
key length
length ----------->
-----------> 12
12
round
round
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem

How
How does
does AES
AES Work?
Work?
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

●
●Every
Every thing
thing is
is stored
stored in
in aa 4X4
4X4 matrix
matrix format,
format,
known
known asas state
state array
array
●
●Each
Each round
round takes
takes state
state array
array as
as input
input and
and gives
gives
similar
similar output
output
●
●16-byte
16-byte matrix,
matrix, with
with each
each cell
cell representing
representing one
one
byte
byte
●
●44 bytes=
bytes= 11 word,
word, so
so each
each state
state array
array has
has words
words
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem

Key
Key Expansion:
Expansion:
The
The key
key is
is expanded
expanded toto n+1
n+1 rounds
rounds with
with nn
being
being number
number of round.
K0 K1of round.
K2 K3
K4 K5 K6 K7
K8 K9 K10 K11
K12 K13 K14 K15
44 word
word in
in each
each key
key
Each
Each key
key isis used
used for
for aa single
single round
round
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem
 Cipher classification /Modern
Ciphers
AES
AES–Byte
–ByteSubstitution
SubstitutionBox
Box
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem

Step1:
Step1: Adding
Adding the
the round
round Key:
Key:
●
●Plain
Plain text
text is
is stored
stored in
in aa state
state array
array and
and
XOR’d
XOR’d with
with KK0.0.
●
● performed
performed onlyonly once
once per
per block
block
●
●Will
Will be
be performed
performed once
once again
again at
at the
the end
end of
of
each
each round.
round.
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem

Step2:
Step2: Byte
Byte substitution
substitution (Sub-Bytes):
(Sub-Bytes):
●
● Clever
Clever lookup
lookup table
table to
to map
map one
one byte
byte to
to another.
another.
●
● Works
Works asas aa substitution
substitution table
table
●
● Each
Each byte
byte is is converted
converted to to hexadecimal,
hexadecimal, with
with 22
equal
equal parts
parts
●
● First
First part
part is
is the
the row,
row, second
second part
part is
is columns.
columns.
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem

Step3:Shift
Step3:Shift Rows
Rows
●
● Shifting
Shifting row
row elements
elements among
among each
each other
other
●
● Increase
Increase complexity
complexity of
of algorithm
algorithm
●
● First
First row
row is
is to
to be
be skipped,
skipped, second
second row
row moves
moves 11
place,
place, third
third row
row moves
moves 22 places
places and
and last
last row
row moves
moves
33 places.
places.
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem

Step4:
Step4: Mix
Mix Columns:
Columns:
●
● Multiply
Multiply each
each column
column with with aa constant
constant matrix.
matrix.
●
● Resultant
Resultant matrix
matrix forms
forms the
the new
new column
column
●
● Not
Not to
to be
be done
done in
in the
the last
last round
round
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem

Step5:Add
Step5:Add round
round key:
key:
●
● The
The expanded
expanded key key is
is used
used with
with thethe result
result matrix
matrix
●
● IfIf it’s
it’s last
last round,
round, the
the result
result is
is ciphertext.
ciphertext.
●
● IfIf not
not the
the last
last round,
round, result
result is
is input
input for
for next
next round.
round.
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem

Step1:
Step1: Add
Add Round-0
Round-0 with
with plaintext
plaintext
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem

Step2:
Step2: Substitution
Substitution ofof Byte:
Byte:
●
●Substitute
Substitute each
each byte
byte with
with corresponding
corresponding
element
element in
in the
the Substitution
Substitution Box
Box
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem

Step
Step 3:
3: Shift
Shift Row:
Row:
●
●First
First row
row shifted
shifted to
to the
the left
left by
by 00 place,
place,
second
second rowrow by
by 11 places,
places, third
third row
row by
by 22
places
places and
and last
last row
row by
by 33 places.
places.
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem

Step
Step 4:
4: Mix
Mix Columns:
Columns:
●
●Multiply
Multiply the
the state
state array
array with
with constant
constant
matrix.
matrix.
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem

Step5:
Step5: Add
Add Round
Round key-1:
key-1:
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem
 Cipher classification /Modern
Ciphers
AES
AES--Example
Exampleof
ofSymmetric
SymmetricCryptosystem
Cryptosystem

●
●The
The Difference
Difference Between
Between DES
DES and
and AES:
AES:
Cipher classification /Modern
Ciphers

DES and AES are

Modern
Symmetric key
cryptosystem
 Cipher classification /Modern
Ciphers
RSA-
RSA- Example
Exampleof
ofAsymmetric/Public-Key
Asymmetric/Public-KeyCryptosystem
Cryptosystem

The
The RSA
RSA algorithm
algorithm

 Used
Used for
for both
both public
public key
key encryption
encryption and
and
digital
digital signatures.
signatures.

 Security
Security is is based
based on on the
the difficulty
difficulty of
of
factoring
factoring large
large integers.
integers.

Major
Major Activities
Activities

 Key
Key Generation
Generation (Algorithm)
(Algorithm)

 Encryption
Encryption

 Digital
Digital signing
signing

 Decryption
Decryption

 Signature
Signature verification
verification
 Cipher classification /Modern
Ciphers
RSA-
RSA- Key
KeyGenerating
GeneratingAlgorithm
Algorithm

1.
1.Generate
Generate two
two large
large random
random primes,
primes, pp and
and qq
2.
2.Compute
Compute nn == pq
pq and
and (φ)
(φ) phi
phi =
= (p-1)(q-1)
(p-1)(q-1)
3.
3.Choose
Choose an
an integer
integer e,e, 11 <
< ee <
< φ,
φ, such
such that
that
gcd(e,
gcd(e, phi)
phi) =
= 11
4.
4.Compute
Compute the the secret
secret exponent
exponent d,d, 11 <
< dd <
< φ,
φ,
such
such that
that
dd =
= ee-1 mod
-1
mod φ φ ,, i.e.
i.e. φ
φ divides
divides (ed-1)
(ed-1)
5.
5.The
The public
public key
key is is (n,
(n, e)
e) and
and the
the private
private key
key is
is
(n,
(n, d).
d).

 Keep
Keep all
all the
the values
values d,
d, p,
p, qq and
and φ
φ secret
secret

 n is known as the modulus
n is known as the modulus

 ee is
is known
known as
as the
the public
public exponent
exponent or
or encryption
encryption
exponent
exponent
 Cipher classification /Modern
Ciphers
RSA-
RSA- Encryption
Encryption

Sender
Sender A
A does
does the
the following
following

 Obtains
Obtains the
the recipient
recipient B's
B's public
public key
key (n,
(n, e)
e)

 Represents
Represents thethe plaintext
plaintext message
message as as aa
positive
positive integer
integer m
m

 Computes
Computes the ciphertext c = m mod
the ciphertext c = mee
mod nn

 Sends
Sends the
the ciphertext
ciphertext cc to
to B
B
RSA-
RSA- Decryption
Decryption

Recipient
Recipient B
B does
does the
the following
following

 Uses
Uses his
his private
private key
key (n,
(n, d)
d) to
to compute
compute m
m==
ccdd mod
mod nn

 Extracts
Extracts the
the plaintext
plaintext from
from the
the message
message
 Cipher classification /Modern
Ciphers
RSA-
RSA- Digital
Digitalsigning
signing
Sender
Sender AA does
does the
the following
following

 Creates
Creates aa message
message digestdigest ofof the
the information
information to
to
be
be sent
sent

 Represents
Represents thisthis digest
digest as
as an
an integer
integer m m between
between 00
and
and n-1
n-1

 Uses
Uses her
her private
private key key (n,
(n, d)d) to
to compute
compute the
the
signature
signature
ss =
= m
m
dd
mod
mod n.
n.
RSA-
RSA-
 Signature verification
Signature verification
 Sends
Sends this
this signature
signature ss to to the
the recipient,
recipient, B.
B.
Recipient
Recipient B B does
does thethe following
following

 Uses
Uses sender
sender A's
A's public
public key
key (n,
(n, e)
e) to
to compute
compute integer
integer vv
== sse mod
e
modnn
 Extracts
 Extracts the
the message
message digest
digest from
fromthis
this integer
integer
 Independently
 Independently computes
computes the
the message
message digest
digest of
of the
the
information
information that
that has
has been
been signed
signed

 If both message digests are identical, the signature is
 Cipher classification /Modern
Ciphers
RSA-
RSA- Key
KeyGeneration
GenerationSimple
SimpleExample
Example
1.
1.Select
Select primes
primes p=11,
p=11, q=3.
q=3.
2.
2.nn == pq
pq =
= 11*3
11*3 == 33
33
phi
phi = = (p-1)(q-1)
(p-1)(q-1) = = 10*2
10*2 = = 2020
3.
3.Choose
Choose e=3 e=3
Check
Check gcd(e,
gcd(e, p-1)
p-1) == gcd(3,
gcd(3, 10) 10) =
= 11 (i.e.
(i.e. 33 and
and 10
10 are
are
relatively
relatively prime
prime -- have
have no no common
common factors
factors except
except 1)1)
and
and check
check gcd(e,
gcd(e, q-1)
q-1) = = gcd(3,
gcd(3, 2) 2) == 1,
1,
therefore
therefore gcd(e,
gcd(e, phi)
phi) = = gcd(e,
gcd(e, (p-1)(q-1))
(p-1)(q-1)) = = gcd(3,
gcd(3, 20)
20)
== 11
4.
4.Compute
Compute dd (1<d<phi)
(1<d<phi) such such thatthat dd =
= ee-1 mod
-1
mod phiphi == 33-1
-1

mod
mod 20 20
i.e.
i.e. find
find aa value
value for
for dd such
such thatthat phi
phi divides
divides ed-1
ed-1 (20
(20
divides
divides 3d-1.)
3d-1.)
Simple
Simple testing
testing (d(d =
= 2,2, 33 ...)
...) gives
gives dd == 77
Check:
Check: ed-1ed-1 = = 3*7
3*7 -- 11 == 20,
20, which
which is is divisible
divisible byby phi
phi
(20).
(20).
 Cipher classification /Modern
Ciphers
Given
Given
Public
Public key
key == (n,
(n, e)
e) == (33,
(33, 3)
3)
Private
Private key
key =
= (n,
(n, d)
d) =
= (33,
(33, 7)
7)

RSA-
RSA- Encryption
EncryptionExample
Example
Now
Now say
say we
we want
want to
to encrypt
encrypt the
the message
message m
m
=
= 77

 cc =
=mme mod
mod nn =
= 773 mod
mod 33
33 =
= 343
343 mod
mod 33
33 =
= 13
e 3
13

 Hence the ciphertext c = 13
Hence the ciphertext c = 13
RSA-
RSA- Decryption
DecryptionExample
Example
To
To check
check decryption
decryption we
we compute
compute

mm=
= ccd mod
mod nn =
= 13
137 mod
mod 33
33 =
= 77
d 7
 Cipher classification /Modern
Ciphers
RSA-
RSA- More
MoreMeaningful
MeaningfulExample
Example

Message:
Message: ATTACKxATxSEVEN
ATTACKxATxSEVEN
Grouping
Grouping the
the characters
characters into
into blocks
blocks of
of three
three and
and
computing
computing aa message
message representative
representative integer
integer for
for
each
each block:
block:

 ATT
ATT ACK
ACKXAT
XAT XSE
XSEVEN
VEN

 In
In the
the same
same way
way that
that aadecimal
decimal number
number can
can be
be
represented
representedas as the
the sum
sum of
of powers
powers of
of ten,
ten, e.g.
e.g. 135
135 == 11
xx 10
102 +
2
+33 xx 10
101 +
1
+5,5, we
we could
couldrepresent
represent our
our blocks
blocks of
of
three
three characters
characters in in base
base 26
26 using
usingA=0,
A=0, B=1,
B=1, C=2,
C=2, ...,
...,
Z=25
Z=25
ATT
ATT =
= 00 xx 26
262+
2
+ 1919 xx 26261 +
1
+ 19
19 = = 513
513
ACK
ACK == 00 xx 26
26 +
22
+ 22 xx 26
26 +
11
+ 1010 == 62
62
XAT
XAT =
= 23
23 xx 26
262 +
2
+ 00 xx 26
261 +
1
+ 19
19 == 15567
15567
XSE
XSE =
= 23
23 xx 26
26 +
22
+ 18
18 xx 26
26 +
11
+ 44 =
= 16020
16020
VEN
VEN == 21
21 xx 26
26 +
22
+ 44 xx 26
26 +
11
+ 13
13 = = 14313
14313
 Cipher classification /Modern
Ciphers
RSA-
RSA- More
MoreMeaningful
MeaningfulExample
Example––Key
KeyGeneration
Generation

1.
1.We
We "generate"
"generate" primes
primes p=137
p=137 and
and q=131
q=131
(we
(we cheat
cheat byby looking
looking forfor suitable
suitable primes
primes
around
around √n)√n)
2.
2.nn == pq
pq = = 137*131
137*131 = = 17,947
17,947
phi
phi == (p-1)(q-1)
(p-1)(q-1) = = 136*130
136*130 = = 17680
17680
3.
3.Select
Select ee == 33
check
check gcd(e,
gcd(e, p-1)
p-1) = = gcd(3,
gcd(3, 136)
136) == 1,
1, OK
OK
and
and
check
check gcd(e,
gcd(e, q-1)
q-1) = = gcd(3,
gcd(3, 130)
130) == 1,
1, OK.
OK.
4.
4.Compute d = e mod phi = 3-1 mod
Compute d = e -1 mod phi = 3-1
-1
mod 17680
17680
== 11787.
11787.

 dd =
= ee-1 mod
mod phi
phi ,, i.e.
i.e. phi
phi divides
divides (ed-1)
-1
(ed-1)
 Cipher classification /Modern
Ciphers
Given
Given
Public
Public key
key == (n,
(n, e)
e) == (17947,
(17947, 3)
3)
Private
Private key
key =
= (n,
(n, d)
d) == (17947,
(17947, 11787)
11787)
RSA-
RSA- More
MoreMeaningful
MeaningfulExample
Example––Encryption/Decryption
Encryption/Decryption
To
To encrypt
encrypt the
the first
first integer
integer that
that represents
represents
"ATT“
"ATT“ (513),
(513), we
we have
have

 cc =
=mme mod
mod nn =
= 513
5133 mod
mod 17947
17947 =
= 8363
e 3
8363
We
We can
can verify
verify that
that our
our private
private key
key is
is valid
valid
by
by decrypting
decrypting

mm = c mod n = 836311787mod
= c mod n = 8363 mod 17947
17947 =
= 513
dd 11787
513
Overall,
Overall, our
our plaintext
plaintext is
is represented
represented by
by the
the set
set of
of
integers
integers mm

 (513,
(513, 62,
62, 15567,
15567, 16020,
16020, 14313)
14313)

 We
We compute
compute corresponding
correspondingcipher
cipher text
text integers
integers cc =
=m
e
me
mod
modnn
Cipher classification /Modern
Ciphers
Diffie-Hellman
Diffie-Hellman
To
To The
The first
first published
published public-key
public-key algorithm
algorithm
appeared
appeared in in the
the seminal
seminal paper
paper by
by Diffie
Diffie and
and
Hellman
Hellman that
that defined
defined public-key
public-key
cryptography
cryptography and and is
is generally
generally referred
referred toto as
as
Diffie-Hellman
Diffie-Hellman key key exchange.
exchange.
The
The purpose
purpose of of the
the algorithm
algorithm is
is to
to enable
enable
two
two users
users toto securely
securely exchange
exchange aa key
key that
that
can
can then
then be
be used
used for
for subsequent
subsequent encryption
encryption
of
of messages.
messages.
Cipher classification /Modern
Ciphers
Diffie-Hellman
Diffie-Hellman Key
Key Agreement
Agreement
 Cipher classification /Modern
Ciphers
The
The symmetric
symmetric (shared)
(shared) key key in
in the
the Diffie-
Diffie-
Hellman
Hellman method
method isis K
K== ggxymod
xy
mod p.
p.

Example: Assume
Example: Assume that
that gg =
= 77 and
and pp =
= 23.
23. The
The
steps
steps are
are as
as follows:
follows:
1.
1.Alice
Alice chooses
chooses xx = = 33 and
and calculates
calculates R1
R1 == 73
73
mod
mod 23
23 == 21.
21.
2.
2.Bob
Bob chooses
chooses yy = = 66 and
and calculates
calculates R2
R2 == 76
76
mod
mod 23
23 == 4.
4.
3.
3.Alice
Alice sends
sends the
the number
number 2121 to
to Bob.
Bob.
4.
4.Bob
Bob sends
sends the
the number
number 44 toto Alice.
Alice.
5.
5. Alice
Alice calculates
calculates the
the symmetric
symmetric keykey K
K= = 43
43
mod
mod 23
23 == 18.
18.
6.
6.Bob
Bob calculates
calculates thethe symmetric
symmetric keykey KK= = 216
216
mod
mod 23
23 == 18.
18.
 Cipher classification /Modern
Ciphers
Digital
Digital Signature
Signature
 Cipher classification /Modern
Ciphers
Digital
DigitalSignature
Signaturefor
forMessage
MessageIntegrity
Integrityand
andConfidentiality
Confidentiality
If
If the
the hashes
hashes match
match then
then we
we have
have guaranteed
guaranteed
the
the following:
following:
●● Integrity:
Integrity: ifif m
m changed
changed then
then the
the hashes
hashes
would
would bebe different
different
●● Authenticity
Authenticity & & Non-repudiation:
Non-repudiation: A A is
is who
who
sent
sent the
the hash,
hash, as
as we
we used
used A’s
A’s public
public key
key to
to
reveal
reveal the
the contents
contents of of the
the signature
signature A A
cannot
cannot deny
deny signing
signing this,
this, nobody
nobody else
else has
has
the
the private
private key.
key.
Satisfies
Satisfies thethe requirements
requirements of of aa Digital
Digital
Signature
Signature
If
If we
we wanted
wanted to to further
further add
add confidentiality,
confidentiality,
then
then we we would
would encrypt
encrypt thethe sent
sent m m + +
signature
signature with
with recipient
recipient public
public key
key
 Cipher classification /Modern
Ciphers
Digital
Digital Signature
Signature for
forAssurance
Assurance
Consider
Consider the the situation
situation where
where Bob
Bob has
has just
just sold
sold
Alice
Alice something
something for for 500500 Birr
Birr through
through aa deal
deal that
that
is
is made
made by by E-mail
E-mail
Alice
Alice sends
sends anan E-mail
E-mail accepting
accepting toto pay
pay 500
500 Birr
Birr
Two issues need to be taken care
Two issues need to be taken care of in additionof in addition
to
to authentication
authentication
 Alice
Alice needs
needs toto be
be assured
assured that
that Bob
Bob will
will not
not modify
modify
the
the amount
amount and and show
show that
that Alice
Alice promised
promised to to pay
pay
more
more than
than 500
500 Birr
Birr
 Bob
Bob needs
needs toto be
be assured
assured that
that Alice
Alice will
will not
not deny
deny
that
that she
she sends
sends the
the message
message
If
If Alice signs the message digitally,
Alice signs the message digitally, the
the twotwo
issues
issues will
will be
be solved
solved
There
There are several ways
are several ways toto place
place digital
digital signatures
signatures
One
One popular
popular wayway is is to
to use
use public-key
public-key cryptosystem
cryptosystem
such
such asas RSA
RSA
 Cipher classification /Modern
Ciphers
Notation:
Notation: K
KXX-- :: Private
Private key
key of
of X
X K
KXX++ :: Public
Public
key
key of
of X
X
●
●Alice
Alice hashas toto first
first obtained
obtained aa signature
signature
using
using hash
hash algorithm
algorithm (h (h =
= H(m)
H(m) )) andand
encrypt
encrypt thethe digital
digital signature
signature using
using her her
private
private key
key (( K
KA-A (H(m))
-
(H(m)) ))
●
●Then
Then encrypt
encrypt the the (message
(message +signature
+signature
included)
included) with Bob’s public key (K BB (m,
with Bob’s public key (K ++
(m,
KK AA (H(m))))
--
(H(m))))
●
●Sends
Sends thethe encrypted
encrypted message
message toto Bob
Bob
●
●Bob
Bob decrypts
decrypts the
the message
message using
using his
his private
private
key
key
●
●Bob
Bob thenthen decrypts
decrypts the the signature
signature using
using
Alice’s
Alice’s public
public key key
 Cipher classification /Modern
Ciphers
Digital
Digital Signature
Signature Using
Using Message
Message Digest
Digest
Hash/Message
Hash/Message Digest:
Digest: Short
Short “signature”
“signature” ofof the
the
message,
message, 128–512
128–512 bits,
bits, that
that depend
depend onon entire
entire
message
message
It
It is
is extremely
extremely improbable
improbable that that unequal
unequal
messages
messages have
have same
same hash
hash
Example:
Example: MD5
MD5 (Message
(Message Digest
Digest version
version 5)
5)
 Cipher classification /Modern
Ciphers
Digital
Digital Signature
Signature Using
Using Public
Public Key
Key
Cryptosystem
Cryptosystem …
…
 Cipher classification /Modern
Ciphers
Key
Key Distribution
Distribution::Verifying
VerifyingSomeone’s
Someone’sPublic
PublicKey
Key
Even
Even with
with public-key
public-key cryptosystems
cryptosystems and and
digital
digital signatures,
signatures, we we still
still have
have the
the
problem
problem of of authentication:
authentication: binding
binding users
users
to
to keys.
keys.
Early
Early days
days articles
articles envisioned
envisioned phonebook-
phonebook-
like
like database
database with
with Name
Name and and Public
Public Key
Key
Problem:
entries.
Problem:
entries. How
How secure
secure is is that
that database
database
itself?
itself?
Attacker
Attacker can can put
put inin his
his own
own key
key for
for
someone
someone else,else, and
and start
start signing
signing fake
fake
contracts
contracts (and
(and even
even checks!).
checks!).
Maybe
Maybe we we can
can secure
secure the
the phonebook,
phonebook, but
but
then
then itit kills
kills the
the idea
idea of
of keys
keys widely
widely and
and
 Cipher classification /Modern
Ciphers
Key
Key Distribution:
Distribution: Problems
Problems
Distribution
Distribution of of aa key
key is
is aa difficult
difficult
matter!
matter!
For
For aa symmetric
symmetric cryptosystem,
cryptosystem, the the
initial
initial key
key must
must be
be communicated
communicated alongalong
aa secured
secured channel(?)
channel(?)
For
For public
public key,
key, we
we need
need aa body
body that
that
certifies
certifies the
the public
public key
key is
is that
that of
of the
the
party
party we
we need
need to
to communicate
communicate with
with
Solution:
Solution: Certification/Certificate
Certification/Certificate
Authority
Authority (CA)
(CA) that
that signs
signs (certifies)
(certifies) the
the
public
public key
key
 Cipher classification /Modern
Ciphers
Certification
Certification
The
The critical
critical thing
thing isis that
that the
the name
name in in the
the certificate
certificate
must
must match
match thethe alleged
alleged name.
name.
Common
Common solution
solution toto public
public key
key distribution
distribution today
today isis
to
to have
have trusted
trusted third
third party
party to
to sign
sign the
the user’s
user’s public
public
encryption
encryption key.
key.
AA certificate
certificate is is aa public
public key
key and
and some
some naming
naming “stuff”,
“stuff”,
digitally
digitally signed
signed by by someone
someone youyou trust
trust (third
(third party)
party) --
Certification
Certification Authority
Authority (CA).
(CA).
Remark:
Remark: JustJust because
because theythey are
are CAs
CAs doesn’t
doesn’t meanmean you
you
should
should trust
trust them.
them.
Resulting
Resulting certificate
certificate willwill contain
contain information
information like like
user’s
user’s name/ID,
name/ID, user’s
user’s public
public key,
key, name
name of of CA,
CA, start
start
date
date ofof certificate,
certificate, and
and length
length of
of time
time itit is
is valid.
valid.
User
User publishes
publishes certificate
certificate with
with the
the X.509
X.509 standard
standard
(for
(for formatting
formatting certificates).
certificates).
 Cipher classification /Modern
Ciphers
The
Theconcept
concept of
of session
sessionkeys
keysafter
after authentication
authentication

During
During the
the establishment
establishment ofof aa secure
secure
channel,
channel, after
after the
the authentication
authentication phase,
phase,
the
the communicating
communicating parties
parties use
use
session/temporary
session/temporary keys
keys
Benefits
Benefits

 The
The session
session key
key is
is safely
safely discarded
discarded when
when the
the
channel
channel is
is no
no longer
longer used
used
 When
 When aa keykey is is used
used very
very often
often it
it becomes
becomes
vulnerable.
vulnerable. Thus
Thus by by using
using the
the main
main key
key less
less
often,
often, we
we make
make them
them vulnerable
vulnerable
 Replay
 Replay attacks
attacks can
can be
be avoided
avoided
Authentication
Authentication keys
keys are
are often
often expensive
expensive to
to
replace
replace
 Cipher classification /Modern
Ciphers
PGP
PGP
 Cipher classification /Modern
Ciphers
Summary
Summary
Advantage
Advantage of
of private/secret
private/secret key
key
cryptography
cryptography is is that
that it
it provides
provides better
better
secrecy
secrecy butbut needs
needs prearranged
prearranged key key
exchange.
exchange.
Advantage
Advantage of of public-key
public-key cryptography
cryptography is is
that
that it
it allows
allows forfor secrecy
secrecy between
between two two
parties
parties whowho havehave notnot arranged
arranged in in
advance
advance to to have
have aa shared
shared keykey (or(or
trusted
trusted some
some third
third party
party to
to give
give it
it to
to
them)
them) and
and the
the disadvantage
disadvantage is
is overhead
overhead
Therefore,
Therefore,
and speed. in
in practice,
practice, hybrid
hybrid systems
systems
and public-key
use speed.
use public-key to to establish
establish session
session key
key
for private key !!