Cis Unit2 Notes

Download as docx, pdf, or txt
Download as docx, pdf, or txt
You are on page 1of 35

UNIT – II

Symmetric key Ciphers: Block Cipher principles, DES, AES, Block cipher operations,
Asymmetric key Ciphers: Principles of public key cryptosystems, RSA algorithm, Diffie-Hellman Key
Exchange.

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.
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 L i-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
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 subkey ki. 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 searching
harder, but may slow cipher
 Number of rounds - Increasing number improves security, but slows cipher
 Subkey generation - Greater complexity can make analysis harder, but slows
cipher
 Round function - Greater complexity can make analysis harder, but slows cipher
 Fast software en/decryption & ease of analysis - are more recent concerns for
practical use and testing
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 subkey ki 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 swapped.

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 RE16 || 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-1 REi = LEi-1 F (REi-1, Ki)

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

recovers the original plaintext.

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.

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

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. 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.
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-

bit ciphertext
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.


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)

where Lcsi 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 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
S-B OX Details
This is a DES that was susceptible to attacks due to tremendous advances in computer hardware in cryptography.
Hence, it was a very complex or competent algorithm it would be feasible to reuse DES rather than writing an of
cryptography.

Required to this variation of DES were introduced known as multiple DES which was as follows as Shown:

1) Double DES

 Mainly, Double DES is simple as it does that normal DES does. Double DES uses twp keys to say K1 and K2
in this algorithm. It first performs DES on the original plain text using K! to get the encrypted text in
cryptography. Here, it again performs DES on the encrypted text but this time with the other key K2 in this
algorithm.
 Firstly, the final output is the encryption of encrypted text with the original plain text encrypted twice with
two different keys shown in the structure as given below

 While the doubly encrypted ciphertext block is first decrypted using the key K2 to produce singly encrypted
ciphertext by plaintext or original text. Hence, this ciphertext block is then decrypted using the key K1 to
obtain the original plain text block in cryptography.
 Mainly, the cryptanalysis for the basic version of DES requires a search of 256 thus the assumption
is Double DES require 2128 keys which is not true for the message.
Here, a Meet-in-the-middle attack is the drawback of double DES in this. Mainly, this attack involves
encryption from one end, decryption from the other and matching the results in the middle hence the
name in the message.

Therefore, the simplest form of multiple encryptions has two encryption stages and two keys in this. Here, given a
plaintext P and two encryption keys K1 and K2, ciphertext C is created as: C = E(K2, E(K1, P))

Then, Decryption requires that the keys be applied in reverse order as: P = D(K1, D(K2, C))

Now, For DES, this scheme involves a key length of 56 * 2 = 112 bits, resulting in a dramatic increase in
cryptographic strength in this. Further, but we need to examine the algorithm more closely for this.

2) Triple DES

Here, to improve the security of DES to a higher level triple DES was proposed in this. While this uses three stages
on DES for encryption and decryption in cryptography.

There basically of two versions of triple-DES are as given:

2.1) Triple DES with Two Keys

 While in triple DES with two keys there are only two keys K1 used by the first and third stages and K2 used
in the second stage in this. Basically, first, the plain text is encrypted with key K1 then the output of step
one is decrypted with K2 and final the output second step is encrypted again with key K1 in cryptography.
 It is also called encrypt decrypt encrypt (ECE) mode in cryptography. Hence, Triple DES with two keys is not
susceptible to the meet-in-the-middle attack in cryptography.

2.2) Triple DES with Three Keys

 It basically had the idea of Triple-DES with three keys:

 While the plain text block P is first encrypted with a key K1 then encrypts with a second key K2 and finally
with a third key K3 where K1, K2, and K3 are all different from each other in this algorithm. This is
Decryption is done in reverse order in this way. Therefore, this algorithm is mostly used in PGP and S/MIME
in cryptography.
 Therefore, the DES cipher's key size of multiple of 56 bits of the message was generally enough when that
algorithm was designed but the availability of increasing computational power made brute force attacks
feasible in this algorithm. Thus, the Triple-DES provides a relatively simple method of increasing the key
size of DES to secure against such attacks like that, without the need to design a completely new block
cipher algorithm by this technique in cryptography.
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.
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.
• 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.
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.
• 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.

BLOCK CIPHER MODES OF OPERATIONS


• Direct use of a block cipher is inadvisable
• Enemy can build up “code book” of plaintext/ciphertext equivalents
• 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
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.
• Decryption works as shown in the figure because of the properties of the XOR operation,
i.e. IV ⊕ IV ⊕ P = P where IV is the Initialisation Vector and P is the plaintext.
• 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.
• Figure shows the CFB scheme.
• In this figure it assumed that the unit of transmission is s bits; a common value is s = 8.
• 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.
• 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.
Counter Mode

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

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 encrypt
messages, 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.

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 may
impersonate user B: he sends a message E(KUA,X) and claims in the message to be B –A
has no 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 KR B. 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:

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 and
confidentiality 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).

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.

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

RSA ALGORITHM[Rivest, Shamir & Adleman]


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
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

Another example of RSA is given as,


Let p = 11, q = 13, e = 11, m = 7
n = pq i.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, involves
trying 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:

– 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.

DIFFIE-HELLMAN KEY EXCHANGE


Diffie-Hellman key exchange (D-H) is a cryptographic protocol that allows two parties
that 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, a2 mod p,..., ap-1 mod 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

i such 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:
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 X A < q and computes YA = αXA mod q. Similarly, user B
independently selects a random integer X A < 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 = (YA)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,
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, Xa 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 1310 (mod 37) which is 4 and sends that to Bob. Let
Bob pick b = 7. Bob calculates 13 7 (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 and
sends that to Bob. Let Bob pick b = 22. Bob calculates 522 (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.


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.

You might also like