Report

Numbers on the Internet GCNU 1025 Numbers Save the Day Internet security • Anonymity on internet • Example: internet crime • IP (internet protocol) address: identification of computer • Information of network/host ID • Assigned by internet service providers (ISP) • Static/Dynamic (details not required) Internet security • IPv4: Internet Protocol version 4 • 4 parts (octets): • 8 bits for each part (32 bits in total) • Each part expressed as base 10 numbers for convenience • At most 232 ≈ 4 billion different addresses Internet security • IPv6: Internet Protocol version 6 • 8 parts: • 16 bits for each part (128 bits in total) • Each part expressed as base 16 numbers • At most 2128 different addresses Internet security • Example: online banking • Double security: password and security device • Number-generating security device • A 6-digit code generated from device ID and time (by a secret method) for each log-in session (access granted only if entered code agrees with one generated by bank server) • Generated code effective only within 15-30 seconds Simple cryptography • Encryption: from plaintexts to ciphers (with a specific rule) • Decryption: from ciphers to plaintexts (with a specific rule) • Cryptography: study of encryption and decryption • Encryption and decryption can be symmetric (same key for both processes) or asymmetric (different keys) Numbers on the Internet GCNU 1025 Numbers Save the Day Caesar cipher • Cipher obtained by simple letter shifting with a fixed (forward) shifting number (A-Z treated as a cycle) • Example: • Plaintext: IT’S NOT A JOURNEY • Cipher: JU'T OPU B KPVSOFZ • Shifting number: 1 (encryption: letters shifted forward by 1 place) Caesar cipher • Example: Classwork • Plaintext: NUMBER IS FUNNY • Shifting number: 4 • Cipher: RYQFIV MW JYRRC • How to decrypt? • Key: shifting number • Caesar cipher: easy to break by simple trial-and-error • Key feature: single shifting number Vigenere cipher • Vigenere cipher: higher security level with multiple shifting numbers • Example: • Shifting numbers (key used in both encryption and decryption): (12, 0, 19, 7) Vigenere cipher • Shifting numbers represented by a word according to the rule • Example: (12, 0, 19, 7) represented by “MATH” Vigenere cipher • Plaintext: THISISBORING • Key: YES = (24, 4, 18) Encrypted message (cipher): RLAQMKZSJGRY Substitution cipher • Systematically replacing each letter by another letter • Examples: Caesar cipher and Vigenere cipher • Simple substitution cipher: Ways of breaking codes • Look for single-letter words (A or I) • Look for special features such as apostrophes (’) • Look for particular patterns • Tackle shorter words first • Frequency analysis Ways of breaking codes • Example: Kieron Bryan’s Murder attempt 2012 • Encrypted letter sent to sister (during investigation) • Code broken by police in 3 days Ways of breaking codes Ways of breaking codes • Example: Kieron Bryan’s Murder attempt 2012 • Particular pattern: 33, 9, 5, 10, 3, 5 (PLEASE) Feb 2012 News: Police cracked the code to uncover gunman's bribery bid Numbers on the Internet GCNU 1025 Numbers Save the Day Ways of breaking codes • Frequency analysis • Example: frequencies for a plaintext passage Ways of breaking codes • Frequency analysis • Compare the standard frequencies with the frequencies obtained from the encrypted message (cipher) • More useful for long messages • Patterns also considered Ways of breaking codes • Frequency analysis • Example: Kieron Bryan’s Murder attempt 2012 • “E” is generally the most frequently used letter • “5” appears most frequently in cipher • Reasonable guess: “5” is the cipher for “E” Classwork: frequency analysis • Identifying shifting number of a Caesar cipher by frequency analysis instead of trial-and-error Ways of breaking codes • Frequency analysis • Example: frequencies for a Vigenere cipher • Key: BRADPITT • Cipher: Ways of breaking codes • Frequency analysis • Example: frequencies for a Vigenere cipher • Key: BRADPITT • Frequencies for cipher: are the numbers useful? Ways of breaking codes • Frequency analysis • Caesar cipher • Preserves frequencies • Easy to break with trial-and-error with the help of frequency analysis • The most frequent cipher letter is likely to represent E or A • Vigenere cipher • Does not preserve frequencies • Not easy to break even with frequency analysis Numbers on the Internet GCNU 1025 Numbers Save the Day Ways of breaking codes • Cryptogram • Common game in newspapers and magazines • Example: Ways of breaking codes • Cryptogram • Common game in newspapers and magazines • Example: • Step 1: frequency analysis (P likely to be cipher of E) Ways of breaking codes • Cryptogram • Common game in newspapers and magazines • Example: • Step 1: frequency analysis (P likely to be cipher of E) Ways of breaking codes • Cryptogram • Common game in newspapers and magazines • Example: • Step 2: look for particular patterns (such as “_EE_”) Ways of breaking codes • Cryptogram • Common game in newspapers and magazines • Example: • Step 3: look for short common words Ways of breaking codes • Cryptogram • Common game in newspapers and magazines • Example: Numbers on the Internet GCNU 1025 Numbers Save the Day Modular arithmetic • Example: letter shifting • 26 “=” 0, 27 “=” 1, 28 “=” 2, 45 “=” 19, 71 “=” 19, etc. • Key number: 26 • Do the numbers differ by a certain number of complete cycles? • Is the difference a multiple of 26? Modular arithmetic • Example: clock • 13 “=” 1, 15 “=” 3, 23 “=” 11, etc. • Key number: 12 • Do the numbers differ by a certain number of complete cycles? • Is the difference a multiple of 12? Modular arithmetic • Example: letter shifting • 26 0 (mod 26), 45 19 (mod 26), 71 • Congruence modulo 26: 19 (mod 26), etc. • Do the numbers differ by a certain number of complete cycles? • Is the difference a multiple of 26? Modular arithmetic • Example: clock • 13 1 (mod 12), 15 3 (mod 12), 23 • Congruence modulo 12: 11 (mod 12), etc. • Do the numbers differ by a certain number of complete cycles? • Is the difference a multiple of 12? Modular arithmetic • Example: 37 89 (mod 26)? YES • Reason: 89 – 37 = 52 is divisible by 26 • Example: 38 89 (mod 25)? NO • Reason: 89 – 38 = 51 is not divisible by 25 Modular arithmetic • Example: congruence modulo 3 • 1 • 2 • 3 4 5 6 7 8 9 10 … (mod 3) 11 … (mod 3) 12 … (mod 3) Modular arithmetic • Application in letter shifting • Example: Caesar cipher with shifting number 4 • 24 + 4 = 28 ≡ 2 (mod 26) Modular arithmetic • Application in letter shifting • Example: Caesar cipher with shifting number 17 Numbers on the Internet GCNU 1025 Numbers Save the Day Announcement • Mid-term test on Nov 7 (Friday) • 20% of final score • 1-hour • Coverage: up to Chapter 2 • Closed book • DO NOT use calculators in MOBILE PHONES! • DO NOT use electronic devices except calculators! • Past midterm paper: http://www.math.hkbu.edu.hk/~ajzhang/GCNU1025/Past_Midterm.pdf Modular arithmetic • Application in letter shifting • Why does the cycle begin with 0? • What is 64? • Answer: 12 • What is the remainder of 64 ÷ 26? • Answer: 12 Modular arithmetic • Application in letter shifting • Example: Caesar cipher (encryption) with shifting number 128 • Operation #1: adding 128 • A encrypted as Y • Operation #2: adding 24 • A encrypted as Y • 128 ≡ 24 (mod 26) Modular arithmetic • Application in letter shifting • Example: Caesar cipher (decryption) with shifting number 88 • Operation #1: subtracting by 88 • A decrypted as Q • Operation #2: subtracting by 10 • A encrypted as Q • 88 ≡ 10 (mod 26) Modular arithmetic • Properties: • Examples: • Shifting number of 128 same as shifting number of 24 • 0 + 128 ≡ 26 + 24 (mod 26) • Shifting number of 88 same as shifting number of 10 • 1 − 88 ≡ 27 − 10 (mod 26) Modular arithmetic • Properties: • Examples: • • • • 2 × 13 ≡ 2 × 25 (mod 12) 2 × 13 ≡ 26 × 25 (mod 12) 25 ≡ 145 (mod 12) 736 ≡ 5936 (mod 26) Numbers on the Internet GCNU 1025 Numbers Save the Day Modular arithmetic Modular arithmetic • Divisions and inverses in ordinary arithmetic • Division can be expressed as multiplication • Example: 6 ÷ 3 = 6 × • 3 and 1/3 are a pair 1 3 1 3 • Property: 3 × = 1 • Example: 8 ÷ 5 = 8 × • 5 and 1/5 are a pair 1 5 1 5 • Property: 5 × = 1 • Inverse of a number: a number with which the product is 1 • Example: inverse of 3 is 1/3 • Example: inverse of 1/5 is 5 Modular arithmetic • Definition of inverse • Example: is 3 an inverse of 9 modulo 26? YES • 3 × 9 = 27 • Is 27 congruent to 1 modulo 26? YES • Example: is 5 an inverse of 7 modulo 26? NO • 5 × 7 = 35 • 35 ≡ 1 (mod 26)? NO Modular arithmetic • Definition of inverse • Example: is 1 an inverse of 4 modulo 6? NO • 1×4 =4 • 4 ≡ 1 (mod 6)? NO • Example: is 2 an inverse of 4 modulo 6? NO • 2×4 =8 • 8 ≡ 1 (mod 6)? NO Modular arithmetic • Definition of inverse • Example: is 3 an inverse of 4 modulo 6? NO • 3 × 4 = 12 • 12 ≡ 1 (mod 6)? NO • Example: is 4 an inverse of 4 modulo 6? NO • 4 × 4 = 16 • 16 ≡ 1 (mod 6)? NO Modular arithmetic • Definition of inverse • Example: is 5 an inverse of 4 modulo 6? NO • 5 × 4 = 20 • 20 ≡ 1 (mod 6)? NO • Example: is 15 an inverse of 4 modulo 6? NO • 3 × 4 = 12 • 12 ≡ 1 (mod 6)? NO Modular arithmetic • Existence of inverse • Example: 4 has no inverse modulo 6 • Reason: 4 and 6 share 2 as a common factor Modular arithmetic • Existence of inverse • Example: 5 has an inverse modulo 6 • Reason: 5 and 6 share no common factor other than 1 Modular arithmetic • Existence of inverse • Example: 9 has an inverse modulo 26 • Reason: 9 and 26 share no common factor other than 1 Modular arithmetic • Existence of inverse • Example: 8 has no inverse modulo 26 • Reason: 8 and 26 share 2 as a common factor Numbers on the Internet GCNU 1025 Numbers Save the Day Modular arithmetic • Uniqueness (modulo ) of inverse • Example: 5 has an inverse modulo 6 • • • • • • Reason: 5 and 6 share no common factor other than 1 5 is an inverse of 5 since 5 × 5 = 25 ≡ 1 (mod 6) 11 is also an inverse of 5 since 11 × 5 = 55 ≡ 1 (mod 6) 17 is also an inverse of 5 since 17 × 5 = 85 ≡ 1 (mod 6) 5, 11 and 17 are all congruent modulo 6 One inverse only in the sense of modulo 6 Modular arithmetic • How to find an inverse? • Trial-and-error • Example: 5 has an inverse modulo 6 • • • • • • • Reason: 5 and 6 share no common factor other than 1 Candidates: 1, 2, 3, 4 and 5 1 is not an inverse of 5: 1 × 5 = 5 is not congruent to 1 (mod 6) 2 is not an inverse of 5: 2 × 5 = 10 is not congruent to 1 (mod 6) 3 is not an inverse of 5: 3 × 5 = 15 is not congruent to 1 (mod 6) 4 is not an inverse of 5: 4 × 5 = 20 is not congruent to 1 (mod 6) 5 is an inverse of 5: 5 × 5 = 25 ≡ 1 (mod 6) Modular arithmetic • How to find an inverse? • Euclidean algorithm • Example: inverse of 13 modulo 74 • Target: find an expression 13 + 74 = 1 so that 13 = 1 − 74 ≡ 1 (mod 74) and hence is an inverse of 13 modulo 74 • Step 1: divide 74 by 13 Modular arithmetic • How to find an inverse? • Euclidean algorithm • Example: inverse of 13 modulo 74 • Target: find an expression 13 + 74 = 1 so that 13 = 1 − 74 ≡ 1 (mod 74) and hence is an inverse of 13 modulo 74 • Step 1: divide 74 by 13 • Subsequent steps: divide the divisor of the previous division by the remainder of the previous division until the remainder is 1 Modular arithmetic • How to find an inverse? • Euclidean algorithm • Example: inverse of 13 modulo 74 • Target: find an expression 13 + 74 = 1 so that 13 = 1 − 74 ≡ 1 (mod 74) and hence is an inverse of 13 modulo 74 • Final step: inverse of 13 modulo 74 is -17 (or 57) Numbers on the Internet GCNU 1025 Numbers Save the Day Public-key & private-key cryptography • Private-key cryptography: same key used for encryption and decryption • • • • Example: Caesar cipher and Vigenere cipher Private key: secret between sender and receiver Symmetric: same key in encryption and decryption Potential risk: interception by third party during transfer of key Public-key & private-key cryptography • Private-key cryptography: same key used for encryption and decryption • • • • Example: Caesar cipher and Vigenere cipher Private key: secret between sender and receiver Symmetric: same key in encryption and decryption Potential drawback: high number of keys needed in a network Public-key & private-key cryptography • Public-key cryptography: different keys used for encryption and decryption • Analogy: padlock example • Open padlock made public • Sender uses open padlock (public key) to secure message • Receiver uses private key to unlock Public-key & private-key cryptography • Public-key cryptography: different keys used for encryption and decryption • Public key: known to public for encryption • Private key: known to receiver only for decryption • No potential risk of interception during key transfer RSA algorithm • Construction of a pair of public key and private key for public-key cryptography • Important ingredient for asymmetry: difficulty of factorization of large number into prime factors • Multiplying 2 big prime numbers to form large number: simple • Example: what is the product of 1009 and 9973? • Factorizing the product without knowing any of the primes: challenging • Example: how to factorize 10062757? • Tools: modular arithmetic and Euclidean algorithm RSA algorithm • Construction of a pair of public key and private key for public-key cryptography • Example: construction of a public key for others (for encryption) and a private key for yourself (for decryption) • Construction of public key • • • • • Choose two prime numbers (known to you only): p = 5 and q = 11 Product of the two primes (known to public): n = 55 Modulo (known to you only): m = (p – 1)(q – 1) = 4 x 10 = 40 Choose a number e (known to public) so that (e, m) = 1: e = 7 Public key: (n, e) = (55, 7) RSA algorithm • Construction of a pair of public key and private key for public-key cryptography • Example: construction of a public key for others (for encryption) and a private key for yourself (for decryption) • Construction of public key • Public key: (n, e) = (55, 7) • Modulo (known to you only): m = (p – 1)(q – 1) = 4 x 10 = 40 • Construction of private key • Inverse d of e modulo m (known to you only) via Euclidean algorithm: inverse of 7 modulo 40 is 23 • Private key: (n, d) = (55, 23) RSA algorithm • Example (cont’): how to use the public key for encryption? • Public key: (n, e) = (55, 7) • Message: “OK” • Step 1: convert message into numbers according to a rule • “OK” converted into “14 10” • Step 2: encryption by raising to the power of e modulo n • “14 10” encrypted as “9 10” RSA algorithm • Example (cont’): how to use the private key for decryption? • Private key: (n, d) = (55, 23) • Received message: “9 10” • Step 1: decryption by raising to the power of d modulo n • “9 10” decrypted as “14 10” • Step 2: convert numbers back into message • “14 10” converted back into “OK” RSA algorithm • Padlock analogy revisited • Open padlock (public key: (55, 7)) made public • Sender uses open padlock (public key: (55, 7)) to secure message • Receiver uses private key (55, 23) to unlock RSA algorithm • Example revisited: construction of a public key for others (for encryption) and a private key for yourself (for decryption) • Construction of public key • • • • • Choose two prime numbers (known to you only): p = 5 and q = 11 Product of the two primes (known to public): n = 55 Modulo (known to you only): m = (p – 1)(q – 1) = 4 x 10 = 40 Choose a number e (known to public) so that (e, m) = 1: e = 7 Public key: (n, e) = (55, 7) • Construction of private key • Inverse d of e modulo m (known to you only) via Euclidean algorithm: inverse of 7 modulo 40 is 23 • Private key: (n, d) = (55, 23) • Security loophole: 55 is too easy to factorize! RSA algorithm • Example revisited: construction of a public key for others (for encryption) and a private key for yourself (for decryption) • Public key: (n, e) = (55, 7) • Private key: (n, d) = (55, 23) • Security loophole: 55 is too easy to factorize! • Real-life example: very big n used for security reason Announcement • Assignment No.3: next week • Coverage: Chapter 3 Numbers on the Internet -End-