1_Cryptanalysis for graduate course.pptx

Discussion on cryptanalysis as apart of cryptography curse for graduate students

1. Unit-3 Building blocks for cryptography

2. Building blocks for cryptography cryptanalysis of affine cipher, cryptanalysis of substitution cipher, cryptanalysis of Vigenère cipher, cryptanalysis of hill and stream ciphers, public-key cryptosystems, RSA cryptosystem, RSA encryption and decryption, cryptographic protocols, Hybrid cryptography

3. What is the plain text?

4. Cryptanalysis

5. Cryptanalysis

6. Relative frequencies of the Alphabets 1. E, having probability about 0.120 2. T, A,O, I, N, S, H, R, each having probability between 0.06 and 0.09 3. D, L, each having probability around 0.04 4. C,U,M,W, F, G,Y, P, B, each having probability between 0.015 and 0.028 5. V, K, J, X,Q, Z, each having probability less than 0.01.

7. Digrams and Trigrams It is also useful to consider sequences of two or three consecutive letters, called digrams and trigrams , respectively. The 30 most common digrams are (in decreasing order): TH , HE , IN , ER , AN , RE , ED , ON , ES , ST , EN , AT , TO , NT , HA , ND , OU , EA , NG , AS , OR , TI , IS , ET , IT , AR , TE , SE , HI , OF . The twelve most common trigrams are: THE , ING , AND , HER , ERE , ENT , THA , NTH , WAS , ETH , FOR , DTH

8. Cryptanalysis of affine cipher Consider a Ciphertext obtained from an Affine Cipher FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH Let's do frequency analysis of this ciphertext

9. Cryptanalysis of affine cipher FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH The most frequent ciphertext characters are: R (8 occurrences), D (7 occurrences), E , H , K (5 occurrences each), and F , V (4occurrences each). As a first guess, R is the encryption of e and D is the encryption of t , since e and t are (respectively) the two most common letters.

10. Cryptanalysis of affine cipher If R (17) is the encryption of e(4) and D(3) is the encryption of t(19) , N umerically, y = ax + b , where a and b are unknowns. Hence the two linear equations in two unknowns can be written as: 4 a + b = 17 19 a + b = 3. Find the solution to this system of equation. Hint: 7 -1 (mod 26)=15 This system has the unique solution a = 6, b = 19 (in Z 26 ). But this is an illegal key, since gcd ( a , 26 ) = 2 > 1. So, our hypothesis must be incorrect.

11. Cryptanalysis of affine cipher Let's guess, R is the encryption of e and E is the encryption of t . Hence the two linear equations in two unknowns can be written as: 4 a + b = 17 19 a + b = 4. Proceeding as above, we obtain a = 13, which is again illegal. Try the next possibility, that R is the encryption of e and H is the encryption of t . This yields a = 8, again impossible. Continuing, let R is the encryption of e and K is the encryption of t . This produces a = 3, b = 5, which is at least a legal key. It remains to compute the decryption function corresponding to K = ( 3, 5 ) , and then to decrypt the ciphertext to see if we get a meaningful string of English. This will confirm the validity of ( 3, 5 ) .

12. Decrypting text Find the plain text by performing decryption with a=3 and b=5 Plain text: algorithms are quite general definitions of arithmetic processes Hurray! Determined the correct key.

13. Example If e is encrypted as d and z as c find the key to affine cipher. E D Z C Hint: 5 -1 (mod 26)=21 Sol a=21, b=23

14. Cryptanalysis of the Substitution Cipher Monoalphabetic cipher

15. Cryptanalysis of the Substitution Cipher Consider a ciphertext obtained from a Substitution Cipher KHOOR ZRUOG Count relative letter frequencies K 0.1 Z 0.1 H 0.1 U 0.1 O 0.3 G 0.1 R 0.2

16. Calculating correlation of Frequency For cipher text KHOOR ZRUOG + + + + + 0.2 + 0.1 + 0.1 + 0.1   K 0.1 Z 0.1 H 0.1 U 0.1 O 0.3 G 0.1 R 0.2

17. Calculation Use these values of relative frequencies

18. Correlation values

19. Observing the plain text Now the plain text need to be calculated for each value of key with highest correlation value.

20. The Vigen è re Cipher Treat letters as numbers: [A=0, B=1, C=2, …, Z=25] Number Theory Notation: Z n = {0, 1, …, n-1} Definition : Given m, a positive integer, P = C = (Z 26 ) n , and K = (k 1 , k 2 , … , k m ) a key, we define: Encryption : e k (p 1 , p 2 … p m ) = (p 1 +k 1 , p 2 +k 2 …p m +k m ) (mod 26) Decryption : d k (c 1 , c 2 … c m ) = (c 1 -k 1 , c 2 -k 2 … c m - k m ) (mod 26) Example: Plaintext: C R Y P T O G R A P H Y Key: L U C K L U C K L U C K Ciphertext: N L A Z E I I B L J J I

21. Security of Vigenere Cipher Vigenere masks the frequency with which a character appears in a language: one letter in the ciphertext corresponds to multiple letters in the plaintext. Makes the use of frequency analysis more difficult. Any message encrypted by a Vigenere cipher is a collection of as many shift ciphers as there are letters in the key.

22. Vigenere Cipher: Cryptanalysis Find the length of the key. Divide the message into that many simple substitution encryptions. S olve the resulting simple substitutions. how?

23. Here is a ciphertext message that has been encrypted with a Vigenère cipher

24. Let’s guess Assume that, somehow, we have discovered that the keyword has length five (which is conveniently the same as the size of the blocks). Then the first letter of each block is encrypted with the same row of the Vigenère square – they are encrypted with the same Caesar cipher. Similarly, the second letter of each block is encrypted with the same row – the same Caesar cipher. The third letters with the same Caesar cipher. The fourth letters with the same Caesar cipher. And, the fifth letters with the same Caesar cipher.

25. Step1-Strip off the first letters of each block and do a frequency analysis on the result.

26. Making observations It appears that ciphertext Y corresponds to plaintext e . (Not just because it is the most frequent letter but because all the high frequency letter patterns fit U would correspond to a ; C would correspond to i ; H and I would correspond to n and o ; and L , M , and N would correspond to r , s , and t .) Now recall that when we are encrypting using a Vigenère square plaintext a corresponds to the first letter of the row being used – the letter of the keyword being used. So, it appears that (because U corresponds to a ) the first letter of the keyword is u . The keyword is u _ _ _ _ .

27. Step2-Strip off the second letters of each block and do a frequency analysis on the result.

28. Observation

29. Step3-Strip off the third letters of each block and do a frequency analysis on the result.

30. Continue to explore The keyword is u b o a t .

31. How to Find the Key Length?

32. Kasisky Test Note: two identical segments of plaintext, will be encrypted to the same ciphertext, if the they occur in the text at the distance , (0 (mod m), m is the key length). Algorithm: Search for pairs of identical segments of length at least 3 Record distances between the two segments: 1, 2, … m divides gcd (1, 2, …)

33. 34 Example of the Kasisky Test Encode the plaintext " maths is short for mathematics" using the keyword key Notice the repeating nature of the key, both times "math", is encrypted in the same way to "WERR". As a cryptanalyst this gives us some useful information. Since the repeating are 15 letters apart, it means the length of the key must be a factor of 15. That is, the key must repeat exactly in a space of 15 letters. Thus, the keyword must be one of the lengths 15, 5, 3 or 1.

34. Example of the Kasisky Test Consider another cipher text example: VHVSSPQUCEMRVBVBBBVHVSURQGIBDUGRNICJQUCERVUAXSSR Find the repeated alphabets and the distance between two repetition. VHVS SP QUCE MRVBVBBB VHVS URQGIBDUGRNICJ QUCE RVUAXSSR The gap between the "VHVS" pair is 18, suggesting a key length of 18, 9, 6, 3 or 2. The gap between the "QUCE" pair is 30, which suggests a key length of 30, 15, 10, 6, 5, 3 or 2. So, looking at both together the most likely key length is 6 or possibly 3 Gcd (18,30)=6

35. Index of coincidence (Friedman) Index of Coincidence (IC) is a statistical measure used in cryptanalysis, particularly for monoalphabetic substitution ciphers. It helps to distinguish between ciphertext that is random (like a truly encrypted message) and ciphertext that has a pattern

36. Index of coincidence (Friedman) How IC Works: Count Letter Frequencies: Determine the frequency of each letter in the ciphertext. Calculate IC: Use IC = Σ(n(n-1)) / (N(N-1)) where: n is the number of occurrences of a particular letter N is the total number of letters in the ciphertext

37. Steps to Determine Key Length Using IC: Divide the Ciphertext: Divide the ciphertext into segments of varying lengths. Calculate IC for Each Segment: Calculate the IC for each segment. Identify Peaks: Look for peaks in the IC values. These peaks often correspond to the correct key length. Test Key Lengths: Try different key lengths based on the identified peaks and analyze the resulting ciphertext for patterns or meaning.

38. Example: Find Index of coincidence for a ciphertext: "XQOWUKPHQPWUXQWPHQXOWUXPHQXOWUXPHQW“ Sol. Frequency of each letter: X: 6 Q: 6 O: 3 W: 6 U: 4 P: 5 H: 4 K:1

39. Example: Frequency of each letter: X: 6 Q: 6 O: 3 W: 6 U: 4 P: 5 H: 4 K:1 Total number of letters = 35. IC = 140/(35 x 34) ≈ 0.117

40. Example: Assume a ciphertext encrypted using a Vigenère cipher. Divide the ciphertext into segments of different lengths and calculate the IC for each segment:

41. The IC for segment length 5 is noticeably higher than the others. This suggests that the key length might be 5. Now different keys of length 5 can be tried and analyzed for the resulting plaintext for meaning or patterns to confirm the correct key.

42. Cryptanalysis of Hill Cipher

43. Cryptanalysis of Hill Cipher The Hill cipher is a polygraphic substitution cipher that encrypts plaintext blocks of a fixed size using matrix multiplication. While it is considered to be relatively secure for small key sizes, it can be susceptible to cryptanalysis for larger key sizes.

44. Example Find the key for a cipher text PQCFKU which is obtained from the plain text Friday . Sol Let, [f r][a b; c d]=[P Q] [5 1] [ a b; c d]=[ 15 16] Similarly, [I d ][a b; c d]=[C F] [8 3] [ a b; c d]=[ 2 5]

45. Sol Using the two equations [5 17] [ a b; c d]=[ 15 16] [8 3] [ a b; c d]=[ 2 5] = Now find the Key using inverse matrix and simplifying  

46. Sol The key is thus calculated as: