Cryptography Presentation By Jyoti Goyal

McGraw-Hill

©The McGraw-Hill Companies, Inc., 2000

CRYPTOGRAPHY The word cryptography in Greek means “secret writing.” The term today refers to the science and art of transforming messages to make them secure and immune to attacks. Cryptography components

The original message before being transformed, is called Plaintext. After the message is transformed is called Cipher text. An encryption algorithm transforms the plaintext to cipher text, and a decryption algorithm transforms the cipher text to plaintext.

2

CIPHER

McGraw-Hill

3 ©The McGraw-Hill Companies, Inc., 2000

A cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. Also called as encipherment.

.

4

CIPHER

CLASSICAL

SUBSTITUTI ON

MODERN

INPUT SIZE BASED

TRANSPOSITI ON

BLOCK CIPHER

STREAM CIPHER

KEY BASED

SYMME TRIC KEY ALGO

ASYMME TRIC KEY ALGO 5

 Classical

cipher:--

6

Substitution Encryption Method - Caesar Cipher A cipher using the substitution method substitutes one symbol with another. For example, we can replace character A with D and T with Z, 0 with 3 and 2 with 7. The first cipher text was used by Julius Caesar and is still called Caesar Cipher. The cipher is shift key characters down.

7

8

Transposition cipher

In transposition cipher, the characters retain their plaintext form but change their positions to create the cipher text. The text is organized into two dimensional table, and the columns are interchanged according to a key.

9

10



Plaintext: attackxatxdawn Permute rows and columns

⇒

 

Cipher text: xtawxnattxadakc Key: matrix size and permutations (3,5,1,4,2) and (1,3,2)

000

h=001

i=010

k=011

l=100

r=101

s=110

t=111

Encryption: Plaintext ⊕ Key = Ciphertext

h Plaintext: Key: Ciphertext:

e

i

l

h

i

t

l

e

r

001 000 010 100 001 010 111 100 000 101 111 101 110 101 111 100 000 101 110 000 110 101 100 001 110 110 111 001 110 101

s

r

l

h

s

s

t

h

s

r

000

h=001

i=010

k=011

l=100

r=101

s=110

t=111

Decryption: Cipher text ⊕ Key = Plaintext

s Cipher text: Key: Plaintext:

r

l

h

s

s

t

h

s

r

110 101 100 001 110 110 111 001 110 101 111 101 110 101 111 100 000 101 110 000 001 000 010 100 001 010 111 100 000 101

h

e

i

l

h

i

t

l

e

r

Modern cipher:-(INPUT SIZE BASED CIPHER) Block ciphers - By whether they work on blocks of symbols usually of a fixed size. Stream ciphers - By whether they work on a continuous stream of symbols.

14

Key BASED CIPHER WHAT IS A KEY ????? A Key is a number (value) that the cipher, as algorithm, operates on.

15

Symmetric-key cryptography

16

In symmetric-key cryptography, the same key is used in both directions. The same key is used by the sender (for encryption) and receiver (for decryption) Some examples of popular and well-respected symmetric algorithms Include DES, AES , Blowfish, TDES, and IDEA.

17

DES Numerology

McGraw-Hill

18 ©The McGraw-Hill Companies, Inc., 2000

Data Encryption Standard (DES) Data Encryption Standard (DES) was designed by IBM and used by U.S. government. DES algorithm encrypts a 64-bit Plaintext using a 56-bit key. DES has two transposition blocks, one swapping block and 16 complex blocks called iteration blocks. DES is a feistel cipher

19

Iteration block 16 iteration blocks are conceptually the same. Each block use different key derived from the original key. The whole DES cipher block is a substitution block that changes a 64-bit plaintext to a 64-bit cipher text. The DES cipher uses the same concept as the Caesar cipher, but the encryption/ decryption algorithm is much more complex.

20

 





Feistel cipher refers to a type of block cipher design, not a specific cipher Split plaintext block into left and right halves: Plaintext = (L0,R0) For each round i=1,2,...,n, compute Li= Ri−1 Ri= Li−1 ⊕ F(Ri−1,Ki) where F is round function and Ki is sub key Cipher text = (Ln,Rn)

L

key

R

32

28

expand 48

32 ⊕

48

S-boxes

28

shift

shift 28

Ki

28

compress

48 28

28

32 32

P box

32 ⊕

32 L

R

key

One Round of DES

 

  

Decryption: Cipher text = (Ln,Rn) For each round i=n,n−1,…,1, compute Ri−1 = Li Li−1 = Ri ⊕ F(Ri−1,Ki) where F is round function and Ki is sub key Plaintext = (L0,R0) Formula “works” for any function F But only secure for certain functions F

   

Plaintext and cipher text consists of fixed sized blocks Cipher text obtained from plaintext by iterating a round function Input to round function consists of key and the output of previous round Usually implemented in software







P-box (permutation box)-is a method of bitshuffling used to permute or transpose bits across S-boxes inputs, retaining diffusion while transposing. S-Box (Substitution-box)-It is a basic component of symmetric key algorithms which performs substitution. It takes some number of input bits, m, and transforms them into some number of output bits, n: an m×nS-Box can be implemented as a lookup table with 2m words of n bits each. Fixed tables are normally used but in some ciphers the tables are generated dynamically from the key. 25



In DES 6×4-bit S-Box (S5) is used : Middle 4 bits of input

S5

Oute r bits

0 000

0 001

0 010

0 011

0 100

0 101

0 110

0 111

1 000

1 001

1 010

1 011

1 100

1 101

1 110

1 111

00

0 010

1 100

0 100

0 001

0 111

1 010

1 011

0 110

1 000

0 101

0 011

1 111

1 101

0 000

1 110

1 001

01

1 110

1 011

0 010

1 100

0 100

0 111

1 101

0 001

0 101

0 000

1 111

1 010

0 011

1 001

1 000

0 110

10

0 100

0 010

0 001

1 011

1 010

1 101

0 111

1 000

1 111

1 001

1 100

0 101

0 110

0 011

0 000

1 110

11

1 011

1 000

1 100

0 111

0 001

1 110

0 010

1 101

0 110

1 111

0 000

1 001

1 010

0 100

0 101

0 011

Given a 6-bit input, the 4-bit output is found by selecting the row using the outer two bits(the first and last bits), and the column using the inner four bits. For example, an input "011011" has outer bits "01" and inner bits "1101"; the corresponding output would be "1001".

26

Key Distribution - Diffie-Hellman Protocol A symmetric key between two parties is useful if it is used only once; it must be created for one session and destroyed when the session is over. Diffie-Hellman protocol: the two parties use the session key to exchange data without having to remember or store it for future use. Before establishing a symmetric key, the two parties need to choose two numbers N and G. The first number, N, is a large prime number with restriction that (N-1)/2 must also be prime. The second number G is also prime. The two numbers are not confidential. The steps for key distribution between Alice and Bob: (1) Alice chooses a larger random number x and calculates R1=G x mod N. (2) Alice sends R1 to Bob. Note that Alice sends R1, not x to Bob. (3) Bob chooses another large number y and calculates R2= Gy mod N. (4) Bob sends R2 to Alice. Again, note that Bob sends R2, not y to Alice. (5) Alice calculates K=(R2)x mod N. Bob also calculates K=(R1)y mod N. Note that K can be proven to be the same calculated by both Alice and Bob. That is the K=Gxy mod N. 27

McGraw-Hill

©The McGraw-Hill Companies, Inc., 2000

Man-in-the-middle attack

TCP/IP Protocol Suite

29

Replay attack: If John has an interest in the data message sent from Alice to Bob. He can intercept both the authentication message and the data message, store them, and resend them later to Bob. Bob has no way to know if this is a replay of a previous message. There nothing in this procedure to guarantee the freshness of the message. For example, suppose Alice’s message instruct Bob to pay John for some job he has done. John can resend the message, thereby illegally getting paid twice for the same job.

TCP/IP Protocol Suite

30

McGraw-Hill

31 ©The McGraw-Hill Companies, Inc., 2000

In public-key cryptography, there are two keys: a private key and a public key. The private key is kept by the receiver. The public key is announced to the public. The public key is used for encryption and is available to public; the private key is available only to an individual.

32

(Rivest,

Shamir and Adleman) RSA

The most common public-key algorithm is called RSA method. In the method, the private key here is a pair of numbers (N, d); the public key is also a pair of numbers (N, e). The sender uses the following algorithm to encrypt the message: C=Pe mod N; P is the plaintext, C is cipher text. The receiver decrypts as following: P=Cd mod N.

33

34

Comparison of symmetric and asymmetric -key cryptography

Symmetric-key cryptography: (1) Advantages: Efficiency, less time to encrypt a message (2) Disadvantages: each pair of users must have a unique key, N users need N(N-1)/2 keys; The key distribution can be difficult. Asymmetric-key cryptography: (1) Advantages: Easy key distribution, the public key can be used for any users; Each user only needs a pair of keys. (2) Disadvantages: algorithm is complex the public key for a user must be verified.

35

Applications of cryptography include ATM cards, computer passwords, and electronic commerce.  authentication, digital signatures, interactive proofs .  to ensure secrecy in communications, such as those of spies, military leaders, and diplomats 







Privacy means that the sender and the receiver expect confidentiality. The transmitted message must make sense to only the intended receiver. To all others, the message must be unintelligible. Hence , cryptography is very important task in order to keep data secure. No doubt it involves time but that time would be of course, of no use if data goes in other hands.

37

McGraw-Hill

©The McGraw-Hill Companies, Inc., 2000