UNIT 2

Lecture Notes
Symmetric key Ciphers: Block Cipher principles, DES, AES, Blowfish, RC4, RC5, Block
cipher operation, Stream ciphers, Asymmetric key Ciphers: Principles of public key
cryptosystems, RSA algorithm, Elgamal Cryptography, Diffie-Hellman Key Exchange,
Knapsack Algorithm.

2. Introduction
In this note, we consider the following problem. Alice wants to send messages to Bob
via some communications channel. Eve has access to the channel and she may eavesdrop on
and possibly tamper with anything sent over the channel. Alice does not want Eve to be able
to eavesdrop on her messages. She wants to communicate confidentially. Also, when Bob
receives a message that looks like it came from Alice, then Bob wants to be sure that Alice
really sent the message and that Eve did not tamper with it. Alice and Bob want integrity.
Alice and Bob share a secret, called the key. Cryptography where the sender and the receiver
(the honest users) have the same knowledge is called symmetric cryptography, where the
word symmetry refers to the symmetry of knowledge. We define what a symmetric
cryptosystem is and what the security requirements are for such cryptosystems . To illustrate
standard attacks, it is useful to study some historic crypto systems and how those systems can
be attacked. This is done , which alternates between discussing historical ciphers and
discussing interesting attacks that apply to the historical ciphers. These constructions do not
provide integrity, nor do they provide confidentiality if Eve is willing to tamper with cipher
texts.

2.1 Block Cipher Principles

Most symmetric block encryption algorithms in current use are based on a

structure referred to as a Feistel block cipher [FEIS73]. For that reason, it is
important to examine the design principles of the Feistel cipher. We begin
with a comparison of stream ciphers and block ciphers. Then we discuss the
motivation for the Feistel block cipher structure. Finally, we discuss some of its
implications.

Stream Ciphers and Block Ciphers

A stream cipher is one that encrypts a digital data stream one bit or one byte at
a time. Examples of classical stream ciphers are the autokeyed Vigenère cipher
and the Vernam cipher. A block cipher is one in which a block of plaintext is
treated as a whole and used to produce a ciphertext block of equal length.
Typically, a block size of 64 or 128 bits is used. Using some of the modes of
operation explained ing, a block cipher can be used to achieve the same effect as
a stream cipher.

1
Far more effort has gone into analyzing block ciphers. In general, they seem
applicable to a broader range of applications than stream ciphers. The vast majority of
network-based symmetric cryptographic applications make use of block ciphers.
Accordingly, the concern in this chapter, and in our discussions throughout the book
of symmetric encryption, will focus on block ciphers.

CONVENTIONAL ENCRYPTION PRINCIPLES

A Conventional/Symmetric encryption scheme has five ingredients

1. Plain Text: This is the original message or data which is fed into the algorithm as input.

2.Encryption Algorithm: This encryption algorithm performs various substitutions and

transformations on the plain text.

3. Secret Key: The key is another input to the algorithm. The substitutions and
transformations performed by algorithm depend on the key.

4. Cipher Text: This is the scrambled (unreadable) message which is output of the
encryption algorithm. This cipher text is dependent on plaintext and secret key. For a given
plaintext, two different keys produce two different cipher texts.

5.Decryption Algorithm: This is the reverse of encryption algorithm. It takes the cipher text
and secret key as inputs and outputs the plain text.

2
The important point is that the security of conventional encryption depends on the secrecy

of the key, not the secrecy of the algorithm i.e. it is not necessary to keep the algorithm

secret, but only the key is to be kept secret. This feature that algorithm need not be kept

secret made it feasible for wide spread use and enabled manufacturers develop low cost

chip implementation of data encryption algorithms. With the use of conventional algorithm,

the principal security problem is maintaining the secrecy of the key.

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 L 0 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 subkey Ki, derived from the overall key K. in general, the subkeys Ki are different
from K and from each other.
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

3
of the data and then taking the XOR of the output of that 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 subkeyki. Following this substitution, a permutation is
performed that consists of the interchange of the two halves of the data. This structure
is a particular form of the substitution-permutation network. The exact realization of a
Feistel network depends on the choice of the following parameters and design features:
 Block size - Increasing size improves security, but slows cipher
 Key size - Increasing size improves security, makes exhaustive key
searchingharder, but may slow cipher
 Number of rounds - Increasing number improves security, but slows cipher
 Subkey generation - Greater complexity can make analysis harder, but
slowscipher
 Round function - Greater complexity can make analysis harder, but slows cipher
 Fast software en/decryption & ease of analysis - are more recent concerns
forpractical use and testing

4
5
The process of decryption is essentially the same as the encryption process. The rule is

as follows: use the cipher text as input to the algorithm, but use the subkeyk i in reverse

order. i.e., kn in the first round, kn-1 in second round and so on. For clarity, we use the

notation LEi and REi for data traveling through the decryption algorithm. The diagram

below indicates that, at each round, the intermediate value of the decryption process is

same (equal) to the corresponding value of the encryption process with two halves of

the value swappe

6
i.e., REi || LEi (or) equivalently RD16-i || LD16-i

After the last iteration of the encryption process, the two halves of the output are

swapped, so that the cipher text is RE 16 || LE16. The output of that round is the cipher

text. Now take the cipher text and use it as input to the same algorithm. The input to the

first round is RE16 || LE16, which is equal to the 32-bit swap of the output of the

sixteenth round of the encryption process. Now we will see how the output of the first

round of the decryption process is equal to a 32-bit swap of the input to the sixteenth

round of the encryption process.

First consider the encryption process,

LE16 = RE15

RE16 = LE15(+) F (RE15, K16)

On the decryption side, LD1 =RD0 = LE16 =RE15

RD1 = LD0 (+) F (RD0, K16)

= RE16 F (RE15, K16)

= [LE15 F (RE15, K16)] F (RE15, K16)

= LE15

Therefore, LD1 = RE15 RD1 = LE15 In general, for the ith iteration of the encryption

algorithm, LEi = REi-1REi = LEi-1 F (REi-1, Ki)

Finally, the output of the last round of the decryption process is RE0 || LE0. A 32-bit

swap recovers the original plaintext.

7
 DEFINITIONS

Encryption: Converting a text into code or cipher.

Converting computer data and messages into something, incomprehensible use a

key, so that only a holder of the matching key can reconvert them.

Conventional or Symmetric or Secret Key or Single Key encryption:

Uses the same key for encryption & decryption.

Public Key encryption:Uses different keys for encryption & decryption

Conventional Encryption Principles

 An encryption scheme has five ingredients:

1. Plaintext – Original message or data.

2. Encryption algorithm – performs substitutions & transformations on plaintext.

3. Secret Key – exact substitutions & transformations depend on this

4. Ciphertext - output ie scrambled input.

5. Decryption algorithm - converts ciphertext back to plaintext.

SIMPLIFIED DATA ENCRYPTION STANDARD (S-DES)

8
 The figure above illustrates the overall structure of the simplified DES. The S-DES
encryption algorithm takes an 8-bit block of plaintext (example: 10111101) and a 10-bit
key as input and produces an 8-bit block of ciphertext as output. The S-DES decryption
algorithm takes an 8-bit block of ciphertext and the same 10-bit key used to produce
that ciphertext as input and produces the original 8-bit block of plaintext.

The encryption algorithm involves five functions:

 an initial permutation (IP)

 a complex function labeled fk, which involves both permutation and substitution
operations and depends on a key input

 a simple permutation function that switches (SW) the two halves of the data

 the function fk again

 a permutation function that is the inverse of the initial permutation

The function fk takes as input not only the data passing through the encryption
algorithm, but also an 8-bit key. Here a 10-bit key is used from which two 8-bit subkeys
are generated. The key is first subjected to a permutation (P10). Then a shift operation
is performed. The output of the shift operation then passes through a permutation
function that produces an 8-bit output (P8) for the first subkey (K1). The output of the
shift operation also feeds into another shift and another instance of P8 to produce the
second subkey (K2).
The encryption algorithm can be expressed as a composition composition1 of
functions: IP-1 ο fK2 ο SW ο fk1 ο IP
Which can also be written as
Ciphertext = IP-1 (fK2 (SW (fk1 (IP (plaintext)))))
Where

K1 = P8 (Shift (P10 (Key)))

K2 = P8 (Shift (shift (P10 Key))))
Decryption can be shown as
Plaintext = IP-1 (fK1 (SW (fk2 (IP (ciphertext)))))

9
 S-DES depends on the use of a 10-bit key shared between sender and receiver.
From this key, two 8-bit subkeys are produced for use in particular stages of the
encryption and decryption algorithm. First, permute the key in the following fashion.
Let the 10-bit key be designated as (k1, K2, k3, k4, k5, k6, k7, k8, k9,
k10). Then the permutation P10 is defined as:
P10 (k1, K2, k3, k4, k5, k6, k7, k8, k9, k10) = (k3, k5, K2, k7, k4, k10 10, k1, k9, k8, k6)
P10 can be concisely defined by the display:
P10
3 5 2 7 4 10 1 9 8 6

This table is read from left to right; each position in the table gives the identity of the
input bit that produces the output bit in that position. So the first output bit is bit 3 of
the input; the second output bit is bit 5 of the input, and so on. For example, the key
(1010000010) is permuted to (10000 01100). Next, perform a circular left shift (LS-1),
or rotation, separately on the first five bits and the second five bits. In our example, the
result is (00001 11000). Next we apply P8, which picks out and permutes 8 of the 10
bits according to the following rule:
P8
6 3 7 4 8 5 10 9

10
The result is subkey 1 (K1). In our example, this yields (10100100). We then go back to
the pair of 5-bit strings produced by the two LS-1 functions and performs a circular left
shift of 2 bit positions on each string. In our example, the value (00001 11000) becomes
(00100 00011). Finally, P8 is applied again to produce K2. In our example, the result is
(01000011).

S-DES encryption
Encryption involves the sequential application of five functions.
Initial and Final Permutations The input to the algorithm is an 8-bit block of
plaintext,which we first permute using the IP function:
IP
2 6 3 1 4 8 5 7
This retains all 8 bits of the plaintext but mixes them up.
Consider the plaintext to be 11110011.
Permuted output = 10111101
At the end of the algorithm, the inverse permutation is used:
IP –1
4 1 3 5 7 2 8 6

The Function fk
The most complex component of S-DES is the function fk, which consists of a
combination of permutation and substitution functions. The functions can be expressed
as follows. Let L and R be the leftmost 4 bits and rightmost 4 bits of the 8-bit input to f K,
and let F be a mapping (not necessarily one to one) from 4-bit strings to 4-bit strings.
Then we let fk(L, R) = ( L (+) F( R, SK), R)
Where SK is a subkey and (+) is the bit-by-bit exclusive-OR function.
e.g., permuted output = 1011 1101 and suppose F (1101, SK) = (1110) for some key
SK. Then f K(10111101) = 10111110, 1101 = 01011101
We now describe the mapping F. The input is a 4-bit number (n1 n2 n3 n4). The first
operation is an expansion/permutation operation:

E/P
4 1 2 3 2 3 4 1

11
R= 1101 E/P output = 11101011 It is clearer to depict the result in this fashion:

The 8-bit subkey K1 = (k11, k12 12, k13 13, k14 14, k15 15, k16 16, k17 17, k18) is
added to this value using exclusive-OR:

Let us rename these 8 bits:

The first 4 bits (first row of the preceding matrix) are fed into the S-box S0 to produce a 2-
bit output, and the remaining 4 bits (second row) are fed into S1 to produce another 2- bit
output.
These two boxes are defined as follows:

The S-boxes operate as follows. The first and fourth input bits are treated as a 2-bit
number that specify a row of the S-box, and the second and third input bits specify a
column of the S-box. The entry in that row and column, in base 2, is the 2-bit output. For
example, if (p0,0 p0,3) = ) (00) and ( p0,1 p0,2) = (10), then the output is from row 0,
column 2 of S0, which is 3, or (11) in ) binary. Similarly, (p1,0 p1,3) and ( p1,1 p1,2) are
used to index into a row and column of S1 to produce an additional 2 bits. Next, the 4
bits produced by S0 and S1 undergo a further permutation as follows:
P4
2 4 3 1

The output of P4 is the output of the function F.

The Switch Function The function f K only alters the leftmost 4 bits of the input. The
switchfunction (SW) interchanges the left and right 4 bits so that the second instance of
f K operates

12
on a different 4 bits. In this second instance, the E/P, S0, S1, and P4 functions are the same.
The key input is K2. Finally apply inverse permutation to get the ciphertext

2.2 DATA ENCRYPTION STANDARD (DES)

The main standard for encrypting data was a symmetric algorithm known as the
Data Encryption Standard (DES). However, this has now been replaced by a new standard
known as the Advanced Encryption Standard (AES) which we will look at later. DES is a 64
bit block cipher which means that it encrypts data 64 bits at a time. This is contrasted to a
stream cipher in which only one bit at a time (or sometimes small groups of bits such as a
byte) is encrypted. DES was the result of a research project set up by International
Business Machines (IBM) corporation in the late 1960’s which resulted in a cipher known as
LUCIFER. In the early 1970’s it was decided to commercialise LUCIFER and a number of
significant changes were introduced. IBM was not the only one involved in these changes as
they sought technical advice from the National Security Agency (NSA) (other outside
consultants were involved but it is likely that the NSA were the major contributors from a
technical point of view). The altered version of LUCIFER was put forward as a proposal for
the new national encryption standard requested by the National Bureau of Standards
(NBS)3 . It was finally adopted in 1977 as the Data Encryption Standard - DES (FIPS PUB
46). Some of the changes made to LUCIFER have been the subject of much controversy even
to the present day. The most notable of these was the key size. LUCIFER used a key size of
128 bits however this was reduced to 56 bits for DES. Even though DES actually accepts a 64
bit key as input, the remaining eight bits are used for parity checking and have no effect on
DES’s security. Outsiders were convinced that the 56 bit key was an easy target for a brute
force attack4 due to its extremely small size. The need for the parity checking scheme was
also questioned without satisfying answers. Another controversial issue was that the S-
boxes used were designed under classified conditions and no reasons for their particular
design were ever given. This led people to assume that the NSA had introduced a “trapdoor”
through which they could decrypt any data encrypted by DES even without knowledge of
the key. One startling discovery was that the S-boxes appeared to be secure against an
attack known as Differential Cryptanalysis which was only publicly discovered by Biham
and Shamir in 1990. This suggests that the NSA were aware of this attack in 1977; 13 years
earlier! In

13
fact the DES designers claimed that the reason they never made the design
specifications for the S-boxes available was that they knew about a number of attacks
that weren’t public knowledge at the time and they didn’t want them leaking - this is
quite a plausible claim as differential cryptanalysis has shown. However, despite all this
controversy, in 1994 NIST reaffirmed DES for government use for a further five years
for use in areas other than “classified”. DES of course isn’t the only symmetric cipher.
There are many others, each with varying levels of complexity. Such ciphers include:
IDEA, RC4, RC5, RC6 and the new Advanced Encryption Standard (AES). AES is an
important algorithm and was originally meant to replace DES (and its more secure
variant triple DES) as the standard algorithm for non-classified material. However as of
2003, AES with key sizes of 192 and 256 bits has been found to be secure enough to
protect information up to top secret. Since its creation, AES had underdone intense
scrutiny as one would expect for an algorithm that is to be used as the standard. To date
it has withstood all attacks but the search is still on and it remains to be seen whether
or not this will last. We will look at AES later in the course.

INNER WORKING OF DES

DES (and most of the other major symmetric ciphers) is based on a cipher known as the

Feistel block cipher. It consists of a number of rounds where each round contains bit-

shuffling, non-linear substitutions (S-boxes) and exclusive OR operations. As with most

encryption schemes, DES expects two inputs - the plaintext to be encrypted and the

secret key. The manner in which the plaintext is accepted, and the key arrangement

used for encryption and decryption, both determine the type of cipher it is. DES is

therefore a symmetric, 64 bit block cipher as it uses the same key for both encryption

and decryption and only operates on 64 bit blocks of data at a time5 (be they plaintext

or ciphertext). The key size used is 56 bits, however a 64 bit (or eight-byte) key is

actually input. The least significant bit of each byte is either used for parity (odd for

DES) or set arbitrarily and does not increase the security in any way. All blocks are

numbered from left to right which makes the eight bit of each byte the parity bit.

14
Once a plain-text message is received to be encrypted, it is arranged into 64 bit blocks

required for input. If the number of bits in the message is not evenly divisible by 64,

then the last block will be padded. Multiple permutations and substitutions are

incorporated throughout in order to increase the difficulty of performing a

cryptanalysis on the cipher

OVERALL STRUCTURE

Figure below shows the sequence of events that occur during an encryption operation. DES

performs an initial permutation on the entire 64 bit block of data. It is then split into 2, 32

bit sub-blocks, Li and Ri which are then passed into what is known as a round (see figure

2.3), of which there are 16 (the subscript i in Li and Ri indicates the current round). Each of

the rounds are identical and the effects of increasing their number is twofold - the

algorithms security is increased and its temporal efficiency decreased. Clearly these are two

conflicting outcomes and a compromise must be made. For DES the number chosen was 16,

probably to guarantee the elimination of any correlation between the ciphertext and either

the plaintext or key6 . At the end of the 16th round, the 32 bit Li and Ri output quantities

are swapped to create what is known as the pre-output. This [R16, L16] concatenation is

permuted using a function which is the exact inverse of the initial permutation. The output

of this final permutation is the 64 bit ciphertext.

15
So in total the processing of the plaintext proceeds in three phases as can be seen from

the left hand side of figure

1. Initial permutation (IP - defined in table 2.1) rearranging the bits to form the

“permuted input”.

2. Followed by 16 iterations of the same function (substitution and permutation). The

output of the last iteration consists of 64 bits which is a function of the plaintext and

key. The left and right halves are swapped to produce the preoutput.

3. Finally, the preoutput is passed through a permutation (IP−1 - defined in table 2.1)

which is simply the inverse of the initial permutation (IP). The output of IP−1 is the 64-

bitciphertext

16
As figure shows, the inputs to each round consist of the Li , Ri pair and a 48 bit subkey

which is a shifted and contracted version of the original 56 bit key. The use of the key can be

seen in the right hand portion of figure 2.2: • Initially the key is passed through a

permutation function (PC1 - defined in table 2.2) • For each of the 16 iterations, a subkey

(Ki) is produced by a combination of a left circular shift and a permutation (PC2 - defined in

table 2.2) which is the same for each iteration. However, the resulting subkey is different for

each iteration because of repeated shifts.

17
19
 DETAILS OF INDIVIDUAL ROUNDS

The main operations on the data are encompassed into what is referred to as the cipher function

and is labeled F. This function accepts two different length inputs of 32 bits and 48 bits
and

outputs a single 32 bit number. Both the data and key are operated on in parallel,
however the

operations are quite different. The 56 bit key is split into two 28 bit halves Ci and Di (C
and D

being chosen so as not to be confused with L and R). The value of the key used in any
round is

simply a left cyclic shift and a permuted contraction of that used in the previous round.

Mathematically, this can be written as

Ci = Lcsi(Ci−1), Di = Lcsi(Di−1)

Ki = P C2(Ci , Di)

whereLcsi is the left cyclic shift for round i, Ci and Di are the outputs after the shifts, P C2(.) is a
function which permutes and compresses a 56 bit number into a 48 bit number and Ki is the actual

20
key used in round i. The number of shifts is either one or two and is determined by the round
number i. For i = {1, 2, 9, 16} the number of shifts is one and for every other round it is two

21
S-BOX Details

21
2.3 ADVANCED ENCRYPTION ALGORITHM (AES)
 AES is a block cipher with a block length of 128 bits.
 AES allows for three different key lengths: 128, 192, or 256 bits. Most of our
discussion will assume that the key length is 128 bits.
 Encryption consists of 10 rounds of processing for 128-bit keys, 12 rounds for
192-bit keys, and 14 rounds for 256-bit keys.
 Except for the last round in each case, all other rounds are identical.
 Each round of processing includes one single-byte based substitution step, a row-
wise permutation step, a column-wise mixing step, and the addition of the round
key. The order in which these four steps are executed is different for encryption
and decryption.
 To appreciate the processing steps used in a single round, it is best to think of a
128-bit block as consisting of a 4 × 4 matrix of bytes, arranged as follows:

Therefore, the first four bytes of a 128-bit input block occupy the first column in
the 4 × 4 matrix of bytes. The next four bytes occupy the second column, and so
on.
The 4×4 matrix of bytes shown above is referred to as the state array in AES.

22
The algorithm begins with an Add round key stage followed by 9 rounds of four stages
and a tenth round of three stages.
This applies for both encryption and decryption with the exception that each stage of a
round the decryption algorithm is the inverse of its counterpart in the encryption
algorithm.
The four stages are as follows: 1. Substitute bytes 2. Shift rows 3. Mix Columns 4. Add
Round Key

Substitute Bytes
• This stage (known as SubBytes) is simply a table lookup using a 16 × 16 matrix of byte
values called an s-box.
• This matrix consists of all the possible combinations of an 8 bit sequence (28 = 16 × 16
= 256).
• However, the s-box is not just a random permutation of these values and there is a
well defined method for creating the s-box tables.

23
• The designers of Rijndael showed how this was done unlike the s-boxes in DES for
which no rationale was given.Our concern will be how state is effected in each round.
• For this particular round each byte is mapped into a new byte in the following way:
the leftmost nibble of the byte is used to specify a particular row of the s-box and the
rightmost nibble specifies a column.
• For example, the byte {95} (curly brackets represent hex values in FIPS PUB 197)
selects row 9 column 5 which turns out to contain the value {2A}.
• This is then used to update the state matrix.

Shift Row Transformation

• This stage (known as ShiftRows) is shown in figure below.
• Simple permutation an nothing more.
• It works as follow: – The first row of state is not altered. – The second row is shifted 1
bytes to the left in a circular manner. – The third row is shifted 2 bytes to the left in a
circular manner. – The fourth row is shifted 3 bytes to the left in a circular manner.

24
MIX COLUMN TRANSFORMATION
• This stage (known as MixColumn) is basically a substitution
• Each column is operated on individually. Each byte of a column is mapped into a new
value that is a function of all four bytes in the column.
• The transformation can be determined by the following matrix multiplication on state
• Each element of the product matrix is the sum of products of elements of one row and
one column.
• In this case the individual additions and multiplications are performed in GF(28 ).
• The MixColumns transformation of a single column j (0 ≤ j ≤ 3) of state can be
expressed as:
s ′ 0,j = (2 • s0,j) ⊕ (3 • s1,j) ⊕ s2,j ⊕ s3,j s
′ 1,j = s0,j ⊕ (2 • s1,j) ⊕ (3 • s2,j) ⊕ s3,j s ′
2,j = s0,j ⊕ s1,j ⊕ (2 • s2,j) ⊕ (3 • s3,j) s ′
3,j = (3 • s0,j) ⊕ s1,j ⊕ s2,j ⊕ (2 • s3,j)

ADD ROUND KEY TRANSFORMATION

• In this stage (known as AddRoundKey) the 128 bits of state are bitwise XORed with the
128 bits of the round key.
• The operation is viewed as a columnwise operation between the 4 bytes of a state
column and one word of the round key.

25
• This transformation is as simple as possible which helps in efficiency but it also effects
every bit of state.
• The AES key expansion algorithm takes as input a 4-word key and produces a linear
array of 44 words. Each round uses 4 of these words as shown in figure.
• Each word contains 32 bytes which means each subkey is 128 bits long. Figure 7 show
pseudocode for generating the expanded key from the actual key.

2.4 BLOWFISH ALGORITHM

• a symmetric block cipher designed by Bruce Schneier in 1993/94
• characteristics
• fast implementation on 32-bit CPUs
• compact in use of memory
• simple structure for analysis/implementation
• variable security by varying key size
• has been implemented in various products
BLOWFISH KEY SCHEDULE
• uses a 32 to 448 bit key, 32-bit words stored in K-array Kj ,j from 1 to 14
• used to generate
• 18 32-bit subkeys stored in P array, P1 ….P18
• four 8x32 S-boxes stored in Si,j , each with 256 32-bit entries
Subkeys and S-Boxes Generation:
1. initialize P-array and then 4 S-boxes in order using the fractional part of pi P1 (
left most 32-bit), and so on,,, S4,255.
2. XOR P-array with key-Array (32-bit blocks) and reuse as needed: assume we
have up to k10 then P10 XOR K10,, P11 XOR K1 … P18 XOR K8
3. Encrypt 64-bit block of zeros, and use the result to update P1 and P2.
4. encrypting output form previous step using current P & S and replace P3 and P4.
Then encrypting current output and use it to update successive pairs of P.
5. After updating all P’s (last :P17 P18), start updating S values using the encrypted
output from previous step.
• requires 521 encryptions, hence slow in re-keying
• Not suitable for limited-memory applications.

26
BLOWFISH ENCRYPTION
• uses two main operations: addition modulo 232 , and XOR
• data is divided into two 32-bit halves L0&R0
fori = 1 to 16 do
Ri= Li-1XOR Pi;
Li= F[Ri] XOR Ri-1;
L17= R16XOR P18;
R17= L16XOR P17;
• where
F[a,b,c,d] = ((S1,a + S2,b) XOR S3,c) + S4,d

27
2.5 Stream Ciphers and RC4

In this section we look at perhaps the most popular symmetric stream cipher, RC4. We
begin with an overview of stream cipher structure, and then examine RC4.

Stream Cipher Structure

A typical stream cipher encrypts plaintext one byte at a time, although a stream cipher
may be designed to operate on one bit at a time or on units larger than a byte at a time.
Figure 6.8 is a representative diagram of stream cipher structure. In this structure a key
is input to a pseudorandom bit generator that produces a stream of 8-bit numbers that
are apparently random. We discuss pseudorandom number generators in Chapter 7. For
now, we simply say that a pseudorandom stream is one that is unpredictable without
knowledge of the input key. The output of the generator, called a keystream, is
combined one byte at a time with the plaintext stream using the bitwise exclusive-OR
(XOR) operation.

For example, if the next byte generated by the generator is 01101100 and the next
plaintext byte is 11001100, then the resulting ciphertext byte is

Decryption requires the use of the same pseudorandom sequence:

Figure 6.8. Stream Cipher Diagram

The stream cipher is similar to the one-time pad discussed in. The difference is that a one-
time pad uses a genuine random number stream, whereas a stream cipher uses a
pseudorandom number stream.

lists the following important design considerations for a stream cipher:

1. The encryption sequence should have a large period. A pseudorandom number generator
uses a function that produces a deterministic stream of bits that eventually repeats. The
longer the period of repeat the more difficult it will be to do cryptanalysis. This is essentially
the same consideration that was discussed with reference to the Vigenère cipher, namely
that the longer the keyword the more difficult the cryptanalysis.

2.The keystream should approximate the properties of a true random number stream as
close as possible. For example, there should be an approximately equal number of 1s and 0s.
If the keystream is treated as a stream of bytes, then all of the 256 possible byte values
should appear approximately equally often. The more random-appearing the keystream is,
the more randomized the ciphertext is, making cryptanalysis more difficult.

3.Note from Figure 6.8 that the output of the pseudorandom number generator is
conditioned on the value of the input key. To guard against brute-force attacks, the key needs
to be sufficiently long. The same considerations as apply for block ciphers are valid here.
Thus, with current
technology, a key length of at least 128 bits is desirable.

With a properly designed pseudorandom number generator, a stream cipher can be as

secure as block cipher of comparable key length. The primary advantage of a stream cipher is
that stream ciphers are almost always faster and use far less code than do block ciphers. The
example in this section, RC4, can be implemented in just a few lines of code. Table 6.2, using
data from compares execution times of RC4 with three well-known symmetric block ciphers.
The advantage of a block cipher is that you can reuse keys. However, if two plaintexts are

28
 encrypted with the same key using a stream cipher then cryptanalysis is often quite simple .
If the two ciphertext streams are XORed together, the result is the XOR of the original
plaintexts. If the plaintexts are text strings, credit card numbers, or other byte streams
with known properties, then cryptanalysis may be successful.

Table 6.2. Speed Comparisons of Symmetric Ciphers on a Pentium II

Cipher Key Length Speed (Mbps)

DES 56 9
3DES 168 3
RC2 variable 0.9
RC4 variable 45

For applications that require encryption/decryption of a stream of data, such as over a data
communications channel or a browser/Web link, a stream cipher might be the better
alternative. For applications that deal with blocks of data, such as file transfer, e-mail, and
database, block ciphers may be more appropriate. However, either type of cipher can be
used in virtually any application.

The RC4 Algorithm

RC4 is a stream cipher designed in 1987 by Ron Rivest for RSA Security. It is a variable key-size
stream cipher with byte-oriented operations. The algorithm is based on the use of a random
permutation.
Analysis shows that the period of the cipher is overwhelmingly likely to be greater than 10100.
Eight to sixteen machine operations are required per output byte, and the cipher can be
expected to run very quickly in software. RC4 is used in the SSL/TLS (Secure Sockets
Layer/Transport Layer Security) standards that have been defined for communication
between Web browsers and servers. It is also used in the WEP (Wired Equivalent Privacy)
protocol and the newer WiFi Protected Access (WPA) protocol that are part of the IEEE
802.11 wireless LAN standard. RC4 was kept as a trade secret by RSA Security. In September
1994, the RC4 algorithm was anonymously posted on the Internet on the Cypherpunks
anonymous remailers list.

The RC4 algorithm is remarkably simply and quite easy to explain. A variable-length key of
from 1 to 256 bytes (8 to 2048 bits) is used to initialize a 256-byte state vector S, with
elements S[0], S[1],..., S [255]. At all times, S contains a permutation of all 8-bit numbers from
0 through 255. For encryption and decryption, a byte k is generated from S by selecting one of
the 255 entries in a
systematic fashion. As each value of k is generated, the entries in S are once again permuted.

29
 Initialization of S

To begin, the entries of S are set equal to the values from 0 through 255 in ascending order;
that is; S[0] = 0, S[1] = 1,..., S[255] = 255. A temporary vector, T, is also created. If the length
of the key K is 256 bytes, then K is transferred to T. Otherwise, for a key of length keylen
bytes, the first keylen elements of T are copied from K and then K is repeated as many times
as necessary to fill out T. These preliminary operations can be summarized as follows:

Next we use T to produce the initial permutation of S. This involves starting with S[0] and
going through to S[255], and, for each S[i], swapping S[i] with another byte in S according
to a scheme dictated by T [i]:

/* Initial Permutation of S */ j = 0;
for i = 0 to 255 do
j = (j + S[i] + T[i]) mod 256;
Swap (S[i], S[j]);

Because the only operation on S is a swap, the only effect is a permutation. S still contains
all the numbers from 0 through 255.

Stream Generation

Once the S vector is initialized, the input key is no longer used. Stream generation involves
cycling through all the elements of S[i], and, for each S[i], swapping S[i] with another byte
in S according to a scheme dictated by the current configuration of S. After S[255] is
reached, the process continues, starting over again at S[0]:

while (true)
i = (i + 1) mod 256;
j = (j + S[i]) mod 256;
Swap (S[i], S[j]);
t = S[i] + S[j]) mod 256; k = S[t];

To encrypt, XOR the value k with the next byte of plaintext. To decrypt, XOR the value k
with the next byte of ciphertext.

30
 Strength of RC4

A number of papers have been published analyzing methods of attacking RC4 [e.g.,
[KNUD98], [MIST98], [FLUH00], [MANT01]). None of these approaches is practical against
RC4 with a reasonable key length, such as 128 bits. A more serious problem is reported in
[FLUH01]. The authors demonstrate
that the WEP protocol, intended to provide confidentiality on 802.11 wireless LAN
networks, is vulnerable to a particular attack approach. In essence, the problem is not with
RC4 itself but the way in which keys are generated for use as input to RC4. This particular
problem does not appear to be relevant to other applications using RC4 and can be
remedied in WEP by changing the way in which keys are generated. This problem points
out the difficulty in designing a secure system that involves both cryptographic functions
and protocols that make use of them.

2.6 RC5 Encryption Algorithm

RC5 is a symmetric key block encryption algorithm designed by Ron Rivest in 1994. It is
notable for being simple, fast (on account of using only primitive computer operations like
XOR, shift, etc.) and consumes less memory.

31
Example:
Key : 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Plain Text : 00000000 00000000
Cipher Text : EEDBA521 6D8F4B15
RC5 is a block cipher and addresses two word blocks at a time.
Depending on input plain text block size, number of rounds and key size, various instances
of RC5 can be defined and each instance is denoted as RC5-w/r/b where w=word size in
bits, r=number of rounds and b=key size in bytes.
Allowed values are:

Possible
Parameter Value

block/word size 16, 32,

(bits) 64

Number of
Rounds 0 – 255

Key Size (bytes) 0 – 255

Note – Since at a time, RC5 uses 2 word blocks, the plain text block size can be 32, 64 or
128 bits.
Notation used in the algorithm:

Symb
ol Operation

Cyclic left
x <<< shift of x by
y y bits

Two’s
compleme
nt addition
of words
where
addition is
modulo
+

^ Bit wise

32
 Symb
ol Operation

Exclusive-
OR

Step-1: Initialization of constants P and Q.

RC5 makes use of 2 magic constants P and Q whose value is defined by the word size w.

Word Size (bits) P (Hexadecimal) Q (Hexadecimal)

16 b7e1 9e37

32 b7e15163 9e3779b9

64 b7e151628aed2a6b 9e3779b97f4a7c15

For any other word size, P and Q can be determined as:

P = Odd((e-2) )

Q = Odd(( -2) )
Here, Odd(x) is the odd integer nearest to x, e is the base of natural logarithms and is the
golden ratio.

Step-2: Converting secret key K from bytes to words.

Secret key K of size b bytes is used to initialize array L consisting of c words where c = b/u,
u = w/8 and w = word size used for that particular instance of RC5. For example, if we
choose w=32 bits and Key k is of size 96 bytes then, u=32/8=4, c=b/u=96/4=24.
L is pre initialized to 0 value before adding secret key K to it.
for i=b-1 to 0
L[i/u] = (L[u/i] <<< 8) + K[i]

Step-3: Initializing sub-key S.

Sub-key S of size t=2(r+1) is initialized using magic constants P and Q.

S[0] = P
for i = 1 to 2(r+1)-1
S[i] = S[i-1] + Q)

Step-4: Sub-key mixing.

The RC5 encryption algorithm uses Sub key S. L is merely, a temporary array formed on
33
 the basis of user entered secret key.
Mix in user’s secret key with S and L.
i = j = 0
A = B = 0
do 3 * max(t, c) times:
A = S[i] = (S[i] + A + B) <<< 3
B = L[j] = (L[j] + A + B) <<< (A + B)
i = (i + 1) % t
j = (j + 1) % c

Step-5: Encryption.

We divide the input plain text block into two registers A and B each of size w bits. After
undergoing the encryption process the result of A and B together forms the cipher text
block.

RC5 Encryption Algorithm:

1. One time initialization of plain text blocks A and B by adding S[0] and S[1] to A and B
respectively. These operations are mod .
2. XOR A and B. A=A^B
3. Cyclic left shift new value of A by B bits.
4. Add S[2*i] to the output of previous step. This is the new value of A.
5. XOR B with new value of A and store in B.
6. Cyclic left shift new value of B by A bits.
7. Add S[2*i+1] to the output of previous step. This is the new value of B.
8. Repeat entire procedure (except one time initialization) r times.
A = A + S[0]
B = B + S[1]
for i = 1 to r do:
A = ((A ^ B) <<< B) + S[2 * i]
B = ((B ^ A) <<< A) + S[2 * i + 1]
return A, B
Alternatively, RC5 Decryption can be defined as:
for i = r down to 1 do:
B = ((B - S[2 * i + 1]) >>> A) ^ A
A = ((A - S[2 * i]) >>> B) ^ B
B = B - S[1]
A = A - S[0]
return A, B

2.7 BLOCK CIPHER MODES OF OPERATIONS

• Direct use of a block cipher is inadvisable

• Enemy can build up “code book” of plaintext/ciphertext equivalents
34
• Beyond that, direct use only works on messages that are a multiple of the cipher block size in length
• Solution: five standard Modes of Operation: Electronic Code Book (ECB), Cipher Block Chaining
(CBC), Cipher Feedback (CFB), Output Feedback (OFB), and Counter (CTR).

Electronic Code Book

• Direct use of the block cipher
• Used primarily to transmit encrypted keys
• Very weak if used for general-purpose encryption; never use it for a file or a message.
• Attacker can build up codebook; no semantic security
• We write {P}k → C to denote “encryption of plaintext P with key k to produce ciphertext C”

35
Cipher Block Chaining
• We would like that same plaintext blocks produce different ciphertext blocks.
• Cipher Block Chaining (see figure) allows this by XORing each plaintext with the
Ciphertext from the previous round (the first round using an Initialisation Vector
(IV)).
• As before, the same key is used for each block.

operation, i.e. IV ⊕ IV ⊕ P = P where IV is the Initialisation Vector and P is the plaintext.

• Decryption works as shown in the figure because of the properties of the XOR

• Obviously the IV needs to be known by both sender and receiver and it should be kept
secret along with the key for maximum security.

Cipher Feedback (CFB) Mode

• The Cipher Feedback and Output Feedback allows a block cipher to be converted into
a stream cipher.
• This eliminates the need to pad a message to be an integral number of blocks. It also
can operate in real time.

36
• Figure shows the CFB scheme.
• In this figure it assumed that the unit of transmission is s bits; a common value is s = 8.

37
• As with CBC, the units of plaintext are chained together, so that the ciphertext of any
plaintext unit is a function of all the preceding plaintext (which is split into s bit
segments).
• The input to the encryption function is a shift register equal in length to the block
cipher of the algorithm (although the diagram shows 64 bits, which is block size used by
DES, this can be extended to other block sizes such as the 128 bits of AES).
• This is initially set to some Initialisation Vector (IV).

OUTPUT FEEDBACK (OFB) MODE

• The Output Feedback Mode is similar in structure to that of CFB, as seen in figure 13.
• As can be seen, it is the output of the encryption function that is fed back to the shift
register in OFB, whereas in CFB the ciphertext unit is fed back to the shift register.
• One advantage of the OFB method is that bit errors in transmission do not propagate.

38
• For example, if a bit error occurs in C1 only the recovered value of P1 is affected;
subsequent plaintext units are not corrupted.
With CFB, C1 also serves as input to the shift register and therefore causes additional
corruption downstream.

39
Counter Mode

2.8 PUBLIC KEY CRYPTOGRAPHY

The development of public-key cryptography is the greatest and perhaps the
only true revolution in the entire history of cryptography. It is asymmetric, involving the
use of two separate keys, in contrast to symmetric encryption, which uses only one key.
Public key schemes are neither more nor less secure than private key (security depends
on the key size for both). Public-key cryptography complements rather than replaces
symmetric cryptography. Both also have issues with key distribution, requiring the use

40
of some suitable protocol. The concept of public-key cryptography evolved from an
attempt to attack two of the most difficult problems associated with symmetric
encryption:
1.) key distribution – how to have secure communications in general without having to
trust a KDC with your key

2.) digital signatures – how to verify a message comes intact from the claimed
sender Public-key/two-key/asymmetric cryptography involves the use of two keys:
 a public-key, which may be known by anybody, and can be used to
encryptmessages, and verify signatures
 a private-key, known only to the recipient, used to decrypt messages, and sign
(create) signatures.
 is asymmetric because those who encrypt messages or verify signatures cannot
decrypt messages or create signatures

Public-Key algorithms rely on one key for encryption and a different but related key
for decryption. These algorithms have the following important characteristics:
 it is computationally infeasible to find decryption key knowing only algorithm &
encryption key
 it is computationally easy to en/decrypt messages when the relevant
(en/decrypt) key is known
 either of the two related keys can be used for encryption, with the other used for
decryption (for some algorithms like RSA)
The following figure illustrates public-key encryption process and shows that a public-key
encryption scheme has six ingredients: plaintext, encryption algorithm, public & private
keys, ciphertext& decryption algorithm.

41
The essential steps involved in a public-key encryption scheme are given below:
1.) Each user generates a pair of keys to be used for encryption and decryption.

2.) Each user places one of the two keys in a public register and the other key is kept
private.

3.) If B wants to send a confidential message to A, B encrypts the message using A’s
public key.

4.) When A receives the message, she decrypts it using her private key. Nobody else can
decrypt the message because that can only be done using A’s private key (Deducing a
private key should be infeasible).

5.) If a user wishes to change his keys –generate another pair of keys and publish the
public one: no interaction with other users is needed.
Notations used in Public-key cryptography:
 The public key of user A will be denoted KUA.
 The private key of user A will be denoted KRA.
 Encryption method will be a function E.
 Decryption method will be a function D.
 If B wishes to send a plain message X to A, then he sends the cryptotext Y=E(KUA,X)
 The intended receiver A will decrypt the message: D(KRA,Y)=X
The first attack on Public-key Cryptography is the attack on Authenticity. An attacker
mayimpersonate user B: he sends a message E(KUA,X) and claims in the message to be B–
A hasno guarantee this is so. To overcome this, B will encrypt the message using his private
key: Y=E(KRB,X). Receiver decrypts using B’s public key KRB. This shows the authenticity of
the sender because (supposedly) he is the only one who knows the private key. The entire
encrypted message serves as a digital signature. This scheme is depicted in the following
figure:

42
But, a drawback still exists. Anybody can decrypt the message using B’s public key. So,
secrecy or confidentiality is being compromised. One can provide both authentication
andconfidentiality using the public-key scheme twice:

B encrypts X with his private key: Y=E(KRB,X)

B encrypts Y with A’s public key: Z=E(KUA,Y)

A will decrypt Z (and she is the only one capable of doing it): Y=D(KRA,Z)

A can now get the plaintext and ensure that it comes from B (he is the only one who
knows his private key): decrypt Y using B’s public key: X=E(KUB,Y).

43
 Applications for public-key cryptosystems:
1.) Encryption/decryption: sender encrypts the message with the receiver’s public key.

2.) Digital signature: sender “signs” the message (or a representative part of the
message) using his private key

3.) Key exchange: two sides cooperate to exchange a secret key for later use in a secret-
key cryptosystem.

The main requirements of Public-key cryptography are:

1. Computationally easy for a party B to generate a pair (public key KUb, private key KRb).

2. Easy for sender A to generate ciphertext:

3. Easy for the receiver B to decrypt ciphertect using private key:

4. Computationally infeasible to determine private key (KRb) knowing public key (KUb)
5. Computationally infeasible to recover message M, knowing KUb and ciphertext C
6. Either of the two keys can be used for encryption, with the other used for decryption:
M= DKRb[EKUb(M)]=DKUb[EKRb(M)]
Easy is defined to mean a problem that can be solved in polynomial time as a function of
input length. A problem is infeasible if the effort to solve it grows faster than polynomial
time as a function of input size. Public-key cryptosystems usually rely on difficult math
functions rather than S-P networks as classical cryptosystems. One-way function is
one, easy to calculate in one direction, infeasible to calculate in the other direction (i.e.,
the inverse is infeasible to compute). Trap-door function is a difficult function that
becomes easy if some extra information is known. Our aim to find a trap-door one-way
function, which is easy to calculate in one direction and infeasible to calculate in the
other direction unless certain additional information is known.
Security of Public-key schemes:
 Like private key schemes brute force exhaustive search attack is always
theoretically possible. But keys used are too large (>512bits).
 Security relies on a large enough difference in difficulty between easy
(en/decrypt) and hard (cryptanalyse) problems. More generally the hard
problem is known, its just made too hard to do in practise.

44
  Requires the use of very large numbers, hence is slow compared to private key
schemes

2.9 RSA ALGORITHM

RSA is the best known, and by far the most widely used general public key
encryption algorithm, and was first published by Rivest, Shamir &Adleman of MIT in
1978 [RIVE78]. Since that time RSA has reigned supreme as the most widely accepted
and implemented general-purpose approach to public-key encryption. The RSA scheme
is a block cipher in which the plaintext and the ciphertext are integers between 0 and n-
1 for some fixed n and typical size for n is 1024 bits (or 309 decimal digits). It is based
on exponentiation in a finite (Galois) field over integers modulo a prime, using large
integers (eg. 1024 bits). Its security is due to the cost of factoring large numbers. RSA
involves a public-key and a private-key where the public key is known to all and is used
to encrypt data or message. The data or message which has been encrypted using a
public key can only be decryted by using its corresponding private-key. Each user
generates a key pair i.e. public and private key using the following steps:
 each user selects two large primes at random - p, q
 compute their system modulus n=p.q
 calculate ø(n), where ø(n)=(p-1)(q-1)
 selecting at random the encryption key e, where 1<e<ø(n),and gcd(e,ø(n))=1
 solve following equation to find decryption key d: e.d=1 mod ø(n) and 0≤d≤n
 publish their public encryption key: KU={e,n}
 keep secret private decryption key: KR={d,n}

Both the sender and receiver must know the values of n and e, and only the receiver
knows the value of d. Encryption and Decryption are done using the following
equations. To encrypt a message M the sender:
– obtains public key of recipient KU={e,n}
– computes: C=Me mod n, where 0≤M<n
To decrypt the ciphertext C the owner:
– uses their private key KR={d,n}
– computes: M=Cd mod n = (Me) d mod n = Med mod n

45
For this algorithm to be satisfactory, the following requirements are to be met.
a) Its possible to find values of e, d, n such that Med = M mod n for all M<n
b) It is relatively easy to calculate Me and C for all values of M < n.
c) It is impossible to determine d given e and n

The way RSA works is based on Number theory: Fermat’s little theorem: if p is
prime and a is positive integer not divisible by p, then ap-1 ≡ 1 mod p. Corollary: For
any positive integer a and prime p, ap ≡ a mod p.

Fermat’s theorem, as useful as will turn out to be does not provide us with integers
d,e we are looking for –Euler’s theorem (a refinement of Fermat’s) does. Euler’s function
associates to any positive integer n, a number φ(n): the number of positive integers smaller
than n and relatively prime to n. For example, φ(37) = 36 i.e. φ(p) = p-1 for any prime p.
For any two primes p,q, φ(pq)=(p-1)(q-1). Euler’s theorem: for any relatively prime
integers a,n we have aφ(n)≡1 mod n. Corollary: For any integers a,n we have aφ(n)+1≡a
mod n Corollary: Let p,q be two odd primes and n=pq. Then: φ(n)=(p-1)(q-1) For any
integer m with 0<m<n, m(p-1)(q-1)+1 ≡ m mod n For any integers k,m with
0<m<n, mk(p-1)(q-1)+1 ≡ m mod n Euler’s theorem provides us the numbers d, e such
that Med=M mod n. We have to choose d,e such that ed=kφ(n)+1, or equivalently, d≡e-
1mod φ(n)

An example of RSA can be given as,

Select primes: p=17 &q=11 Compute n
= pq =17×11=187 Compute ø(n)=(p–
1)(q-1)=16×10=160 Select e
:gcd(e,160)=1; choose e=7
Determine d: de=1 mod 160 and d< 160 Value is d=23 since 23×7=161= 10×160+1
Publish public key KU={7,187}
Keep secret private key KR={23,187}
Now, given message M = 88 (nb. 88<187)
encryption: C = 887 mod 187 = 11
decryption: M = 1123 mod 187 = 88

46
Another example of RSA is given as,
Let p = 11, q = 13, e = 11, m = 7
n = pqi.e. n= 11*13 = 143
ø(n)= (p-1)(q-1) i.e. (11-1)(13-1) = 120
e.d=1 mod ø(n) i.e. 11d mod 120 = 1 i.e. (11*11) mod 120=1;so
d = 11 public key :{11,143} and private key: {11,143}
C=Me mod n, so ciphertext = 711mod143 = 727833 mod 143; i.e. C =
106 M=Cd mod n, plaintext = 10611 mod 143 = 1008 mod 143; i.e. M = 7

For RSA key generation,

– determine two primes at random - p, q

– select either e or d and compute the other

– means must be sufficiently large

– typically guess and use probabilistic test

Security of RSA
There are three main approaches of attacking RSA algorithm.
Brute force key search (infeasible given size of numbers) As explained before,
involvestrying all possible private keys. Best defence is using large keys.
Mathematical attacks (based on difficulty of computing ø(N), by factoring modulus
N)There are several approaches, all equivalent in effect to factoring the product of two
primes. Some of them are given as:

47
 – factor N=p.q, hence find ø(N) and then d

– determine ø(N) directly and find d

– find d directly

The possible defense would be using large keys and also choosing large numbers for p
and q, which should differ only by a few bits and are also on the order of magnitude
1075 to 10100. And gcd (p-1, q-1) should be small.

2.10 ElGamal Encryption Algorithm:

ElGamal encryption is a public-key cryptosystem. It uses asymmetric key encryption for

communicating between two parties and encrypting the message.
This cryptosystem is based on the difficulty of finding discrete logarithm in a cyclic group
that is even if we know ga and gk, it is extremely difficult to compute gak.

Idea of ElGamal cryptosystem

Suppose Alice wants to communicate with Bob.

1. Bob generates public and private keys:

 Bob chooses a very large number q and a cyclic group Fq.
 From the cyclic group Fq, he choose any element g and
an element a such that gcd(a, q) = 1.
 Then he computes h = ga.
 Bob publishes F, h = ga, q, and g as his public key and retains a as private key.
2. Alice encrypts data using Bob’s public key :
 Alice selects an element k from cyclic group F
such that gcd(k, q) = 1.
 Then she computes p = gk and s = hk = gak.
 She multiples s with M.
 Then she sends (p, M*s) = (gk, M*s).
3. Bob decrypts the message :
 Bob calculates s′ = pa = gak.
 He divides M*s by s′ to obtain M as s = s′.
 In this cryptosystem, the original message M is masked by multiplying gak to it.
To remove the mask, a clue is given in form of gk. Unless someone knows a, he
will not be able to retrieve M. This is because finding discrete log in a cyclic
group is difficult and simplifying knowing g a and gk is not good enough to
compute gak.

48
 2.11 DIFFIE-HELLMAN KEY EXCHANGE
Diffie-Hellman key exchange (D-H) is a cryptographic protocol that allows two
partiesthat have no prior knowledge of each other to jointly establish a shared secret
key over an insecure communications channel. This key can then be used to encrypt
subsequent communications using a symmetric key cipher. The D-H algorithm depends
for its effectiveness on the difficulty of computing discrete logarithms.
First, a primitive root of a prime number p, can be defined as one whose powers
generate all the integers from 1 to p-1. If a is a primitive root of the prime number p,
then the numbers, a mod p, a2mod p,..., ap-1mod p, 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

isuch that .The exponent i is referred to as the

discrete logarithm of b for the base a, mod p. We express this value as dloga,p(b). The
algorithm is summarized below:

49
For this scheme, there are two publicly known numbers: a prime number q and an
integer α that is a primitive root of q. Suppose the users A and B wish to exchange a key.
User A selects a random integer XA< q and computes YA = αXA mod q. Similarly, user B
independently selects a random integer XA< q and computes YB = αXB mod q. Each side
keeps the X value private and makes the Y value available publicly to the other side.
User A computes the key as K = (YB)XA mod q and user B computes the key as K = (Y A)XB
mod q. These two calculations produce identical results.
Discrete Log Problem
The (discrete) exponentiation problem is as follows: Given a base a, an exponent b and a
modulus p, calculate c such that ab ≡ c (mod p) and 0 ≤ c < p. It turns out that this problem
is fairly easy and can be calculated "quickly" using fast-exponentiation. The discrete log
problem is the inverse problem: Given a base a, a result c (0 ≤ c < p) and a modulus p,

50
calculate the exponent b such that ab≡ c (mod p). It turns out that no one has found
a quick way to solve this problem With DLP, if P had 300 digits, X a and Xb have more
than 100 digits, it would take longer than the life of the universe to crack the method.
Examples for D-H key distribution scheme:
1) Let p = 37 and g = 13.

Let Alice pick a = 10. Alice calculates 13 10 (mod 37) which is 4 and sends that to Bob. Let
Bob pick b = 7. Bob calculates 137 (mod 37) which is 32 and sends that to Alice. (Note: 6 and
7 are secret to Alice and Bob, respectively, but both 4 and 32 are known by all.)
10 (mod 37) which is 30, the secret key.

7 (mod 37) which is 30, the same secret key.

2) Let p = 47 and g = 5. Let Alice pick a = 18. Alice calculates 5 18(mod 47) which is 2
andsends that to Bob. Let Bob pick b = 22. Bob calculates 5 22 (mod 47) which is 28 and
sends that to Alice.
18 (mod 47) which is 24, the secret key.

22 (mod 47) which is 24, the same secret key

Man-in-the-Middle Attack on D-H protocol

Suppose Alice and Bob wish to exchange keys, and Darth is the adversary. The attack
proceeds as follows:
1. Darth prepares for the attack by generating two random private keys XD1 and XD2 and
then computing the corresponding public keys YD1 and YD2.

2. Alice transmits YA to Bob.

3. Darth intercepts YA and transmits YD1 to Bob. Darth also calculates K2 = (YA)XD2mod q.

4. Bob receives YD1 and calculates K1 = (YD1)XE mod q.

5. Bob transmits XA to Alice.

6. Darth intercepts XA and transmits YD2 to Alice. Darth calculates K1 = (YB)XD1 mod q.

7. Alice receives YD2 and calculates K2 = (YD2)XA mod q.

51
At this point, Bob and Alice think that they share a secret key, but instead Bob and Darth
share secret key K1 and Alice and Darth share secret key K2. All future communication
between Bob and Alice is compromised in the following way:
1. Alice sends an encrypted message M: E(K2, M).

2. Darth intercepts the encrypted message and decrypts it, to recover M.

3. Darth sends Bob E(K1, M) or E(K1, M'), where M' is any message. In the first case,
Darth simply wants to eavesdrop on the communication without altering it. In the
second case, Darth wants to modify the message going to Bob.
The key exchange protocol is vulnerable to such an attack because it does not
authenticate the participants. This vulnerability can be overcome with the use of digital
signatures and public-key certificates.

ELLIPTIC CURVE CRYPTOGRAPHY (ECC)

Elliptic curve cryptography (ECC) is an approach to public-key cryptography based
onthe algebraic structure of elliptic curves over finite fields. The use of elliptic curves in
cryptography was suggested independently by Neal Koblitz and Victor S. Miller in 1985.
The principal attraction of ECC compared to RSA is that it appears to offer equal
security for a far smaller bit size, thereby reducing the processing overhead.
Elliptic Curve over GF(p)
Let GF(p) be a finite field, p > 3, and let a, b
4a3 + 27b2 ≡ 0 (mod p).An elliptic curve, E(a,b)(GF(p)),is

defined as the set of points (x,y) ᴄ GF(p) * GF(p) which satisfy the equation
y2 ≡ x3 + ax + b (mod p), together with a special point, O, called the point at infinity.
LetP and Q be two points on E(a,b)(GF(p)) and O is the point at infinity.
• P+O = O+P = P

• If P = (x1,y1) then -P = (x1 ,-y1) and P + (-P) = O.

• If P = (x1,y1) and Q = (x2,y2), and P and Q are not O.

then P +Q = (x3 ,y3)

where x3 = ƛ 2 - x1 - x2

52
y3 = ƛ (x1 - x3) - y1 and
ƛ = (y2-y1)/(x2-x1) if P ≠ Q
ƛ = (3x12+a)/ 2y1 if P = Q

An elliptic curve may be defined over any finite field GF(q). For GF(2m), the curve has a
different form:- y2+xy=x3+ax2+b,where b !=0.

Cryptography with Elliptic Curves

The addition operation in ECC is the counterpart of modular multiplication in RSA, and
multiple addition is the counterpart of modular exponentiation. To form a cryptographic
system using elliptic curves, some kind of hard problem such as discrete logarithm or
factorization of prime numbers is needed. Considering the equation, Q=kP, where Q,P are
points in an elliptic curve, it is “easy” to compute Q given k,P , but “hard” to find k given Q,P.
This is known as the elliptic curve logarithm problem. k could be so large as to make brute-
force fail.

ECC Key Exchange

Pick a prime number p= 2180 and elliptic curve parameters a and b for the equation
y2 ≡ x3 + ax + b (mod p) which defines the elliptic group of points Ep(a,b).
Selectgenerator point G=(x1,y1) in Ep(a,b) such that the smallest value for which nG=O
be a very large prime number. Ep(a,b) and G are parameters of the cryptosystem known
to all participants. The following steps take place:
• A & B select private keys nA<n, nB<n

• compute public keys: PA=nA×G, PB=nB×G

• Compute shared key: K=nA×PB, K=nB×PA {same since K=nA×nB×G }

ECC Encryption/Decryption As with key exchange system, an

encryption/decryptionsystem requires a point G and and elliptic group Ep(a,b) as
parameters. First thing to be done is to encode the plaintext message m to be sent as an
x-y point Pm. Each user chooses private key nA<n and computes public key PA=nA×G.
To encrypt and send a message to Pm to B, A chooses a random positive integer k and
produces the ciphertextCm consisting of the pair of points Cm={kG, Pm+kPb}. here, A
uses B’s public key. To

53
 decrypt the ciphertext, B multiplies the first point in the pair by B’s secret key and subtracts
the result from the second point Pm+kPb–nB(kG) = Pm+k(nBG)–nB(kG)
=Pm A has masked the message Pm by adding kPbto it. Nobody but A knows the value ofk, so
even though Pb is a public key, nobody can remove the mask kPb. For an attacker to recover
the message, he has to compute k given G and kG, which is assumed hard.
Security of ECC To protect a 128 bit AES key it would take a RSA Key Size of 3072
bitswhereas an ECC Key Size of 256 bits.

Hence for similar security ECC offers significant computational advantages.

Applications of ECC:
 Wireless communication devices
 Smart cards
 Web servers that need to handle many encryption sessions
 Any application where security is needed but lacks the power, storage and computational power
that is necessary for our current cryptosystems

2.12 KNAPSACK ALGORITHM

Public-Key cryptography was invented in the 1970s by Whitfield Diffie, Martin Hellman and
Ralph Merkle.
Public-key cryptography needs two keys. One key tells you how to encrypt (or code) a
message and this is "public" so anyone can use it. The other key allows you to decode (or
decrypt) the message. This decryption code is kept secret (or private) so only the person.

who knows the key can decrypt the message. It is also possible for the personwith the private

54
key to encrypt a message with the private key, then anyone holding the public key can decrypt
the message, although this seems to be of little use if you are trying to keep something secret!

The First General Public-Key Algorithm used what we call the Knapsack Algorithm. Although we
now know that this algorithm is not secure we can use it to look at how these types of encryption
mechanisms work.
The knapsack algorithm works like this:

Imagine you have a set of different weights which you can use to make any total weight that you
need by adding combinations of any of these weights together.

Let us look at an example:

Imagine you had a set of weights 1, 6, 8, 15 and 24. To pack a knapsack weighing 30, you could
use weights 1, 6, 8 and 15. It would not be possible to pack a knapsack that weighs 17 but this
might not matter.

You might represent the weight 30 by the binary code 11110 (one 1, one 6, one 8, one 15 and no
24).

Example:

Plain text 10011 11010 01011 00000

Knapsack 18 15 24 1 15 24 1 8 15 24 8 15 24
6
6 8

Cipher text 115 + 24 = 40 1 + + 15 = 22 6 15 + 24 = 45 0

6
+

55
What total weights is it possible to make?

So, if someone sends you the code 38 this can only have come from the plain text 01101. When
the Knapsack Algorithm is used in public key cryptography, the idea is to create two different
knapsack problems. One is easy to solve, the other not. Using the easy knapsack, the hard
knapsack is derived from it. The hard knapsack becomes the public key. The easy knapsack is the
private key. The public key can be used to encrypt messages, but cannot be used to decrypt
messages. The private key decrypts the messages.The Superincreasing Knapsack Problem

An easy knapsack problem is one in which the weights are in a superincreasing sequence. A
superincreasing sequence is one in which the next term of the sequence is greater than the sum
of all preceding terms. For example, the set {1, 2, 4, 9, 20, 38} is superincreasing, but the
set {1, 2, 3, 9, 10, 24} is not because 10 < 1+2+3+9.

It is easy to solve a superincreasing knapsack. Simply take the total weight of the knapsack and
compare it with the largest weight in the sequence. If the total weight is less than the number,
then it is not in the knapsack. If the total weight is greater then the number, it is in the knapsack.
Subtract the number from the total, and compare with the next highest number. Keep working
this way until the total reaches zero. If the total doesn't reach zero, then there is no solution.
So, for example, if you have a knapsack that weighs 23 that has been made from the weights of
the superincreasing series {1, 2, 4, 9, 20, 38} then it does not contain the weight
38 (as 38 > 23) but it does contain the weight 20; leaving 3; which does not contain the weight 9
still leaving 3; which does not contain the weight 4 still leaving 3; which contains the weight 2,
leaving 1; which contains the weight 1. The binary code is therefore 110010.
It is much harder to decrypt a non-superincreasing knapsack problem. Give a friend a non-
superincreasing knapsack and a total and see why this is the case.

One algorithm that uses a superincreasing knapsack for the private (easy) key and a non-
superincreasing knapsack for the public key was created by Merkle and Hellman They did this
by taking a superincreasing knapsack problem and converting it into a non- superincreasing one
that could be made public, using modulus arithmetic.

Making the Public Key

To produce a normal knapsack sequence, take a superincreasing sequence; e.g. {1, 2, 4, 10, 20,
40}. Multiply all the values by a number, n, modulo m. The modulus should be a number greater
than the sum of all the numbers in the sequence, for example, 110. Themultiplier should have no

56
factors in common with the modulus. So let's choose 31. The normal knapsack sequence would
be:
1×31 mod(110) = 31
2×31 mod(110) = 62
4×31 mod(110) = 14
10×31 mod(110) = 90
20×31 mod(110) = 70
40×31 mod(110) = 30
So the public key is: {31, 62, 14, 90, 70, 30} and the
private key is {1, 2, 4, 10, 20.40}.

Let's try to send a message that is in binary code: 100100111100101110

The knapsack contains six weights so we need to split the message into groups of six: 100100

111100 101110

This corresponds to three sets of weights with totals as follows 100100 = 31 + 90 = 121 111100
= 31+62+14+90 = 197 101110 =
31+14+90+70 =205So the coded message is 121 197 205. Now the receiver has to decode the
message...

The person decoding must know the two numbers 110 and 31 (the modulus and the multiplier).
Let's call the modulus "m" and the number you multiply by "n".

We need n−1, which is a multiplicative inverse of n mod m, i.e. n(n−1) = 1 mod m

In this case I have calculated n−1 to be 71.All you then have to do is multiply each of the codes 71
mod 110 to find the total in the knapsack which contains {1, 2, 4, 10, 20, 40} and hence to decode
the message.

The coded message is 121 197 205:

121×71 mod(110) = 11 = 100100

197×71 mod(110) = 17 = 111100
205×71 mod(110) = 35 = 101110

The decoded message is:

100100111100101110.
Just as I thought!
Simple and short knapsack codes are far too easy to break to be of any real use. For a knapsack
code to be reasonably secure it would need well over 200 terms each of length 200 bits.
57