Cryptography and applications

ggggggggggggggggggggggggggggggg

1. Cryptography and Applications Pham Van Hau ( [email protected] ) School of computer science and engineering-international university

2. The History of Cryptography Cryptography has roots that begin around 2000 B.C. in Egypt used to decorate tombs to tell the life story of the deceased not so much about hiding the messages themselves ; rather, the hieroglyphics were intended to make the life story seem more noble, ceremonial , and majestic

3. Some Basic Terminology plaintext - original message ciphertext - coded message cipher - algorithm for transforming plaintext to ciphertext key - info used in cipher known only to sender/receiver encipher (encrypt) - converting plaintext to ciphertext decipher (decrypt) - recovering ciphertext from plaintext cryptography - study of encryption principles/methods cryptanalysis ( codebreaking ) - study of principles/ methods of deciphering ciphertext without knowing key cryptology - field of both cryptography and cryptanalysis 3

4. Classical Substitution Ciphers where letters of plaintext are replaced by other letters or by numbers or symbols or if plaintext is viewed as a sequence of bits, then substitution involves replacing plaintext bit patterns with ciphertext bit patterns 4

5. Caesar Cipher earliest known substitution cipher by Julius Caesar first attested use in military affairs replaces each letter by 3rd letter on a b c d e f g h i j k l m n o p q r s t u v w x y z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C example: meet me after the toga party PHHW PH DIWHU WKH WRJD SDUWB 5

6. Caesar Cipher mathematically give each letter a number a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 then have Caesar cipher as: c = E( p ) = ( p + k ) mod (26) p = D(c) = (c – k ) mod (26) 6

7. Cryptanalysis of Caesar Cipher only have 26 possible ciphers A maps to A,B,..Z could simply try each in turn given ciphertext, just try all shifts of letters do need to recognize when have plaintext eg. break ciphertext "GCUA VQ DTGCM" 7

8. More substitution ciphers Mono-alphabetic Cipher Playfair Cipher Polyalphabetic Cipher Vigenère Cipher Autokey Cipher One Time Pad

9. Monoalphabetic Cipher rather than just shifting the alphabet could shuffle (jumble) the letters arbitrarily each plaintext letter maps to a different random ciphertext letter hence key is 26 letters long Plain: abcdefghijklmnopqrstuvwxyz Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext: ifwewishtoreplaceletters Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA 9

10. Monoalphabetic Cipher Security now have a total of 26! = 4 x 1026 keys with so many keys, might think is secure but would be !!!WRONG!!! problem is language characteristics 10

11. The Strength of the Cryptosystem The strength (work factor ): an estimate of the effort and resources it would take an attacker to penetrate a cryptosystem strength of an encryption method comes from the algorithm, the secrecy of the key , the length of the key, the initialization vectors, how they all work together within the cryptosystem

12. Cryptanalysis letters are not equally commonly used in English E is by far the most common letter followed by T,R,N,I,O,A,S other letters like Z,J,K,Q,X are fairly rare have tables of single, double & triple letter frequencies for various languages 12

13. English Letter Frequencies 13

14. Use in Cryptanalysis key concept - monoalphabetic substitution ciphers do not change relative letter frequencies discovered by Arabian scientists in 9 th century calculate letter frequencies for ciphertext compare counts/plots against known values if caesar cipher look for common peaks/troughs peaks at: A-E-I triple, NO pair, RST triple troughs at: JK, X-Z for monoalphabetic must identify each letter tables of common double/triple letters help 14

15. Example Cryptanalysis given ciphertext: UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ count relative letter frequencies (see text) guess P & Z are e and t guess ZW is th and hence ZWP is the proceeding with trial and error finally get: it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow 15

16. Playfair Cipher not even the large number of keys in a monoalphabetic cipher provides security one approach to improving security was to encrypt multiple letters the Playfair Cipher is an example invented by Charles Wheatstone in 1854, but named after his friend Baron Playfair 16

17. Playfair Key Matrix a 5X5 matrix of letters based on a keyword fill in letters of keyword (sans duplicates) fill rest of matrix with other letters eg. using the keyword MONARCHY 17 Z X W V U T S Q P L K I/J G F E D B Y H C R A N O M

18. Encrypting and Decrypting plaintext is encrypted two letters at a time if a pair is a repeated letter, insert filler like 'X’ if both letters fall in the same row, replace each with letter to right (wrapping back to start from end) if both letters fall in the same column, replace each with the letter below it (again wrapping to top from bottom) otherwise each letter is replaced by the letter in the same row and in the column of the other letter of the pair 18

19. Example Encryption of the “Hello world” message Step 1: split into two letter tokken: Hello world= he ll ow or ld Step 2: Encrypt each two letter tokken 19

20. Security of Playfair Cipher security much improved over monoalphabetic since have 26 x 26 = 676 digrams would need a 676 entry frequency table to analyse (verses 26 for a monoalphabetic) and correspondingly more ciphertext was widely used for many years eg. by US & British military in WW1 it can be broken, given a few hundred letters since still has much of plaintext structure 20

21. Polyalphabetic Ciphers polyalphabetic substitution ciphers improve security using multiple cipher alphabets make cryptanalysis harder with more alphabets to guess and flatter frequency distribution use a key to select which alphabet is used for each letter of the message use each alphabet in turn repeat from start after end of key is reached 21

22. Vigenère Cipher simplest polyalphabetic substitution cipher effectively multiple caesar ciphers key is multiple letters long K = k 1 k 2 ... k d i th letter specifies i th alphabet to use use each alphabet in turn repeat from start after d letters in message decryption simply works in reverse 22

23. Example of Vigenère Cipher write the plaintext out write the keyword repeated above it use each key letter as a caesar cipher key encrypt the corresponding plaintext letter eg using keyword deceptive key: deceptivedeceptivedeceptive plaintext: wearediscoveredsaveyourself ciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ 23

24. Security of Vigenère Ciphers have multiple ciphertext letters for each plaintext letter hence letter frequencies are obscured but not totally lost start with letter frequencies see if look monoalphabetic or not if not, then need to determine number of alphabets, since then can attach each 24

25. Kasiski Method method developed by Babbage / Kasiski repetitions in ciphertext give clues to period so find same plaintext an exact period apart which results in the same ciphertext of course, could also be random fluke eg repeated “VTW” in previous example suggests size of 3 or 9 then attack each monoalphabetic cipher individually using same techniques as before 25

26. Autokey Cipher ideally want a key as long as the message Vigenère proposed the autokey cipher with keyword is prefixed to message as key knowing keyword can recover the first few letters use these in turn on the rest of the message but still have frequency characteristics to attack eg. given key deceptive key: deceptivewearediscoveredsav plaintext: wearediscoveredsaveyourself ciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA 26

27. One-Time Pad if a truly random key as long as the message is used, the cipher will be secure called a One-Time pad is unbreakable since ciphertext bears no statistical relationship to the plaintext since for any plaintext & any ciphertext there exists a key mapping one to other can only use the key once though problems in generation & safe distribution of key 27

28. Transposition Ciphers now consider classical transposition or permutation ciphers these hide the message by rearranging the letter order without altering the actual letters used can recognise these since have the same frequency distribution as the original text 28

29. Rail Fence cipher write message letters out diagonally over a number of rows then read off cipher row by row eg. write message out as: m e m a t r h t g p r y e t e f e t e o a a t giving ciphertext MEMATRHTGPRYETEFETEOAAT 29

30. Row Transposition Ciphers a more complex transposition write letters of message out in rows over a specified number of columns then reorder the columns according to some key before reading off the rows Key: 4 3 1 2 5 6 7 Plaintext: a t t a c k p o s t p o n e d u n t i l t w o a m x y z Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ 30

31. scytale cipher Around 400 B.C., the Spartans would write a message on a sheet of papyrus (a type of paper) that was wrapped around a staff (a stick or wooden rod), which was then delivered and wrapped around a different staff by the recipient. The message was only readable if it was wrapped around the correct size staff, which made the letters properly match up

32. Enigma Code Machine http://www.youtube.com/watch?v=Hb44bGY2KdU

33. Product Ciphers ciphers using substitutions or transpositions are not secure because of language characteristics hence consider using several ciphers in succession to make harder, but: two substitutions make a more complex substitution two transpositions make more complex transposition but a substitution followed by a transposition makes a new much harder cipher this is bridge from classical to modern ciphers 33

34. Symmetric Cryptography

35. Block and Stream Ciphers block ciphers work on blocks of bits stream ciphers, which work on one bit at a time

36. Initialization Vectors R andom values that are used with algorithms to ensure patterns are not created during the encryption process. (If IVs are not used, then two identical plaintext values that are encrypted with the same key will create the same ciphertext . ) They are used with keys Do not need to be encrypted when being sent to the destination.

37. Key Distribution given parties A and B have various key distribution alternatives: A can select key and physically deliver to B third party can select & deliver key to A & B if A & B have communicated previously can use previous key to encrypt a new key if A & B have secure communications with a third party C, C can relay key between A & B

38. Strengths and Weaknesses Strengths Much faster (less computationally intensive) than asymmetric systems. Hard to break if using a large key size. Weaknesses Requires a secure mechanism to deliver keys properly. Each pair of users needs a unique key, so as the number of individuals increases , so does the number of keys, possibly making key management overwhelming . Provides confidentiality but not authenticity or nonrepudiation

39. Types of Symmetric Systems Data Encryption Standard (DES) 3DES (Triple DES) Blowfish Twofish IDEA (International Data Encryption Algorithm) RC4 , RC5, RC6 AES (Advanced Encryption Standard) SAFER (Secure and Fast Encryption Routine) Serpent

40. Asymmetric Cryptography

41. RSA by Rivest , Shamir & Adleman of MIT in 1977 best known & widely used public-key scheme based on exponentiation in a finite (Galois) field over integers modulo a prime nb . exponentiation takes O((log n) 3 ) operations (easy) uses large integers ( eg . 1024 bits) ‏ security due to cost of factoring large numbers nb . factorization takes O(e log n log log n ) operations (hard)

42. Ideas... Given a big number n, a message M (that is converted to integer value), if we can choose e and d that satisfy the following conditions: C=M e mod n for all M<n M= C d mod n=M ed mod n or M ed ≡ M mod n (denote M ed conguence M modulo n) It is infeasible to dermine d given e and n.

43. How RSA Works Given two primes p, q, and two integers m, n, such that n= p.q and 0<m<n, an arbitrary integer k. Because of Euler's Theorem: m ø (n)*k+1 ≡ m mod n (1) in which, the totient ø(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n. ø(9)=6 since the six numbers 1, 2, 4, 5, 7 and 8 are coprime to 9 We can have m ed ≡ m mod n, if ed =ø(n)*k+1 or ed ≡ 1 mod ø(n) according to rules of modular arithmetic, this happens only if e (and therefore d) is relative prime to ø(n). Or gcd (ø(n),e)=1 Since p, q are two primes, we have ø(n)=(p-1)(q-1), it is easy to have e, and d

44. RSA Key Setup each user generates a public/private key pair by: selecting two large primes at random - p, q computing their system modulus n= p.q note ø(n)=(p-1)(q-1) selecting at random the encryption key e where 1< e<ø(n), gcd ( e,ø (n))=1 solve following equation to find decryption key d e.d ≡ 1 mod ø(n) and 0 ≤ d ≤ n publish their public encryption key: PU={ e,n } keep secret private decryption key: PR={ d,n }

45. RSA Use to encrypt a message M the sender: obtains public key of recipient PU={ e,n } computes: C = M e mod n , where ≤ M < n to decrypt the ciphertext C the owner: uses their private key PR={ d,n } computes: M = C d mod n note that the message M must be smaller than the modulus n (block if needed) ‏

46. RSA Example - Key Setup Select primes: p =17 & q =11 Compute n = pq =17 x 11=187 Compute ø( n )=( p– 1)( q- 1)=16 x 10=160 Select e : gcd (e,160)=1; choose e =7 Determine d : de ≡ 1 mod 160 and d < 160 Value is d=23 since 23 x 7=161= 10 x 160+1 Publish public key PU={7,187} Keep secret private key PR={23, 187}

47. RSA Example - En/Decryption sample RSA encryption/decryption is: given message M = 88 ( nb . 88<187 ) ‏ encryption: C = 88 7 mod 187 = 11 decryption: M = 11 23 mod 187 = 88

48. RSA Security possible approaches to attacking RSA are: brute force key search (infeasible given big size of keys) ‏ mathematical attacks (based on difficulty of computing ø(n), by factoring modulus n) ‏ timing attacks (on running of decryption) ‏

49. Factoring Problem mathematical approach takes 3 forms: factor n= p.q , hence compute ø(n) and then d determine ø(n) directly and compute d find d directly currently believe all equivalent to factoring Cryptanalysis have seen slow improvements over the years currently assume 1024-2048 bit RSA is secure ensure p, q of similar size and matching other constraints

50. Timing Attacks developed by Paul Kocher in mid-1990’s exploit timing variations in operations eg . multiplying by small vs large number or IF's varying which instructions executed infer operand size based on time taken RSA exploits time taken in exponentiation countermeasures use constant exponentiation time add random delays blind values used in calculations

51. Strengths and Weaknesses Strengths Better key distribution than symmetric systems Better scalability than symmetric systems Can provide authentication and nonrepudiation Weaknesses Works much more slowly than symmetric systems Mathematically intensive tasks

52. Key Management public-key encryption helps address key distribution problems have two aspects of this: distribution of public keys use of public-key encryption to distribute secret keys

53. Distribution of Public Keys can be considered as using one of: public announcement publicly available directory public-key authority public-key certificates

54. Public Announcement users distribute public keys to recipients or broadcast to community at large eg . append PGP keys to email messages or post to news groups or email list major weakness is forgery anyone can create a key claiming to be someone else and broadcast it until forgery is discovered can masquerade as claimed user

55. Publicly Available Directory can obtain greater security by registering keys with a public directory directory must be trusted with properties: contains { name,public -key} entries participants register securely with directory participants can replace key at any time directory is periodically published directory can be accessed electronically still vulnerable to tampering or forgery

56. Public-Key Authority improve security by tightening control over distribution of keys from directory has properties of directory and requires users to know public key for the directory then users interact with directory to obtain any desired public key securely does require real-time access to directory when keys are needed

57. Public-Key Authority

58. Public-Key Certificates certificates allow key exchange without real-time access to public-key authority a certificate binds identity to public key usually with other info such as period of validity, rights of use etc with all contents signed by a trusted Public-Key or Certificate Authority (CA) ‏ can be verified by anyone who knows the public-key authorities public-key

59. Public-Key Certificates

60. Public-key infrastructure ( PKI ) A public-key infrastructure ( PKI ) is a set of hardware, software, people, policies, and procedures needed to create, manage, distribute, use, store, and revoke digital certificates PKI is an arrangement that binds public keys with respective user identities by means of a certificate authority ( CA )

61. Differences Between Symmetric and Asymmetric Systems Attribute Symmetric Asymmetric Keys One key is shared between two or more entities One entity has a public key, and the other entity has the corresponding private key. Key exchange Out-of-band through secure mechanisms. A public key is made available to everyone, and a private key is kept secret by the owner. Speed Algorithm is less complex and faster. The algorithm is more complex and slower. Use Bulk encryption, which means encrypting files and communication paths. Key distribution and digital signatures. Security service provided Confidentiality. Authentication and nonrepudiation

62. Types of Asymmetric Systems The Diffie -Hellman Algorithm RSA El Gamal Elliptic Curve Cryptosystems LUC Knapsack Zero Knowledge Proof

63. Hybrid Encryption Methods

64. Public-Key D istribution of Secret Keys use previous methods to obtain public-key can use for secrecy or authentication but public-key algorithms are slow so usually want to use private-key encryption to protect message contents hence need a session key have several alternatives for negotiating a suitable session

65. Simple Secret Key Distribution proposed by Merkle in 1979 A generates a new temporary public key pair A sends B the public key and their identity B generates a session key K sends it to A encrypted using the supplied public key A decrypts the session key and both use problem is that an opponent can intercept and impersonate both halves of protocol

66. Public-Key Distribution of Secret Keys if have securely exchanged public-keys:

67. Hybrid Key Distribution retain use of private-key KDC shares secret master key with each user distributes session key using master key public-key used to distribute master keys especially useful with widely distributed users rationale performance backward compatibility

68. Diffie -Hellman Key Exchange first public-key type scheme proposed by Diffie & Hellman in 1976 along with the exposition of public key concepts note: now know that Williamson (UK CESG) secretly proposed the concept in 1970 is a practical method for public exchange of a secret key used in a number of commercial products

69. Diffie -Hellman Key Exchange a public-key distribution scheme cannot be used to exchange an arbitrary message rather it can establish a common key known only to the two participants value of key depends on the participants (and their private and public key information) based on exponentiation in a finite (Galois) field (modulo a prime or a polynomial) - easy security relies on the difficulty of computing discrete logarithms (similar to factoring) – hard

70. Diffie -Hellman Setup all users agree on global parameters: large prime integer or polynomial q a being a primitive root mod q each user ( eg . A) generates their key chooses a secret key (number): x A < q compute their public key : y A = a x A mod q each user makes public that key y A

71. Diffie -Hellman Key Exchange shared session key for users A & B is K AB : K AB = a x A. x B mod q = y A x B mod q (which B can compute) = y B x A mod q (which A can compute) K AB 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 attacker needs an x, must solve discrete log

72. Diffie -Hellman Example users Alice & Bob who wish to swap keys: agree on prime q=353 and a =3 select random secret keys: A chooses x A =97, B chooses x B =233 compute respective public keys: y A = 3 97 mod 353 = 40 (Alice) ‏ y B = 3 233 mod 353 = 248 (Bob) ‏ compute shared session key as: K AB = y B x A mod 353 = 248 97 = 160 (Alice) ‏ K AB = y A x B mod 353 = 40 233 = 160 (Bob) ‏

73. Key Exchange Protocols users could create random private/public D-H keys each time they communicate users could create a known private/public D-H key and publish in a directory, then consulted and used to securely communicate with them both of these are vulnerable to a meet-in-the-Middle Attack authentication of the keys is needed