#### Read Microsoft PowerPoint - 5_4601_07 text version

Introduction to Cryptography

Dr. Arjan Durresi Louisiana State University Baton Rouge, LA 70810 [email protected] These slides are available at: http://www.csc.lsu.edu/~durresi/CSC4601-07/

Louisiana State University

Overview

Definitions Secret keys Public keys Hash functions

5- Introduction to Cryptography - 1

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 2

CSC 4601 S07

Communication Secrecy

The history of codes and ciphers is the story of centuries-old battle between codemakers and codebreakers Evolution of codes. Always under attack from codebreakers. Analogous to the situation of a strain of infectious bacteria under the attack of antibiotics Technologies involved from mathematics to linguistics, from information theory to quantum theory

Louisiana State University

The Evolution of Secret Writing

In The histories, Herodotus, "the father of history", chronicled the conflicts between Greece and Persia in the fifth century B.C. The art of secret writing saved the Greece Demaratus send information to Greece about Persian preparation using secret messages: scraping the wax off a pair of wooden folding tablets, writing on the wood underneath and then covering the message with wax again. Herodotus chronicled also the story of Histaiaeus who wanted to encaurage Aristagoras of Miletus to revolt against Persians To convey his instructions securely, Histaiaeus shaved the head of his messenger, wrote the message on his scalp, and then waited for the hair to grow. It seems this period of history tolerated a certain lack of urgency. Hiding a message is known as steganography derived from the Greek word steganos meaning "covered" and graphein"to write".

5- Introduction to Cryptography - 4 CSC 4601 S07

5- Introduction to Cryptography - 3

CSC 4601 S07

Louisiana State University

In the two thousand years since Herodotus, various forms of steganography has been used. The ancient Chinese wrote messages on fine silk, which then was scrunched into a tiny ball and covered in wax and swallowed by a messenger. In the 16th century, the Italian scientist Giovanni Porta described how to conceal a message within a hard-boiled egg by making an ink from mixture of alum and pint vinegar and then write on the shell. The solution penetrates the shell and leaves the message on the egg inside and can be read when the shell is removed. Today write messages on pictures posted on the web

Louisiana State University

The Evolution of Secret Writing

5- Introduction to Cryptography - 5

CSC 4601 S07

offer security, but it suffers from a fundamental weakness. If the message is found the secret is revealed. Hence in parallel with steganography, there was the evolution of Cryptography, derived from the Greek word kryptos "hidden". The aim of cryptography is not to hide the existence of the message, but rather hide its meaning, a process known as encryption. To render the message unintelligible, it is scrambled according a particular protocol agreed beforehand between the sender and the intended recipient. The advantage of cryptography is that if the enemy intercepts an encrypted message, then the message is unreadable.

Louisiana State University

The Evolution of Secret Writing The longevity of steganography illustrates that can

5- Introduction to Cryptography - 6

CSC 4601 S07

Possible to combine cryptography and steganography. For example, during Second World War, German agents in Latin America would photographically shrink a page of text down to a dot less than 1 mm and then hide it in a letter. Sometimes they also scrambled the text before reducing it. Cryptography is more powerful because of this ability to prevent the information from falling into enemy hands.

Louisiana State University

Cryptography

Cryptography

Cryptography can be divided into: transposition and substitution. In transposition, the letters of the message are simply rearranged. For very short messages, such as a single word, this method is relatively insecure. "For example, consider this short sentence." 35 letters with more than 50 *1030 distinct arrangements. If each person would check one arrangement per second, it would take all people more than thousand time the life of universe to check all arrangements. This seems unbreakable, but there is a drawback. If letter are randomly jumbled without rule, then unscrambling the text will be impossible for the enemy as well as for the recipient.

Louisiana State University

5- Introduction to Cryptography - 7

CSC 4601 S07

5- Introduction to Cryptography - 8

CSC 4601 S07

Cryptography

Have a history of at least 4000 years Ancient Egyptians enciphered some of their hieroglyphic writing on monuments

Spartan Scytale

Wrap a strip of paper around a tube of specific size, then write your message sideways (generally one letter per strip). Only someone with same size tube can read your message.

Louisiana State University

5- Introduction to Cryptography - 9

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 10

CSC 4601 S07

Cryptography

Ancient Hebrews enciphered certain words in the scriptures 2000 years ago Julius Ceasar used a simple substitution cipher, now known as the Caesar cipher Roger Bacon described several methods in 1200s Geoffrey Chaucer included several ciphers in his works Leon Alberti devised a cipher wheel, and described the principles of frequency analysis in the 1460s Blaise de Vigenère published a book on cryptology in 1585, & described the polyalphabetic substitution cipher Increasing use, esp in diplomacy & war over centuries

Louisiana State University

Substitution Ciphers

Make a table for all the letters of the alphabet. Pick a new code letter to stand for each one. Go through your message, and replace each letter with its code letter from the table. Only someone with the table could decode your message.

bed Original Code Letter

Louisiana State University

a b c d e f g h i j D F I Q K X M Z R P FKQ

5- Introduction to Cryptography - 12 CSC 4601 S07

5- Introduction to Cryptography - 11

CSC 4601 S07

Caesar Cipher aka Decoder Rings

Caesar used a simple substitution cipher. He just "shifted" the alphabet. But since there's only 26 ways to shift, these codes are easy to break (just try all 26 ways).

Image: Old Time Radio Premiums

Kma-Stra Secret Writing

A harder-to-break cipher can be designed by instead of just shifting the letters of the alphabet, you assign each letter a totally random code letter. This form of secret-writing is one of the 64 arts explained in the Kma-Stra.

Original Code Letter

Louisiana State University

a b c d e f g h i j ... D E F G H I J K L M ...

CSC 4601 S07

Original Code Letter

Louisiana State University

a b c d e f g h i j D F I Q K X M Z R P

CSC 4601 S07

5- Introduction to Cryptography - 13

5- Introduction to Cryptography - 14

Newspaper Cryptograms

Why don't we all just use this approach to hide our information? Because people can figure out how to decode it! In fact, substitution ciphers are behind the cryptogram puzzles you see in the newspaper. People solve these in an afternoon... Computers make them even easier to solve.

Process data into unintelligible form, reversible, without data loss Usually one-to-one (not compression) Analog cryptography example: voice changers Other services: Integrity checking: no tampering Authentication: not an imposter Plaintext encryption ciphertext decryption plaintext

5- Introduction to Cryptography - 16 CSC 4601 S07

Definitions

Louisiana State University

5- Introduction to Cryptography - 15

CSC 4601 S07

Louisiana State University

Secret Key Cryptography

Originally a way to keep secret data private Encode a message using a secret "key" A long and colorful history Today, it has many uses Privacy Authentication verifying someone (something's) identity Data Integrity reassuring the recipient of the message that the message has not been altered since it was generated by a legitimate source

Louisiana State University

What is Encryption?

You and I agree on a secret way to transform data Later, we use that transform on data we want to pass over an unsafe communications channel Instead of coming up with new transforms, design a common algorithm customized with a "key"

5- Introduction to Cryptography - 17

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 18

CSC 4601 S07

Secret Key Encryption for Privacy

Key Key

How Secure is Encryption?

An attacker who knows the algorithm we're using could try all possible keys Security of cryptography depends on the limited computational power of the attacker A fairly small key (e.g. 64 bits) represents a formidable challenge to the attacker Algorithms can also have weaknesses, independent of key size

Plaintext

Encrypt

Ciphertext

Decrypt

Plaintext

Louisiana State University

5- Introduction to Cryptography - 19

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 20

CSC 4601 S07

How do we know how good an algorithm is?

A problem of mathematics: it is very hard to prove a problem is hard It's never impossible to break a cryptographic algorithm - we want it to be as hard as trying all keys Fundamental Tenet of Cryptography: If lots

To Publish or Not to Publish

If the good guys break your algorithm, you'll hear about it If you publish your algorithm, the good guys provide free consulting by trying to crack it The bad guys will learn your algorithm anyway Today, most commercial algorithms are published; most military algorithms are not

of smart people have failed to solve a problem then it probably won't be solved (soon)

Louisiana State University

5- Introduction to Cryptography - 21

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 22

CSC 4601 S07

Computational Difficulty

Algorithm needs to be efficient. Otherwise only short keys can be used. Most schemes can be broken: depends on $$$. E.G. Try all possible keys. Longer key is often more secure: Encryption O(N+1). Brute-force cryptanalysis: O(2N+1), twice as hard with each additional bit. Cryptanalysis tools: Special-purpose hardware. Parallel machines. Internet coarse-grain parallelism.

Louisiana State University

Secret Key vs. Secret Algorithm

Secret algorithm: additional hurdle Hard to keep secret if used widely: Reverse engineering, social engineering Commercial: published Wide review, trust Military: avoid giving enemy good ideas Dutch linguist in 1883, Kerckhoff's Principle: " The security of a cryptosystem must not depend on keeping secret the crypto-algorithm. The security depends only on keeping secret the key."

5- Introduction to Cryptography - 23

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 24

CSC 4601 S07

Classical Substitution Ciphers

Where letters of plaintext are replaced by other letters or by numbers or symbols Or if plaintext is viewed as a sequence of bits, then substitution involves replacing plaintext bit patterns with ciphertext bit patterns

Caesar Cipher

Earliest known substitution cipher by Julius Caesar First attested use in military affairs Replaces each letter by 3rd letter on Example: meet me after the toga party PHHW PH DIWHU WKH WRJD SDUWB

Louisiana State University

5- Introduction to Cryptography - 25

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 26

CSC 4601 S07

Caesar Cipher

can define transformation as:

a b c d e f g h i j k l m n o p q r s t u v w x y z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Cryptanalysis of Caesar Cipher

only have 26 possible ciphers A maps to A,B,..Z could simply try each in turn a brute force search given ciphertext, just try all shifts of letters do need to recognize when have plaintext eg. break ciphertext "GCUA VQ DTGCM"

mathematically give each letter a number

a b c 0 1 2 n o 13 14 d e f 3 4 5 p q 15 16 g h i 6 7 8 r s 17 18 j k l m 9 10 11 12 t u v w x y Z 19 20 21 22 23 24 25

then have Caesar cipher as: C = E(p) = (p + k) mod (26) p = D(C) = (C k) mod (26)

Louisiana State University

5- Introduction to Cryptography - 27

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 28

CSC 4601 S07

Monoalphabetic Cipher

rather than just shifting the alphabet could shuffle (jumble) the letters arbitrarily each plaintext letter maps to a different random ciphertext letter hence key is 26 letters long Plain: abcdefghijklmnopqrstuvwxyz Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext: ifwewishtoreplaceletters Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA

Monoalphabetic Cipher Security

now have a total of 26! = 4 x 1026 keys with so many keys, might think is secure but would be !!!WRONG!!! problem is language characteristics

Louisiana State University

5- Introduction to Cryptography - 29

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 30

CSC 4601 S07

Language Redundancy and Cryptanalysis

human languages are redundant eg "th lrd s m shphrd shll nt wnt" letters are not equally commonly used in English e is by far the most common letter then T,R,N,I,O,A,S other letters are fairly rare cf. Z,J,K,Q,X have tables of single, double & triple letter frequencies

English Letter Frequencies

Louisiana State University

5- Introduction to Cryptography - 31

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 32

CSC 4601 S07

Use in Cryptanalysis

key concept - monoalphabetic substitution ciphers do not change relative letter frequencies discovered by Arabian scientists in 9th century calculate letter frequencies for ciphertext compare counts/plots against known values if Caesar cipher look for common peaks/troughs peaks at: A-E-I triple, NO pair, RST triple troughs at: JK, X-Z for monoalphabetic must identify each letter tables of common double/triple letters help

Example Cryptanalysis

given ciphertext:

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

count relative letter frequencies (see text) guess P & Z are e and t guess ZW is th and hence ZWP is the proceeding with trial and error finally get:

it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow

Louisiana State University

5- Introduction to Cryptography - 33

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 34

CSC 4601 S07

Playfair Cipher

not even the large number of keys in a monoalphabetic cipher provides security one approach to improving security was to encrypt multiple letters the Playfair Cipher is an example invented by Charles Wheatstone in 1854, but named after his friend Baron Playfair

Playfair Key Matrix

a 5X5 matrix of letters based on a keyword fill in letters of keyword (sans duplicates) fill rest of matrix with other letters eg. using the keyword MONARCHY MONAR CHYBD EFGIK LPQST UVWXZ

Louisiana State University

Louisiana State University

5- Introduction to Cryptography - 35

CSC 4601 S07

5- Introduction to Cryptography - 36

CSC 4601 S07

Encrypting and Decrypting

plaintext encrypted two letters at a time: if a pair is a repeated letter, insert a filler like 'X', eg. "balloon" encrypts as "ba lx lo on" 2. if both letters fall in the same row, replace each with letter to right (wrapping back to start from end), eg. "ar" encrypts as "RM" 3. if both letters fall in the same column, replace each with the letter below it (again wrapping to top from bottom), eg. "mu" encrypts to "CM" 4. otherwise each letter is replaced by the one in its row in the column of the other letter of the pair, eg. "hs" encrypts to "BP", and "ea" to "IM" or "JM" (as desired)

1.

Security of the Playfair Cipher

security much improved over monoalphabetic since have 26 x 26 = 676 digrams would need a 676 entry frequency table to analyse (verses 26 for a monoalphabetic) and correspondingly more ciphertext was widely used for many years (eg. US & British military in WW1) it can be broken, given a few hundred letters since still has much of plaintext structure

Louisiana State University

5- Introduction to Cryptography - 37

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 38

CSC 4601 S07

Polyalphabetic Ciphers

another approach to improving security is to use multiple cipher alphabets called polyalphabetic substitution ciphers makes cryptanalysis harder with more alphabets to guess and flatter frequency distribution use a key to select which alphabet is used for each letter of the message use each alphabet in turn repeat from start after end of key is reached

Vigenère Cipher

simplest polyalphabetic substitution cipher is the Vigenère Cipher effectively multiple caesar ciphers key is multiple letters long K = k1 k2 ... kd ith letter specifies ith alphabet to use use each alphabet in turn repeat from start after d letters in message decryption simply works in reverse

Louisiana State University

5- Introduction to Cryptography - 39

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 40

CSC 4601 S07

Example

write the plaintext out write the keyword repeated above it use each key letter as a caesar cipher key encrypt the corresponding plaintext letter eg using keyword deceptive key: deceptivedeceptivedeceptive plaintext: wearediscoveredsaveyourself ciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ

Security of Vigenère Ciphers

Have multiple ciphertext letters for each plaintext letter hence letter frequencies are obscured but not totally lost Start with letter frequencies see if look monoalphabetic or not If not, then need to determine number of alphabets, since then can attach each

Louisiana State University

5- Introduction to Cryptography - 41

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 42

CSC 4601 S07

Kasiski Method

Method developed by Babbage / Kasiski Repetitions in ciphertext give clues to period So find same plaintext an exact period apart Which results in the same ciphertext Of course, could also be random fluke eg repeated "VTW" in previous example Suggests size of 3 or 9 Then attack each monoalphabetic cipher individually using same techniques as before

Autokey Cipher

ideally want a key as long as the message Vigenère proposed the autokey cipher with keyword is prefixed to message as key knowing keyword can recover the first few letters use these in turn on the rest of the message but still have frequency characteristics to attack eg. given key deceptive

key: deceptivewearediscoveredsav plaintext: wearediscoveredsaveyourself ciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA

Louisiana State University

5- Introduction to Cryptography - 43

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 44

CSC 4601 S07

One-Time Pad

if a truly random key as long as the message is used, the cipher will be secure called a One-Time pad is unbreakable since ciphertext bears no statistical relationship to the plaintext since for any plaintext & any ciphertext there exists a key mapping one to other can only use the key once though have problem of safe distribution of key

Transposition Ciphers

now consider classical transposition or permutation ciphers these hide the message by rearranging the letter order without altering the actual letters used can recognise these since have the same frequency distribution as the original text

Louisiana State University

5- Introduction to Cryptography - 45

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 46

CSC 4601 S07

Rail Fence cipher

write message letters out diagonally over a number of rows then read off cipher row by row eg. write message out as:

m e m a t r h t g p r y e t e f e t e o a a t

Row Transposition Ciphers

a more complex scheme write letters of message out in rows over a specified number of columns then reorder the columns according to some key before reading off the rows

Key: 3 4 1 2 5 6 7 Plaintext: a t t a c k p o s t p o n e d u n t i l t w o a m x y z Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ

giving ciphertext

MEMATRHTGPRYETEFETEOAAT

Louisiana State University

5- Introduction to Cryptography - 47

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 48

CSC 4601 S07

Product Ciphers

ciphers using substitutions or transpositions are not secure because of language characteristics hence consider using several ciphers in succession to make harder, but: two substitutions make a more complex substitution two transpositions make more complex transposition but a substitution followed by a transposition makes a new much harder cipher this is bridge from classical to modern ciphers

Rotor Machines

before modern ciphers, rotor machines were most common product cipher were widely used in WW2 German Enigma, Allied Hagelin, Japanese Purple implemented a very complex, varying substitution cipher used a series of cylinders, each giving one substitution, which rotated and changed after each letter was encrypted with 3 cylinders have 263=17576 alphabets

Louisiana State University

5- Introduction to Cryptography - 49

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 50

CSC 4601 S07

Steganography

an alternative to encryption hides existence of message using only a subset of letters/words in a longer message marked in some way using invisible ink hiding in LSB in graphic image or sound file has drawbacks high overhead to hide relatively few info bits

Louisiana State University

5- Introduction to Cryptography - 51

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 52

CSC 4601 S07

Cryptanalysis: Breaking an Encryption Scheme

Ciphertext only: Exhaustive search until "recognizable plaintext" Need enough ciphertext Known plaintext: Secret may be revealed (by spy, time), thus <ciphertext, plaintext> pair is obtained Great for monoalphabetic ciphers Chosen plaintext: Choose text, get encrypted Useful if limited set of messages Encryption schemes have to withstand all three types of attacks

Louisiana State University

Models for Evaluating Security

Unconditional security (perfect secrecy) Uncertainty/entropy H(p)=H(p|c) No matter how much computer power is available, the cipher cannot be broken since the ciphertext provides insufficient information to uniquely determine the corresponding plaintext Complexity-theoretic security Provable security As difficult to break as solving well-known and supposedly difficult problem

Louisiana State University

5- Introduction to Cryptography - 53

CSC 4601 S07

5- Introduction to Cryptography - 54

CSC 4601 S07

Models for Evaluating Security

Computational security Given limited computing resources (eg time needed for calculations is greater than age of universe), the cipher cannot be broken Ad hoc security

Brute Force Attacks

Number of encryption/sec: 1 million to 1 billion/sec 56-bit key broken in 1 week with 120,000 processors ($6.7m) 56-bit key broken in 1 month with 28,000 processors ($1.6m) 64-bit key broken in 1 week with 3.1 × 107 processors ($1.7b) 128-bit key broken in 1 week with 5.6 × 1026 processors

5- Introduction to Cryptography - 56 CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 55

CSC 4601 S07

Louisiana State University

Uses of Cryptography

Transmitting secret data over an insecure channel Storing secret data on an insecure medium Message integrity checksum/authentication code (MIC/MAC) Authentication: "challenge" the other party to encrypt or decrypt a random number

Types of Cryptography

Secret key cryptography: one key Public key cryptography: two keys - public, private Hash functions: no key

Louisiana State University

5- Introduction to Cryptography - 57

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 58

CSC 4601 S07

Secret Key Cryptography

Same key is used for encryption and decryption Symmetric cryptography Ciphertext approximately the same length as plaintext Substitution codes, DES, IDEA Message transmission: Agree on key (but how?) Communicate over insecure channel Secure storage: crypt

Louisiana State University

Symmetric Cipher Model

5- Introduction to Cryptography - 59

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 60

CSC 4601 S07

Secret Key Algorithms

DES (Data Encryption Standard) 56 bit key (+ 8 parity bits) controversial! Input and output are 64 bit blocks slow in software, based on (sometime gratuitous) bit diddling IDEA (International Data Encryption Algorithm) 128 bit key Input and output are 64 bit blocks designed to be efficient in software

Louisiana State University

Secret Key Algorithms

Triple DES Apply DES three times (EDE) using K1, K2, K3 where K1 may equal K3 Input and output 64 bit blocks Key is 112 or 168 bits Advanced Encryption Standard (AES) New NIST standard to replace DES. Public Design and Selection Process. Key Sizes 128,192,256. Block size 128.

5- Introduction to Cryptography - 61

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 62

CSC 4601 S07

Secret Key Algorithms

RC2 (Rivest's Cipher #2) Variable key size Input and output are 64 bit blocks RC4 (Rivest's Cipher #4) Variable key size Extremely efficient Stream cipher - one time use keys Many other secret key algorithms exist It is hard to invent secure ones! No good reason to invent new ones

Louisiana State University

XOR (Exclusive-OR)

Bitwise operation with two inputs where the output bit is 1 if exactly one of the two input bits is one (B XOR A) XOR A) = B If A is a "one time pad", very efficient and secure Common encryption schemes (e.g. RC4) calculate a pseudo-random stream from a key

5- Introduction to Cryptography - 64 CSC 4601 S07

5- Introduction to Cryptography - 63

CSC 4601 S07

Louisiana State University

Secret Key Integrity Protection

Plaintext

Challenge / Response Authentication

Alice (knows K) I'm Alice Bob (knows K) Pick Random R Encrypt R using K (getting C)

Generate MAC

MAC

Verify MAC

Yes/No If you're Alice, decrypt C

Key

Key

R

Louisiana State University

5- Introduction to Cryptography - 65

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 66

CSC 4601 S07

Secret Key Cryptography (Cont'd)

Strong authentication: prove knowledge of key without revealing it: Send challenge r, verify the returned encrypted {r} Fred can obtain chosen plaintext, cihpertext pairs Challenge should chosen from a large pool Integrity check: fixed-length checksum for message Send Message Integrity Code (MIC) along with the message

Public Key Encryption for Privacy

Public Key Private Key

Plaintext

Ciphertext

Plaintext

Louisiana State University

5- Introduction to Cryptography - 67

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 68

CSC 4601 S07

Public Key Cryptography

Asymmetric cryptography Invented/published in 1975 Two keys: private (d), public (e) Encryption: public key; Decryption: private key Signing: private key; Verification: public key Much slower than secret key cryptography

Public Key Cryptography

Two keys per user: a private key and a public key. The keys reverse each other's effects. Encrypt a message for Alice using her public key Decryption requires her private key Generating Digital Signatures requires the private key Verifying them requires the public key

Louisiana State University

5- Introduction to Cryptography - 69

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 70

CSC 4601 S07

Public Key Cryptography (Cont'd)

Data transmission: Alice encrypts ma using eB, Bob decrypts to ma using db. Storage: Can create a safety copy: using public key of trusted person. Authentication: No need to store secrets, only need public keys. Secret key cryptography: need to share secret key for every person to communicate with.

5- Introduction to Cryptography - 71 CSC 4601 S07

Public Key Cryptography (Cont'd)

Digital signatures Encrypt hash h(m) with private key Authorship Integrity Non-repudiation: can't do with secret key cryptography

Louisiana State University

Louisiana State University

5- Introduction to Cryptography - 72

CSC 4601 S07

Public Key Integrity Protection

Plaintext

Public Key Authentication

Alice (knows A's private key) I'm Alice Bob (knows A's public key) Pick Random R Encrypt R using A's public key (getting C)

Generate Signature

Signature

Verify Signature

Yes/No If you're Alice, decrypt C

Private Key

Public Key

Decrypt C R

Louisiana State University

5- Introduction to Cryptography - 73

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 74

CSC 4601 S07

Message Digest Functions

m

Hash Algorithms

Message digests, one-way transformations Length of h(m) much shorter then length of Usually fixed lengths: 48-128 bits Easy to compute h(m) Given h(m), no easy way to find m Computationally infeasible to find m1, m2 s.t. h(m1) = h(m2) Example: (m+c)2, take middle n digits

Message

Digest

Digest Value

Louisiana State University

5- Introduction to Cryptography - 75

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 76

CSC 4601 S07

Hash Algorithms (Cont'd)

Password hashing Doesn't need to know password to verify it Store h(p+s), s (salt), and compare it with the user-entered p Salt makes dictionary attack less convenient Message integrity Agree on a password p Compute h(p|m) and send with m Doesn't require encryption algorithm, so the technology is exportable

Louisiana State University

Message Digest Functions

Also known as cryptographic hashes Non-reversible function Takes an arbitrary size message and mangles it into a fixed size digest It should be impossible to find two messages with the same MD, or come up with a message with a given MD Useful as a shorthand for a longer thing

5- Introduction to Cryptography - 77

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 78

CSC 4601 S07

Message Digest Functions

MD2, MD4, and MD5 used to be most popular. SHA-1 taking over All produce 128 bit digests MD4 and MD2 were recently "broken" and MD5 has significant weaknesses SHA-1 was proposed by the U.S. government. It produces a 160 bit digest Message digests are not difficult to design, but most are not secure

Combining Cryptographic Functions for Performance

Public key cryptography is slow compared to hashes and secret key cryptography Public key cryptography is more convenient & secure in setting up keys Algorithms can be combined to get the advantages of both

Louisiana State University

5- Introduction to Cryptography - 79

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 80

CSC 4601 S07

Hybrid Encryption

Instead of: Message Encrypted with Alice's Public Key Use: Randomly Chosen K Encrypted with Alice's Public Key Message Use: Instead of:

Hybrid Signatures

Message Signed with Bob's Private Key

+

Encrypted with Secret Key K

CSC 4601 S07

Message

+

Message Digest (Message) Signed with Bob's Private Key

Louisiana State University

5- Introduction to Cryptography - 81

Louisiana State University

5- Introduction to Cryptography - 82

CSC 4601 S07

Signed and Encrypted Message

Randomly Chosen K Encrypted with Alice's Public Key Digest (Message) Signed with Bob's Private Key Encrypted with Secret Key K

Summary

Message+

+

Definitions Secret keys Public keys Hash functions

Louisiana State University

5- Introduction to Cryptography - 83

CSC 4601 S07

Louisiana State University

5- Introduction to Cryptography - 84

CSC 4601 S07

#### Information

##### Microsoft PowerPoint - 5_4601_07

14 pages

#### Report File (DMCA)

Our content is added by our users. **We aim to remove reported files within 1 working day.** Please use this link to notify us:

Report this file as copyright or inappropriate

569244

### You might also be interested in

^{BETA}