Symmetric Cryptosystems

Lesson 3
 Initial examples
• Ex1: let p be a large prime, 2159 < p < 2160. K =
ℳ = ∁= 𝑍𝑝∗ .
𝐸𝑘 𝑚 ≡ 𝑘 ∗ 𝑚 𝑚𝑜𝑑 𝑝
𝐷𝑘 𝑐 ≡ 𝑘 ′ ∗ 𝑐 (𝑚𝑜𝑑 𝑝)
• Ex2: let K, ℳ, ∁ = {0, 1, … , 2𝐵 − 1} be the sets
of all binary strings of length B.
𝐸𝑘 𝑚 = 𝑘 ⊕ 𝑚
𝐷𝑘 𝑐 = 𝑘 ⊕ 𝑐
 Analysis
If (K, ℳ, ∁, 𝐸, 𝐷) is to be a successful cipher, it must have the
following properties (Kerckhoff principal):
1. For any kK, mℳ, it must be easy to compute the
cipher text Ek(m).
2. For any kK, c∁, it must be easy to compute the
plaintext Dk(c).
3. Given one or more c1 , c2 , … , cn ∁ are encrypted using
kK, it must be difficult to compute any of the
corresponding plaintexts 𝐷𝑘 𝑐1 , 𝐷𝑘 𝑐2 , … , 𝐷𝑘 𝑐𝑛
without knowing k.
4. Given one or more pairs 𝑚1 , 𝑐1 , … (𝑚𝑛 , 𝑐𝑛 ), it must be
difficult to decrypt any cipher c that is not in the given list
without knowing k (chosen plaintext attack).
 Analysis…
• Ex1: 𝐸𝑘 𝑚 ≡ 𝑘 ∗ 𝑚 𝑚𝑜𝑑 𝑝 . It doesn’t have
Property 4 (chosen cipher/plaintext attack).

• Ex2: 𝐸𝑘 𝑚 = 𝑘 ⊕ 𝑚 (chosen plaintext

attack)
 Random bit sequences…
Suppose that we could construct a function 𝑅: 𝐾 ×
ℤ → {0,1} with the following properties:
1. For all k𝐾, jℤ, it is easy to compute R(k, j).
2. Given an arbitrarily long sequence of integer
𝑗1 , … , 𝑗𝑛 and given all of values
𝑅 𝑘, 𝑗1 , … , 𝑅(𝑘, 𝑗𝑛 ), it is hard to determine k.
3. Given any list 𝑗1 , … , 𝑗𝑛 and given all of
𝑅 𝑘, 𝑗1 , … , 𝑅(𝑘, 𝑗𝑛 ), it is had to guess the value
of 𝑅(𝑘, 𝑗) with better than 50% chance of
success for any j not already in the list.
 …and symmetric cipher
• There are two basic approaches to constructing candidates
for R, and these two methods provide a good illustration of
the fundamental conflict in cryptography between security
and efficiency.
• The first approach is to repeatedly apply an ad hoc
collection of mixing operations that are well suited to
efficient computation and that appear to be very hard to
untangle. This method is the basic of all most modern
symmetric cryptosystems (DES, AES, …)
• The second approach is to construct R using a function
whose efficient inversion is a well-known mathematical
problem that is believed to be difficult. This method is less
attractive for real-world ciphers.
 Modern symmetric cryptosystems
• DES – Data Encryption Standard (IBM,1970).
• DES uses a 56-bit key and encrypts blocks of
64 bits at a time.
• DES mixing operations are linear, with the only
nonlinear component being the use of eight S-
box (Substitution box).
• Each S-box is a look-up table in which six input
bits are replaced by four output bit.
 DES S-Box
• Here is how an S-box is used. The input is a list
of 6 bit Input = 123456.
• First use the 2-bit binary number 16 to
choose the row of the S-box, then use the 4-
bit binary number 2345 to choose the
column of the S-box.
• The output is the entry of the S-box for the
chosen row and column, and converted into a
4-bit binary number.
 S-box and Example
• Suppose that Input = ‘110010’. ‘10’ = 2 → use
row 2, and ‘1001’ = 9, use column 9. Output
will be 12 = 1100.
• S-box(x) = F(A(x)) where A: affine, F(x):non-
linear function.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
 Advanced Encryption Standard
• AES (J. Daemen and V. Rijmen, 2000). A block
cipher in which the plaintext-cipher text blocks
are 128 bits in length and the key size may be
128, 192, 256 bits.
• AES is similar to DES in hat it encrypts/decrypts
by repeating a basic operation several times (10,
12, or 14 rounds depending on the size key).
• AES S-box is constructed using the operation of
taking multiplication inverses in the field F28.
 block cipher mode of operation
Mode Formulas Ciphertext
Electronic
(ECB) Yi = F(PlainTexti, Key) Yi
codebook
Cipher block
(CBC) Yi = PlainTexti XOR Ciphertexti−1 F(Y, Key); Ciphertext0 = IV
chaining

Propagating Yi = PlainTexti XOR (Ciphertexti−1 XOR

(PCBC) F(Y, Key); Ciphertext0 = IV
CBC PlainTexti−1)

Cipher Plaintext XOR F(Y, Key);

(CFB) Yi = Ciphertexti−1
feedback Ciphertext0 = IV

Output
(OFB) Yi = F(Yi−1, Key); Y0 = F(IV, Key) Plaintext XOR Yi
feedback

Counter (CTR) Yi = F(IV + g(i), Key); IV = token() Plaintext XOR Yi