[SOLVED] CS algorithm scheme Public-Key Crypto

Public-Key Crypto

Review: Integrity
Problem: Sending a message over an
untrusted channel without being changed
Provably-secure solution: Random function
Practical solution:
m, v := fk(m) Mallory m, v =? fk(m) e.g. Attack at dawn, 628369867
Pseudorandom function (PRF) Input: arbitrary-length k
Output: fixed-length value
Secure if practically indistinguishable from
a random function, unless know k Real-world use:
Message authentication codes (MACs) built on cryptographic hash functions
Popular example: HMAC-SHA256k(m) [Cautions?!]
k
Alice
k
Bob
2

Review: Confidentiality
Problem: Sending message in the presence
of an eavesdropper without revealing it Provably-secure solution: One-time pad
Practical solution:
Pseudorandom generator (PRG)
c
Bobk
p := D (c) k
Input: fixed-length k
Output: arbitrary-length stream
Secure if practically indistinguishable from a random stream, unless know k
Real-world use:
Stream ciphers (cant reuse k)
Popular example: AES-128 + CTR mode
Block ciphers (need padding/IV)
Popular example: AES-128 + CBC mode
[Cautions?!]
k
Alice
c := E (p) k
Eve

Review: Diffie-Hellman Key Exchange Lets Alice and Bob agree on a shared secret
value by having a public conversation
Alice
Generates random secret a (0 < a < p)BobGenerates random secret b (0 < b < p)gb mod p Computes xag modpEveComputes xba ab=(g modp) modp =(g modp) modpaAlicebBob ba=g modpab=g modpx == x Problem: Man-in-the-middle attacksga modp gv modpgu modp gb modpCaution: D-H gives you a shared secret, but dont know whos on the other end! aAliceuvMallorybBobSuppose Alice publishes data to lots of people, and they all want to verify integrity…Cant share an integrity key with everybody, or else anybody could forge messagesSuppose Bob wants to receive data from lots of people, confidentially…Schemes weve discussed would require a separate key shared with each person[What to do?] Solution:Public-key CryptoSo far, encryption key == decryption key symmetric key cryptoNew idea: Keys are distinct, and you cant find one from the otherAlmost always used by splitting key-pair Alice keeps one key private (private key)Publishes the other key (public key) Many applicationsInvented in 1976 by Diffie and Hellman (earlier by Clifford Cocks of British intelligence, in secret)Best known, most common public-key algorithm: RSARivest, Shamir, and Adleman 1978 Requirements for a public key crypto system to be secure1. Computationally easy for B to generate a key pair: PUb, PRb2. Computationallyeasyforsender A to generate the ciphertext for message M: C=E(PUb, M)3. Computationally easy for receiver B to decrypt the ciphertext: M=D(PRb, C)4. Computational infeasible to guess PRb knowing PUb.5. Computational infeasible to recover M from PUb and C.How RSA worksKey generation:1. Pick large (say, 1024 bits) random primes p and q2. Compute N := pq(RSA uses multiplication mod N)3. Pick e to be relatively prime to (p-1)(q-1)4. Find d so that ed mod (p-1)(q-1) = 15. Finally:To encrypt: To decrypt:Public key is (e,N) Private key is (d,N)eE(x) = x mod ND(x) = xd mod N Why RSA worksIt works theorem: For all 0 < x < N,can show that D(E(x)) = x Proof:edD(E(x)) = (x mod pq) mod pqed=x modpq= xa(p-1)(q-1)+1 mod pq for some a (because ed mod (p-1)(q-1) = 1)= (x(p-1)(q-1))ax mod pq= (x(p-1)(q-1) mod pq)ax mod pq = 1ax mod pq(because of the fact that if p,q are prime, then for all 0 < x < N,x(p-1)(q-1) mod pq = 1) =x Is RSA secure?Best known way to compute d from eis factoring N into p and q.Best known factoring algorithm:General number field sieveTakes more than polynomial time but less than exponential timeto factor n-bit number.(Still takes way too long if p,q are large enough and random.)Fingers crossed…but cant rule out a breakthrough! Signing with the public key for confidentiality or secrecy: Does this provide integrity? Signing with private key for integrity/authentication. Does this provide confidentiality? Subtle fact: RSA can be used for either confidentiality or integrityRSA for confidentiality:Encrypt with public key Decrypt with private keyyour eyes only messageRSA for integrity:Encrypt (sign) with private key Decrypt (verify) with public keycalled a digital signature[What if we want both confidentiality and integrity on the same message?] How to have both confidentiality and integrity (using RSA)?Alice (A) wants to send a secret message M to Bob (B) so that Bob can verify that it comes from Alice.Which one(s) is/are secure?1. E(E(M,PRA),PUB)2. E(E(M, PUB), PRA)3. C=E(M, PRA) t=E(H(C), PUB) Send C||t4. C=E(M, PUB) t=E(H(C), PRA) Send C||t Review: Public-key CryptoSo far, encryption key == decryption keysymmetric key crypto New idea: Keys are distinct.RSA: N := pqPublic key is (e,N)Private key is (d,N)To encrypt: E(x) = x mod NeTo decrypt: D(x) = xd mod NRSA for confidentiality:Encrypt with public key Decrypt with private keyRSA for integrity (digital signatures): Encrypt (sign) with private keyDecrypt (verify) with public key[Cautions?!]RSA drawback: PerformanceFactor of 1000 or more slower than AES.Dominated by exponentiation cost goes up (roughly) as cube of key size.Message must be shorter than N. [How big should the RSA keys be?]Use in practice:Encryption:Use RSA to encrypt a random x < N, compute k := PRF(x), encrypt message using a symmetric cipher and key kSigning:Compute v := PRF(m), use RSA to sign a carefully padded version of v (many gotchas!)Almost always should use crypto libraries to get the details right True or false:Public-key encryption is a general- purpose technique that has made symmetric encryption obsolete True or false:Key distribution is trivial when using public-key encryption, compared to the cumbersome handshaking involved with key distribution centers for symmetric encryption. Attacks against RSA1. Bruteforce:tryingallpossible private keys2. Mathematicalattacks:factoring3. Timingattacks:usingtherunning time of decryption4. Hardware-based fault attack: induce faults in hardware to generate digital signatures5. Chosenplaintextattackon unpadded RSA ExerciseSuppose Bob uses RSA crypto with a very large modulus n for which the factorization cannot be found in a reasonable amount of time.Suppose Alice sends a message to Bob by representing each alphabet letter as an integer between 0 and 25 (A->0, , Z->25) and then encrypting each number separately using RSA with large e and large n.
Is this method secure?
If yes, why?
If not, how to efficiently attack this encryption method?

Solution:
For a set of message block values SM = {0, 1, 2, , 25}. The set of corresponding ciphertext block values SC = {0e mod N, 1e mod N, , 25e mod N}, and can be computed by everybody with the knowledge of the public key of Bob.
The most efficient attack is to compute Me mod N for all possible values of M, then create a look-up table with a ciphertext as an index, and the corresponding plaintext as a value of the appropriate location in the table.

Two subtle textbook RSA problems:
1. For small e and m: m^e mod N == m^e Trivial to decrypt!
2. If m is chosen from a small set, easy to confirm a ciphertext is a given message (anyone can encrypt!)
Chosen plaintext attack

Solution: RSA Padding
Need to make sure m is as large enough to wrap around N
Need to randomize before encryption

So Far:
The Security Mindset Message Integrity Confidentiality
Key Exchange
Building a Secure Channel Public Key Crypto
Next Week:
Begin Web Security Unit
HTTPS: Secure channels for the web