Similar presentations:

# Cryptography Theory and Practice. Applied Cryptography

## 1. CSE 589 -- Part VIIII

Five or six weeks later, she asked me if I had decipheredthe manuscript… I told her that I had.

“Without the key, sir, excuse me if I believe the thing

impossible.”

“Do you wish me to name your key, madame?”

“If you please.”

I then told her the key-word which belonged to no

language, and I saw her surprise. She told me it was

impossible, for she believed herself the only possessor of

that word which she kept in her memory and which she had

never written down.

## 2.

I should have told her the truth -- that the samecalculation which had served me for deciphering the

manuscript had enabled me to learn the word -- but on a

caprice it struck me to tell her that a genie had revealed it

to me. This false disclosure fettered Madame d’Urfe to me.

That day I became the master of her soul, and I abused my

power.

From the autobiography

of Casanova (1757)

## 3. Cryptography

Cormen, Leiserson, Rivest, Chapter 33Cryptography Theory and Practice,

by Douglas Stinson

Applied Cryptography

by Bruce Schneier

## 4. Outline

OverviewPerfect Secrecy

Public Key Cryptography

Mathematical Background to RSA

RSA

• Implementation Details

• Security Provided

Digital Signatures

Attacks Against RSA

## 5. Cryptography

Goal:• to be able to communicate securely over a channel,

any medium for communication between two parties.

• Telephone, radio waves, Internet, satellite communication,

etc.

• of immense commercial importance, particularly with

increasing use of Internet for commercial purposes.

## 6. Security Risks of Internet Communication

Eavesdropping• intermediaries listen in on private conversations

• Solution: encryption (public or private-key)

Manipulation

• intermediaries change information in a private communication

• Solution: methods for preserving data integrity (one-way

hash fn’s and MACs)

Impersonation

• a sender or receiver communicates under false identification

• Solution: authentication (signatures, etc.)

## 7. Terminology

A sender wants to send a message to a receiver securely -wants to make sure no eavesdropper can read the message.ciphertext

Plaintext ----> Encryption -----------> Decryption ----> Plaintext

M

E(M)

C=E(M)

D(C)

M=D(C)

plaintext -- original message

encryption -- process of disguising message so as to hide its substance

ciphertext -- encrypted message

decryption -- process of turning ciphertext back into plaintext.

cryptography -- art and science of keeping messages secure

cryptanalysis -- art and science of breaking ciphertext

## 8. Cryptography: communication in the presence of adversaries.

Goals:• privacy: adversary learns nothing about message sent

• authentication: recipient of message can convince herself

that the message as received originated with alleged sender.

• signatures: recipient of a message can convince a third party

that the message as received originated with the alleged

signer.

• minimality: nothing is communicated except that which is

specifically desired to be communicated.

• simultaneous exchange: something of value not released

untile something else of value received.

• multi-party coordination: parties can coordinate activities

towards common goal even in presence of adversaries.

## 9. The cast of characters

Alice: first participant in all protocolsBob: second participant in all protocols

Eve: eavesdropper

Mallory: malicious active attacker

Trent: trusted arbitrator

## 10. Cryptanalysis

One possibility: security through obscurityRestricted algorithms: depend on keeping inner

workings of algorithm secret.

Difficult for communications between parties with

no prior contact, as in Internet commerce

applications.

Wildly optimistic to assume details of security

mechanisms won’t fall into the wrong hands.

No quality control or standardization

## 11. Kerckhoff’s Doctrine

Associated with algorithm is key. All security is inkey.

Kerckhoffs: If the strength of your cryptosystem relies

on the fact that the attacker does not know the algorithm’s

hidden workings, you’re sunk!!!

Key question: can we do it?

As Edgar Allan Poe wrote in “The Gold-Bug”:

It may well be doubted whether human ingenuity can

construct an enigma of the kind which human ingenuity

may not, by proper application, resolve.

## 12. Key-Based Security All security in key; alg can be published

EK1 (M)= C, DK2 (C) = Mkeyspace -- range of possible key values

Symmetric algorithms: encryption key can be

calculated from decryption key and vice versa

(usually same)

• stream ciphers -- operate on plaintext a bit (byte) at a time

• block ciphers -- operate on group (block) of bits.

Examples: DES, RC4, IDEA, Blowfish.…

Notable feature: fast

## 13. Protocol for communicating using symmetric cryptography

Alice and Bob agree on a cryptosystemAlice and Bob agree on a key

Alice encrypts plaintext using encryption

algorithm and key => ciphertext

Alice sends ciphertext to Bob

Bob decrypts ciphertext with same algorithm

and key and reads it.

## 14. Problems

keys must be distributed in secretif key compromised, all is lost

# keys needed grows like Omega (n2)

## 15.

What does it mean to say an algorithm is unbreakable?## 16. Shannon’s Theory

“Communication Theory of Secrecy Systems”by Claude Shannon, 1949.

Many important ideas

## 17. Two approaches to discussing security of a cryptosystem

Computational securitycannot be broken with “available resources” current or

future.

• best known method of breaking system takes

unreasonably large amount of time

• can reduce the security of the cryptosystem to some wellstudied problem that is thought to be difficult.

Unconditional security

cannot be broken, even with infinite computational

resources.

## 18. Unconditional Security

Framework: probability theoryProbability distribution over plaintexts (known to Eve)

Probability distribution over keys.

## 19. Perfect Secrecy

Cryptosystem has perfect secrecy ifProb (plaintext | ciphertext) = Prob(plaintext)

I.e., a posteriori probability of plaintext, given that the

ciphertext is observed is identical to the a priori probability

of plaintext.

## 20. Realization of Perfect Secrecy: The One-time Pad (1917)

Realization of Perfect Secrecy: The Onetime Pad (1917)P = C = K = n bit strings

EK(p) = bitwise xor of K and p = c.

DK(c) = bitwise xor of K and c = p

Problems:

• amount of key that must be communicated securely equals

amount of plaintext

• severe key management problems since can use each key

for only one encryption

(vulnerable to known plaintext attack)

## 21. Computational Security: Types of cryptanalytic attack

ciphertext only -- analyze ciphertexts to gain info aobutplaintext

known-plaintext attack -- intercept ciphertexts for which

plaintexts are known

chosen-plaintext attack -- choose plaintexts to be encrypted

adaptive-chosen-plaintext attack -- modify choices based on

results

chosen ciphertext attack -- get Bob to decrypt ciphertexts

of choosing

rubber-hose cryptanalysis -- threaten, blackmail, torture

until key is released

## 22.

Public Key CryptographyWe stand today on the brink of a revolution in cryptography.

Diffie and Hellman, 1976

## 23. Public-Key Cryptography

Private key crypto => Alice and Bob must secretlychoose K, exposure of EK renders system insecure

=> requires prior communication of the key K using

secure channel before any ciphertext is

transmitted.

Public-key system:

Idea: to find a cryptosystem where computationally

infeasible to determine D given E => E could be

made public by publishing it in a directory.

=> Alice can send encrypted message using public E

Bob is only person who can decrypt it, using secret

decryption rule.

## 24. Public-Key Cryptography

Idea due to Diffie & Hellman 1976 (indep Merkle)First realization 1977: Rivest, Shamir, Adleman.

Since then, many others.

Security rests on different computational problems.

RSA -- factoring large integers (??)

McEliecee -- decoding linear code (NP-complete)

El Gamal -- discrete logarithm problem (??)

Chor-Rivest -- knapsack (NP-complete)

….

Public-key cryptosystem can never provide unconditional

security.

## 25. Idea: uses trapdoor one-way function.

EK should be easy to computeDK (inverting EK ) should be hard

=> EK should be a one-way function

Example of possible one-way function:

n=pq (p,q two large prime numbers)

f(x) = x b mod n

Don’t want EK to be one-way from Bob’s point of

view => Bob must possess trapdoor, secret

information that permits easy inversion of EK

## 26. One-Way Functions

A function f is one-way if, given x it is easyto compute f(x), but given f(x) it is hard to

compute x (superpolynomial, or exponential

time).

Trapdoor one-way functions: easy to

compute f(x) given x, hard to compute x

given f(x). But there is some secret

information y, s.t. given f(x) and y, easy to

compute x.

## 27. Number Theoretic Preliminaries

… both Gauss and lesser mathematicians may be justified inrejoicing that there is one science [number theory] at any

rate… whose very remoteness from ordinary human

activities should keep it gentle and clean.

From the autobiography

A Mathematician’s Apology

of G.H. Hardy,

number theorist and pacifist,

1940

## 28. Number-theoretic Preliminaries

Modular arithmetic• Digression about cryptanalytic attacks

Prime numbers

Greatest common divisor

Inverses modulo a number

Fermat’s Little Theorem

Euler Totient Function

Chinese Remainder Theorem

• Factoring

• Prime Number Generation

## 29. Modular Arithmetic

“clock arithmetic”If Mildred says she’ll be home by 10:00 and she’s 13 hours

late, what time does she get home and for how many years

does her father ground her? => arithmetic modulo 12.

(10 + 13) mod 12 = 23 mod 12 = 11 mod 12

23 = 11 mod 12

a = b (mod n) if a = b + k n for some integer k

<=> a is congruent to b, modulo n

<=> b is the residue of a, modulo n

<=> a non-negative, 0 <= b<= n => b is remainder of a

when divided by n.

## 30. Digression to use modular arithmetic; cryptanalysis

Caesar cipher:plaintext

a b c d e ….

+K=

ciphertext

d e f g h

K is offset between 0 and 26 => EK (P) = P+K mod 26

Easy attack: try all possible keys.

Moral: cryptosystem insecure if # keys too small.

## 31. Possible solution: use more keys => Addition Cipher

Possible solution: use more keys=> Addition Cipher

Imagine alien alphabet with 1012 keys.

Break message up into blocks of numbers

between 0 and 1012 - 1

## 32. Known-plaintext attack

Alice sends Bob message using block size of 20digits.

Eve intercepts, and she knows message starts with

“Dear Bob” => knows both plaintext and ciphertext

of first block.

cyph = plain + key mod 1020

=> key = cyph - plain mod 1020

Also works if Eve knows of some number of ways

Alice’s message likely to begin. Tries each one =>

set of possible keys => tries each key on entire

message.

Using prior knowledge about message -- in English

## 33. Ciphertext-only attack

To get useful information about plaintext.Each month Alice sends Bob amount to spend,

encrypted with 20-digit addition cipher, same key.

Eve intercepts Jan and Feb ciphertexts.

Jan ciph = Jan plain + key mod 1020

Feb ciph = Feb plain + key mod 1020

Jan ciph - Feb ciph = Jan plain - Feb plain mod 1020

## 34. Modular Arithmetic (cont.)

Like normal arithmetic: commutative, associative anddistributive

Can reduce intermediate results modulo n.

(a*b) mod n = ((a mod n)(b mod n) mod n)

Speeding up exponentiation in modular arithmetic

a8 mod n = (a*a*a*a*a*a*a*a) mod n

= ((a2 mod n) 2 mod n) 2 mod n

a 25 mod n = (a*a 8 * a 16) mod n

= (a* ((a2) 2 ) 2 * (((a 2) 2) 2) 2 ) mod n

= (a* (((a * a 2) 2) 2) 2) mod n

Can be done in O( log x) operations [a x mod n]

## 35. Prime Numbers and GCD

A prime number is an integer greater than 1 whose onlyfactors are 1 and itself. No other number evenly divides it.

Examples: 2, 3, 5, 7, 11, 13,…,73, 2521, 2756839 -1

Two numbers, a and n, are relatively prime when they share

no factors in common other than 1, i.e., the greatest common

divisor (gcd) of a and n is equal to 1.

gcd(a,n) = 1

Examples: 4, 9

15, 28

15, 27

5, 12

## 36. Inverses Modulo a Number

4 and 1/4 are inverses because 4* 1/4 = 1In modulo world, want to find x such that

1 = a*x (mod n)

Also written a -1 = x (mod n)

Has unique solution if a and n are relatively prime.

If a and n aren’t relatively prime, has no solution.

4x = 1 (mod 7) <=> Finding x, k such that 4x = 7k + 1

Inverse of 5 modulo 14 = 3

2 has no inverse modulo 14.

## 37. Extended Euclidean Algorithm

can be used to calculate the gcd of two numbers a and bto calculate the the multiplicative inverse modulo n of a number

a.

## 38. Fermat’s Little Theorem

If m is a prime and a is not a multiple of m,then

am-1 = 1 mod m

## 39. Euler Totient Function (Euler phi function f(n) )

f(n) = number of positive integers less thann that are relatively prime to n (n > 1).

If n is prime, f(n) =

If n = pq, where p and q are prime,

f(n) =

## 40. Multiplicative Inverse

Euler’s generalization of Fermat’s Little Theorem.If gcd(a,n) = 1, then

af(n) mod n = 1

=> a-1 mod n =

Example: 5-1 mod 7

## 41. Special case of Chinese Remainder Theorem

p and q primeThere is a unique x < pq such that

x = a mod p

x = b mod q

Can find it by first finding u such that uq=1 mod p

Then x = (((a-b)u)mod p)q + b

Easy corollary: x = a mod p,

x = a mod q

=> x = a mod n.

## 42. Summary of Number-theoretic Preliminaries

Modular Arithmetic:• Speed up calculations by reducing modulo n

• Exponentiation is fast.

Two numbers relatively prime when share no common factors.

a -1 (mod n) is the number x such that ax (mod n) = 1.

• has unique solution if a and n are relatively prime.

• has no solution otherwise.

Extended Euclidean Algorithm

• to calculate gcd(a,b)

• to calculate a -1 (mod n)

## 43. Summary, cont.

Fermat’s Little Theorem: If m is a prime and a isnot a multiple of m, then

am-1 = 1 mod m

Euler phi function f(n) = number of positive

integers less than n that are relatively prime to n

(n > 1).

If n = pq, where p and q are prime, f(n) =(p-1)(q-1)

Euler’s generalization of FLT: If gcd(a,n) = 1, then

af(n) mod n = 1

## 44. Summary, cont.:

Special Case of Chinese Remainder Theorem:p, q prime, n= pq

There is a unique x < pq such that

x = a mod p

x = b mod q

Easy corollary: x = a mod p,

=> x = a mod n.

x = a mod q

## 45.

The RSA Cryptosystem## 46. RSA

Bob selects at random 2 large prime numbers p and q, say 150decimals each.

Compute n = pq

Bob chooses integer e relatively prime to f(n) = (p-1)(q-1).

Compute d as multiplicative inverse of e, modulo f(n).

Publish P=(e,n) as public key.

Keep secret S=(d,n) as private (secret) key.

Domain of plaintexts is Zn

Encryption function E(M) = C = Me (mod n)

Decryption function D(C) = Cd (mod n)

## 47. Example

p=47, q = 71 => n= pq = 3337encryption key e must have no factors in common with (p1)(q-1)=46 * 70 = 3220.

Choose e at random to be 79.

=> d= 79 -1 mod 3220 = 1019. [ (1019 x 79) mod 3220 = 1]

Publish e, n; keep d secret.

To encrypt M = 688, then E(M) = 688 79 mod 3337 = 1570

To decrypt C= 1570, then D(C) = 1570 1019 mod 3337 = 688

## 48. Issues

Why does it work?How do we implement it?

What kind of security guarantees does it

provide?

## 49. Why does it work? Encryption & decryption inverses

Why does it work?Encryption & decryption inverses

N=pq, de = 1 mod f(n)

E(M) = M e mod n = C

D(C) = C d mod n.

Assume M and n relatively prime

de = 1 mod f(n) => de = t f(n) +1 for t integer

=> (M e) d mod n = M ed mod n

= M t f(n) +1 mod n

= (Mf(n)) t M mod n

= 1t M mod n

by F.L.T.

= M mod n

## 50. Implementing RSA

Bob generates two large primes, p & q• Probabilistic primality testing O((log n) 3)

Bob computes n = pq and f(n) =(p-1)(q-1)

Bob chooses random e (1 < e < f(n)) such that

gcd(e, f(n) ) = 1

• Euclidean algorithm

Bob computes d = e

-1

mod f(n)

• Extended Euclidean Algorithm O((log n)2)

Bob publishes n and e in a directory as his public

key.

## 51. Probabilistic Primality Testing

FLT: am-1 = 1 mod m, for m prime (*)For most composite numbers, equation false for more

than half the a’s.

Gives way to test a number m to see if it’s prime.

Choose a random 1<= a <= m-1.

Raise it to power m-1 to see if equation (*) is true.

If not, m isn’t prime.

If is, repeat with bunch more random a’s.

## 52. Probabilistic Primality Testing

To find a random 100 digit prime number,pick random 100 digit number, and perform

test.

Keep going until you choose a number that

turns out to be prime.

Luckily, primes are plentiful.

(Prime Number Theorem: # primes <= N

about N/ ln N)

=> About 1/230 100 digit numbers are prime.

## 53. A few obvious questions….

If everyone needs a different prime number,won’t we run out?

• About 10151 prime numbers < 512 bits

What is two people accidentally pick the

same prime number?

If someone creates a database of all primes,

won’t he be able to use the database to break

public-key algorithms?

## 54. Implementing RSA, cont.

Break input into numerical blocks smallerthan n.

Encryption and decryption

• Modular exponentiation

## 55. Security of RSA

Rests on difficulty of factoring largenumbers.

If factoring large integers is easy, breaking

RSA is easy

Converse unproven: it is conjectured that if

factoring large numbers is hard, breaking

RSA is hard.

Sure as hell better make sure n is a very very

big number.

## 56. Factoring

Factoring a number means finding its prime factors.10 = 2 * 5

60 = 2 * 2 * 3 * 5

8338169264555846052842102071 =

179424673 * 2038074743 * 22801763489

To factor a number n, best known algorithm (number

field sieve) has exponential running time

e

c (ln n) 1/3 (lnln n) 2/3

## 57. A bit of factoring history...

1971 The big news was the factoring of a 41 digit number.1991 RSA Data Security Inc set up RSA Factoring

Challenge: list of hard numbers, each product of 2 primes,

ranging from 100 digits to 500 digits.

1994 “RSA129”, one of challenge numbers, 129 digits (428)

bits), factored over 8 months, using 1600 computers on

Internet around the world (~5000 MIPS-years)

“We conclude that commonly used 512-bit RSA moduli are vulnerable to

any organization prepared to spend a few million dollars and to wait a

few months.”

With this method, a 250-digit number would take

100,000,000 times as long.

## 58. General Comments About Public-Key Cryptosystems

Slow.Vulnerable to exhaustive search, and chosenciphertext attacks.

## 59. Hybrid Cryptosystems

In practice, public-key crypto used to secure and distributesession keys, which are then used with private-key crypto to

secure message traffic.

Bob sends Alice his public key.

Alice generates random session key K, encrypts it using Bob’s

public key, and sends it to Bob.

Bob decrypts Alice’s message using his private key to recover

session key.

Both encrypt their communications using same session key.

Public-key crypto solves important key-management problem.

## 60. Exercise: Show RSA encryption and decryption inverses.

N=pq, de = 1 mod f(n)E(M) = M e mod n = C

D(C) = C d mod n.

Show (M e) d mod n = 1, also in case where M, n not relatively

prime.

## 61.

Digital Signatures## 62. Digital Signatures

Hand-written signatures used as proof ofauthorship or agreement with contents of a

document.

authentic

unforgeable

not reusable

unalterable

cannot be repudiated.

Not so obvious how to do on a computer.

• Trivial to copy, cut and paste, easy to modify,….

## 63. Digital Signatures

Two components:• secret signing algorithm Sk (M) = Signature

• public verification algorithm Vk (M, Signature)

Vk (M, Signature)= true if Sk(M) = Signature,

false otherwise.

## 64. Signing Documents with Public Key Cryptography

How Alice sends a signed message to Bob usingRSA

• Alice signs with her private key. S (M) = DA(M)

• Bob verifies with Alice’s public key. V (C) = EA(C)

A

B

C = D A(M)

C,M

----------->

M = E A(C)

Authentic, unforgeable, not reusable, unalterable, can’t be

repudiated.

## 65. Just to be completely clear… Using RSA...

How Alice sends a secret message to BobA

B

C = E B(M)

C

----------->

M = D B(C)

How Alice sends a signed message to Bob

A

B

C = D A(M)

C

----------->

M = E A(C)

## 66. Digital Signatures

=> can use RSA public-key cryptosystem toprovide digital signatures.

There are many other digital signature

schemes:

• Discrete Log Signature Schemes.

• DSA

• …..

## 67. Problem

Copy of signed digital message identical tooriginal.

• Bob can cheat by reusing document and signature

together.

• Example: Alice sends Bob a signed digital check for

$1000.

Solution: timestamp.

## 68. Digital Signatures + Encryption proof of authorship + privacy

Alice signs with her private key then encrypts withBob’s public key

A

B

C = E B( S A(M))

C

----------->

Bob decrypts with his private key, then verifies

with Alice’s public key.

S A(M) = D B(C)

M = V A(C)

## 69. Issues

Bad idea to encrypt then sign.Timestamps should be used to prevent reuse

of messages.

## 70. Digital Signatures useful for

Authentication: protocol by which thereceiver of a message is convinced of the

identity of the sender and the integrity of

the message.

## 71. Chosen Ciphertext Attack Against RSA: Scenario 1

Eve collects c. She needs m, for which m = cdshe chooses random r < n, she gets Bob’s public key and then

computes

x = r e mod n => x d = r ed mod n

=> x d = r mod n

y = xc mod n

t = r -1 mod n

Eve gets Bob to decrypt y with his private key. Bob sends Eve

u =y d mod n.

Now Eve computes

tu mod n = r -1 y d mod n = r -1 x d c d mod n

= c d mod n = m.

## 72. Chosen Ciphertext Attack Against RSA: Scenario 2

Trent is a computer notary public. When Alice wants adocument notarized, she sends it to Trent who signs it with

an RSA digital signature.

Mallory wants Trent to sign a message he otherwise wouldn’t,

call it m’

Mallory chooses arbitrary x and computes y = x e mod n

(where e is Trent’s public key).

Then he computes m=ym’ mod n and sends m to Trent to sign.

Trent returns md mod n = (ym’) d mod n = xm’ d mod n.

Mallory calculates (md mod n) x -1 mod n = m’ d mod n, which is

the signature of m’.