Introduction to Computer Security and Number Theory
Explore the fundamental concepts of computer security, public key encryption, RSA encryption, and modular arithmetic in number theory. Understand properties of the modulo operator and learn how modular arithmetic exhibits specific mathematical properties.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
COMPUTER SECURITY COMPUTER SECURITY UNIT UNIT- -5: BASE NUMBER THEORY, PUBLIC KEY 5: BASE NUMBER THEORY, PUBLIC KEY ENCRYPTION,RSA ENCRYPTION,RSA 1
INTRODUCTION TO NUMBER THEORY INTRODUCTION TO NUMBER THEORY Modular Arithmetic Given any positive integer n and any integer a, if we divide a by n, we get an integer quotient q and an integer remainder r that obey the following relationship: a = qn + r Example: a = 11; n = 7; 11 = 1 * 7 + 4; r = 4 a = -11; n = 7; -11 = (-2) * 7 + 3; r = 3 2
INTRODUCTION TO NUMBER THEORY INTRODUCTION TO NUMBER THEORY Two integers a and b are said to be congruent modulo n, if (a mod n) = (b mod n) This is written as a b mod n Example: a = 23, b = 8, n = 5 23 mod 5 = 8 mod 5 We can write for the formula 23 8 mod 5 3
Properties of the Modulo Operator Properties of the Modulo Operator The modulo operator have the following properties: a b mod n if n| (a-b). a b mod n implies b a mod n. a b mod n and b c mod n imply a c mod n. Example: a b mod n if n|a-b 23 8 mod 5 (23-8)/5 = 15/5 = 3 a b mod n if (a-b/n) a mod n b mod n 4
Example: 23 8 mod 5 if (23-8)/5 23 mod 5 8 mod 5 if 15/5 3 3 3 Example 2: a b mod n implies b a mod n a mod n b mod n a mod n b b a mod n 5
Modular arithmetic exhibits the following properties: Modular arithmetic exhibits the following properties: 1. [(a mod n) + (b mod n)] mod n = (a + b) mod n 2. [(a mod n) - (b mod n)] mod n = (a - b) mod n 3. [(a mod n) * (b mod n)] mod n = (a * b) mod n Examples of the three properties: Ex: 11 mod 8 = 3; 15 mod 8 = 7 1. [(11 mod 8) + (15 mod 8)] mod 8 = (11 + 15) mod 8 2. [(11 mod 8) (15 mod 8)] mod 8 = (11 15) mod 8 3. [(11 mod 8) (15 mod 8)] mod 8 = (11 15) mod 8 6
we demonstrate the first property. Define (a mod n) = ra and (b mod n) = rb. Then we can write a = ra + jn for some integer j and b = rb + kn for some integer k. Then (a + b) mod n = (ra + jn + rb + kn) mod n = (ra + rb + (k + j)n) mod n = (ra + rb) mod n = [(a mod n) + (b mod n)] mod n 7
Define the set Zn as the set of nonnegative integers less than n: Zn= {0, 1 (n-1)} This is referred to as the set of residues, or residue classes modulo n. to be more precise, each integer in Zn represents a residue class. However, if we take a = 5 and n = 8, whose only common factor is 1, Z8 0 1 2 3 4 5 6 7 Multiply by 5 0 5 10 15 20 25 30 35 Residues 0 5 2 7 4 1 6 3 The line of residues contains all the integers in Z8, in a different order. 8
Euclids Algorithm One of the basic techniques of number theory is Euclid s algorithm, which is a simple procedure for determining the greatest common divisor of two positive integers. Greatest Common Divisor We will use the notation gcd(a,b) to mean the greatest common divisor of a and b. Definition is the following: gcd(a, b) = max[k, such that k|a and k|b] gcd(60,24) = 12 9
also, because all nonzero integers divide 0, we have gcd(a, 0) = |a|. we stated that two integers a and b are relatively prime if their only common positive integer factor is 1. This is equivalent to saying that a and b are relatively prime if gcd(a, b) = 1. 10
8 and 15 are Relatively Prime because the positive divisors of 8 are 1, 2, 4, and 8, and the positive divisors of 15 are 1, 3, 5, and 15, so 1 is the only integer on both lists. 11
Finding the Greatest Common Divisor ( GCD ) Euclid s algorithm is based on the following theorem: for any nonnegative integer a and any positive integer b, gcd(a, b) = gcd(b, a mod b) -------- (1) gcd(55, 22) = gcd(22, 55 mod 22) = gcd(22,11) = 11 Euclid s algorithm made repeated use of Equation (1) to determine the greatest common divisor, as follows. The algorithm assumes a > b > 0. It is acceptable to restrict the algorithm to positive integers because gcd(a, b) = gcd(|a|, |b|). 12
EUCLID(a, b) A a; B b 1. 2. if B = 0 return a 3. R = A mod B A B B R 4. 5. 6. goto step 2 13
It is easy to determine the greatest common divisor of two positive integers if we express each integer as the product of power of primes. 300 = 22 * 31 * 52 18 = 21 * 32 gcd(18, 300) = 21 * 31 * 50 = 6 14
Two theorems that play important roles in public Two theorems that play important roles in public- -key cryptography are are Fermat s theorem and Euler s theorem. Fermat s theorem and Euler s theorem. key cryptography 1. Fermat s Theorem Fermat s theorem states the following: If p is prime and a is a positive integer not divisible by p, then ap-1 1 mod p . (1) 15
Proof: From the above, we know that if all of the elements of Zp, where Zpis the set of integers {0, 1 p-1}, are multiplied by a, modulo p, the result consists of all of the elements of Zp in some sequence. Then {a mod p, 2a mod p, 3a mod p, , (p-1)a mod p} = {1, 2 p-1} (in some order) multiplying the numbers in both sets (a mod p) * (2a mod p) * *((p-1) a mod p) = 1*2*3* * (p-1) taking mod p on both sides [ (a mod p) * (2a mod p) * *((p-1) a mod p)] mod p = [1*2*3* * (p-1)] mod p 16
now from the rule [(a mod p) * (b mod p)] mod p = (a * b) mod p we can write it as [a*2a*3a* *(p-1)a] mod p = [1*2* *(p-1)] mod p ap-1 (p-1)! (p-1)! mod p ap-1 1 mod p ap-1 1 mod p [we can cancel (p-1)! on both sides according to the formula if a * b a*c mod n then b c mod n if a is relatively prime to n.] An alternative form of the theorem is also useful: if p is prime and a is any positive integer then ap a mod p 17
ap a mod p P = 5, a = 3, 35= 243 3 mod 5 P = 5, a = 10, 105= 100000 10 mod 5 0 mod 5 Example: a = 7, p = 19 72= 49 11 mod 19 74 = 72 * 72= 49 * 49 11 mod 19 * 11 mod 19 78 = 74 * 74 7 mod 19 * 7 mod 19 716 = 78 * 78 11 mod 19 * 11 mod 19 718 = 716 * 72 7 mod 19 * 11 mod 19 [try to write it in mod 19 format] 11 * 11 mod 19 121 mod 19 7 mod 19 [from formula] 49 mod 19 11 mod 19 11 *11 mod 19 121 mod 19 7 mod 19 7 * 11 mod 19 77 mod 19 1 mod 19 718 1 mod 19 ap-1 1 mod p 18
Eulers Totient Function Calculate relatively prime numbers below the given number. n-number, (n) Relatively primes below the n. If n is a prime number, (n) = n-1. If n is not a prime number (n) = (pq) [here p, q are prime numbers] (n) = (p-1) * (q-1) Determine (37) and Because 37 is prime all of the +veintegers from 1 to 36 are relatively prime to 37. Thus (37) = 36. 19
To determine (35), we list all of the positive integers less than 35 that are relatively prime to it. 1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34. There are 24 numbers on the list, so (35) = 24. Example: (21) = (3-1) * (7-1) = 2 * 6 = 12 Where the 12 integers are {1, 2, 4, 5,8,10, 11, 13, 16, 17, 19, 20} 20
2 Eulers theorem Euler s theorem states that for every a and n that are relatively prime: a (n) 1 mod n 21
Eulers theorem states that for every a and n that are relatively prime: a (n) 1 mod n Proof: The above equation is true if n is prime, because in that case (n) = n-1 and Fermat s theorem holds. however, it also holds for any integer n. Recall that (n) is the number of +ve integers less than n that are relatively prime to n. Consider the set of such integers, labeled as follows: R = { x1, x2, } 22
now multiply each element by a, modulo n: S = { (ax1 mod n), (ax2 mod n), (a mod n) } = { x1, x2, } (in some order) because a is relatively prime to n and xi is relatively prime to n. so, axi must also be relatively prime to n. Thus all the members of S are integers less than n that are relatively prime to n. Multiply both the set elements and take mod n then [(ax1 mod n)*(ax2 mod n)* *a mod n)] mod n = [ x1* x2* * ] mod n [ax1*ax2* *a ] mod n = [x1* x2* * ] mod n [ax1*ax2* *a ] [x1* x2* * ] mod n a (n) 1 mod n. 23
Example: a = 3; n = 10; a (n) 1 mod n. 34= 81 1 mod 10 [here (10) = 4] n = 11 (n) = (11-1) = 10 (2) a = 2 210= 1024 1 mod 11 24
The briefcase example Alice Bob 1 2 3 4 5 26
The briefcase example Properties: 1. There is only one key for each padlock 2. The padlocks are so strong that they cannot be removed by force Problems: 3. You have no way of being sure that it is the correct person who finally gets your message 4. The briefcase has to be sent back and forward three times, which seems pretty inefficient. 27
Desirable properties Use the properties and problems for the briefcase example to come up with a specification of four properties that are desirable for any cipher system that is to be used between two entities who do not already share a symmetric key. 28
Public key blueprint The keys used to encrypt and decrypt are different. Anyone who wants to be a receiver needs to publish an encryption key, which is known as the public key. Anyone who wants to be a receiver needs a unique decryption key, which is known as the private key. It should not be possible to deduce the plaintext from knowledge of the ciphertext and the public key. Some guarantee needs to be offered of the authenticity of a public key. 29
Example A popular implementation of public-key encryption is the Secure Sockets Layer (SSL). Originally developed by Netscape, SSL is an Internet security protocol used by Internet browsers and Web servers to transmit sensitive information. SSL has become part of an overall security protocol known as Transport Layer Security (TLS). In your browser, you can tell when you are using a secure protocol, such as TLS, in a couple of different ways. You will notice that the "http" in the address line is replaced with "https," and you should see a small padlock in the status bar at the bottom of the browser window. When you're accessing sensitive information, such as an online bank account or a payment transfer service like PayPal or Google Checkout, chances are you'll see this type of format change and know your information will most likely pass along securely. TLS and its predecessor SSL make significant use of certificate authorities. Once your browser requests a secure page and adds the "s" onto "http," the browser sends out the public key and the certificate, checking three things: 1) that the certificate comes from a trusted party; 2) that the certificate is currently valid; and 3) that the certificate has a relationship with the site from which it's coming. 30
The browser then uses the public key to encrypt a randomly selected symmetric key. Public-key encryption takes a lot of computing, so most systems use a combination of public-key and symmetric key encryption. When two computers initiate a secure session, one computer creates a symmetric key and sends it to the other computer using public-key encryption. The two computers can then communicate using symmetric- key encryption. Once the session is finished, each computer discards the symmetric key used for that session. Any additional sessions require that a new symmetric key be created, and the process is repeated. 31
Design of a public key algorithm In a public key system, if everyone knows everything necessary: the encryption algorithm and the encryption key to determine the ciphertext then how is it possible that they cannot then work out what the plaintext (decryption key) is from this information? 32
One way functions A one-way function is a function that is easy to compute and difficult to reverse. How might we express this notion of a one way function informally in complexity theoretic terms? 33
OWF: Multiplying two primes It is easy to take two prime numbers and multiply them together. If they are fairly small we can do this in our heads, on a piece of paper, or on a calculator. As they get bigger and bigger it is fairly easy to write a computer program to compute the product. Multiplication runs in polynomial time. Multiplication of two primes is easy. 34
OWF: Multiplying two primes Multiplication of two prime numbers is believedto be a one-way function. We say believedbecause nobody has been able to provethat it is hard to factorise. Maybe one day someone will find a way of factorising efficiently. 35
OWF: Modular exponentiation The process of exponentiation just means raising numbers to a power. Raising a to the power b, normally denoted ab just means multiplying a by itself b times. In other words: ab = a x a x ax x a Modular exponentiation means computing ab modulo some other number n. We tend to write this as ab mod n. Modular exponentiation is easy . 36
OWF: Modular exponentiation However, given a, b, and abmod n (when n is prime), calculating b is regarded by mathematicians as a hard problem. This difficult problem is often referred to as the discrete logarithm problem. In other words, given a number a and a prime number n, the function f(b) = ab mod n is believed to be a one-way function. 37
Suitable OWFs We have seen that the encryption process of a public key cipher system requires a one way function. 38
RSA 39
RSA The RSA public key encryption algorithm was the first practical implementation of public key encryption discovered. It remains the most used public key encryption algorithm today. It is named after the three researchers Ron Rivest, Adi Shamir and Len Adleman who first published it. Make sure you are familiar with the concepts of modular arithmetic, prime numbers, the Euclidean Algorithm and the method of Repeated Squares. 40
Setting up RSA Let n be the product of two large primes p and q By large we typically mean at least 512 bits. Select a special number e greater than 1 and less than (p-1)(q-1). The precise mathematical property that e must have is that there must be no numbers that divide neatly into e and into (p-1)(q-1), except for 1. Publish the pair of numbers (n,e) Compute the private key d from p, q and e 41
Computing the private key The private key d is computed to be the unique inverse of e modulo (p-1)(q-1). In other words, d is the unique number less than (p-1)(q-1) that when multiplied by e gives you 1 modulo (p-1)(q-1). Written mathematically: ed = 1 mod (p-1)(q-1) The Euclidean Algorithm is the process that you need to follow in order to compute d. 42
Computing the private key 1. Who is capable of running the Euclidean Algorithm to find the private key? 2. How efficient is this process? 43
Choosing e Let s consider p=3 and q=7. What choices of e are acceptable? In this case (p-1)(q-1) = 2 x 6 = 12. Any suitable choice of e must have the property that there are no numbers that neatly divide into e and 12 except for 1. Let s just try them all out: e=2: this is no good, since 2 divides both e and 12. In fact this will be true for all multiples of 2 as well, so e=4, e=6, e=8 and e=10 are also not possible. e=3: this is no good, since 3 divides both e and 12. In fact this will be true for all multiples of 3 as well, so e=6 and e=9 are also not possible. The remaining choices are e=5, e=7 and e=11. Since in each case there is no number that divides into them and 12 other than 1, all these choices of e are possible. 44
Setting up RSA: example Step 1: Let p = 47 and q = 59. Thus n = 47 x 59 = 2773 Step 2: Select e = 17 Step 3: Publish (n,e) = (2773, 17) Step 4: (p-1) x (q-1) = 46 x 58 = 2668 Use the Euclidean Algorithm to compute the modular 2668. The result is d = 157 << Check: 17 x 157 = 2669 = 1(mod 2668) >> inverse of 17 modulo Public key is Private key is 157 (2773,17) 45
Encryption and decryption The first job is to represent the plaintext as a series of numbers modulo n. The encryption process to obtain the ciphertext C from plaintext M is very simple: C = Me mod n The decryption process is also simple: M = Cd mod n 46
Encryption and decryption: example Public key is Private key is 157 (2773,17) Plaintext block represented as a number: M = 31 Encryption using Public Key: C = 3117 (mod 2773) = 587 Decryption using Private Key: M = 587157 (mod 2773) = 31 47
Choose an integer e < n that is relatively prime to f(n). Find a second integer d such that ed mod f(n) = 1. The public key is (e, n), and the private key is d. Let m be a message. Then: c = me mod n and m = cd mod n 48
Example - RSA Let p = 7 and q = 11. Then n = 77 and f(n) = 60. Alice chooses e = 17, so her private key is d = 53. In this cryptosystem, each plaintext character is represented by a number between 00 (A) and 25 (Z); 26 represents a blank. Bob wants to send Alice the message "HELLO WORLD." Using the representation above, the plaintext is 07 04 11 11 14 26 22 14 17 11 03. Using Alice's public key, the ciphertext is 0717 mod 77 = 28 0417 mod 77 = 16 1117 mod 77 = 44 ... 0317 mod 77 = 75 or 28 16 44 44 42 38 22 42 19 44 75. In addition to confidentiality, RSA can provide data and origin authentication. If Alice enciphers her message using her private key, anyone can read it, but if anyone alters it, the (altered) ciphertext cannot be deciphered correctly. 49
Example Suppose Alice wishes to send Bob the message "HELLO WORLD" in such a way that Bob will be sure that Alice sent it. She enciphers the message with her private key and sends it to Bob. As indicated above, the plaintext is represented as 07 04 11 11 14 26 22 14 17 11 03. Using Alice's private key, the ciphertext is 0753 mod 77 = 35 0453 mod 77 = 09 1153 mod 77 = 44 ... 0353 mod 77 = 05 or 35 09 44 44 93 12 24 94 04 05. In addition to origin authenticity, Bob can be sure that no letters were altered. Providing both confidentiality and authentication requires enciphering with the sender's private key and the recipient's public key. 50
