Computer Science CSC/ECE 574 Dr. Peng Ning 1 Topic 5.2 Public Key Cryptography CSC/ECE 574 Computer and Network Security Computer Science CSC/ECE 574 Dr. Peng Ning 2 Outline I. Introduction II. RSA III. Diffie-Hellman Key Exchange IV. Digital Signature Standard Computer Science CSC/ECE 574 Dr. Peng Ning 3 Introduction Computer Science CSC/ECE 574 Dr. Peng Ning 4 Public Key Cryptography • Invented and published in 1975 • A public / private key pair is used – public key can be announced to everyone – private key is kept secret by the owner of the key • Also known as asymmetric cryptography • Much slower to compute than secret key cryptography plaintext encryption ciphertext decryption plaintext Public key Private key different! Computer Science CSC/ECE 574 Dr. Peng Ning 5 Plaintext Alice Signs Plaintext with digital signature Bob Verifies Signature Valid / Not Valid Alice’s Private Key Alice’s Public Key Applications of Public Key Crypto 1. Message integrity with digital signatures Alice computes hash, signs with her private key (no one else can do this without her key) Bob verifies hash on receipt using Alice’s public key using the verification equation Computer Science CSC/ECE 574 Dr. Peng Ning 6 Applications (Cont’d) • The digital signature is verifiable by anybody • Only one person can sign the message: non-repudiation – Non-repudiation is only achievable with public key cryptographyComputer Science CSC/ECE 574 Dr. Peng Ning 7 Applications (Cont’d) 2. Communicating securely over an insecure channel – Alice encrypts plaintext using Bob’s public key, and Bob decrypts ciphertext using his private key – No one else can decrypt the message (because they don’t have Bob’s private key) Plaintext Alice Encrypts Ciphertext Bob Decrypts Plaintext Bob’s Public Key Bob’s Private Key Computer Science CSC/ECE 574 Dr. Peng Ning 8 Applications (Cont’d) 3. Secure storage on insecure medium – Alice encrypts data using her public key – Alice can decrypt later using her private key 5. User Authentication – Bob proves his identity to Alice by using his private key to perform an operation (without divulging his private key) – Alice verifies result using Bob’s public key Computer Science CSC/ECE 574 Dr. Peng Ning 9 Applications (Cont’d) 5. Key exchange for secret key crypto – Alice and Bob use public key crypto to negotiate a shared secret key between them Computer Science CSC/ECE 574 Dr. Peng Ning 10 Public Key Algorithms • Public key algorithms covered in this class, and their applications System Encryption / Decryption? Digital Signatures? Key Exchange? RSA Yes Yes Yes Diffie-Hellman Yes DSA Yes Computer Science CSC/ECE 574 Dr. Peng Ning 11 Public-Key Requirements • It must be computationally – easy to generate a public / private key pair – hard to determine the private key, given the public key • It must be computationally – easy to encrypt using the public key – easy to decrypt using the private key – hard to recover the plaintext message from just the ciphertext and the public key Computer Science CSC/ECE 574 Dr. Peng Ning 12 Trapdoor One-Way Functions • Trapdoor one-way function – Y=fk(X): easy to compute if k and X are known – X=f -1k(Y): easy to compute if k and Y are known – X=f -1k(Y): hard if Y is known but k is unknown • Goal of designing public-key algorithm is to find appropriate trapdoor one-way functionComputer Science CSC/ECE 574 Dr. Peng Ning 13 The RSA Cipher Computer Science CSC/ECE 574 Dr. Peng Ning 14 RSA (Rivest, Shamir, Adleman) • The most popular public key method – provides both public key encryption and digital signatures • Basis: factorization of large numbers is hard • Variable key length (1024 bits or greater) • Variable plaintext block size – plaintext block size must be smaller than key size – ciphertext block size is same as key size Computer Science CSC/ECE 574 Dr. Peng Ning 15 Generating a Public/Private Key Pair • Find (using Miller-Rabin) large primes p and q • Let n = p*q • do not disclose p and q! • φ(n) = ??? • Choose an e that is relatively prime to φ(n) • public key = <e,n> • Find d = multiplicative inverse of e mod φ(n) (i.e., e*d = 1 mod φ(n)) • private key = <d,n> Computer Science CSC/ECE 574 Dr. Peng Ning 16 RSA Operations • For plaintext message m and ciphertext c Signing: s = md mod n, m < n Verification: m = se mod n Encryption: c = me mod n, m < n Decryption: m = cd mod n Computer Science CSC/ECE 574 Dr. Peng Ning 17 RSA Example: Encryption and Signing • Choose p = 23, q = 11 (both primes) – n = p*q = 253 – φ(n) = (p-1)(q-1) = 220 • Choose e = 39 (relatively prime to 220) – public key = <39, 253> • Find e-1 mod 220 = d = 79 (note: 39*79 ≡ 1 mod 220) – private key = <79, 253> Computer Science CSC/ECE 574 Dr. Peng Ning 18 Example (Cont’d) • Suppose plaintext m = 80 Encryption c = 8039 mod 253 = ____ (c = me mod n) Decryption m = ____79 mod 253 = 80 (cd mod n) Signing (in this case, for entire message m) s = 8079 mod 253 = ____ (s = md mod n) Verification m = ____39 mod 253 = 80 (se mod n)Computer Science CSC/ECE 574 Dr. Peng Ning 19 Example (Cont’d) • Suppose plaintext m = 80 Encryption c = 8039 mod 253 = 37 (c = me mod n) Decryption m = 3779 mod 253 = 80 (cd mod n) Signing (in this case, for entire message m) s = 8079 mod 253 = 224 (s = md mod n) Verification m = 22439 mod 253 = 80 (se mod n) Computer Science CSC/ECE 574 Dr. Peng Ning 20 Another Example • Choose p = 17, q = 11 (both primes) – n = p*q = 187 – φ(n) = (p-1)(q-1) = 160 • Choose e = 7 (relatively prime to 160) – public key = <7, 187> • Find e-1 mod 160 = d = 23 i.e., 7*23 = 1 mod 160 – private key = <23, 187> Computer Science CSC/ECE 574 Dr. Peng Ning 21 Example (Cont’d) • Suppose plaintext m = 88 • Encryption – c = 11 = 887 mod 187 (c = me mod n) • Decryption – m = 88 = 1123 mod 187 (cd mod n) • Signing (entire message, not just hash) – s = 11 = 8823 mod 187 (s = md mod n) • Verification – m = 88 = 117 mod 187 (se mod n) why the same???! Computer Science CSC/ECE