Cryptography 101RSA Public Key EncryptionPublic & Private KeysHow does it work?Public KeyExampleEncryptionDecryptionSlide 9SummaryCryptography 101How is data actually securedRSA Public Key Encryption•RSA – names after the inventors–Rivest, Shamir, and Adleman•Basic Idea:•Your private key is the only key that can unlock (decrypt) messages that were locked (encrypted) with your public key.Public & Private Keys•Share you public key–Thus, users can send you encrypted data•Never share your private key–Thus, no one else can decrypt messages that are sent to you and encrypted with you public keyHow does it work?•Answer: Math•Background:–What are the factors of 30?–What are prime numbers.–What are the prime factors of 30?Public Key•Public Key = PK = p*q•Example: –p = 5–q = 11–PK = 55•55 is special; Its the product of two prime numbers.Example•http://www.antilles.k12.vi.us/math/cryptotut/rsa3.htm•PK = 55•Here I’m going to encrypt the letter ‘E’•‘E’ is represent in ASCII as 69•The encryption technique will actually transform the letter ‘E’ (69) into the number ‘1’ (49)Encryption•Take your text (T = 69)•Enlarge it by raising it to a power (e = 3)–Here I can pick E to be whatever I want•Divide by Public Key (PK = 55)•The remainder is the encrypted cipher-text (C =49)•693 = 328,509•328,509 / 55 = 5972 R 49Decryption•How do you decrypt 49 back into a 69?•You have to compute a special value–The book calls this value s–Most other books call this value d•s = (1/e) * (2 * (p-1) * (q-1) + 1)•s = 1/3 * (2*4*10 + 1)•s = 1/3 * 81•s = 27Decryption•How do you decrypt 49 (C) back into a 69 (T)?•Take your ciphertext (C = 49)•Enlarge it by raising it to a power (s = 27)–Here s depends on your choice of p, q, and e.•Divide by Public Key (PK = 55)•The remainder is the original (C =49)•4927 = a really big number•really big number / 55 = 5972 R 69Summary•Encryption –uses the Public Key (PK) and specially selected value (e)–These are both Public knowledge–In fact, the Public key is both PK and e•Decryption–uses a specially computed value s (some books call it d)–This value is kept private.–It computationally impossible to figure out s unless you know p and q.–The private key is s. But keep in mind that s is computed from p, q, and