Report

PUBLIC KEY CRYPTOGRAPHY ALGORITHM Concept and Example 1 IT352 | Network Security |Najwa AlGhamdi RSA 1. It’s a block cipher algorithm. 2. Plain text and cipher text are integer between 0 to n-1 for some n. 3. RSA algorithm involve the following operations 1. Key Generation. 2. Encryption/Decryption 2 IT352 | Network Security |Najwa AlGhamdi RSA - Key Generation • Each user generates a public/private key pair by: 1. selecting two large primes at random: p, q & p<> q 2. computing their system modulus n=p.q 3. Calculate ø(n)=(p-1)(q-1) والقاسمn عدد األرقام الموجبة التي اقل منø(n) is Euler Totient : . 1 المشترك بينها هو 4. selecting at random the encryption key e – where 1<e<ø(n), gcd(e,ø(n))=1 5. solve following equation to find decryption key d – e.d mod ø(n) = 1 and 0≤d≤n 6. publish their public encryption key: PU={e,n} 7. keep secret private decryption key: PR={d,n} 3 IT352 | Network Security |Najwa AlGhamdi – RSA – Encryption/ Decryption • to encrypt a message M the sender: – obtains public key of recipient PU={e,n} – computes: C = Me mod n, where 0≤M<n • to decrypt the ciphertext C the owner: – uses their private key PR={d,n} – computes: M = Cd mod n • Both Sender and Receiver know the value of n, e. • Only receiver knows d. 4 IT352 | Network Security |Najwa AlGhamdi Example • Plain Text =88; Steps 5 Values 1. Select two prime numbers p=17 , q = 11 2. Calculate n = pq N = 17 ×11 = 187 3. Calculate ø(n)=(p-1)(q-1) ø(n)= 16 × 10 = 160 4. Select e such that e is relatively prime to ø(n) = 160 e= 7 5. Determine d such that de mod 160 = 1 d = 23 , because 27 ×7 = 161 = ( 1×160) +1 Public key {7, 187} Private Key {23, 187} IT352 | Network Security |Najwa AlGhamdi Example • Plain Text =88; sample RSA encryption/decryption is: given message M = 88 (nb. 88<187) encryption: C = 887 mod 187 = 11 decryption: M = 1123 mod 187 = 88 6 IT352 | Network Security |Najwa AlGhamdi 1. Diffie-Hellman Key Exchange • The purpose is to share a secrete key securely and use it in the encryption. • Diffie- Hellman is using discrete logarithm • 7 IT352 | Network Security |Najwa AlGhamdi 1. Diffie-Hellman Key Exchange: Discrete Logarithm • Primitive root of a prime number p is a number whose power generate all integers from 1 to p-1 . • Example : p = 7 , then a = 3 Power – A mod p , a^2 mod p , a ^3 mod p .. Contain all numbers from 1 to p-1 0 3^0 mod 7 = 1 1 3^ 1 mod 7 = 3 2 3^2 mod 7 = 2 3 3^3 mod 7 = 6 4 3^4 mod 7 = 4 5 3^5 mod 7 = 5 …… 8 IT352 | Network Security |Najwa AlGhamdi Number 2. Diffie Hellman Setup 1. all users agree on global parameters: – large prime integer q – a being a primitive root mod q 2. each user generates their key – User A • chooses a secret key (number): xA < q xA • compute their public key: yA = a mod q – User B • chooses a secret key (number): xB < q xB • compute their public key: yB = a mod q 9 IT352 | Network Security |Najwa AlGhamdi 2. Diffie Hellman Setup 3. Generation of Secret Key xA User A : K = (yB) mod q xB User B : K = (yA) mod q 10 IT352 | Network Security |Najwa AlGhamdi 2. Diffie Hellman Key Exchange • shared session key for users A & B is KAB: xB KAB = yA mod q (which B can compute) xA = yB mod q (which A can compute) • KAB is used as session key in private-key encryption scheme between Alice and Bob • if Alice and Bob subsequently communicate, they will have the same key as before, unless they choose new public-keys y A A B yB 11 IT352 | Network Security |Najwa AlGhamdi Man in the Middle Attack 1. 2. 3. 4. 5. 6. 7. 12 Darth prepares by creating two private / public keys Alice transmits her public key to Bob Darth intercepts this and transmits his first public key to Bob. Darth also calculates a shared key with Alice Bob receives the public key and calculates the shared key (with Darth instead of Alice) Bob transmits his public key to Alice Darth intercepts this and transmits his second public key to Alice. Darth calculates a shared key with Bob Alice receives the key and calculates the shared key (with Darth instead of Bob) Darth can then intercept, decrypt, re-encrypt, forward all messages between Alice & Bob IT352 | Network Security |Najwa AlGhamdi