Computer Security

1.1.1. Computer Security

1.1.2. Network Security

1.1.3. Internet Security

2.1.1. Data Confidentiality

2.1.2. Privacy

2.1.3. Authentication

2.2.1. Data Integrity

2.2.2. System Integrity

3.1.1. Security Threat

3.1.2. Two types of Attacks

1. Active Attack
   
   • An attacker tries to modify the content of the messages.
   • The data stream is directly modified.
   • This is a threat for System Integrity and Availability.
   • You can’t prevent an active attack. You (the victim) get to know about it only after the content of the messages is modified.
   • Here, the result is an actual damaged system.
   • Examples include Denial of Service (make a resource unavailable to everyone by spamming traffic and requests and slowing it down), Password Tracking, Replay Attack and Viruses.
   • A simpler example would be “Gina forging Roger’s signature”, as this is an act of data fabrication.
   • Here’s another example: “Henry spoofs Julie’s IP address to gain access to her computer”
2. Passive Attack
   
   • An attacker observes the messages, and uses them for malicious purposes information.
   • Here, the data stream is just monitored, not modified.
   • This is a threat for Confidentiality.
   • You can prevent and detect a passive attack. A passive attack becomes an active attack when data is modified.
   • You (the victim) won’t get to know if the attack happened.
   • The result is not a damaged system.

   • Examples include snooping and sniffing. Eavesdropping is a generalized term that means listening to/intercepting communication. Sniffing is a type of eavesdropping.

     Term	Meaning
     Sniffing	Using software (sniffers) to capture packets
     Snooping	Observing screens, keystrokes, or files

   • Here’s an example of a passive attack: “John copies Mary’s assignment”. The assignment wasn’t changed - it’s an act of eavesdropping.

3.2.1. Definitions by different standards

1. X.800
   
   • It’s a
   1. Authentication
      
   2. Access Control (Data Privacy)
      
   3. Confidentiality
      
   4. Data Integrity
      
   5. Non-Repudiation (Rejection)
      
      • Protection against Denial of Service.

3.2.2. Notorization

5.2.1. Types of attacks on access controls

1. Brute-Force Attacks
   
   • You keep trying all combinations of characters in all possible lengths, until you actually crack the password.
2. Dictionary Attacks
   
   • Guessing passwords from a predefined dictionary of common words, phrases and passwords,

5.2.2. Layered Security Tools/Devices

5.2.3. Zero-Day Attack

6.1.1. Virus

6.1.2. Trojan Horse

6.1.3. Trapdoors/Backdoor

6.1.4. Logic Bomb

6.2.1. Worms

6.2.2. Zombie

7.2.1. Based on Encryption Techniques

1. Substitution
   
   1. Classical Substitution Cipher
      
      • Every occurrence of a plain text symbol is replaced by a corresponding ciphertext character.
      1. Ceaser/Shift Cipher
         

         This is the earliest known subsitution cipher. \[ C_{1} = e(m_{1}) = m_{1} + k\mod(s) \]

         1. For example, let m = college, k = 3 and s = 26.
            
            • C₁[1] = (position of ’c’) + 3mod(26) = f
            • C₁[2] = (position of ’o’) + 3mod(26) = r
            • C₁[3] = (position of ’l’) + 3mod(26) = o
            • C₁[4] = (position of ’l’) + 3mod(26) = o
            • C₁[5] = (position of ’e’) + 3mod(26) = h
            • C₁[6] = (position of ’g’) + 3mod(26) = j
            • C₁[7] = (position of ’e’) + 3mod(26) = h
            • Hence, C₁ = e(college) = froohjh
         2. In general, for alphabets, Ceasar Cipher is given as
            

            Encryption:	\(E(P) = (P+K)\mod(26)\)
            Decryption:	\(D(C) = (C-K)\mod(26)\)

         3. For example, Encrypt KHOOR with k=4
            
            • C₁[1] = (position of ’K’) + 4mod(26) = O
            • C₁[2] = (position of ’H’) + 4mod(26) = L
            • C₁[3] = (position of ’O’) + 4mod(26) = S
            • C₁[4] = (position of ’O’) + 4mod(26) = S
            • C₁[5] = (position of ’R’) + 4mod(26) = V
            • Hence the string is OLSSV
         4. Decrypt Ciphertext ABC, k=3
            
            • A: \((0-3)\mod26 = -3\mod(26) = (-3+26)\mod(26) = 23\)
         5. Code for Encryption
            

            def encrypt(plaintext: str, k: int, alphabet_size: int):
                encrypted_text = ""
                start = None
                for c in plaintext:
                    if ord(c)>=ord('A') and ord(c)<=ord('Z'):
                        start = ord('A')
                        diff = 0
                    elif ord(c)>=ord('a') and ord(c)<=ord('z'):
                        start = ord('a')
                        diff = 0
                    elif ord(c)>=ord('0') and ord(c)<=ord('9'):
                        start = ord('0')
                        diff = 16
                        
                    if c!=' ':
                        encrypted_text += chr(start+(ord(c)-start+k)%(alphabet_size - diff))
                    else:
                        encrypted_text += ' '
                print(encrypted_text)
                
            encrypt("Hello World3!", 2, 26) 
            
            
            

            Jgnnq Yqtnf57
            

         6. Code for Decryption
            

            def decrypt(plaintext: str, k: int, alphabet_size: int):
                decrypted_text = ""
                
                for c in plaintext:
                    if ord(c)>=ord('A') and ord(c)<=ord('Z'):
                        decrypted_text += chr(ord('A')+(ord(c)-ord('A')-k)%alphabet_size)
                    elif ord(c)>=ord('a') and ord(c)<=ord('z'):
                        decrypted_text += chr(ord('a')+(ord(c)-ord('a')-k)%alphabet_size)
                    elif c == ' ':
                        decrypted_text += ' '
                    elif ord(c)>=ord('0') and ord(c)<=ord('9'):
                        decrypted_text += chr(ord('0')+(ord(c)-ord('0')-k)%10)
                print(decrypted_text)
                
            decrypt("Jgnnq Yqtnf5", 2, 26) 
            
            
            

            Hello World3
            

            The logic for encryption and decryption is pretty simple:

            • You iterate through the characters of the text (say each character is c)
            • ord(c)-ord('A') finds the alphabetic position (0-25)
            • Add/Subtract Shift value on this alphabetic position and take modulo alphabet size. This value is again between 0 and 25.
            • Add the above value to the ASCII value of A, and convert it back into a character.
         7. Cryptanalysis
            
            1. Break the ciphertext WKLV using cryptanalysis
               

               The program given below is a very simple Python Script to generate all possible plaintexts for a given ciphertext.

               def breakCaesar(x):
                   for k in range(26):
                       for c in x.upper():
                           shift = (ord(c) - ord('A') - k)%26 
                           cipher_char = chr(ord('A')+shift)
                           print(cipher_char, end="")
                       print(end=", ")
                       
               breakCaesar("WKLV")
               
               

               WKLV, VJKU, UIJT, THIS, SGHR, RFGQ, QEFP, PDEO, OCDN, NBCM, MABL, LZAK, KYZJ, JXYI, IWXH, HVWG, GUVF, FTUE, ESTD, DRSC, CQRB, BPQA, AOPZ, ZNOY, YMNX, XLMW,
               

               Explanation: For each alphabet, this is what’s happening:

               • ord(c) - ord('A') is basically the difference between the ASCII value of the character in the string, and the ASCII value of the letter ’A’. This difference is in the range 0-25. ord(c) - ord('A') is the value of \(C\) in \(D(C) = (C-K)\mod(26)\).
               • - k is doing the \((C-K)\) part in \(D(C) = (C-K)\mod(26)\).
               • % 26 is doing the \(\mod(26)\) part in \(D(C) = (C-K)\mod(26)\).
               • We add ord('A') to the shift so that we can convert this number back to ASCII.
               • To convert the ASCII value back into a number, we have to typecast it into a character, by passing it into the chr() function.
            2. Break the ciphertext GWTBS
               

               breakCaesar("GWTBS")
               

               GWTBS, FVSAR, EURZQ, DTQYP, CSPXO, BROWN, AQNVM, ZPMUL, YOLTK, XNKSJ, WMJRI, VLIQH, UKHPG, TJGOF, SIFNE, RHEMD, QGDLC, PFCKB, OEBJA, NDAIZ, MCZHY, LBYGX, KAXFW, JZWEV, IYVDU, HXUCT,
               

   2. Simple Substitution/ Monoalphabetic
      
      • Rather than shifting the alphabets, you shuffle the alphabets randomly.
      • Every plain text letter maps to a random cipher text letter, hence there are 26 keys.
      • Given a ciphertext, there are \(26!\) possible plain texts.
      • The relative letter frequencies never change.
   3. Polygram
      
      • A block of plain text symbols is replaced by a corresponding ciphertext block of characters.
      • Sequence of two plain text characters are known as digrams, replaced by other digrams.

      • For example, the word

        CO LL EG Ex
        

        This can become, say (random, just for example):

        xy ab up ld
        

      1. Playfair Cipher
         
         1. Explanation
            
            • Make a \(5 \times 5\) matrix. In these 25 spaces, you’ll have to fill all 26 alphabets. To accommodate the extra alphabet, we merge I and J in one box, by convention.
            • You start by filling the alphabets of the keyword given (without repetition).
            • After you’re done with that, start with the rest of the alphabet, and fill in the rest of the gaps in order without repetition.
            1. Example we’ll be using to learn the rules
               
               • keyword: CRYPTOGRAPHY CLASS SPRING

               C	R	Y	P	T
               O	G	A	H	L
               S	I/J	N	B	D
               E	F	K	M	Q
               U	V	W	X	Z

            2. How to Encrypt a given plain text
               
               1. If letters of a pair are both same, then add an x after the first letter and encrypt the new pair.

                  • For example: If you have the word H E L L O, you’d resolve it as:

                    HE LX LO
                    

                    and not

                    HE LL O
                    

               2. If letters appear on the same row, replace them with the letters to their immediate right with wrapping, according to the direction.

                  • For example, consider one row of the matrix to be:

                    O

                    G

                    A

                    H

                    L

                    For HA, the corresponding plain text could be LH or AG. In our course, we’ll stick to AG.

               3. If letters appear on the same column, replace them with the letters immediately below, also with wrapping according to the direction.

                  • For example, consider one column of the matrix to be:

                    Y

                    A

                    N

                    K

                    W

                    • For NK, the corresponding plain text would be KW.
                    • For YW, the corresponding plain text would be AY.
               4. If letters are not on the same row/column, replace them with the letters on the same row respectively but add the other pair of corners of the rectangle, by the original pair.
            3. Demonstration of the plain text being encrypted
               
               • Consider the plain text “Hello find the solution”.

               • This will be broken into:

                 HE   LX   LO   FI   ND   TH   ES   OL   UT   IO   NZ
                 

               • And the encrypted text will look like:

                 OQ   OZ   OG   IG   BS   PL   SO   GO   ZC   SG   DW             
                 

         2. Solving another Example
            

            • Keyword: KEYWORD

              K	E	Y	W	O
              R	D	A	B	C
              F	G	H	I/J	L
              M	N	P	Q	S
              T	U	V	X	Z

            1. Plain Text: Why don’t you
               

               • This will be broken into:

                 WH   YD   ON   TY   OU
                 

               • And the encrypted text will look like:

                 KL   OR   KS   ZK   KZ
                 

            2. Plain Text: Come to the window
               

               • This will be broken into:

                 CO   ME   TO   TH   EW   IN   DO   WX
                 

               • And the encrypted text will look like:

                 OZ   NK   ZK   VF   YO   GQ   CE   BW
                 

         3. Code for Encryption
            

            def encrypt(plaintext: str, keyword: str):
                visited = {}
                matrix = [[0]*5 for i in range(5)]
                i = 0
                j = 0
                for c in keyword:
                    if c not in visited:
                        matrix[i][j] = c
                        visited[c] = (i,j)
                        if j==4:
                            i += 1
                            j = 0
                        else:
                            j += 1
                for x in range(26):
                    if chr(ord('A')+x) not in visited:
                        visited[chr(ord('A')+x)] = (i,j)
                        if chr(ord('A')+x)=='J':
                            continue
                        matrix[i][j] = chr(ord('A')+x)
                        if j==4:
                            i += 1
                            j = 0
                        else:
                            j += 1
                if len(plaintext)%2!=0:
                    plaintext += 'X'
                for i in range(1, len(plaintext), 2):
                    ch1_i = visited[plaintext[i-1]][0]
                    ch1_j = visited[plaintext[i-1]][1]
                    ch2_i = visited[plaintext[i]][0]
                    ch2_j = visited[plaintext[i]][1]
                 
                    if ch1_j == ch2_j:
                        print(matrix[ch1_i][(ch1_j + 1)%5], end='')
                        print(matrix[ch2_i][(ch2_j + 1)%5], end='')
                    elif ch1_i == ch2_i:
                        print(matrix[(ch1_j + 1)%5][ch1_i], end='')
                        print(matrix[(ch2_j + 1)%5][ch2_i], end='')
                    else:
                        print(matrix[ch1_i][ch2_j], end='')
                        print(matrix[ch2_i][ch1_j], end='')
                        
                     
                     
                     
            encrypt('WHYDONTYOU','KEYWORD')
            

            YIEAESVKEZ
            

         4. Code for Decryption
            

            def decrypt(ciphertext: str, keyword: str):
                visited = {}
                matrix = [[0]*5 for i in range(5)]
                i = 0
                j = 0
                for c in keyword:
                    if c not in visited:
                        matrix[i][j] = c
                        visited[c] = (i,j)
                        if j==4:
                            i += 1
                            j = 0
                        else:
                            j += 1
                for x in range(26):
                    if chr(ord('A')+x) not in visited:
                        visited[chr(ord('A')+x)] = (i,j)
                        if chr(ord('A')+x)=='J':
                            continue
                        matrix[i][j] = chr(ord('A')+x)
                        if j==4:
                            i += 1
                            j = 0
                        else:
                            j += 1
                for i in range(1, len(ciphertext), 2):
                    ch1_i = visited[ciphertext[i-1]][0]
                    ch1_j = visited[ciphertext[i-1]][1]
                    ch2_i = visited[ciphertext[i]][0]
                    ch2_j = visited[ciphertext[i]][1]
                 
                    if ch1_j == ch2_j:
                        print(matrix[ch1_i][(ch1_j + 1)%5], end='')
                        print(matrix[ch2_i][(ch2_j + 1)%5], end='')
                    elif ch1_i == ch2_i:
                        print(matrix[(ch1_j - 1)%5][ch1_i], end='')
                        print(matrix[(ch2_j - 1)%5][ch2_i], end='')
                    else:
                        print(matrix[ch1_i][ch2_j], end='')
                        print(matrix[ch2_i][ch1_j], end='')
                     
            decrypt('YIEAESVKEZ', 'KEYWORD')
                        
            

            WHYDONTYOU
            

            Some things to note in this code are:

            • To go through the matrix, maintain separate variables for row and column. If the row exceeds 4, reset row to zero, and increase the column value by 1.
            • visited[c] stores the matrix coordinates (i and j) of the character c. In other words, the position of a character in the matrix can be obtained as (visited[c][0], visited[c][1]).
            • Make sure that the plaintext is of even length. If not, pad it with a character.
            • Once you actually have the matrix, you iterate having a skip value of 2, to pick two characters at a time:
              • If both characters are in the same row, move both forward (modulo 5 of coures) by 1 unit. Hence the column is modified.
              • If both characters are in the same column, move both downwards by 1 unit. Hence the row is modified.
              • If it is neither of the cases, you swap the columns of both characters.
      2. Hill Cipher
         

         Consider the Example: Plaintext = CODE, Key = \(\begin{bmatrix} 3 & 3 \\ 2 & 5 \end{bmatrix}\)

         1. Encryption
            

            \[\text{Cipher Text} = \begin{bmatrix} \text{Key} \end{bmatrix} \times \text{Plain Text} \mod(26)\]

            • Plaintext:

              CO   DE
              

              In numeric indices: \[\begin{bmatrix} 2 \\ 14 \end{bmatrix} \text{ and } \begin{bmatrix} 3 \\ 4 \end{bmatrix}\]

            • CipherText: \[ \begin{bmatrix} 3 & 3 \\ 2 & 5 \end{bmatrix} \times \begin{bmatrix} 2 \\ 14 \end{bmatrix} \mod(26) = \begin{bmatrix} 22\\ 22 \end{bmatrix}\] \[ \begin{bmatrix} 3 & 3 \\ 2 & 5 \end{bmatrix} \times \begin{bmatrix} 3 \\ 4 \end{bmatrix} \mod(26) = \begin{bmatrix} 21 \\ 0 \end{bmatrix}\]

            • In alphabetic form:

              WW   VA
              

         2. Decryption
            

            \[\text{Plain Text} = \begin{bmatrix} \text{Key} \end{bmatrix}^{-1} \times \text{Cipher Text} \mod(26)\]

            • \([\frac{1}{\det{k}} \times \text{adj}(k) ] \times \text{(Cipher Text)} \mod(26)\)
            • \([9^{-1} \times \text{adj}(k) ] \times \text{(Cipher Text)} \mod(26)\)
            • \([9^{-1} \times \begin{bmatrix} 5 & -3 \\ -2 & 3 \end{bmatrix} ] \times \text{(Cipher Text)} \mod(26)\)
            • \([ \begin{bmatrix} 5 & -3 \\ -2 & 3 \end{bmatrix} 9^{-1} \mod(26)] \times \text{(Cipher Text)} \mod(26)\)

            Refer to Extended Euclidean Algorithm

            • \([ \begin{bmatrix} 5 & -3 \\ -2 & 3 \end{bmatrix} \times 3] \times \text{(Cipher Text)} \mod(26)\)
            • \([ \begin{bmatrix} 15 & -9 \\ -6 & 9 \end{bmatrix}] \times \begin{bmatrix}22 \\ 22\end{bmatrix} \mod(26) = \begin{bmatrix}2 \\ 14\end{bmatrix}\)
            • \([ \begin{bmatrix} 15 & -9 \\ -6 & 9 \end{bmatrix}] \times \begin{bmatrix}21 \\ 0\end{bmatrix} \mod(26) = \begin{bmatrix} 3 \\ 4 \end{bmatrix}\)
   4. Homophonic
      
      • If a letter \(x\) appears for \(y\%\) of all characters, we assign \(y\) number of symbols to represent it.
   5. Polyalphabetic
      
      • In Caesar cipher, the key was a single number.
      • Polyalphabetic cipher uses a key to select which alphabet is used for each alphabet of the message.
      • Once the key reaches the end it is repeated from the beginning to match the length of the plain text.
      1. Vigenere Cipher
         
         1. Encryption
            
            • This is one of the simplest polyalphabetic substitution cipher.
            • It is effectively multiple caeser ciphers.
            • \(K = K_{1} K_{2} K_{3}....K_{L}\), where \(L\) is the length of the key.
            • The same plain text character is encrypted to different cipher text characters.

            • Assume plain text to be “WE ARE DISCOVERED SAVE YOURSELF” and the key to be “DECEPTIVE”

              Making the alphabet-index mapping programmatically:

              print('|', end='')
              for i in range(26):
                  print(f'{i} - {chr(ord('A')+i)} |', end='')
              
              

              0 - A

              1 - B

              2 - C

              3 - D

              4 - E

              5 - F

              6 - G

              7 - H

              8 - I

              9 - J

              10 - K

              11 - L

              12 - M

              13 - N

              14 - O

              15 - P

              16 - Q

              17 - R

              18 - S

              19 - T

              20 - U

              21 - V

              22 - W

              23 - X

              24 - Y

              25 - Z

            • We map each alphabet of the plain text to the key repeated as many times as required:

              W E A R E D I S C O V E R E D S A V E Y O U R S E L F
              D E C E P T I V E D E C E P T I V E D E C E P T I V E
              _____________________________________________________
              Z I C V T W Q N G R Z G V T W A V Z H C Q Y G L M G J
              

            • In Vigenere Cipher the length of the keyword can be found out as two identical sequences of plain text letters occur at a distance that is an integer multiple of the keyword length will generate identical cipher text sequences.

            • Since the periodic nature of the keyword was the issue, Vigenere proposed an autokey system, in which a keyword is concatenated with the plain text to match the length of the plain text.

              W E A R E D I S C O V E R E D S A V E Y O U R S E L F
              D E C E P T I V E W E A R E D I S C O V E R E D S A V 
              _____________________________________________________
              

         2. Code
            

            def encrypt(plaintext: str, key: str):
                j = 0
                for i in range(len(plaintext)):
                    print(chr(ord('A') + (ord(list(plaintext)[i]) + ord(list(key)[j]) - 2*ord('A'))%26), end='')
                    j = (j+1)%len(key)
                 
                 
            def decrypt(ciphertext: str, key: str):
                j = 0
                for i in range(len(ciphertext)):
                    print(chr(ord('A') + (ord(list(ciphertext)[i]) - ord(list(key)[j]) - 2*ord('A'))%26), end='')
                    j = (j+1)%len(key)
                 
                    
            encrypt('WEAREDISCOVEREDSAVEYOURSELF', 'DECEPTIVEDECEPTIVEDECEPTIVE')
            print()
            decrypt('ZICVTWQNGRZGVTWAVZHCQYGLMGJ', 'DECEPTIVEDECEPTIVEDECEPTIVE')
            

            ZICVTWQNGRZGVTWAVZHCQYGLMGJ
            WEAREDISCOVEREDSAVEYOURSELF
            

         3. Cryptanalysis
            
            1. Example 1: Plain Text = “acbxzcb”, Cipher Text = “bxbywdb”
               

               	0	1	2	3	4	5	6
               Plain Text →	a	c	b	x	z	c	b
               Cipher Text →	b	x	b	y	w	d	b

      2. Vernam Cipher (one-time pad)
         
         • You perform bitwise XOR on the ASCII value of the characters of the plain text and the key.

         • Here is the XOR Table:

           A	B	A XOR B
           0	0	0
           0	1	1
           1	0	1
           1	1	0

         • For example:

           	String Given	Char-by-char ASCII Value	Char-by-char value in Binary
           Plain text →	CAT	676584	010000110100000101010100
           Key →	DOG	687971	010001000100111101000111
           		Plain Text XOR Key →	000001110000111000010011

         • One thing to note is that the key length has to be at least as long as the plain text.
         • Theoretically, this cipher is impossible to decrypt because the key has to be purely random.
         1. Code
            

            def encrypt(plaintext: str, key: str):
                cipher = []
                if len(plaintext) != len(key):
                    return False
                for i in range(len(plaintext)):
                    cipher.append(chr(ord(plaintext[i]) ^ ord(key[i])))
                return cipher
             
             
            for x in encrypt('CAT', 'DOG'):
                print(ord(x), end=' ')
             
            print()
            
            # decryption
            print(encrypt(encrypt('CAT', 'DOG'), 'DOG'))
            
            

            7 14 19 
            ['C', 'A', 'T']
            

2. Transposition / Permutation Cipher
   
   • This cipher hides the message by rearranging the letters of the plain text without changing the actual letters.
   1. Railfence Cipher
      
      1. Encryption
         
         • Here you write message’s letters diagonally over the rows, then read the message row-by-row.

         • For example, plain text = “meet me after the party”, and the number of rows is 3 (this is the key).

           m

           t

           a

           e

           h

           a

           y

           e

           m

           f

           r

           e

           r

           e

           e

           t

           t

           p

           t

         • The cipher text would be “mtahaeyemfrereettpt”
      2. Decryption
         
         • For example, let the cipher text be “mtahaeyemfrereettpt”
         • The length of the text is 18, and the number of rails is 3.
         • Find the positions of letters in each rail:
           • Rail 1: 0, 3, 6, 9, 12, 15, 18
           • Rail 2: 1, 4, 7, 10, 13, 16
           • Rail 3: 2, 5, 8, 11, 14, 17

         • So the ciphertext is:

           0	3	6	9	12	15	18	1	4	7	10	13	16	2	5	8	11	14	17
           m	t	a	e	h	a	y	e	m	f	r	e	r	e	e	t	t	p	t

         • Now that we’ve mapped the correct indices, we can find the plain text:

           0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
           m	e	e	t	m	e	a	f	t	e	r	t	h	e	p	a	r	t	y

      3. Cryptanalysis
         
         • The only way is to brute force and try different key lengths.
      4. Code
         

         def encrypt(plaintext: str, rails: int):
             cleaned = plaintext.replace(" ", "")
             cipher = ""
             for i in range(rails):
                 for j in range(i, len(cleaned), rails):
                     cipher += cleaned[j]
             print(cipher)
             
         encrypt("meet me after the party", 3)
         
         
         def decrypt(ciphertext,key):
             n = len(ciphertext)
             plaintext = [''] * n
             idx = 0
          
             for i in range(key):
                 for j in range(i, n, key):
                     plaintext[j] = ciphertext[idx]
                     idx += 1
             print(''.join(plaintext))
                     
                 
          
         decrypt("mtaehayemfrereettpt", 3)
             
         

         mtaehayemfrereettpt
         meetmeaftertheparty
         

   2. Columnar Transposition
      
      • Write the characters of the message in rows over a specified number of columns.
      • The number of columns is the length of the key, and the key tells us the order in which the cipher text is written.
      • The cipher text is essentially the columns of this table written in the order the key was mentioned.

      • For example, key = 4312567 (meaning 7 columns), and the plain text is “attack postponed until two am”

        4	3	1	2	5	6	7
        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

        The cipher text would be “ttnaaptmtsuoaodwcoixknlypetz”.

3. Product
   

7.2.2. Based on Number of Keys

1. Single/Private Key
   
   • It’s called symmetric key encryption.
2. Two-key or Public Key cryptography
   
   • It’s called assymmetric key encryption.
   • Public key is used to encrypt the message and private key is used to decrypt.
   • Public key for Party b is denoted as \(KU_{b}\) \[C = E(\text{KB}_{B}, M)\]
   • Private key for Party b is denoted as \(KR_{b}\). \[M = D(\text{KU}_{B},E(\text{KR}_{B}, M))\]
   1. Encryption/Decryption
      
      • If you know the private key, you automatically get the public key too. But knowing the public key doesn’t give you the public key at all.
      • Not all algorithms support all the 3 applications. It may have one or two of the applications.

      Algorithm	Encryption/Decryption	Digital Signature	Key Exchange
      RSA	Yes	Yes	Yes
      Elliptic Curve	Yes	Yes	Yes
      Diffie-Hellman	No	No	Yes
      DSS	No	Yes	No

   2. Security of Public key algorithms
      
      • Brute force is always possible, so make sure you:
        • Use a very large key
        • At the same time, consider the security/performance trade-off.
      • Due to public/private key relationships, the number of bits in the key should be much larger the symmetric crypto keys.
   3. RSA (Rivest Shamir Adelman) Algorithm
      
      • This is the model widely used Public Key Cryptography (PKC).
      • To encrypt a message there is no need to exchange a secret key separately.
      1. Key Generation
         
         • Select \(p\), \(q\), where \(p\) and \(q\) are prime.
         • Calculate \(n = p \times q\)
         • Select integer \(e\), such that \(\text{gcd}(\phi(n), e) = 1; 1 < e < \phi(n)\)
         • Calculate \(d = e^{-1}\mod(\phi(n))\)
         • Public Key \(\text{KU} = {e,n}\)
         • Private Key \(\text{KR} = {d,n}\)
      2. Encryption
         
         1. Rules
            
            • Plaintext \(M < n\)
            • Ciphertext \(C = M^{d}\mod(n)\)
         2. Examples
            
            1. Example 1
               
               • \(p=3\), \(q=11\)
               • \(n=p \times q = 3 \times 11 = 33\)
               • \(\phi(n) = \phi(33) = \phi(3 \times 11) = 2 \times 10 = 20\)
                 • Verification of φ(33): \(Z_{33}^{*}\) = (all the numbers from 1 to 33, coprime with \(33\)) = [1,2,4,5,7,8,10,13,14,16,17,19,20,23,25,26,28,29,31,32]
               • Consider \(e=7\) (because it satisifies the GCD criteria):

               • \(d = e^{-1} \mod(20)\)

                 • \(d = 7^{-1} \mod(20)\)

                 \(q\)	\(a\)	\(m\)	\(r\)	\(u_{0}\)	\(u_{1}\)	\(u\)
                 0	7	20	6	1	0	1

            2. Example 2
               
      3. Decryption
         
         • Ciphertext = \(C\)
         • Plaintext = \(M = C^{d}\mod(n)\)
      4. Attacks against RSA
         
         1. Brute Force
            
         2. Mathematical Attakcs
            
            • Factor n
            • Calculate φ(n)
         3. Timings Attack
            
            • Use the running time of the algorithm to determine the key
   4. ElGamal Encryption Algorithm
      
      • It’s also a public-key cryptosystem like RSA.
      • It’s based on the difficulty of finding discrete logarithm.
      1. Algorithm
         
         • Select a large prime \(q\).
         • Select \(x\) to be a member of the group \(Z_{q}^{*}\)
         • Select \(g\) such that \(y = g^{x} \mod(q)\)
           • Public key: \((g,y,q)\)
           • Private Key: \(x\)
      2. Encryption
         
         • Select a random number \(r\) from \(Z_{q}^{*}\)
         • \(c_{1} = g^{r} \mod(q)\)
           • \(c_{1}\) carries the random exponent information required to compute the shared secret
           • \(g\) is called the primitive root.
         • \(c_{2} = (p \cdot y^{r}) \mod(q)\)
           • \(c_{2}\) contains the encrypted message, and hence this is the only cipher text involved.
      3. Decryption
         
         • \(P = [C_{2} (C_{1}^{x})^{-1}]\mod(q)\)
         • Encrypted message along with shared secret is needed for decryption.
         • Use Discrete Logarithm
      4. Examples
         
         1. Encrypt a message \(m\) having value 10 using a public key \(9\), where a random number generated is \(3\) and primitive root \(11\) and a prime number \(23\)
            
            • Given:
              • \(p=10\)
              • \(y=9\)
              • \(g=11\)
              • \(q=23\)
              • \(r=3\)
            • Encryption:
              • \(c_{1} = 11^{3} \mod(23) = 20\)
              • \(c_{2} = (10 \cdot 9^{3}) \mod(23) = 160 \mod(23) = 22\)
              • Cipher text \(C = (20, 22)\)
            • Decryption:
              • \(20^{6} = 16\mod(23)\)
              • Plaintext = \(10\)
         2. \(q = 23\), \(g = 7\), \(x = 9\), \(r = 3\), \(m = 20\)
            
   5. Diffie Hellman
      
      • This is used for key-exchange where both the parties jointly establish a shared secret over an unsecured channel.
      • Both parties agree on a generator \(g\) (an integer) and a large prime number \(p\), both of which are known to the public

      • They possess their own private keys \(a\) and \(b\) respectively. Only they know about this.

        Alice	Public	Bob
        \(a\)	\(p\), \(g\)	\(b\)

      • Now calculate the public key:

        Alice	Public	Bob
        \(a\)	\(p\), \(g\)	\(b\)
        	\(A = g^{b} \mod(p)\), \(B = g^{a} \mod(p)\)

      • Now we exchange public keys:

        Alice	Public	Bob
        \(a\)	\(p\), \(g\)	\(b\)
        	\(A = g^{a} \mod(p)\), \(B = g^{b} \mod(p)\)
        \(B = g^{b} \mod(p)\)		\(A = g^{a} \mod(p)\)

      • Calculate shared secret key:

        Alice	Public	Bob
        \(a\)	\(p\), \(g\)	\(b\)
        	\(A = g^{a} \mod(p)\), \(B = g^{b} \mod(p)\)
        \(B = g^{b} \mod(p)\)		\(A = g^{a} \mod(p)\)
        \(\text{Secret Key} = K = B^{a}\)		\(\text{Secret Key} = K = A^{b}\)

      1. Perform Diffie Hellman Key exchange using a prime number 13, and a generator of prime number 6, where person 1 has a private key 5, and person 2 has a private key 4. Calculate the shared secret among person 1 and 2.
         

7.2.3. Based on how plaintext is processed

1. Block
   
   • Block Cipher transforms a fixed length of plaintext data into a block of ciphertext of the same length, with the help of a secret key.
   • The most commonly used length of text (size of the block) is 64 bits.
   • Two types are:
     • Transposition
     • Substitution
2. Stream
   

8.1.1. Commutative

8.1.2. Associative

8.1.3. Distributive

8.3.1. Fundamental Theorem of Arithmetic

8.3.2. GCD

1. What it is
   
   • Greatest common divisor is the largest number that divides both numbers.
   • Consider this example: \[8 = 2 \times 2 \times 2\] \[32 = 2 \times 2 \times 2 \times 2 \times 2\]

   • GCD tells us how many 2’s you can take such that both numbers definitely have. The limiting factor is the smaller number (8) and hence:

     When you have two numbers: \[\text{num1} = x^{a} \times y^{b} \times z^{c}\] \[\text{num2} = x^{p} \times y^{q} \times z^{r}\]

     • The GCD of \(\text{num1}\) and \(\text{num2}\) is \(\text{min}(a,p) \times \text{min}(b,q) \times \text{min}(c,r) \times \text{. . .}\)

   • For LCM, it would be \(\text{max}(a,p) \times \text{max}(b,q) \times \text{max}(c,r) \times \text{. . .}\), because you need the smallest number that the numbers themselves can completely fit themselves in.
   • Consider a Venn diagram, where each circle is \(\text{num1}\) and \(\text{num2}\). The contents inside a circle are all the primes that number contains. For example the contents of the number 24 would be 2, 2, 2 and 3, since \(24 = 2^{3} \times 3\)
     • GCD is the intersection of primes and it’s the common part in the venn diagram. Hence you take the minimum of the powers.
     • LCM is the union of primes and it’s both the numbers taken together as a whole.
2. How to find
   

   For example, the GCD for 24598 and 7895 would be:

   Prime factorization of 24798

   2	24598
   7	12299
   7	1757
   251	251
   1	1

   Prime factorization of 7895

   5	7895
   1579	1579
   1	1

   The answer is 1.

8.3.3. Euclidean Algorithm

8.3.4. Modular Arithmetic Operations

1. Standard Rules
   

   \[[a\mod(n) + (b\mod(n))] \mod(n) = (a+b)\mod(n)\] \[[a\mod(n) - (b\mod(n))] \mod(n) = (a-b)\mod(n)\] \[[a\mod(n) \times (b\mod(n))] \mod(n) = (a \times b)\mod(n)\]

   Note: The notation of modulo \(m\) is \(Z_{m}\)

2. Inferences
   

   Some inferences you can make out from this is:

   • \((a-b)\mod(n) = 0\) is the same as \(a\mod(n) = b\mod(n)\).
3. How to do \((\text{negativeNumber})\mod(x)\)
   
   • It’s simply \((\text{negativeNumber}+nx)\mod(x)\), where \(n\) can be anything that turns that negative number into a positive one.

8.3.5. Addition Modulo \(n\) table

8.3.6. Congruence

8.3.7. Inverses

1. Additive Inverse
   

   \[-a + a\mod(m) = 0\]

2. Multiplicative Inverse
   
   • Normal multiplicative inverse of \(a\) is a number such that if you multiply \(a\) with it, you get 1. \[a \times x = 1\] and the value of \(x = a^{-1}\).
   • In modulo arithmetic: \[a \times x \equiv 1 \mod(m) \]

   • The multiplicative inverse of \(a\mod(m)\) is \(x\) such that \(a\cdot x\mod(m) = 1\mod(m) = 1\).

   Note:

   • Multiplicative inverse of \(a \mod(n)\) is represented as \(a^{-1} \mod(n)\)
   • Multiplicative inverse exists for \(a \mod(n)\) if \(GCD(a,n) = 1\).
   • For example, \(2^{-1} \mod(7) = 4\), i.e. \(2 \times 4 \mod(7) = 1\)
     • Hence 4 is the multiplicative inverse of \(2\mod(7)\).
     • Also, 2 is the multiplicative inverse of \(4\mod(7)\).
   • All in all, to find \(a^{-1}\mod(m)\), find the number \(x\) to multiply \(a\) with, such that \(a \times x \mod(m) = 1\).
   1. Extended Euclidean Algorithm
      

      • Consider this example of finding multiplicative inverse of \(356\mod(45)\) or \(356\) in \(Z_{45}\) (different ways of asking the same thing):

        \[u = u_{0} - q \cdot u_{1}\] And in the below table, always initialize \(u_{0}\) and \(u_{1}\) to be 1 and 0 respectively.

        \(q\)	\(a\)	\(m\)	\(r\)	\(u_{0}\)	\(u_{1}\)	\(u\)
        7	356	45	41	1	0	1
        1	45	41	4	0	1	-1
        10	41	4	1	1	-1	11
        4	4	1	0	-1	11

        The value of \(u_{1}\) in the row where \(r\) becomes 0, is the multiplicative inverse.

      • In the above table, you always carry the value of \(a\) , \(m\) , \(u_{0}\) and \(u_{1}\) from their respective top right neighbour, but you calculate \(q\) and \(r\).
      • Check if \(2^{-1}\mod(10)\) exists:
        • Can’t be found because \(GCD(2, 10) = 2 \ne 1\)
        • Hence multiplicative inverse doesn’t exist

      • Find the multiplicative inverse of \(9\mod(10)\):

        \(q\)	\(a\)	\(m\)	\(r\)	\(u_{0}\)	\(u_{1}\)	\(u\)
        0	9	10	9	1	0	1
        1	10	9	1	0	1	-1
        9	9	1	0	1	-1

        The multiplicative inverse is -1. So it’s \(-1\mod(10) = (-1+10)\mod(10) = 9\) So the final multiplicative inverse is 9.

   2. Multiplicative Inverse Pair
      
      • In general, if we have \(a \cdot x \mod(m) = 1\), then \((a,x)\) is a multiplicative inverse pair.

      • When we’re asked to find multiplicative inverse pair of, say \(Z_{10}\), we have to find the pairs of numbers which are multiplicative inverses of each other.

        \(1\cdot x \mod(10)\)	\(x=1\)
        \(2\cdot x \mod(10)\)	\(x=1\)

   3. Solving a congruence
      
      • Consider the example \[15x \equiv 7\mod(32)\]
      • Since GCD(15,32) = 1, we can find the modular inverse of \(15\mod(32)\).
        • \(15a \equiv 1\mod(32)\)
        • \(a = 15\)
        • Hence \(15 \equiv 15^{-1}\mod(32)\)
      • \(15x \equiv 7\mod(32)\)
      • Multiply both sides by the value of \(15^{-1}\mod(32)\)
      • \(15 \times 15x \equiv 15 \times 7\mod(32)\)
      • \(x \equiv 105\mod(32)\) because \(15 \times 15 \equiv 1\mod(32)\)
      • \(x \equiv 9\mod(32)\)

8.3.8. Equivalence Class

8.4.1. Conditions for \(\phi(P)\)

8.4.2. Examples

1. \(\phi(27)\)
   
   • \(\phi(3^{3}) = 3^{3} - 3^{2} = 18\)
2. \(\phi(630)\)
   
   • \(\phi(630) = \phi(63 \times 10)\)
   • \(\phi(630) = \phi(63) \times \phi(10) = (63 - 7) \times (\phi(2)\times\phi(5))\)
   • \(\phi(630) = 56 \times 1\)
   • \(\phi(630) = 56\)

8.5.1. Steps

1. Convert the number \(B\) into binary. Represent \(B\) as a sum of unique powers of 2.
   

   Eg. \(B = 11\)

   • \(B\) in binary is 1011.
   • So \(B = 8 + 2 + 1\)
2. \(A^{i}\mod(C)\) such that \(i \le B\)
   
3. Find \(A^{C}\mod(C)\),
   

8.5.2. Examples

1. \(11^{13}\mod(53)\)
   
   • Step 1:
     • \(13 = 8 + 4 + 1\)
   • Step 2:
     • \(11^{1}\mod(53) = 11\mod(53) = 11\)
     • \(11^{2}\mod(53) = (11^{1}\mod(53) \times 11^{1}\mod(53))\mod(53) = 121\mod(53) = 15\)
     • \(11^{4}\mod(53) = (11^{2}\mod(53) \times 11^{2}\mod(53))\mod(53) = 225\mod(53) = 13\)
     • \(11^{8}\mod(53) = (11^{4}\mod(53) \times 11^{4}\mod(53))\mod(53) = 169\mod(53) = 10\)
   • Step 3:
     • \(11^{(8 + 4 + 1)}\mod(53) = (11^{8}\mod(53) \times 11^{4}\mod(53) \times 11^{1}\mod(53))\mod(53)\)
     • \(11^{(13)}\mod(53) = (10 \times 13 \times 11)\mod(53)\)
     • \(11^{(13)}\mod(53) = (1430)\mod(53)\)
     • \(11^{(13)}\mod(53) = 52\)
   • Hence \(11^{(13)}\mod(53) = 52\)

8.6.1. Examples

1. Find \(3^{-1}\mod(31)\) using Fermat’s Little Theorem
   
   • By Fermat’s little theorem, \(3^{30} \equiv 1\mod(31)\)
   • On dividing by 3, you get \(3^{29} \equiv \frac{1}{3}\mod(31)\)
   • \(3^{29} \equiv 3^{-1}\mod(31)\)
   • \(3^{-1} \equiv 3^{29}\mod(31)\)
   • Now you can solve \(3^{29}\mod(31)\) using fast exponentiation method.
2. TODO Compute \(3^{-592} \mod(1831)\) using Fermat’s Little Theorem
   

8.7.1. Examples

1. Find \(6^{24} \mod(35)\) using Euler’s Theorem
   
   • gcd(6,35) = 1, hence they are coprime
   • \(\phi(35) = \phi(5) \times \phi(7) = 4 \times 6 = 24\)
   • Hence \(6^{24} \mod(35) \equiv 1\mod(35)\)
2. Find \(37^{103}\mod(40)\) using Euler’s theorem
   
   • \(37^{\phi(40)}\mod(40) = 37^{\phi(2^{3}) \times \phi(5)}\mod(40) = 37^{16}\mod(40)\)
   • So according to euler’s theorem, \(37^{16} \equiv 1\mod(40)\)
   • \(103 = 6\cdot16 + 7\)
   • So \((37^{16\times6 + 7}) \equiv 1\mod(40)\)
   • So \((37^{16})^{6} \times 37^{7} \equiv 1^{6} \times 37^{7}\mod(40)\)
   • Now the problem reduces to \(37^{7}\mod(40)\)
   • We also know that \(37\mod(40)\) is the same as \(-3\mod(40)\)
   • So \((-3)^{7} \mod(40) = -1 \times 3^{7}\mod(40)\)
   • Now you can use fast exponentiation method (you could have used it for 37 directly too, but this is better).
3. Find \(71^{-1}\mod(100)\) using Euler’s Theorem
   
   • gcd(71, 100) = 1, hence they are coprime
   • \(\phi(100) = \phi(5^{2} \times 2^{2}) = 20 \times 2 = 40\)
   • \(71^{40} \mod 100 = 1\)
   • Find: \(71^{39} \mod 100\)
   • \(71^{1} \mod 100 = 71\)
   • \(71^{2} \mod 100 = 41\)
   • \(71^{4} \mod 100 = 81\)
   • \(71^{8} \mod 100 = 61\)
   • \(71^{16} \mod 100 = 21\)
   • \(71^{32} \mod 100 = 41\)
   • \(71^{32+4+2+1} \mod 100 = 41\times81\times41\times71 \mod 100\)
4. Find \(8^{-1} \mod(77)\)