EECS 70 Discrete Mathematics and Probability TheorySpring 2014 Anant Sahai Note 6This note is partly based on Section 1.4 of “Algorithms," by S. Dasgupta, C. Papadimitriou and U. Vazirani,McGraw-Hill, 2007.An online draft of the book is available at http://www.cs.berkeley.edu/ vazirani/algorithms.htmlPublic Key CryptographyIn this note, we discuss a very nice and important application of modular arithmetic: the RSA public-keycryptosystem, named after its inventors Ronald Rivest, Adi Shamir and Leonard Adleman.Cryptography is an ancient subject that really blossomed into its modern form at the same time1as theother great revolutions in the general fields of information science/engineering. The basic setting for basiccryptography is typically described via a cast of three characters: Alice and Bob, who with to communicateconfidentially over some (insecure) link, and Eve, an eavesdropper who is listening in and trying to discoverwhat they are saying.Let’s assume that Alice wants to transmit a message x (written in binary) to Bob. She will apply her encryp-tion function E to x and send the encrypted message E(x) (also called the cyphertext) over the link; Bob,upon receipt of E(x), will then apply his decryption function D to it and thus recover the original message(also called the plaintext): i.e., D(E(x)) = x.Since the link is insecure, Alice and Bob have to assume that Eve may get hold of E(x). (Think of Eveas being a “sniffer" on the network.) Thus ideally we would like to know that the encryption function E ischosen so that just knowing E(x) (without knowing the decryption function D) doesn’t allow one to discoveranything about the original message x.For millenia cryptography was based on what are now called private-key protocols. In such a scheme,Alice and Bob meet beforehand and together choose a secret codebook, with which they encrypt all futurecorrespondence between them. (This codebook plays the role of the functions E and D above.) Eve’s onlyhope then is to collect some encrypted messages and use them to at least partially figure out the codebook.Public-key schemes, such as RSA, are significantly more subtle and tricky: they allow Alice to send Boba secure message without ever having met him privately before! This almost sounds impossible, becausein this scenario there is a symmetry between Bob and Eve: why should Bob have any advantage over Evein terms of being able to understand Alice’s message? The central idea between the RSA cryptosystem isthat Bob is able to implement a digital lock, to which only he has the key. Now by making this digital lockpublic, he gives Alice (or, indeed, anybody else) a way to send him a secure message which only he canopen.Here is how the digital lock is implemented in the RSA scheme. Each person has a public key known to thewhole world, and a private key known only to themselves. When Alice wants to send a message x to Bob,1And in reality, involving some of the same cast of characters. Both Alan Turing and Claude Shannon were active in code-breaking during the war and Shannon had a classic paper that is considered the birth of the information-theoretic understanding ofsecrecy and dovetails with his other more famous paper that gave rise to the modern information-theoretic view of communication.Both cryptography and communication weave together information, computation, and randomness in surprising ways. In 70, youjust get a tiny taste of these spectacularly beautiful fields.EECS 70, Spring 2014, Note 6 1she encodes it using Bob’s public key. Bob then decrypts it using his private key, thus retrieving x. Eve iswelcome to see as many encrypted messages for Bob as she likes, but she will not be able to decode them(under certain simple assumptions explained below).But before we can go into how to use modulo arithmetic to achieve this sort of scheme, we need to reviewsome basic properties of functions.BijectionsA function is a mapping from a set (called the domain) of inputs A to a set of outputs B: for input x ∈ A,f (x) must be in the set B. To denote such a function, we write f : A → B.Consider the following examples of functions, where both functions map {0,. ..,m − 1} to itself:f (x) = x + 1 mod mg(x) = 2x mod mA bijection is a function for which every b ∈ B has a unique pre-image a ∈ A such that f (a) = b. Note thatthis consists of two conditions:1. f is onto: every b ∈ B has a pre-image a ∈ A.2. f is one-to-one: for all a, a0∈ A, if f (a) = f (a0) then a = a0.Looking back at our examples, we can see that f is a bijection; the unique pre-image of y is y − 1. However,g is only a bijection if m is odd. Otherwise, it is neither one-to-one nor onto. The following lemma can beused to prove that a function is a bijection:Lemma: For a finite set A, f : A → A is a bijection if there is an inverse function g : A → A such that ∀x ∈ Ag( f (x)) = x.Proof: If f (x) = f (x0), then x = g( f (x)) = g( f (x0)) = x0. Therefore, f is one-to-one. Since f is one-to-one,there must be |A| elements in the range of f . This implies that f is also onto. 2RSAA particularly practical family of bijections is the RSA function, named after its inventors Ronald Rivest,Adi Shamir and Leonard Adleman:E(x) ≡ xemod Nwhere N = pq (p and q are two large primes), E : {0, ..., N − 1} → {0, ..., N − 1} and e is relatively primeto (p − 1)(q − 1). The inverse of the RSA function is:D(x) ≡ xdmod Nwhere d is the inverse of e mod (p − 1)(q − 1).Let’s bring back our standard cast of characters and assume that Alice wants to transmit a message x (mappedinto a number between 2 and N −1. Can you see why we avoid both 0 and 1?) to Bob. In order to encrypt themessage, Alice only needs Bob’s public key (N,e). In order to decrypt the message, Bob needs his privateEECS 70, Spring 2014, Note 6 2key d. The pair (N, e) can be thought of as the serial number of the public lock - anyone can place a messagein a box and lock it, but only Bob has the key d to open the lock. The idea is that since Eve does not haveaccess to d, she will not be able to gain information about Alice’s message.Here is an example:Example: Let p = 5, q = 11, and N = pq = 55. (In practice, p and q would be much larger.) Then we canchoose e = 3, which is relatively prime to (p − 1)(q − 1) = 40. Thus Bob’s public key is (55,3). His privatekey is d = 3−1mod 40 = 27. For any message x that Alice (or anybody else) wishes to send to Bob, theencryption of x is
View Full Document
Unlocking...