UofODay2007

Information about UofODay2007

Published on January 7, 2008

Author: Heng

Source: authorstream.com

Content

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, 2007 Cryptography 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 e We 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 hard How 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 billion Idea::  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 5 Multiplication 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 91 The 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 [email protected]

Related presentations


Other presentations created by Heng

Cattle Farming
28. 12. 2007
0 views

Cattle Farming

1920 2000 Presidents Review
13. 04. 2008
0 views

1920 2000 Presidents Review

07 Messaging
30. 03. 2008
0 views

07 Messaging

SITE motivation
27. 03. 2008
0 views

SITE motivation

Hands On Session
14. 03. 2008
0 views

Hands On Session

Key Messages
05. 03. 2008
0 views

Key Messages

courseweb
24. 02. 2008
0 views

courseweb

interim01 presentation
20. 02. 2008
0 views

interim01 presentation

Rivkin Fish
07. 01. 2008
0 views

Rivkin Fish

lecture 1
02. 10. 2007
0 views

lecture 1

Sikhism and Baisakhi
26. 11. 2007
0 views

Sikhism and Baisakhi

Plant Reproduction Chapter41
12. 12. 2007
0 views

Plant Reproduction Chapter41

schoff
25. 10. 2007
0 views

schoff

Watkins
26. 10. 2007
0 views

Watkins

chap 18 web
26. 10. 2007
0 views

chap 18 web

After the Fall of Rome
29. 10. 2007
0 views

After the Fall of Rome

tropopause folding ialongo
30. 10. 2007
0 views

tropopause folding ialongo

tw gannon eb XML tech overview
07. 11. 2007
0 views

tw gannon eb XML tech overview

Rodos
30. 10. 2007
0 views

Rodos

AUC DV2003 Woo2
19. 11. 2007
0 views

AUC DV2003 Woo2

Ken
23. 11. 2007
0 views

Ken

Greco Persian Wars
14. 12. 2007
0 views

Greco Persian Wars

columbia dvp
28. 12. 2007
0 views

columbia dvp

The Neanderthal Enigma
31. 12. 2007
0 views

The Neanderthal Enigma

RobertTwilley
03. 01. 2008
0 views

RobertTwilley

AnalysisModeltalk 01Nov05
29. 10. 2007
0 views

AnalysisModeltalk 01Nov05

MTG Benefits
08. 11. 2007
0 views

MTG Benefits

shraiman lecture2 boulder 2
04. 01. 2008
0 views

shraiman lecture2 boulder 2

01 13 05 Andersonian
15. 11. 2007
0 views

01 13 05 Andersonian

TexasVulnerable
30. 12. 2007
0 views

TexasVulnerable

pwps merrell ann phare
28. 12. 2007
0 views

pwps merrell ann phare

DFASBRACAllHandsDec15
30. 10. 2007
0 views

DFASBRACAllHandsDec15

07 15 WMWW Romans 8 Intro
31. 10. 2007
0 views

07 15 WMWW Romans 8 Intro

PIPPresentation
05. 12. 2007
0 views

PIPPresentation

lpgassafety
06. 11. 2007
0 views

lpgassafety

April 11 2007 Presentation
13. 12. 2007
0 views

April 11 2007 Presentation

vcmeeting 2005 12 07
01. 10. 2007
0 views

vcmeeting 2005 12 07

Risa ERF 2005
03. 01. 2008
0 views

Risa ERF 2005

Illum
17. 12. 2007
0 views

Illum

BilgMuh tanitim
30. 11. 2007
0 views

BilgMuh tanitim

04 Technopole Brest
14. 11. 2007
0 views

04 Technopole Brest

25Prok
09. 10. 2007
0 views

25Prok

GA PRGTIPGTE07Norman
29. 12. 2007
0 views

GA PRGTIPGTE07Norman

childsafeysor
25. 12. 2007
0 views

childsafeysor

ekleziologia
21. 11. 2007
0 views

ekleziologia

011116 dg coord price
30. 10. 2007
0 views

011116 dg coord price