Asymmetric Key Cryptography

Information about Asymmetric Key Cryptography

Published on August 9, 2010

Author: aSGuest59667



CHAPTER 13 Asymmetric Key Cryptography : CHAPTER 13 Asymmetric Key Cryptography Slides adapted from "Foundations of Security: What Every Programmer Needs To Know" by Neil Daswani, Christoph Kern, and Anita Kesavan (ISBN 1590597842; Except as otherwise noted, the content of this presentation is licensed under the Creative Commons 3.0 License. Agenda : Agenda Problem with Symmetric Key Crypto: Alice & Bob have to agree on key! In 1970, Diffie & Hellman propose asymmetric or public key cryptography RSA & Elliptic Curve Cryptography (ECC) Certificate Authorities (CAs) Identity-Based Encryption (IBE) Authentication via Encryption 13.1. Why Asymmetric Key Cryptography? : 13.1. Why Asymmetric Key Cryptography? So two strangers can talk privately on Internet Ex: Bob wants to talk to Alice & Carol secretly Instead of sharing different pairs of secret keys with each (as in symmetric key crypto) Bob has 2 keys: public key and private (or secret) key Alice and Carol can send secrets to Bob encrypted with his public key Only Bob (with his secret key) can read them 13.1. … To Mess With Poor Eve : 13.1. … To Mess With Poor Eve Source: 13.1. Public Key System : 13.1. Public Key System 13.1. The Public Key Treasure Chest : 13.1. The Public Key Treasure Chest Public key = Chest with open lock Private key = Key to chest Treasure = Message Encrypting with public key Find chest with open lock Put a message in it Lock the chest Decrypting with private key Unlock lock with key Take contents out of the chest 13.1. Asymmetric Encryption : 13.1. Asymmetric Encryption Alice encrypts a message with different key than Bob uses to decrypt Bob has a public key, kp, and a secret key, ks. Bob’s public key is known to Alice. Asymmetric Cipher: F-1(F(m,kp),ks) = m 13.2. RSA (1) : 13.2. RSA (1) Invented by Rivest/Shamir/Adelman (1978) First asymmetric encryption algorithm Most widely known public key cryptosystem Used in many protocols (e.g., SSL, PGP, …) Number theoretic algorithm: security based on difficulty of factoring large prime numbers 1024, 2048, 4096-bit keys common 13.2. RSA (2) : 13.2. RSA (2) Public Key Parameters: Large composite number n with two prime factors Encryption exponent e coprime to (n) = (p-1)(q-1) Private Key: Factors of n: p, q (n = pq) Decryption exponent d such that ed ´ 1 (mod (n)) Encryption: Alice sends c = me mod n Decryption: Bob computes m = cd mod n Euler’s Theorem: a(n) ´ 1 (mod n) Check: med ´ m ¢ m(n) ´ m (mod n) 13.3. Elliptic Curve Cryptography : 13.3. Elliptic Curve Cryptography Invented by N. Koblitz & V. Miller (1985) Based on hardness of elliptic curve discrete log problem Standardized by NIST, ANSI, IEEE for government, financial use Certicom, Inc. currently holds patent Small keys: 163 bits (<< 1024-bit RSA keys) 13.3: RSA vs. ECC : 13.3: RSA vs. ECC RSA Advantages: Has been around longer; math well-understood Patent expired; royalty free Faster encryption ECC Advantages: Shorter key size Fast key generation (no primality testing) Faster decryption 13.4. Symmetric vs. Asymmetric Key Cryptography : 13.4. Symmetric vs. Asymmetric Key Cryptography Symmetric-Crypto (DES, 3DES, AES) Efficient (smaller keys / faster encryption) because of simpler operations (e.g. discrete log) Key agreement problem Online Asymmetric-Crypto (RSA, ECC) RSA 1000x slower than DES, more complicated operations (e.g. modular exponentiation) How to publish public keys? Requires PKI / CAs Offline or Online 13.5. Certificate Authorities : 13.5. Certificate Authorities Trusted third party: CA verifies people’s identities Authenticates Bob & creates public key certificate (binds Bob’s identity to his public key) CA also revokes keys and certificates Certificate Revocation List: compromised keys Public Key Infrastructure (PKI): CA + everything required for public key encryption 13.6. Identity-Based Encryption : 13.6. Identity-Based Encryption Ex: e-mail address as identity & public key Bob gets his private key from a generator (PKG) after authenticating himself via a CA Commercialized by Voltage Security (2002) Revoked Keys: concatenate current date to public key Then PKG doesn’t provide private key after date when compromised 13.7. Authentication with Encryption : 13.7. Authentication with Encryption Alice issues “challenge” message to person Random # (nonce) encrypted with Bob’s public key If person is actually Bob, he will be able to decrypt it Bob {384764342}PK(Bob) 384764342 Alice Eve {957362353}PK(Bob) ??? A Word of Caution : A Word of Caution In the previous example, as well as some other examples presented in later chapters, the simple toy protocols that we discuss are for instructive and illustration purposes only. They are designed to make concepts easy to understand, and are vulnerable to various types of attacks that we do not necessarily describe. Do not implement these protocols as is in software. For example, the simple “challenge” authentication method is vulnerable to a man-in-the-middle attack. Mallory gets a challenge from Alice, sends it to Bob She takes his response and returns it to Alice Bob needs to authenticate Alice as well Summary : Summary Asymmetric Cryptography: Two Keys Public key published in directory Secret key known only to Bob Solves key exchange problem Examples: RSA, ECC PKI required: CAs, Trusted Third Parties Applications: IBE, Authentication, SSL…

Related presentations