Network Security: Asymmetric Encryption PDF

Network Security III. Asymmetric Encryption Prof. Dr. Torsten Braun, Institut für Informatik Bern, 30.09.2024 – 07.10.2024 Network Security: Asymmetric Encryption Network Security: Asymmetric Encryption Table of Contents 1. Introduction 2. Rivest Shamir Adleman Algorithm 3. Key Managem...

Network Security III. Asymmetric Encryption Prof. Dr. Torsten Braun, Institut für Informatik Bern, 30.09.2024 – 07.10.2024 Network Security: Asymmetric Encryption Network Security: Asymmetric Encryption Table of Contents 1. Introduction 2. Rivest Shamir Adleman Algorithm 3. Key Management 4. Elliptic Curves 3 Network Security: Asymmetric Encryption 1. Introduction 1. Asymmetric Encryption public key private key 5404 3214 5404 3214 5673 1023 e(PU, m) 5673 1023 valid 11/25 m rjfjfeoprir0klkln65k6ln565kl6n65n5 D(PR, e(PU, m)) valid 11/25 4 Network Security: Asymmetric Encryption 1. Introduction 2. Asymmetric Encryption Problems − Attacker knows public key, encryption scheme, and cipher text. − Everybody can send a message to a receiver and imitate identities. − Very computing intensive compared to symmetric encryption 5 Network Security: Asymmetric Encryption 1. Introduction 3. Asymmetric Encryption Applications − Encryption and decryption − Digital signatures: encrypting a (part of a) message with a private key − Symmetric key exchange 6 Network Security: Asymmetric Encryption 1. Introduction 4. Asymmetric Encryption: Requirements − Computationally easy to − Computationally infeasible to − generate a public/private key pair − determine the private key PR − encrypt a message C = e(PU, M) − recover message M knowing the − decrypt a message M = D(PR, C) public key PU and ciphertext C − 2 keys are applied in either order: M = D(PU, e(PR, M)) = D(PR, e(PU, M)) 7 Network Security: Asymmetric Encryption 1. Introduction 5. Asymmetric Encryption: Public Key Cryptanalysis Key size must be Another attack: − large enough to make find private key from public key. Today, it has not been mathematically brute-force attack infeasible, proven that this is infeasible for all − but small enough for practical asymmetric encryption algorithms. encryption and decryption. 8 Network Security: Asymmetric Encryption 2. Rivest Shamir Adleman 1. Algorithm Key Generation − Encryption: c = me mod n 1. Selection of 2 big prime numbers − m: message in plaintext p, q, e.g., 1024 bits − c: message in ciphertext 2. Calculate n = p·q; z = (p-1)·(q-1) − Decryption: m = cd mod n 3. Select e < n, so that e and z do − Security is based on the fact that not have common factors. there are no fast algorithms for prime factorization. 4. Select d so that e·d mod z = 1. 5. Public key: , private key: 9 Network Security: Asymmetric Encryption 2. RSA 2. Example Key Generation Encryption − p = 7, q = 11 − m = 9, c = 97 mod 77 = 37 − n = 77; Decryption z = (p-1)·(q-1) = 60 = 5·3·2·2 − e=7 − m = 3743 mod 77 = 9 − 7d mod 60 = 1  d = 43 (7·43 = 301, 301 mod 60 = 1) − = ; = 10 Network Security: Asymmetric Encryption 2. RSA 3. Processing of Multiple Blocks 11 Network Security: Asymmetric Encryption 2. RSA 4.1 Security Attacks − Brute force − Timing attacks − Mathematical attacks − Measuring decryption running time dependent on data − Efforts to factoring the product of two primes − Solutions − constant time − random delays − Blinding: multiply ciphertext before exponentiation Default solution: large keys 12  Network Security: Asymmetric Encryption 2. RSA 4.2 Security Attacks − Hardware fault-based attacks − inducing hardware faults in generating signatures, e.g., by reducing processor power − requires access to the hardware − Chosen ciphertext attack − exploits properties of RSA algorithm − Adversary chooses ciphertext and is given corresponding plaintext. − From that the private key could be derived. 13 Network Security: Asymmetric Encryption 2. RSA 5. Factorization 2020: RSA-250 (829 bits) was factored. 14 Network Security: Asymmetric Encryption 3. Key Management 1. Session Key Exchange − Public keys → certificates KDC − Key Distribution Center − Negotiation of N keys with N clients − KDC calculates session keys and uses one of the N keys for key exchange − Diffie Hellman Key Exchange 15 Network Security: Asymmetric Encryption 3. Key Management 2.1 Diffie Hellman Key Exchange − A and B exchange prime p and − Session key: z = ny mod p generator g (also prime). = mx mod p = gxy mod p − A selects secret random number x (private key), − Security by infeasibility to calculates n = gx mod p, and compute x and y (discrete transmits n (public key) to B. logarithm), which is much more − B selects secret random complex than prime factorization number y (private key), calculates m = gy mod p, and transmits m (public key) to A. 16 Network Security: Asymmetric Encryption 3. Key Management 2.2 Diffie Hellman Key Exchange Example − p = 47, g = 3, A: x = 8, B: y = 10 − Problem: − A → B: (47, 3, n = 28 (= 38 mod 47)) „Man in the Middle“ attack − B → A: (47, 3, m= 17 (= 310 mod 47)) − Solution: Authenticated DH − Key z = 178 mod 47 = 2810 mod 47 = exchange using private or 380 mod 47 = 4 public keys 17 Network Security: Asymmetric Encryption 3. Key Management 3. „Man in the Middle“ Attack p, g, n = gx mod p p, g, gz mod p gz mod p m = gy mod p encryption encrpytion with gxz mod p 18 with gyz mod p Network Security: Asymmetric Encryption 4. Elliptic Curves 1. Arithmetics − Most public-key cryptography − Elliptic Curve Cryptography is products and standards use RSA. showing up in standardization efforts including IEEE P1363 for − The key length for secure RSA use has increased over recent Public-Key Cryptography. years and generates heavier − ECC aims to offer equal security processing load on for a far smaller key size. applications using RSA. 19  Network Security: Asymmetric Encryption 4. Elliptic Curves 2. Elliptic Curves over Real Numbers E(-1,0) − Elliptic curves are not ellipses. − Elliptic curves are described by cubic equations, similar to those used for calculating the circumference of an ellipse (Weierstrass equation): y2 + axy + by = x3 + cx2 + dx + e E(1,1) − Here: equations of the form y2 = x3 + ax + b − To plot such a curve, we need to compute y = √(x 3 + ax + b) − Sets of points E(a, b) depict curves, e.g., E(-1,0), E(1,1) − For any 3 points in such a set: the sum is O (zero point). 20 Network Security: Asymmetric Encryption 4. Elliptic Curves 3. Addition Rules O = -O To add two points P, Q with P+O=P different x coordinates: draw a straight line and find the P + (-P) = O point of intersection: P + Q = -R 21 Network Security: Asymmetric Encryption 4. Elliptic Curves 4. Elliptic Curves over Zp − Elliptic curve cryptography makes − here: use of elliptic curves, y2 mod p = (x3 + ax + b) mod p, in which variables and coefficients are restricted to elements of a which is for example satisfied by finite field. a=1, b=1, x=9, y=7, p=23 − Prime curve over Zp − 72 mod 23 = (93 + 9 + 1) mod 23 − values: integers from 0 to p-1 − 49 mod 23 = 739 mod 23 − good for software processing − 3=3 − Binary curve over GF(2m) − values in GF(2m) and − Coefficients a, b and variables x, y calculations over GF(2m) are all elements of Zp. − good for hardware processing 22  Network Security: Asymmetric Encryption 4. Elliptic Curves 5. Points on the Elliptic Curve E23(1,1) 22 21 (0, 1) (6, 4) (12, 19) 20 19 (0, 22) (6, 19) (13, 7) 18 17 16 (1, 7) (7, 11) (13, 16) 15 14 (1, 16) (7, 12) (17, 3) 13 12 y 11 (3, 10) (9, 7) (17, 20) 10 9 (3, 13) (9, 16) (18, 3) 8 7 6 (4, 0) (11, 3) (18, 20) 5 4 (5, 4) (11, 20) (19, 5) 3 2 1 (5, 19) (12, 4) (19, 18) 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 x Network Security: Asymmetric Encryption 4. Elliptic Curves 6.1 Ep(a,b) Addition Rules 1. P + O = P 2. P = (xP, yP): P + (xP, -yP) = O 3. P = (xP, yP), Q = (xQ, yQ), P≠-Q: R = P + Q = (xR, yR) 4. Multiplication as repeated addition, e.g., 4P = P + P + P + P 24 Network Security: Asymmetric Encryption 4. Elliptic Curves 6.2 Ep(a,b) Addition Rules: Example: P + Q, Q ≠ P P + Q = R, P ≠ Q xR = (112 – 3 – 9) mod 23 xR = (2 – xP – xQ) mod p = 109 mod 23 = 17 yR = ( (xP – xR) – yP) mod p yR = (11・(3 – 17) -10) mod 23  = (yQ - yP)/(xQ - xP) mod p = -164 mod 23 = 20 P = (3, 10) = (xP, yP) yR mod 23 = -164 mod 23⎮+ 184 Q = (9, 7) = (xQ, yQ) = 20 mod 23 a = b = 1, p = 23  = ((7 – 10) / (9 - 3)) mod 23 = (-3 / 6) mod 23 = (-1 / 2) mod 23 R = (17, 20) = (-1) mod 23 / 2 = 22 / 2 = 11 25 Network Security: Asymmetric Encryption 4. Elliptic Curves 7. Elliptic Curves over GF(2 m) − A finite field (Galois Field) GF(2m) − Example: GF(24) with the irreducible consists of 2m elements together with polynomial f(x) = x4 + x + 1 addition and multiplication operations that can be defined over polynomials. − Generator g with f(g) = 0: g4 = g + 1, in binary: g = 0010 − Cubic equation appropriate for cryptographic applications is − g5 = g4 g = (g + 1) g = g2 + g = 0110 (XOR) y2 + xy = x3 + ax2 + b, g0=0001 g4=0011 g8=0101 g12=1111 x, y, a, b are elements of GF(2m). g1=0010 g5=0110 g9=1010 g13=1101 g2=0100 g6=1100 g10=0111 g14=1001 26 g3=1000 g7=1011 g11=1110 g15=0001 Network Security: Asymmetric Encryption 4. Elliptic Curves 8. Example Point on E24(g4,1) y2 + xy = x3 + g4x2 + 1 (g5, g3) satisfies equation. (g3)2 + g5 g3 = (g5)3 + g4 (g5)2 + 1 g6 + g8 = g15 + g14 + 1 1100 + 0101 = 0001 + 1001 + 0001 1001 = 1001 27  Network Security: Asymmetric Encryption 4. Elliptic Curves 9. Points on the Elliptic Curve E24(g4,1) 0 g14 g13 g12 (0, 1) (g5, g3) (g9, g13) g11 g10 (1, g6) (g5, g11) (g10, g) g9 g8 (1, g13) (g6, g8) (g10, g8) y g7 g6 (g3, g8) (g6, g14) (g12, 0) g5 g4 (g3, g13) (g9, g10) (g12, g12) g3 g2 g 1 1 g g2 g3 g4 g5 g6 g7 g8 g9 g10 g11 g12 g13 g14 0 28 x Network Security: Asymmetric Encryption 4. Elliptic Curves 10.1 E2m(a,b) Addition Rules 1. P + O = P 2. P = (xP, yP): P + (xP, xP + yP) = O (xP, xP + yP) = -P 3. P = (xp, yp), Q = (xQ, yQ): R = P + Q = (xR, yR) 4. P = (xp, yp): R = 2P = (xR, yR) 29  Network Security: Asymmetric Encryption 4. Elliptic Curves 10.2 E2m(a,b) Addition Rules: Example 2P, P = (g5, g3) xR =  +  + a, a = g4, b = 1 yR = xP2 + ( + 1) xR  = xP + yP/xP = g5+g3/g5 = g5+g-2 = g5+g13 = (g5)2 + (g5 + g13 + 1) 1 xR= (g10 + 2g18 + g26) + g5 + g13 + g4 = g10 + g5 + g13 + 1 = g10 + 0 + g11 + g5 + g13 + g4 = 0111 + 0110 + 1101 + 0001 = 0111 + 1110 + 0110 + 1101 + 0011 = 1101 = 0001 = 1 = g0 = g13 2P = (1, g13) 30 Network Security: Asymmetric Encryption 4. Elliptic Curves 11. Elliptic Curve Cryptography To form a cryptographic system − Q = k・P; using elliptic curves, we need to Q, P belong to a prime curve. find a “hard problem”, e.g., − It is easy to compute Q given k, P, − factoring the product of two e.g., 100P=2(2(P+2(2(2(P + 2P))))) primes or − It is hard to find k given Q, P. − taking the discrete logarithm. − This is known as the elliptic curve logarithm problem. 31 Network Security: Asymmetric Encryption 4. Elliptic Curves 12. Example ECC − E23(9, 17) is defined by − P = (16, 5); 2P = (20, 20); y2 mod 23 = (x3 + 9x + 17) mod 23. 3P = (14, 14); 4P = (19, 20); 5P = (13, 10); 6P = (7, 3); − What is the discrete logarithm k of 7P = (8, 7); 8P = (12, 17); Q = (4, 5) to the base P = (16, 5)? 9P = (4, 5). − Brute-force method is to compute − discrete logarithm Q = (4, 5) to multiples of P until Q is found. the base P = (16, 5) is k = 9. − In reality, k would be so large as to make the brute-force approach infeasible. 32  Network Security: Asymmetric Encryption 4. Elliptic Curves Global Public Elements 13. Analog to Diffie Hellman Eq(a, b) elliptic curve with parameters a, b, and q, where q is a prime or an integer of the form 2m G point on elliptic curve whose order is large value n Key Exchange − An attacker would need to calculate k User A Key Generation given base point G and kG. Select private nA nA < n Calculate public PA P A = nA ´ G − Example: p=211, Ep(0, -4): y2 = x3-4; G=(2, 2) − 240 G = O User B Key Generation Select private nB nB < n − Private key nA = 121 Calculate public PB P B = nB ´ G → public key PA = 121 (2, 2) = (115, 48) − nB = 203 → PB = 203 (2, 2) = (130, 203) Calculation of Secret Key by User A K = nA ´ PB − Shared key = 121・(130, 203) = 203・(115, 48) = 121・203 (2, 2) = (161, 69) Calculation of Secret Key by User B K = nB ´ PA 33 Network Security: Asymmetric Encryption 4. Elliptic Curves 14. Comparable Key Sizes in Terms of Computational Efforts for Cryptanalysis Symmetric key Diffie-Hellman, RSA ECC algorithms Digital Signature (size of n in bits) (modulus size in Algorithm bits) 80 L = 1024 1024 160–223 N = 160 112 L = 2048 2048 224–255 N = 224 128 L = 3072 3072 256–383 N = 256 192 L = 7680 7680 384–511 N = 384 256 L = 15,360 15,360 512+ 34 N = 512 Thanks for Your Attention Prof. Dr. Torsten Braun, Institut für Informatik Bern, 30.09.2024 – 07.10.2024 35