MODULE - II

Presented by: Arif Mohammad Abdul

 Block Cipher : Introduction
• A block cipher is a symmetric encryption which operates on
blocks of data.
• A block cipher breaks plaintext into fixed sized blocks (fixed
number of bits i.e., n bits).
• Sizes of block is depends on type of symmetric algorithm.
• All input plaintext bits need to be present before processing
the block.
• If the plaintext length is not divisible by n, and the last block
is only partially filled, then that block needs to be padded.
• When padding is applied, Alice and Bob need to agree on the
padding.
• Takes one block of plaintext at a time and transfer it into
same length of ciphertext block using user’s provided secret
key.
 Block Cipher
Secret Key
Data
Data Block Data Block Data Block Plaintext
Data Block Data Block Data Block
Block

Symmetric Encrypted

Data Block
Algorithm Block

Ciphertext

Data Block
 Symmetric Algorithm
• Symmetric algorithm uses only one key (a
secret key) is used to both encrypt and
decrypt the message.

GITAM GITAM
University University
 Symmetric Algorithm
Shared
Key

Public
Network

Data Data

An Enemy , A very smart

Person

Alice, Bob, Eve Framework

 Symmetric Algorithms
Some of the symmetric algorithms include:
• Data Encryption Standard (DES)
• Triple DES
• Advanced Encryption Standard (AES)
Simplified-DES
 Simplified-DES
• It is simple version of DES.
• It has similar properties and structure to DES
with smaller parameters.
• It is a block cipher.
• It has 8-bits block size of plain text or cipher
text.
• It uses 10-bits key size for encryption.
• It has Two Rounds.
 Simplified-DES Algorithm
• The S-DES encryption algorithm takes
– An 8 bit block of plaintext (eg. 10111101)
– A 10 bit key as input
– Produces an 8 bit block of ciphertext
• The S-DES decryption algorithm takes
– An 8 bit block of ciphertext
– The same 10 bit key used
– Produces an 8 bit block of plaintext
S-DES Overall Structure
 S-DES Encryption
• The Encryption Algorithm as a composition of
functions:
Ciphertext = IP-1 (fk2 (SW(fk1(IP(Plaintext)))))
Where
K1 = P8(Shift(P10(Key)))
K2 = P8(Shift(Shift(P10(Key))))
 S-DES Rules
• Initial Permutation (IP)
• Inverse Initial Permutation (IP-1)
• Permutation (P10)
• Permutation (P8)
• Expansion/Permutation (E/P(F))
• Permutation (P4)
S-DES - 10 bit Sub-Key Generation
Sub-Keys Generation Procedure:
1. Randomly select 10 bit key.
2. Apply P10 rule on selected 10 bit key.
3. Split key into two equal halves, circular left
shift.
4. Apply P8 rule on resultant bits, K1 generated.
5. Circular left shift twice.
6. Apply P8 rule on resultant bits, K2 generated.
S-DES - 10 bit Sub-Key Generation
10 – Bit key

10

P10

5 5

LS-1 LS-1

P8
K1

LS-2 LS-2

5 5

P8
K2
 S-DES - Two Rounds Encryption Steps
The Encryption Algorithm involves 5 Steps:
1. An initial permutation (IP)
2. A complex function (F), which includes
permutation and substitution operations Substitution

3. The function (f )
k

4. Permutation function that switches (SW)

the two halves of the data
5. Step 2 and Step 3 repeat in second round
6. Finally a permutation function that is the
inverse of the initial permutation (IP-1)
S-DES - Two Rounds Encryption
8 – Bit Plaintext

IP

fk F

fk F

IP-1

8 – Bit Ciphertext
S-DES – 8 bit Encryption
8 – Bit Plaintext

IP
4 4 1101

fk F
4 4
1011 1111

0100

1101 0100
fk F

1101 1100
0001
IP-1

8 – Bit Ciphertext
S-DES – 8 bit Expansion/Permutation
F function Process:
How will get F(R,SK) = 1111?
1. Take right 4 bits of IP (1101).
2. Apply E/P rule on right 4 bits of IP.
3. XoR with sub-key K1.
4. Divide output into two equal parts (Left & Right).
5. Use substitution boxes(S-Boxes) S0 &S1 on Left &
Right.
6. The 4 bits produced by S0 and S1 undergo
permutation P4.
7. The output of P4 is the output of the function F.
S-DES – 8 bit One Round
Expansion/Permutation
Right Permuted 4 Bits
1101

E/P
11101011
10100100
K1

0100 1111

S0 S1

11 11

P4

1111
 S-DES Decryption

• The Decryption Algorithm as a composition of

functions:
Plaintext = IP-1 (fk1 (SW(fk2(IP(Ciphertext)))))
Where
K1 = P8(Shift(P10(Key)))
K2 = P8(Shift(Shift(P10(Key))))
 S-DES Example
1. Key : 1010000010
Rules : Same rules
Find K1 and K2 :?

2. Plaintext : GITAM (Convert into binary)

Key : 1010110001
Rules : Same rules
Ciphertext : ?
 S-DES Strength
• Along with permutations and substitutions, S-
boxes making cryptanalysis difficult.
• A brute-force attack on simplified DES is
certainly feasible. With a 10-bit key, there are
only 210 = 1024 possibilities.
• Given a ciphertext, an attacker can try each
possibility and analyze the result to determine
if it is reasonable plaintext.
 Block Cipher Principles
Stream Cipher Vs Block Cipher
A stream cipher is one that encrypts a digital
data stream one bit or one byte at a time.
 Block Cipher Principles
• A block cipher is one in which a block of
plaintext is treated as a whole and used to
produce a cipher text block of equal length.

• A majority of symmetric algorithms make use

of block ciphers.
Block Cipher Transformation

Reversible Irreversible
 Reversible
• Reversible or nonsingular: There are 2n
possible different plaintext blocks each must
produce a unique ciphertext.
• If n = 2
Reversible Mapping
Plaintext Ciphertext
00 11
01 10
10 00
11 01
 Irreversible
• A ciphertext could have been produced by one
or two plaintext blocks.
Irreversible Mapping
Plaintext Ciphertext
00 11
01 10
10 01
11 01

• So if restrict to reversible mappings, the number

of different transformations is 2n !
• Key size = n * 2n
Ideal Block Cipher
 Ideal Block Cipher
• Ideal block cipher define reversible mapping
between plaintext and ciphertext.
• But there is a practical problem with this
approach.
• If a small block size, then it is equivalent to
classical substitution cipher.
• As we discuss early, such substitution cipher
vulnerable to a statistical analysis.
• For a large block size is not practical.
 Ideal Block Cipher
• If consider n = 4 bits, then a 4 bit input
produces one of 16 possible input states,
which is mapped by the substitution cipher
into a unique one of 16 possible output states.
• The mapping itself a key.
 Ideal Block Cipher
For n bits substitution block
Encryption Decryption cipher the key size is n * 2n .

For 4 bits block the key require

64 bits.

This is vulnerable to a statistical

analysis.

For 64 bits block the key require

64 * 264 = 270 = 1021 .

This is a desirable length for

statistical attack but impractical.
The Feistel Cipher
 The Feistel Cipher
• Feistel proposed the concept of a product
cipher, which makes cryptographically strong.
• Most symmetric block ciphers are based on
a Feistel Cipher Structure.
• A block cipher operates on a plaintext block
of n bits to produce a ciphertext block of n
bits.
• The Feistel Cipher is a practical application of
a proposal by Claude Shannon.
 The Feistel Cipher
• The idea of a product cipher that alternates
substitution-permutation (S-P).
• Substitution-Permutation based on the two
primitive cryptographic operations:
substitution (S-box)
permutation (P-box)
• Feistel introduces to two functions to make
difficult to statistical cryptanalysis:
Diffusion
Confusion
 The Feistel Cipher
Diffusion:
The mechanism of diffusion seeks to make the
statistical relationship between the plaintext and
ciphertext as complex as possible.
It encrypts a message M = m1, m2, m3, …......

Confusion:
The mechanism of confusion seeks to make the
statistical relationship between the ciphertext and
key as complex as possible.
The Feistel Cipher Structure
• The input to the encryption
algorithm are a plaintext block of
length 2w bits and a key K.
• The plaintext block is divided into
two halves L0 and R0.
• The two halves of the data pass
through “n‟ rounds of processing
and then combine to produce the
ciphertext block.
• Each round “i‟ has inputs Li-1 and Ri-
1, derived from the previous round,
as well as the sub-key Ki, derived
from the overall key K.
• The sub-keys Ki are different from K
and from each other.
The Feistel Cipher Structure
 The Feistel Cipher Structure
• All rounds have the same structure.
• A substitution is performed on the left half of
the data (as similar to S-DES).
• This is done by applying a round function F to
the right half of the data.
• Then taking the XOR of the output of F function
and the left half of the data.
• The round function has the same general
structure for each round but is parameterized by
the round sub-key ki.
• Following this substitution, a permutation is
performed that consists of the interchange of
the two halves of the data.
 The Feistel Cipher Structure - Design
Features
• Block size - Increasing size improves security
• Key size - Increasing size improves security,
makes exhaustive key searching harder
• Number of rounds - Increasing number improves
security
• Sub-key generation - Greater complexity can
make analysis harder
• Round function - Greater complexity can make
analysis harder
• Fast software en/decryption & ease of analysis -
are more recent concerns for practical use and
testing.
The Feistel Cipher Encryption & Decryption
First consider the
encryption process,
LE16 = RE15
RE16 = LE15 XoR F(RE15, K16)
Decryption Process,
LD1 = RD0 = LE16 = RE15
RD1 = LD0 XoR F(RD0, K16)
= RE16 XoR F(RE15, K16)
= LE15 XoR F(RE15, K16) XoR F(RE15, K16)
• Therefore, LD1 = RE15 and RD1 = LE15
• In general, for the ith iteration of the
encryption algorithm,
LEi = REi-1
REi = LEi-1 XoR F(REi-1, Ki) = REi XoR F(LEi, Ki)
• Finally, the output of the last round of the
decryption process is RE0 || LE0 A 32-bit swap
recovers the original plaintext.
 DES History
• Most widely used block cipher in world
• Adopted in 1977 by NBS (now NIST)
– as FIPS PUB 46
• Encrypts 64-bit data using 56-bit Key
• IBM developed Lucifer cipher
– by team led by Feistel
– used 64-bit data blocks with 128-bit key
• Then redeveloped as a commercial cipher with input
from NSA and others
• In 1973 NBS issued request for proposals for a national
cipher standard
• IBM submitted their revised Lucifer which was
eventually accepted as the DES
• DES has become widely used, especially in financial
applications
DES Encryption Overview
DES Encryption

• 64 – bit Plaintext
• Initial Permutation (IP)
• 16 rounds with 16 sub-keys
• Swapping
• Inverse Initial Permutation (IP-1)
 DES Rules
• Initial Permutation (IP) • Inverse Initial Permutation (IP-1)

• Expansion Permutation (E) • Permutation Function (P)

DES Sub-Key Generation
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

In DES, the conversion to 56 Odd parity bit

bits is done by neglecting every 8th bit.
 DES Sub-Key Generation Rules
• Permuted Choice One (PC-1) • Schedule of circular Left
Shifts

• Permuted Choice Two (PC-2)

 DES Sub-Key Generation
• 64 – bit key used as input to the algorithm.
• The bits of the key are numbered from 1
through 64; every eighth bit is ignored.
• The resulting 56 bit key divide into two equal
half's labeled as C0 ,D0 after the permutation
done through Permuted Choice - 1.
• At each round, apply circular left shift as
governed by rule Schedule of Left Shifts.
• After circular left shift serve as input to
Permuted Choice – 2.
 Structure of Single Round of DES Algorithm
32bits 32bits 28 bits 28 bits

L R i-1 C i-1 D i-1

i-1
32
32 Expansion/ Left shift (s)
permutation (E table)
Left shift (s)

48
f
k
F XOR Ki
48
Permutation/contraction
(permuted choice 2)
48
Substitution/
choice (S-box)
32
Permutation
(P)
32
XOR

Li Ri C D i
i
Li = Ri-1
Ri = Li-1  F(Ri-1 , Ki)
 First Round (i=1) of DES Algorithm
32bits 32bits 28 bits 28 bits

L R 0 C 0 D 0
0
32
32 Expansion/ Left shift (s)
permutation (E table)
Left shift (s)

48
f
k
F XOR
48
K1 Permutation/contraction
(permuted choice 2)
48
Substitution/
choice (S-box)
32
Permutation
(P)
32
XOR

L1 R1 C D 1
1
L1 = R1-1 = R0
R1 = L1-1  F(R1-1 , K1) = L0  F(R0 , K1)
 IP & IP-1
• IP(plaintext) = L(0): R(0), where L(0) and R(0) are
the left –half and the right-half of the output
after the permutation done through IP.

• Even bits allocated to L(0)

• Odd bits allocated to R(0)
• IP does not add to security.
• It makes the function a little complex.

Inverse Input Permutation reverses it back.

Thus IP-1( IP( X)) = X
 Function: Expansion/Permutation
Expansion/Permutation:
• To get 48 bits from 32 bits of Ri
• Each input block of 4 bits contributes 2 bits to each
output block.

• E(Ri-1)  Ki
 Function: S-Box Permutation
• After generating 48 bits from E/P, XOR with sub-key
K1’s 48 bits, then get 48 bits as an output.

• This output transferred to S-Box to reduce again to 32

bits.

• S-Box permutation uses eight 4x16 S-boxes for

converting 48 bits to 32 bits.

• S-Boxes provide Non-linear output to strength the

cipher.

• Divide 48 bits to 8 units of 6 bits each.

Function: S-Box Permutation Structure

Right half 32 bits

Expansion

Output Sub-Key Ki

Output Eight 4x16 S-Boxes

Permutation

32 bits Output
S-Boxes
Function: S-Box Permutation Functionality
• Using 8 4X16 S-boxes, each group of 6 bits is
reduced to 4 bits as follows:
1. For each S-Box: Row Number = Outermost 2 bits;
the first and the last bit determine the row #.
2. For each S-Box: Column Number = Inner 4 bits;
the middle 4 bits determine the column #.
3. Using the row and column number, the S-box yields
a decimal number (lying between 0 and 15).
4. Its 4 bit binary equivalent is the output of the S-
box.
• The 32 bit output from the eight S-Boxes is
1. Permutation (P)
2. XOR with left half (f )
k

3. Switch the left half and the right half (Swap)

Function: S-Box Permutation Functionality
 The Avalanche Effect
• A small change in plaintext or key results in
changing approximate half of the bits in
ciphertext.
TRIPLE DES
 Multiple DES
• DES is vulnerable to a brute force attack
(256).
• Need another alternative, which would
preserve the security.
• Multiple encryption with DES and
multiple keys is alternative to DES.
Types of Multiple DES

Double DES

Triple DES
 Double DES Encryption
64 bit Plaintext • Given a plaintext P
and two encryption
56 bits key – K1 DES Cipher
keys K1 & K2
• Generated ciphertext
X Centre Cipher
by
C = Ek2 [Ek1 [P]]
56 bits key – K2 DES Cipher
• This approach uses a
key length is
Ciphertext
56 * 2 = 112 bits.
 Double DES Decryption
64 bit Ciphertext

DES
56 bits key – K2
De-Cipher

Centre
X De-Cipher P = Dk1 [Dk2 [C]]

DES
56 bits key – K1
De-Cipher

Plaintext
 Meet-in-the-middle attack
• This attack requires pair of known plaintext
and ciphertext.
• Attack works from both ends of double DES.
• Encrypt from one end and decrypt from
another end.
• Cryptanalyst analysis on X, which is center
ciphertext.
• X produces the same result, while encrypting
plaintext with K1 and decrypting ciphertext
with K2 .
 Meet-in-the-middle attack

• The center text is produces by

using encryption and decryption
X = Ek1 (P) and X = Dk2 (C)
• Encrypt P using all possible values
of K1 and record all values obtained
for X.
• Decrypt C using all possible values
of K2 and record all values obtained
for X.
• Create two tables sorted by X
values.
• Now compare the values for X until
find the pairs of K1 & K2 for the
values of X in both tables.
 Triple DES
• Triple DES is a counter attack to meet-in-the-
middle attack.
• It uses in two different ways

2 Keys 3 Keys
 Triple DES with Two Keys
64 bit Plaintext • This approach process
Encrypt-Decrypt-Encrypt
56 bits key – K1 DES Cipher (EDE).
A C = Ek1[Dk2 [Ek1 [P]]
56 bits key – K2
DES Reverse • The Key length is 56 * 3 =
Cipher
168 bits.
B
• The drawback of this
56 bits key – K1 DES Cipher
approach is large key
length.
Ciphertext
 Triple DES with Three Keys
64 bit Plaintext

56 bits key – K1 DES Cipher

56 bits key – K2 Centre Cipher

• C = Ek3[Dk2 [Ek1 [P]]

56 bits key – K3 DES Cipher

Ciphertext
Modes of Operation
 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
Modes of Operation
Electronic Cipher Block
Code Book Chaining (CBC)
(ECB) Mode Mode

Cipher Output
Feedback Feedback
(CFB) Mode (OFB) Mode

Counter (CTR)
Mode
Electronic Codebook Book (ECB)
• Message is broken into independent blocks
that are encrypted.
• Each block is a value which is substituted, like
a codebook.

• Each block is encoded independently of the

other blocks
Ci= Ek(Pi)
• Secure transmission of single values.
Electronic Codebook Book (ECB)
Plaintext
 Limitations & Advantage of ECB

• Message repetitions may show in ciphertext

• Weakness is due to the encrypted message
blocks being independent
• 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
• Use Initial Vector (IV) to start process
• Ci = Ek(Pi XOR IV)
• IV prevents same P from making same C
 Message Padding
• At end of message must handle a possible last short
block
• Which is not as large as block size of cipher
• Pad either with known non-data value
• e.g., nulls
• or pad last block along with count of pad size
• e.g., [ b1 b2 b3 0 0 0 0 5]
• means have 3 data bytes, then 5 bytes pad +
count
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
(Avalanche Effect)
• 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
• 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
• Result is feed back for next stage
• 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)
• Ci = Pi XOR Ek(IV)
Cipher FeedBack (CFB)
 Advantages and Limitations of
CFB
• Note that the block cipher is used in
encryption mode at both ends (XOR)
• Limitation is need to stall while do block
encryption after every s-bits
 Output FeedBack (OFB)
• Message is treated as a stream of bits
• Output of cipher is added to message
• Output is then feed back
• Oi = Ek(IV)
• Ci = Pi XOR Oi
• 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
⚫ OTP

➢ can pre-compute
➢ 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)
• Similar to OFB but encrypts counter value rather than any
feedback value
• Oi = Ek(CTRi)
• Ci = Pi XOR Oi

• Must have a different counter value for every plaintext block

(never reused)
• again, OTP issue
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, must ensure never reuse key/counter
values, otherwise could break (OFB)
Feedback Characteristics
Advanced Encryption
Standards
Advanced Encryption Standards
• The Advanced Encryption Standard (AES), also
known by its original name Rijndael.
• AES is a non-Feistel cipher that encrypts and
decrypts a data block of 128 bits. It uses 10, 12, or
14 rounds. The key size, which can be 128, 192, or
256 bits, depends on the number of rounds.

AES has defined three versions, with 10, 12,

and 14 rounds.
Each version uses a different cipher key size
(128, 192, or 256), but the round keys are
always 128 bits.
7.93
 General design of AES
encryption cipher

7.94
 Data units used in AES

7.95
 Block-to-state and
state-to-block transformation

7.96
 Changing plaintext to state

7.97
 Structure of each round
at the encryption site

7.98
 AES TRANSFORMATIONS

To provide security, AES uses four types of

transformations:

Substitution

Permutation

Mixing
Key - Adding
Column
7.99
 Key Expansion in AES-128

7.100
 Working Procedure of AES

• [Link]
aGDJVwnGP/view?usp=sharingz
Rivest Cipher (RC – 6)
 RC – 6
• Created by Ronald Rivest et al. for AES
submission
• Follows the evolution of RC5 cipher
– Parameterized family of algorithms
• Improvements over RC5
– Uses four w-bit registers
– Integer multiplication
– Quadratic equation
– Fixed bit shifting
 RC6 Cipher

• Main design objective: simplicity

• Not reported vulnerable to any known
practical attacks
• Consists of three components
– Key expansion algorithm
• Identical to RC5 version
– Block encryption algorithm
– Block decryption algorithm
 RC6 Structure

• Specification: RC6-w/r/b
– w is the word size in bits
– r is the number of non-negative rounds
– b is the key size in bits
• Round Stages
– Pre-whitening
– r rounds
– Post-whitening
 More RC6 Structure

• Pre-whitening
– Removes inference of part of the input to the first round of
encryption
• r rounds
– Uses integer multiplication
– Uses a quadratic equation
• f(x) = x(2x + 1)(mod 2w)
– Uses fixed bit shifting
 Final RC6 Structure

• Post-whitening
– Removes inference of part of the input to the last
round of encryption
RC6 Structure
 Key Setup

• The user supplies a key of b bytes, where 0 ≤ b

≤ 255
• The key bytes are zero-padded and stored in
little-endian order
– (2r+4) words are derived and stored in a round key
array S
 RC6 Encryption

• B and D are pre-

Input:
Plaintext stored in four w-bit input registers A,B,C,D
Number r of rounds
whitened w-bit round keys S[0,…,2r + 3]

Output:
• The loop controls Ciphertext stored in A,B,C,D

Procedure:
the rounds B = B + S[0]
D = D + S[1]
defined by r for i = 1 to r do
{
t = (B x (2B + 1)) <<< log2 w
• A and C are post- u = (D x (2D + 1)) <<< log2 w
A = ((A t) <<< u) + S[2i]
C = ((C u) <<< t) + S[2i+ 1]
whitened (A,B,C,D) = (B,C,D,A)
}
A = A + S[2r + 2]
C = C + S[2r + 3]

(Rivest et al., 1998a)

 RC6 Decryption

• C and A are pre-

Input:
Ciphertext stored in four w-bit input registers A,B,C,D
Number r of rounds
whitened w-bit round keys S[0,…,2r + 3]

Output:
• The loop runs in Plaintext stored in A,B,C,D

Procedure:
reverse for r C = C - S[2r + 3]
A = A - S[2r + 2]
rounds for i = r downto 1 do
{
(A,B,C,D) = (D,A,B,C)
• D and B are post- u = (D x (2D + 1)) <<< log2 w
t = (B x (2B + 1)) <<< log2 w
C = ((C - S[2i + 1]) >>> t) u
whitened A = ((A - S[2i]) >>> u) t
}
D = D - S[1]
B = B - S[0]

(Rivest et al., 1998a)