p_i (plaintext chunk i)
|
|
v
[ E_k ] (encryption with key k)
|
c_i (ciphertext chunk i)
ith block of plaintext goes to ith block of ciphertext
This is bad for various reasons (see prev. lecture)
Used in practice
p_i
|
v
c_(i-1) -> [XOR] |-----> ...
| |
(prev ciphertext) | |
v |
[ E_k ] |
|
| |
|-------
|
v
c_i (ciphertext i)
Method
- Let p_i = plaintext i, c_i = cipher i, and c_i-1 = previous ciphertext
- c_i = E_k( p_i XOR c_i-1)
- Take previous ciphertext, XOR with plaintext, and encrypt
- The first plaintext (p_0) encrypted with Initialization Vector (IV)
- No need to encrypt IV, doesn't help adversary
- Make IV random
- Why? So same msg won't have same ciphertext
- pros
- No longer have problem of same plaintext -> same ciphertext
- Run backwards to decrypt
- Resilient to errors
- Only need c_i and c_i-1 to get p_i
- Everything else can be messed up
- Self-synchronizing (can't start decoding at any location in stream)
- In XOR-based stream cipher, if get unsynchronized, you are sunk
- attack
- Adversary can do splicing attacks
- Send c0' and c1' from different msg with same key
- All encryption schemes vulnerable in some way
"Secret-key" or "symmetric key"
- Encryption key = decryption key
- Studied up until now
"Asymmetric key" or "public key"
- Encryption and decryption keys different
- Knowing one doesn't help you find the other
- Poorly named
- Not asymmetric, since decryption is inverse of encryption
- Not "public", since one key must be private (decryption, probably)
Invented 1976, Diffie and Hellman. Showed it would be useful.
RSA (Rivest Shamir Adelman) Algorithm
- 1978, patent expired in 2000. Free for anyone to use
- Uses some number theory
To generate keys
- pick random, large (1024 bit) primes p and q (there are efficient ways to do this)
- let N = p x q
- Pick e to be relatively prime to (p-1)(q-1) [Relatively prime: no common factors (besides 1). 8 and 9 are relatively prime.]
- Pick d so that: e*d mod (p-1)(q-1) = 1
- The keys are (e, N) and (d, N)
- Each key is a pair of numbers
Encryption/decryption of x
- E(x) = x^e mod N [encrypt x]
- D(x) = x^d mod N [decrypt x]
- Note than encryption and decryption are the same operation with different keys (exponentiation homogenous, like XOR)
"It works" theorem: For all x, E( D(x) ) = D ( E(x) ) = x
x^(de) mod N = x^(ed)mod N
= x^(k * (p-1)(q-1) + 1) mod N
= x * x^(k * (p-1)(q-1) ) mod N
[ Note that e*d mod (p-1)(q-1) = 1 ]
[ So, e*d = 1 + k * (p-1)(q-1) for some k ]
[ x^(k*(p-1)(q-1) ) drops out (=1, not sure why), ]
so left with ]
= x mod N
Note: x (the data we are encrypting, as an integer) can't be > N
Why secure (probably)
- Hard to find (e,N) given (d,N) and vice versa
- Best known way: factor N, finding p and q (only prime factors)
- If adv. can get p and q, knows everything (can replicate key generation)
Really slow
- Has humungous exponentiation
- 1000 times slower than symmetric key
- If symmetric key works, use it!
Common mode of use
- Keep one key private
- Make other key public
"Your eyes only" message
- Someone encrypts with your public key, only you can decrypt
- Doesn't work with symmetric key: if you give encryption key to many people, they can read each other's messages
Verifiable message/digital signature
- Encrypt with private key. Anyone can decrypt with public key to check signature.
- Only you could have made the message
- Remember: encryption and decryption the same. No key is the "encryption key"... one is the inverse of the other.
Both of above (private and verifiable message)
- Alice -> Bob
- Alice encrypts with Alice's private key (verifiable)
- Alice encrypts result with Bob's public key (only Bob can read decrypt it)
- 2 encryptions
Diagram:
[msg]
|-- Alice's digital sig--|
|-------- Bob's public key encryption ----|
Ideas
- Verifiable by anyone
- Unforgeable (only you can sign something under your name)
- Nontransferable (signature can't be transferred to different document)
- Real signatures transferable: use scissors and a Xerox machine
- Nondeniable: signer can't claim didn't sign
- Don't get this in practice
- Signer can claim key was lost/stolen, and wasn't him who signed
First approach
- Signature on m = RSA(privatekey, m)
- Has problems
- Message may be big ( > N)
- Fix: encrypt hash of message (the hash is small, 160 bits)
- Tampering possible
- To get my signature on x:
- Ask me to sign xy^e mod N (y is any value)
- Result is x^d * y^ed mod N = x^d * y mod N (y^ed = y because of encryption)
- Divide by y mod N to get x^d mod N
- This is the signature on x. (exploits exponentiation: homogenous transformation)
- How to get someone to sign something "random"? Handshake protocols... try to agree on key. Key looks "randomish"
- Fix: append known constant to hash
- Or, send plaintext to encrypt. I encrypt the hash
- Thus, need x with the same hash as y, unlikely
Beware "gotchas"
- Don't use RSA or another algorithm as a black box w/o understanding it
- Use standards (designed to be more secure)
Method for encrypting long msg in a public-key fashion
- Choose random symmetric key K_r (K sub r), used by DES or AES, etc.
- Encrypt K_r with the public key of recipient (only 1 public-key operation). Creates "your eyes only" message.
- Encrypt message with K_r using symmetric key, like AES (fast)
- Same level of security, assuming K_r strong
- Then, throw away K_r, no need to store it
- Much faster than public key, just as flexible
- Establish key using handshake protocol
Example
[ k_r ] [ message ]
protected by public key protected by k_r
