CS 389 Final Review Chapter 8: Encipherment Using Modern Symmetric-Key Ciphers • Block Cipers o Modes of Operations ! Electronic Codebook (ECB) Mode ! Cipher Block Chaining (CBC) Mode ! Cipher Feedback (CFB) Mode ! Output Feedback (OFB) Mode ! Counter (CTR) Mode • Stream Ciphers o RC4 o A5/1 Chapter 9: Mathematics of Cryptography (Part III: Primes and Related Congruence Equations) • Primes o A prime is divisible only by itself and 1. o There is an infinite number of primes. o Checking for Primeness. ! Sieve of Eratosthenes o Euler’s Phi-Function ! Euler’s phi-function f (n) denotes the number of integers that are both smaller than n and relatively prime to n. ! Properties: ! The difficulty of finding f(n) depends on the difficulty of finding the factorization of n. o Fermat’s Little Theorem ! p is a prime, a is an integer such that p does not divide a. • ap ! 1 " 1 mod p • ap " a mod p ! Multiplicative Inverses • a!1 mod p = a p ! 2 mod p o Euler’s Theorem ! If a and n are co-prime (relatively prime) • First Version o af(n) " 1 (mod n) • Second Versiono a k # f(n) + 1 " a (mod n) ! Multiplicative Inverses • Euler’s theorem can be used to find multiplicative inverses modulo a composite • a!1 mod n = af(n)!1 mod n o Generating Primes ! Mersenne Primes: • A number in the form Mp = 2p ! 1 is called a Mersenne number and may or may not be a prime. ! Fermat Primes o Primality Testing ! Finding an algorithm to correctly and efficiently test a very large integer and output a prime or a composite has always been a challenge in number theory. ! Divisibility Algorithm • The bit-operation complexity of the divisibility test is exponential. ! Fermat Test • If n is a prime, an!1 " 1 mod n • If n is a composite, it is possible that an!1 " 1 mod n ! Square Root Test o Factorization ! Greatest Common Divisor ! Least Common Multiplier ! Trial Division Method ! Fermat Method o Chinese remainder theorem ! The Chinese remainder theorem (CRT) is used to solve a set of congruent equations with one variable, but different moduli. ! Solution To Chinese Remainder Theorem • Find M = m1 # m2 # … # mk. This is the common modulus. • Find M1 = M/m1, M2 = M/m2, …, Mk = M/mk. • Find the multiplicative inverse of M1, M2, …, Mk using the corresponding moduli (m1, m2, …, mk). Call the inverses M1!1, M2!1, …, Mk !1. • The solution to the simultaneous equations is o o Exponentiation and Logarithm o Fast Exponentiation o Logarithm ! Order of the Group ! Order of an Element! Primitive Roots In the group G = <Zn!, #>, when the order of an element is the same as f(n), that element is called the primitive root of the group. ! The group G = <Zn*, #> has primitive roots only if n is 2, 4, pt, or 2pt. ! If the group G = <Zn*, #> has any primitive root, the number of primitive roots is f(f(n)). ! Cyclic Group If g is a primitive root in the group, we can generate the set Zn* as Zn! = {g1, g2, g3, …, gf(n)} ! The idea of Discrete Logarithm • Properties of G = <Zp*, #> : 1. Its elements include all integers from 1 to p ! 1. 2. It always has primitive roots. 3. It is cyclic. The elements can be created using gx where x is an integer from 1 to f(p) = p ! 1. 4. The primitive roots can be thought as the base of logarithm. ! The discrete logarithm problem has the same complexity as the factorization problem. Chapter 10: Asymmetric-Key Cryptography • Symmetric-key cryptography is based on sharing secrecy; • Asymmetric-key cryptography is based on personal secrecy. • Asymmetric key cryptography uses two separate keys: one private and one public. • Plaintext/Ciphertext o Unlike in symmetric-key cryptography, plaintext and ciphertext are treated as integers in asymmetric-key cryptography. • Encryption/Decryption o C = f (Kpublic , P) , P = g(Kprivate , C) • Trapdoor One-Way Function o The main idea behind asymmetric-key cryptography is the concept of the trapdoor one-way function. o One-Way Function (OWF) ! f is easy to compute. ! f !1 is difficult to compute. o Trapdoor One-Way Function (TOWF) ! f is an One-Way Function ! Given y and a trapdoor, x can be computed easily. • Knapsack Cryptosystem o Definition ! a = [a1, a2, …, ak ] and x = [x1, x2, …, xk]. ! Given a and x, it is easy to calculate the knapsack sum s. ! However, given s and a it is difficult to find x. o Super-increasing Tuple ! ai $ a1 + a2 + … + ai!1 o Secret Communication with Knapsacks• RSA cryptosystem o Key Generation o Encryption o Decryption Chapter 11: Message Integrity and Message Authentication • Message and Message Digest o The message digest needs to be safe from change. • Cryptographic Hash Function Criteria o A cryptographic hash function must satisfy three criteria: ! preimage resistance, ! Second preimage resistance, and ! Collision resistance. o Random Oracle Mode ! The hash function based on the random oracle model behaves as follows: 1. When a new message of any length is given, then oracle creates and gives a fixed-length message digest that is a random strong of 0’s and 1’s. The oracle records the message and the message digest. 2. When a message is given for which a digest exists, the oracle simply gives the digest in the record. 3. The digest for a new message needs to be chosen independently from all previous digests. This implies that the oracle cannot use a formula or an algorithm to calculate the digest. ! Pigeonhole Principle • If n pigeonholes are occupied by n + 1 pigeons, then at least one pigeonhole is occupied by two pigeons. • The generalized version of the pigeonhole principle is that if n pigeonholes are occupied by kn + 1 pigeons, then at least one pigeonhole is occupied by k + 1 pigeons. • Four Versions of the Birthday Problems o Their descriptions, solutions, and comparison. ! Attacks on Random Oracle Model • Preimage Attack • Second Preimage Attack • Collision Attack • Alternate Collision Attack o Message Authentication ! Modification Detection Code (MDC) ! Message Authentication Code (MAC) • The security of a MAC depends on the security of the underlying hash algorithm. Chapter 12 is ignored and will not be covered in the exam.Chapter 13: Digital Signature • A digital signature needs a public-key system. The signer signs with her private key; the verifier