Unit II
Symmetric key Ciphers
Asymmetric key Ciphers
Conventional Encryption
Principles
• An encryption scheme has five ingredients:
– Plaintext
– Encryption algorithm
– Secret Key
– Ciphertext
– Decryption algorithm
• Security depends on the secrecy of the
key, not the secrecy of the algorithm
Conventional Encryption
Principles
Cryptography
• Classified along three independent
dimensions:
– The type of operations used for transforming
plaintext to ciphertext
– The number of keys used
• symmetric (single key)
• asymmetric (two-keys, or public-key encryption)
– The way in which the plaintext is processed
Feistel Cipher Structure
• Block size: larger block sizes mean greater
security
• Key Size: larger key size means greater
security
• Number of rounds: multiple rounds offer
increasing security
• Subkey generation algorithm: greater
complexity will lead to greater difficulty of
cryptanalysis.
• Fast software encryption/decryption: the
speed of execution of the algorithm
becomes a concern
Conventional Encryption
Algorithms
• Data Encryption Standard (DES)
– The most widely used encryption scheme
– The algorithm is reffered to the Data
Encryption Algorithm (DEA)
– DES is a block cipher
– The plaintext is processed in 64-bit
blocks
– The key is 56-bits in length
DES
• The overall processing at each
iteration:
– Li = Ri-1
– Ri = Li-1 F(Ri-1, Ki)
• Concerns about:
– The algorithm and the key length
(56-bits)
Triple DEA
• Use three keys and three executions
of the DES algorithm (encrypt-
decrypt-encrypt)
C = EK3[DK2[EK1[P]]]
• C = ciphertext
• P = Plaintext
• EK[X] = encryption of X using key K
• DK[Y] = decryption of Y using key K
• Effective key length of 168 bits
Triple DEA
Modes of Operation
block ciphers encrypt fixed size blocks
e.g., DES encrypts 64-bit blocks
need some way to en/decrypt arbitrary amounts of data in practice
NIST SP 800-38A defines 5 modes
have block and stream modes
to cover a wide variety of applications
can be used with any block cipher
Electronic Codebook Book (ECB)
message is broken into independent blocks that are encrypted
each block is a value which is substituted, like a codebook, hence name
each block is encoded independently of the other blocks
C = E (P )
i K i
uses: secure transmission of single values
Electronic
Codebook Book
(ECB)
Advantages and Limitations of ECB
message repetitions may show in ciphertext
if aligned with message block
particularly with data such graphics
or with messages that change very little, which become a code-book
analysis problem
weakness is due to the encrypted message blocks being independent
vulnerable to cut-and-paste attacks
main use is sending a few blocks of data
Cipher Block Chaining (CBC)
message is broken into blocks
linked together in encryption operation
each previous cipher block is chained with current plaintext block, hence name
use Initial Vector (IV) to start process
C = E (P XOR C )
i K i i-1
C = IV
-1
IV prevents same P from making same C
uses: bulk data encryption, authentication
Cipher Block
Chaining (CBC)
Advantages and Limitations of CBC
a ciphertext block depends on all blocks before it
any change to a block affects all following ciphertext blocks...
need Initialization Vector (IV)
which must be known to sender & receiver
if sent in clear, attacker can change bits of first block, by changing
corresponding bits of IV
hence IV must either be a fixed value (as in EFTPOS)
or derived in way hard to manipulate
or sent encrypted in ECB mode before rest of message
or message integrity must be checked otherwise
Stream Modes of Operation
block modes encrypt entire block
may need to operate on smaller units
real time data
convert block cipher into stream cipher
cipher feedback (CFB) mode
output feedback (OFB) mode
counter (CTR) mode
Cipher FeedBack (CFB)
message is treated as a stream of bits
added to the output of the block cipher
result is feed back for next stage (hence name)
standard allows any number of bits (1,8, 64 or 128 etc) to be feed back
denoted CFB-1, CFB-8, CFB-64, CFB-128, etc.
most efficient to use all bits in block (64 or 128)
C = P XOR E (C )
i i K i-1
C = IV
-1
uses: stream data encryption, authentication
s-bit
Cipher FeedBack
(CFB-s)
Advantages and Limitations of CFB
most common stream mode
appropriate when data arrives in bits/bytes
limitation is need to stall while do block encryption after every s-bits
note that the block cipher is used in encryption mode at both ends (XOR)
Output FeedBack (OFB)
message is treated as a stream of bits
output of cipher is added to message
output is then feed back (hence name)
O = E (O )
i K i-1
C = P XOR O
i i i
O = IV
-1
feedback is independent of message
can be computed in advance
Output FeedBack
(OFB)
Advantages and Limitations of OFB
needs an IV which is unique for each use
if ever reuse attacker can recover outputs...
OTP
can pre-compute
bit errors do not propagate
more vulnerable to message stream modification...
change arbitrary bits by changing ciphertext
sender & receiver must remain in sync
only use with full block feedback
subsequent research has shown that only full block feedback (ie CFB-64 or
CFB-128) should ever be used
Counter (CTR)
a “new” mode, though proposed early on
similar to OFB but encrypts counter value rather than any feedback value
O = E (i)
i K
C = P XOR O
i i i
must have a different key & counter value for every plaintext block (never
reused)
again, OTP issue
uses: high-speed network encryptions
Counter (CTR)
Advantages and Limitations of CTR
efficiency
can do parallel encryptions in h/w or s/w
can preprocess in advance of need
good for bursty high speed links
random access to encrypted data blocks
provable security (good as other modes)
never have cycle less than 2b
The AES Cipher - Rijndael
designed by Rijmen-Daemen in Belgium
has 128/192/256 bit keys, 128 bit data
an iterative rather than Feistel cipher
processes data as block of 4 columns of 4 bytes
operates on entire data block in every round
designed to have:
resistance against known attacks
speed and code compactness on many CPUs
design simplicity
AES Structure
data block of 4 columns of 4 bytes is state
key is expanded to array of words
has 9 rounds in which state undergoes:
byte substitution (1 S-box used on every byte)
shift rows (permute bytes between groups/columns)
mix columns (subs using matrix multiply of groups)
add round key (XOR state with key material)
view as alternating XOR key & scramble data bytes
initial XOR key material & incomplete last round
AES Structure
Substitute Bytes
A simple substitution of each byte
uses one table of 16x16 bytes containing a permutation of all 256 8-bit values
each byte of state is replaced by byte indexed by row (left 4-bits) & column (right
4-bits)
eg. byte {95} is replaced by byte in row 9 column 5
which has value {2A}
S-box constructed using defined transformation of values in GF(28)
designed to be resistant to all known attacks
Substitute Bytes
Substitute Bytes Example
Shift Rows
A circular byte shift in each each
1st row is unchanged
2nd row does 1 byte circular shift to left
3rd row does 2 byte circular shift to left
4th row does 3 byte circular shift to left
Decrypt inverts using shifts to right
Since state is processed by columns, this step permutes bytes between
the columns
Shift Rows
Mix Columns
each column is processed separately
each byte is replaced by a value dependent on all 4 bytes in the column
effectively a matrix multiplication in GF(28) using prime poly m(x)
=x8+x4+x3+x+1
Mix Columns
Add Round Key
XOR state with 128-bits of the round key
again processed by column (though effectively a series of byte operations)
inverse for decryption identical
since XOR own inverse, with reversed keys
designed to be as simple as possible
a form of Vernam cipher on expanded key
requires other stages for complexity / security
Add Round Key
AES Round
AES Key Expansion
ASYMMETRIC-KEY CRYPTOGRAPHY
An asymmetric-key (or public-key) cipher uses two keys: one private and one public.
We discuss two algorithms: RSA and Diffie-Hellman.
To create an RSA public/private key pair, here are the basic steps:
1- Choose two prime numbers, p and q such that p q .
2- Calculate the modulus, n = p q.
3- Calcuate ( n ) = ( p – 1 )( q – 1 ).
4- Select integer e such that gcd (( n ), e) = 1 and 1 < e < ( n ). (* gcd is greater
common divisor)
5- Calculate an integer d from the quotient de 1 (mod ( n )).
To encrypt a message, M, with the public key (e, n), create the ciphertext, C, using the
equation:
RSA
Diffie-Hellman Key Exchange:
It is a protocol that enables two users to establish a secret key using a public-key scheme based on discrete logarithms.
The protocol is secure only if the authenticity of the two participants can be established.
Primitive Root:
A primitive root of a prime number p as one whose powers modulo generate all the integers from 1 to p-1. That is, if
a is a primitive root of the prime number p, then the numbers
are distinct and consist of the integers from 1 through p - 1 in some permutation.
For any integer b and a primitive root a of prime number p, we can find a unique exponent i such that
The exponent i is referred to as the discrete logarithm of b for the base a, mod p.
Diffie-Hellman Key Exchange Algorithm:
For this scheme, there are two publicly known numbers: a prime number q and an integer α that is a primitive root of
Diffie-Hellman Key Exchange Algorithm
Diffie-Hellman Key Exchange Example:
Key exchange is based on the use of the prime number q=353 and a primitive root of 353,
in this case =3. A and B select secret keys X =97, X =233 respectively. Each
A B
computes its public key:
After they exchange public keys, each can compute the common secret key:
