CSC 316 Chapter 2c, Spring 2004

Chapter 2 Basic Encryption (Part C) V. Sawma, Computer Security 2 Outline NP-completeness & Encryption Symmetric (secret key) vs Asymmetric (public key) Encryptions Popular Encryption Algorithms  DES  AES  RSA Encryption  El Gamal Algorithms Hashing Algorithms V. Sawma, Computer Security 3 Review of Concepts Rate of growth:  Polynomial functions Example: n, 10n, n2, 5n3, …  Exponential functions Example: 2n, 210n, … The order of functions matters! V. Sawma, Computer Security 4 Review of Concepts Polynomial bounded An algorithm is said to be polynomial bounded if its worst-case complexity is bounded by a polynomial function of the input size. That is, there exists a polynomial function p such that the algorithm terminates after at most p(n) steps, where n is the input size. A problem is said to be polynomial bounded if there is a polynomial bounded algorithm for it. V. Sawma, Computer Security 5 Nondeterminism A nondeterministic algorithm has two phases: 1. The nondeterministic phase (the guessing phase)  A guess at a solution for the problem is proposed. 2. The deterministic phase (the checking phase)  A deterministic algorithm is executed, with or without the proposed solution from phase 1. V. Sawma, Computer Security 6 Complexity Classes Complexity Classes: Class P P is the class of problems that are polynomial- bounded. Class NP NP is the class of problems for which there is a nondeterministic polynomial-bounded algorithm. A theorem: P  NP Implication: A deterministic algorithm is a special case of a nondeterministic algorithm (with phase 1 ignored). V. Sawma, Computer Security 7 Characteristics of Hard Problems P.632 Each problem is solvable, and a relatively simple approach solves it (although the approach may be time-consuming). There are 2n cases to consider if we use the approach of enumerating all possibilities, where n is the input size. The problems exist in various areas (logic, number theory, graph theory, …). If it were possible to guess perfectly, each problem could be solved in relatively little time. That is, the verification process is polynomial bounded. V. Sawma, Computer Security 8 A broad Knapsack problem From Baase, Computer Algorithms (2nd ed.) Given:  a knapsack of capacity C (a positive integer  N objects with sizes s1, …, sn and “profits” p1, …, pn, where s1, …, sn and p1, …, pn are positive integers. Problem: Find the largest total profit of any subset of the objects that fits in the knapsack (and find a subset that achieves the maximum profit). V. Sawma, Computer Security 9 The Graph Coloring Problem A coloring of a graph G = (V, E) is a mapping C: VS, where S is a finite set of “coloring”, such that if vw  E then C(v)  C(w); that is, adjacent vertices are not assigned the same color. A decision problem: Given G and a positive integer k, is there a coloring of G using at most k colors? (Is G k-colorable?) An application: Scheduling the final exams at a university without conflicts. Let V be the set of courses. Let E be the pairs of courses whose exams must not be at the same time. Suppose there are 15 time slots (3 exams per day X 5 days). Then the exams can be scheduled in the 15 time slots without conflicts if and only if the graph G = (V, E) is 15- colorable. V. Sawma, Computer Security 10 NP-completeness P.632 A problem is called NP-complete if it can represent the entire class NP. Implication: If a NP-complete problem can be solved by a deterministic, polynomial time algorithm, then all NP problems can be solved by such algorithms. The converse implication: “If for even one of the NP-complete problems it could be shown that there was no deterministic algorithm that ran in polynomial time, then no deterministic algorithm could exist for any of them.” V. Sawma, Computer Security 11 Does P = NP or P  NP? NP-complete problems have been studied for a long time by many different groups of people and so far no polynomial, deterministic solution has been found for any one of the problems. Implication: It is very likely that no polynomial, deterministic solution exists for NP-complete problems. That is, NP  P. Note: The question ‘Does P = NP?’ is still an open question. V. Sawma, Computer Security 12 NP-completeness & Cryptography Hard-to-solve problems are fundamental to cryptography, because the interceptor would need to work hard to break the encryption. But, be aware of the fallacies: 1. An NP-complete problem does not guarantee that there is no solution easier than exponential. 2. Every NP-complete problem has a deterministic exponential time solution. That is, O(2n). 3. Continuing advances in hardware make problems of larger size tractable. 4. The interceptor does not always have to solve the hard problem in order to crack the encryption. V. Sawma, Computer Security 13 Properties of Arithmetic Identity & Inverse  A number i is called an identity for • if x • i = x and i • x = x for every number x.  The number b is called the inverse of a under • if a • b = i , where i be an identity for •. Prime Number A prime number is any positive number that is divisible (with remainder 0) only by itself and 1. Greatest Common Divisor (gcd) of two numbers, a and b, is the largest integer that divides both a and b. V. Sawma, Computer Security 14 The greatest common divisor of two positive integers a and b, sometimes written (a, b), is the largest divisor common to a and b. Example: gcd(15,10)=5 because 5 divides both 10 and 15, and nothing larger than 5 does. If p is a prime, for any number q < p, gcd(p,q)=1. Greatest Common Divisor V. Sawma, Computer Security 15 Euclidean Algorithm • The Euclidean Algorithm is a procedure for computing the gcd of two numbers. • It exploits the fact that if x divides a and b, x also divides a-(k*b) for every k. • Suppose x divides both a and b; then a=x*a1 and b=x*b1. But a-(k*b) = x * a1 – (x*k*b1) = x * (a1- k*b1) = x * d So that x divides a-(k*b) V. Sawma, Computer Security 16 Euclidean Algorithm (contd.) Example: To calculate gcd(3615807, 2763323) 3,615,807 = (1) * 2,763,323 + 852, 484 2,763,323 = (3) * 852,484 + 205,871 852,484 = (4) * 205,871 + 29,000 205,871 = (7) * 29,000 + 2,871 29,000 = (10) * 2,871 + 290 2,871 = (9) * 290 + 261 290 = (1) * 261 + 29 261 = (9) * 29 +0 V. Sawma, Computer Security 17 Fermat’s Theorem In number theory, Fermat’s theorem states that for any prime p and any element a<p, ap mod p = a or ap-1 mod p =1 This result leads to the inverse. For a prime p and an element a<p, the inverse of a is the element x such that ax mod p = 1 Combining the last two equations: ax mod p = 1 = ap-1 mod p so that x = ap-2 mod p V. Sawma, Computer Security 18 Fermat’s Theorem Example: To find inverse of 3 mod 5: 3-1 mod 5 = 35-2 mod 5 = 33 mod 5 = 27 mod 5 = 2 V. Sawma, Computer Security 19 Modular Arithmetic Example + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 * 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 V. Sawma, Computer Security 20 Principles of Modular Arithmetic Examples: X 3 * x 3 * x mod 5 1 3 3 2 6 1 3 9 4 4 12 2 5 15 0 6 18 3 7 21 1 X 3 * x 3 * x mod 6 1 3 3 2 6 0 3 9 3 4 12 0 5 15 3 6 18 0 7 21 3 3 * x mod 5 3 * x mod 6 V. Sawma, Computer Security 21 Secret versus Public Key Encryptions Secret Key Encryption Algorithms  Also called single key, symmetric, private key, or conventional algorithms.  Both the encryptor and the decryptor use the same key.  Example: DES, AES Public Key Encryption Algorithms  The sender uses the receiver’s public key to encrypt the message.  The receiver uses his own private key to decrypt the encrypted message.  Examples: RSA Encryption, El Gamal Algorithms V. Sawma, Computer Security 22 Secret Key Encryptions Advantages The symmetry of the key provides a two-way channel. Both ends can both encrypt and decrypt information. Authentication of incoming messages: An incoming ciphertext is authenticated because only legitimate sender can produce the ciphertext. V. Sawma, Computer Security 23 Secret Key Encryptions Disadvantages 1. A single-point failure: A compromised key allows the interceptor not only to decrypt all the ciphertext encrypted by the key, but also to fabricate “bogus” ciphertext to be sent to legitimate receivers. 2. Distribution of keys can be a problem. (Key distribution in pieces) 3. The number of keys increases rapidly, roughly half of the square of the number of people. – Adding a new user into an existing network of N users requires the addition of N new keys. 4. The symmetric key encryptions can be relatively weak, unless based on hard problems. V. Sawma, Computer Security 24 Public Key Encryptions Proposed by Diffie and Hellman in 1976. Each user has two keys: a public key and a private key, which operate as inverses. P = C (KPRIV, E (KPUB, P ) ) Advantage: No need for a shared key between every two users. See table 2-5 p. 75 for a comparison between secret key and public key encryption.