- Greetings and felicitations!
**Reading**: Pfleeger, pp. 91-118

- Puzzle
- Point is that PGP relies on 2 keys, derives strength from weakest of them

- RSA
- Provides both authenticity and confidentiality
- Go through algorithm:

Idea:*C*=*M*e mod*n*,*M*=*C*d mod*n*, with*ed*mod PHI(*n*) = 1.

Proof:*M*^{PHI(n)}mod*n*= 1 [by Fermat's theorem as generalized by Euler]; follows immediately from*ed*mod PHI(*n*) = 1.

Public key is (*e*,*n*); private key is*d*. Choose*n*=*pq*; then PHI(*n*) = (*p*-1)(*q*-1). - Example:
*p*= 5,*q*= 7;*n*= 35, PHI(*n*) = (5-1)(7-1) = 24. Pick*d*= 11. Then*de*mod PHI(*n*) = 1, so choose*e*= 11. To encipher 2,*C*=*M*e mod*n*= 211 mod 35 = 2048 mod 35 = 18, and*M*=*C*d mod*n*= 1811 mod 35 = 2. - Example:
*p*= 53,*q*= 61,*n*= 3233, PHI(*n*) = (53-1)(61-1) = 3120. Take*d*= 791; then*e*= 71. Encipher*M*=`RENAISSANCE`:`A`=`00`,`B`=`01`, ...,`Z`=`25`,*blank*=`26`. Then:

*M*=`RE NA IS SA NC E`blank =`1704 1300 0818 1800 1302 0426`

*C*= (1704)^{71}mod 3233 = 3106;*etc.*=`3106 0100 0931 2691 1984 2927`

- Authentication:
- validating client (user) identity
- validating server (system) identity
- validating both (mutual authentication)

- Basis
- What you know
- What you have
- What you are

- Passwords
- How UNIX does selection
- Problem: common passwords; Go through Morris and Thompson,
Klein and mine,
*etc*. - May be pass phrases: goal is to make search space as large as possible and distribution as uniform as possible
- Other ways to force good password selection: random, pronounceable, computer-aided selection
- Go through problems, approaches to each,
*esp*. proactive

- Password Storage
- In the clear; MULTICS story
- Encipheres; key must be kept available; get to it and it's all over
- Hashed; present idea of one-way functions using identity and sum
- Show UNIX version

- Attack Schemes Directed to the Passwords
- Exhaustive search: UNIX is 1-8 chars, say 96 possibles; it's about 7e16
- Inspired guessing: think of what people would like (see above)
- Random guessing: can't defend against it; bad login messages aid it
- Scavenging: passwords often typed where they might be recorded as
login name, in other contexts,
*etc*. - Ask the user: very common with some public access services
- Expected time to guess

- Password aging
- Pick age so when password is guessed, it's no longer valid
- Implementation: track previous passwords vs. upper, lower time bounds

- Ultimate in aging: One-Time Pads
- Password is valid for only one use
- May work from list, or new password may be generated from old by a function
- Example: S/Key

- Challenge-response systems
- Computer issues challenge, user presents response to verify secret information known/item possessed
- Example operations:
*f*(*x*) =*x*+1, random, string (for users without computers), time of day, computer sends*E*(*x*), you answer*E*(*D*(*E*(*x*))+1) - Note: password never sent on wire or network
- Attack: monkey-in-the-middle
- Defense: mutual authentication (will discuss more sophisticated network-based protocols later)

- Biometrics
- Depend on physical characteristics
- Examples: pattern of typing (remarkably effective),
retinal scans,
*etc*.

- Location
- Bind user to some location detection device (human, GPS)
- Authenticate by location of the device

You can also see this document in its native format, in Postscript, in PDF, or in ASCII text.

Send email to cs153@csif.cs.ucdavis.edu.

Department of Computer Science

University of California at Davis

Davis, CA 95616-8562