logging in or signing up UofODay2007 Heng Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: Embed: Flash iPad Dynamic Copy Does not support media & animations Automatically changes to Flash or non-Flash embed WordPress Embed Customize Embed URL: Copy Thumbnail: Copy The presentation is successfully added In Your Favorites. Views: 127 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: January 07, 2008 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Simple and Unbreakable: The Mathematics of Internet Security: Simple and Unbreakable: The Mathematics of Internet Security Dr. Monica Nevins Department of Mathematics and Statistics University of Ottawa University of Ottawa Day, 2007Cryptography ca. 50 BC: Cryptography ca. 50 BC Example: VENI, VIDI, VICI Becomes: YHQL, YLGL, YLFL Caesar cipher: Shift each letter forward by 3 Second World War : Enigma: Second World War : Enigma Secret device Secret settings (rotors and plugs) 1020 possibilities "Uncrackable" Cracked by mathematicians in early 1940.Today: Today Millions of people need private, secure communication over the internet every day. Everyone has access to every interchange of communication. How can we start secure communications without first having secure communications?A Thought Experiment: A Thought Experiment Say the only secure communication in this room is to lock your message in a box. Anything not in the box can be read or duplicated or stolen. Could you send me a secret message (that I can read but no one else can)?The model for public key cryptography: The model for public key cryptography M C C, d …M ! C?? Alice Bob Eve d e eWe need a one-way function: We need a one-way function Multiply : 17 x 11 = ? 187 Factor : 91 = ? X ? 7 x 13 This is a one-way function: Multiplication is easy Factoring is hardHow hard is factoring? : How hard is factoring? Say N has 20 digits. To find a factor, you need to search up to: N ~ 10 digits How many numbers is that? 1010 = 10,000,000,000 = 10 billionIdea:: Idea: Find two large prime numbers p and q . Set N = pq. But: isn't finding primes just as hard as factoring? NO! Check out the AKS algorithm, 2003.But how does this give us a cryptosystem?: But how does this give us a cryptosystem?Modular Arithmetic: Modular Arithmetic Doing math "mod 10" means taking the remainder after division by 10 4 x 4 = 16 implies 4 x 4 = 6 mod 10 4 x 4 = 16 implies 4 x 4 = 1 mod 5Multiplication Table, mod 5: Multiplication Table, mod 5 Mysterious patterns, but : easy to calculate.More powerful: exponentiation: More powerful: exponentiation Consider powers of 4 mod 91: 41 = 4 42 = 16 43 = 64 44 = 256 = 74 mod 91 45 = 1024 = 23 mod 91 … Exponentiation “mod N” is one-way: Exponentiation “mod N” is one-way Calculating powers mod N is easy; Calculating roots mod N is hard. Except: it’s easy if you have the secret key: j(N) = (p-1)(q-1) For example: N = 91 = 13 x 7 gives j(N) = 12 x 6 = 72.How the secret key works: How the secret key works When e and d satisfy ed = 1 mod j(N), (Example: 5 x 29 = 145 = 1 mod 72) then C = Me mod N if and only if M = Cd mod N.RSA Cryptosystem: RSA Cryptosystem Two primes: p = 7, q = 13. Set N = pq = 91. Choose an e = 5. Public key: (N, e) = (91, 5) Now j(N) = 72 and d = 29, since ed = 5 x 29 = 145 = 1 mod 72. Private key: d = 29.RSA Encryption: RSA Encryption Get the public key (N,e) = (91,5) Secret message: M = 4 Calculate C = Me mod N: C = 45 mod 91 = 1024 mod 91 = 23 mod 91The Cryptogram: The Cryptogram 23 ??RSA Decryption: RSA Decryption Given C = 23 and private key d = 29, calculate: Cd = 2329 mod 91 Since 236 = 1 mod 91, 2329 = 235 = 6436343 = 4 mod 91 So the secret message was M = 4 !Security of RSA: Security of RSA Mathematicians have been studying number theory for ages --- we have confidence that there are no shortcuts. New technologies (quantum computer) Need new cryptosystems built on different mathematical concepts to ensure we stay ahead of technology (elliptic curves, lattice cryptosystems, etc)For more information: For more information Come and enjoy undergraduate studies in Pure Mathematics at the University of Ottawa mnevins@uottawa.ca You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
UofODay2007 Heng Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: Embed: Flash iPad Dynamic Copy Does not support media & animations Automatically changes to Flash or non-Flash embed WordPress Embed Customize Embed URL: Copy Thumbnail: Copy The presentation is successfully added In Your Favorites. Views: 127 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: January 07, 2008 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Simple and Unbreakable: The Mathematics of Internet Security: Simple and Unbreakable: The Mathematics of Internet Security Dr. Monica Nevins Department of Mathematics and Statistics University of Ottawa University of Ottawa Day, 2007Cryptography ca. 50 BC: Cryptography ca. 50 BC Example: VENI, VIDI, VICI Becomes: YHQL, YLGL, YLFL Caesar cipher: Shift each letter forward by 3 Second World War : Enigma: Second World War : Enigma Secret device Secret settings (rotors and plugs) 1020 possibilities "Uncrackable" Cracked by mathematicians in early 1940.Today: Today Millions of people need private, secure communication over the internet every day. Everyone has access to every interchange of communication. How can we start secure communications without first having secure communications?A Thought Experiment: A Thought Experiment Say the only secure communication in this room is to lock your message in a box. Anything not in the box can be read or duplicated or stolen. Could you send me a secret message (that I can read but no one else can)?The model for public key cryptography: The model for public key cryptography M C C, d …M ! C?? Alice Bob Eve d e eWe need a one-way function: We need a one-way function Multiply : 17 x 11 = ? 187 Factor : 91 = ? X ? 7 x 13 This is a one-way function: Multiplication is easy Factoring is hardHow hard is factoring? : How hard is factoring? Say N has 20 digits. To find a factor, you need to search up to: N ~ 10 digits How many numbers is that? 1010 = 10,000,000,000 = 10 billionIdea:: Idea: Find two large prime numbers p and q . Set N = pq. But: isn't finding primes just as hard as factoring? NO! Check out the AKS algorithm, 2003.But how does this give us a cryptosystem?: But how does this give us a cryptosystem?Modular Arithmetic: Modular Arithmetic Doing math "mod 10" means taking the remainder after division by 10 4 x 4 = 16 implies 4 x 4 = 6 mod 10 4 x 4 = 16 implies 4 x 4 = 1 mod 5Multiplication Table, mod 5: Multiplication Table, mod 5 Mysterious patterns, but : easy to calculate.More powerful: exponentiation: More powerful: exponentiation Consider powers of 4 mod 91: 41 = 4 42 = 16 43 = 64 44 = 256 = 74 mod 91 45 = 1024 = 23 mod 91 … Exponentiation “mod N” is one-way: Exponentiation “mod N” is one-way Calculating powers mod N is easy; Calculating roots mod N is hard. Except: it’s easy if you have the secret key: j(N) = (p-1)(q-1) For example: N = 91 = 13 x 7 gives j(N) = 12 x 6 = 72.How the secret key works: How the secret key works When e and d satisfy ed = 1 mod j(N), (Example: 5 x 29 = 145 = 1 mod 72) then C = Me mod N if and only if M = Cd mod N.RSA Cryptosystem: RSA Cryptosystem Two primes: p = 7, q = 13. Set N = pq = 91. Choose an e = 5. Public key: (N, e) = (91, 5) Now j(N) = 72 and d = 29, since ed = 5 x 29 = 145 = 1 mod 72. Private key: d = 29.RSA Encryption: RSA Encryption Get the public key (N,e) = (91,5) Secret message: M = 4 Calculate C = Me mod N: C = 45 mod 91 = 1024 mod 91 = 23 mod 91The Cryptogram: The Cryptogram 23 ??RSA Decryption: RSA Decryption Given C = 23 and private key d = 29, calculate: Cd = 2329 mod 91 Since 236 = 1 mod 91, 2329 = 235 = 6436343 = 4 mod 91 So the secret message was M = 4 !Security of RSA: Security of RSA Mathematicians have been studying number theory for ages --- we have confidence that there are no shortcuts. New technologies (quantum computer) Need new cryptosystems built on different mathematical concepts to ensure we stay ahead of technology (elliptic curves, lattice cryptosystems, etc)For more information: For more information Come and enjoy undergraduate studies in Pure Mathematics at the University of Ottawa mnevins@uottawa.ca