【正文】 Lecture 3: Public Key Cryptography CS 392/6813: Computer Security Fall 2020 Nitesh Saxena *Adopted from Previous Lectures by Nasir Memon 11/4/2020 Lecture 3: Pubic Key Cryptography 2 Course Admin ? Good/Bad News ? HW1 will not be graded! ? Not a trick – just for the benefit of this course ? HW2 due ing Monday (09/22) ? HW3 will be posted soon after 11/4/2020 Lecture 3: Pubic Key Cryptography 3 Outline of Today’s Lecture ? Public Key Crypto Overview ? Number Theory Background ? Public Key Encryption ? RSA ? ElGamal ? Public Key Signatures (digital signatures) ? RSA ? DSS 11/4/2020 Lecture 3: Pubic Key Cryptography 4 Recall: Private Key/Public Key Cryptography ? Private Key: Sender and receiver share a mon (private) key ? Encryption and Decryption is done using the private key ? Also called conventional/sharedkey/singlekey/ symmetrickey cryptography ? Public Key: Every user has a private key and a public key ? Encryption is done using the public key and Decryption using private key ? Also called twokey/asymmetrickey cryptography 11/4/2020 Lecture 3: Pubic Key Cryptography 5 Private key cryptography revisited. ? Good: Quite efficient (as you’ll see from the HW2 exercise on AES) ? Bad: Key distribution and management is a serious problem – for N users O(N2) keys are needed 11/4/2020 Lecture 3: Pubic Key Cryptography 6 Public key cryptography model ? Good: Key management problem potentially simpler ? Bad: Much slower than private key crypto (we’ll see later!) 11/4/2020 Lecture 3: Pubic Key Cryptography 7 Public Key Encryption ? Two keys: ? public encryption key e ? private decryption key d ? Encryption easy when e is known ? Decryption easy when d is known ? Decryption hard when d is not known ? We’ll study such public key encryption schemes。 first we need some number theory. ? Security notions/attacks very similar to what we studied for private key encryption 11/4/2020 Lecture 3: Pubic Key Cryptography 8 Group: Definition (G,.) (where G is a set and . : GxG?G) is said to be a group if following properties are satisfied: 1. Closure : for any a, b G, G 2. Associativity : for any a, b, c G, a.()=().c 3. Identity : there is an identity element such that = = a, for any a G 4. Inverse : there exists an element a1 for every a in G, such that = = e Abelian Group: Group which also satisfies mutativity , ., = Examples: (Z,+) 。 (Z,*)?。 (Zm, “modular addition”) ? ???11/4/2020 Lecture 3: Pubic Key Cryptography 9 Definitions related to a group ? An element g in G is said to be a generator of a group if a = gi for every a in G, for a certain integer i ? A group which has a generator is called a cyclic group ? The number of elements in a group is called the order of the group ? Order of an element a is the lowest i such that ai = e ? A subgroup is a subset of a group that itself is a group 11/4/2020 Lecture 3: Pubic Key Cryptography 10 Divisors ? x divides y (written x | y) if the remainder is 0 when y is divided by x ? 1|8, 2|8, 4|8, 8|8 ? The divisors of y are the numbers that divide y ? divisors of 8: {1,2,4,8} ? For every number y ? 1|y ? y|y 11/4/2020 Lecture 3: Pubic Key Cryptography 11 Prime numbers ? A number is prime if its only divisors are 1 and itself: ? 2,3,5,7,11,13,17,19, … ? Fundamental theorem of arithmetic: ? For every number x, there is a unique set of primes {p1, … ,pn} and a unique set of positive exponents {e1, … ,en} such that ene nppx *...*1 1?11/4/2020 Lecture 3: Pubic Key Cryptography 12 Common divisors ? The mon divisors of two numbers x,y are the numbers z such that z|x and z|y ? mon divisors of 8 and 12: