sec-03-crypto.pdf

Public-Key Cryptography Vorlesung “Einführung in die IT-Sicherheit” Prof. Dr. Martin Johns Overview Topic of the unit Public-key Cryptography Parts of the unit Part #1: Asymmetric cryptosystems Part #2: Mathematical Prerequisites Part #3: Rivest-Shamir-Adleman algorithm Part #4: Di e-Hellman key exc...

Public-Key Cryptography Vorlesung “Einführung in die IT-Sicherheit” Prof. Dr. Martin Johns Overview Topic of the unit Public-key Cryptography Parts of the unit Part #1: Asymmetric cryptosystems Part #2: Mathematical Prerequisites Part #3: Rivest-Shamir-Adleman algorithm Part #4: Di e-Hellman key exchange Page 2 ffi Problem: Key Exchange K 1 Shared secret Alice M 2 Alice EK Encryption C Bob DK Decryption M Bob Paradox situation for symmetric cryptosystems Secure key exchange needed for secure communication Communication between unknown parties not possible Page 3 Multi-party Key Exchange Involved multi-party key exchange with symmetric keys Quadratic growths: n parties → (n2 - n) / 2 keys Problem rooted in symmetry of cryptosystem (shared keys) Alice Bob KAB KAC Carol Page 4 KAD KBC KCD KBD Dave Asymmetric Keys Solution: Two types of keys Public key K+ = enables encryption but no decryption Private key K– = used for decryption only Hard to deduce private from public key... similar to a classic mailbox Page 5 Key Exchange with Public Keys K+ 1 Retrieval of public key only Alice M 2 Alice EK+ Encryption C DK- Bob M Decryption C and K+? Asymmetric Cipher K+ = public key of Bob No exchange of shared key necessary Page 6 K– = private key of Bob Bob Key Exchange with Public Keys Scalable communication with multiple parties Linear number of exchanges: n parties → n public keys Real-world systems with millions of keys (e.g. PGP) Alice Bob Database KA- KB- KA+, KB+, KC+, KD+ KCCarol Page 7 KDDave Overview Topic of the unit Public-key Cryptography Parts of the unit Part #1: Asymmetric cryptosystems Part #2: Mathematical Prerequisites Part #3: Rivest-Shamir-Adleman algorithm Part #4: Di e-Hellman key exchange Page 8 ffi Trapdoor One-Way Functions Trapdoor one-way function F(x) = y Given input x: easy to compute output y Given output y: hard to compute input x Given y and a secret: easy to compute x Trapdoor basis for asymmetry Encryption with public key ~ Computing y Decryption with private key ~ Computing x with secret … we need some math for these trapdoors Page 9 Modular Arithmetic Modulo operation Operator determining the remainder of a division For two integers a and n (modulus), we have Modular arithmetic a mod n = b if a = b + kn Arithmetic with integer numbers under a given modulus Examples: Page 10 11 6 3+4 3·5 23 1 2 0 3 (mod (mod (mod (mod 5) 5) 5) 5) More Math Greatest common divisor: gcd(a,b) = c Largest integer c dividing a and b without remainder Computation using factorization or Euclidean algorithm Numbers a and b co-prime if gcd(a,b) = 1 Modular multiplicative inverse: a · a 1 ⌘1 (mod m) Inverse for modular multiplication Computation using extended Euclidean algorithm Inverse exists only if a and m co-prime Page 11 Hard Problems Trapdoor build around a mathematical problem Problem hard to solve but easy to verify (asymmetry) No polynomial-time algorithm for solution known Examples: Integer factorization and discrete logarithm › Integer factorization Given an integer n, nd its m prime factors n = p · p · · · pm with pi 2 P Example: n = 4711 Page 12 fi Let’s see… p1 = 7, p2 = 673 Hard Problems (cont) Trapdoor build around a mathematical problem Problem hard to solve but easy to verify (asymmetry) No polynomial-time algorithm for solution known Examples: Integer factorization and discrete logarithm › Discrete logarithm Given integers g, p, b, nd an integer a such that ga ⌘ b Example: a ⌘ Page 13 fi (mod p) (mod ) Let’s see… a = 4 Asymmetric Algorithms Di e-Hellman (DH) Key Exchange Developed by Di e and Hellman in 1976 Based on di culty of computing discrete logarithms RSA Algorithm (Encryption & Signing) Developed by Rivest, Shamir and Adleman in 1978 Based on di culty of integer factorization Elgamal Schemes (Encryption & Signing) Develop by Elgamal in 1985 Based on di culty of computing discrete logarithms ffi ffi ffi ffi ffi Page 14 Overview Topic of the unit Public-key Cryptography Parts of the unit Part #1: Asymmetric cryptosystems Part #2: Mathematical Prerequisites Part #3: Rivest-Shamir-Adleman algorithm Part #4: Di e-Hellman key exchange Page 15 ffi RSA Algorithm Standard algorithm for public-key cryptography Developed by Rivest, Shamir and Adleman in 1978 Based on di culty of factorizing large integers › Key generation Choose random primes p, q and compute n = p · q Compute Euler function j(n) = (p )(q ) Choose random encryption key e with gcd(e, j(n)) = Compute decryption key d = e mod j(n) Page 16 ffi RSA Algorithm (cont) Standard algorithm for public-key cryptography Developed by Rivest, Shamir and Adleman in 1978 Based on di culty of factorizing large integers › Encryption with public key e, n Encrypt message m to ciphertext c = me mod n › Decryption with private key d Decrypt ciphertext c to message m = c d mod n Page 17 ffi RSA Algorithm (cont) Why does RSA work? c d ⌘ med ⌘ m +k j(n) ⌘ m · mk j(n) ⌘ m · Substitute c d=e Page 18 (mod n) That’s simple mod j(n) Euler’s theorem Security of RSA Main attack vectors against RSA Decrypting ciphertext c = me mod n → Di culty of computing roots in modular arithmetic Deriving private key d = e mod j(n) → Di culty of computing prime factors from n Security depends on size of prime numbers Factorization of numbers up to 1024 bits feasible Keys with 4096 and more bits considered secure ffi ffi Page 19 Overview Topic of the unit Public-key Cryptography Parts of the unit Part #1: Asymmetric cryptosystems Part #2: Mathematical Prerequisites Part #3: Rivest-Shamir-Adleman algorithm Part #4: Di e-Hellman key exchange Page 20 ffi Di e-Hellman Key Exchange Public-key algorithm for secure key exchange Developed by Di e and Hellman in 1976 Based on di culty of computing discrete logarithms › Initialization Alice and Bob agree on prime n and generator g x g mod n = b < b < n For all there is an x such that › Generation of secrets Alice select random number x and sets X = g x mod n Bob selects random number y and sets Y = g y mod n ffi ffi ffi Page 21 Di e-Hellman Key Exchange (cont) Public-key algorithm for secure key exchange Developed by Di e and Hellman in 1976 Based on di culty of computing discrete logarithms › Key exchange Alice sends X to Bob and Bob sends Y to Alice Alice computes shared key k = Y x mod n Bob computes shared key k = X y mod n ffi ffi ffi Page 22 Di e-Hellman Key Exchange (cont) Why does the key exchange work? y k⌘X ⌘g xy ⌘g Substitute X x ·y ⌘g ffi ⌘ Yx Reverse direction Logarithm rule Page 23 yx (mod n) Security of Di e-Hellman Main attack vectors against key exchange Determining shared k = g xy mod n → Di culty of deriving gxy from gx and gy mod n Deriving secret number x = logg (X ) mod n → Di culty of computing discrete logarithms Security depends on size of X and Y Di culty similar to integer factorization Numbers with 4096 and more bits considered secure ffi ffi ffi ffi Page 24 Summary Page 25 Security and Hard Problems Security of symmetric-key algorithms ⇝ complexity Di usion and confusion through involved bit operations Security of asymmetric-key algorithms ⇝ hard problems Trapdoor property based on hard mathematical problems No polynomial-time solutions known today Will these mathematical problems stay hard?... advances in quantum computing... novel polynomial-time algorithms (or even: P = NP?) ff Page 26 Summary Public-key cryptography Asymmetric keys → secure key exchange Scalable encryption with multiple parties Security based on trapdoor one-way functions Integer factorization → RSA algorithm Discrete logarithm → Di e-Hellman key exchange Security depends on large key sizes (> 3000 bit) Page 27 ffi