Software Security - Week 10

Data Privacy

• Encryption is converting data into an unreadable, encoded version accessible only with authorization.
• Decryption reverses encryption, restoring data to its original form.
• Encryption ensures data privacy and confidentiality.
• Algorithms like Data Encryption Standard (DES) and RSA are used for encryption and decryption.

Types of Encryption

• Symmetric Key Encryption/Private Key Encryption: Uses a single key for both encryption and decryption.
• Asymmetric Key Encryption/Public Key Encryption: Uses a pair of keys—one for encryption and another for decryption.

Symmetric Cipher Model

• Encryption Algorithm: Performs substitution and transposition on plaintext, using the plaintext and a secret key to produce ciphertext.
• Secret Key: Input to the encryption algorithm, independent of the plaintext and algorithm.
• Ciphertext: The scrambled message output. Different keys yield different outputs for the same message.
• Decryption Algorithm: Reverses the encryption algorithm, taking ciphertext and the key to produce plaintext.

Basic Symmetric Encryption Techniques

• Substitution: Plaintext letters are replaced by other letters, numbers, or symbols.
• Transposition: The position of letters or bits is changed.

Substitution Technique: Caesar Cipher

• The Caesar cipher is an early and simple substitution method.
• Each letter is replaced by a letter a fixed number of positions down the alphabet.
• Example: With a shift of 2:
  • A becomes C
  • B becomes D
  • C becomes E

Encryption and Decryption

• Plaintext: The original message.
• Ciphertext: The encrypted message.
• Encryption: Represented as En(x) = (x + n) \mod 26
• Decryption: Represented as Dn(x) = (x - n) \mod 26
  • Where:
    • E denotes encryption.
    • D denotes decryption.
    • x denotes the letter's value.
    • n denotes the key value.

Example - Encryption

• Encryption using modular arithmetic (A = 0, B = 1, …, Z = 25).
• Plaintext: ATTACKATONCE
• Key: 4
• Encryption: En (x) = (x + n) \mod 26

| Plaintext Letter (x) | A | T | T | A | C | K | A | T | O | N | C | E |
| :------------------- | :- | :- | :- | :- | :- | :- | :- | :- | :- | :- | :- | :- |
| Letter (x) | 0 | 19 | 19 | 0 | 2 | 10 | 0 | 19 | 14 | 13 | 2 | 4 |
| Key (n) | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| Ciphertext En(x) | E | X | X | E | G | O | E | X | S | R | G | I |

Example - Decryption

• Ciphertext: EXXEGOEXSRGI
• Key: 4
• Decryption: Dn (x) = (x - n) \mod 26

| Ciphertext Letter (x) | E | X | X | E | G | O | E | X | S | R | G | I |
| :-------------------- | :- | :- | :- | :- | :- | :- | :- | :- | :- | :- | :- | :- |
| Letter (x) | 4 | 23 | 23 | 4 | 6 | 14 | 4 | 23 | 18 | 17 | 6 | 8 |
| Key (n) | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| Plaintext Dn(x) | A | T | T | A | C | K | A | T | O | N | C | E |

Advantages and Disadvantages of Caesar Cipher

• Advantages
  • Easy to use in cryptography, providing minimum security.
  • Uses a short key.
  • Suitable for systems with limited computing resources.
• Disadvantages
  • Vulnerable to brute force attacks.

Symmetric Cipher – Playfair Cipher

• A multiple-letter encryption technique using a 5x5 matrix of letters constructed with a keyword.
• Example keyword: MONARCHY

Encryption Rules for Playfair Cipher

1. Repeating plaintext letters should be replaced by a filler (e.g., balloon -> ba lx lo on).
2. Plaintext letters in the same row are replaced by the letter to the right (e.g., ON -> NA).
3. Plaintext letters in the same column are replaced by the letter beneath (e.g., BA -> IB).
4. If plaintext letters are not in the same row or column, they are replaced by the letter in their own row and the column of the other letter (e.g., LO -> PM).

Decryption for Playfair Cipher – Reverse of Encryption

• Plaintext: BALLOON -> BA LX LO ON
• Ciphertext: IB SU PM NA

1. Ciphertext letters in the same row are replaced by the letter to the left (e.g., NA -> ON).
2. Ciphertext letters in the same column are replaced by the letter above (e.g., IB -> BA).
3. If ciphertext letters are not in the same row or column, they are replaced by the letter in their own row and the column of the other letter (e.g., SU -> LX).

Advantages and Disadvantages of Playfair Cipher

• Advantages:
  • Difficult to perform frequency analysis.
• Disadvantages:
  • Vulnerable to frequency analysis attacks (e.g., ciphertext (AB) and its reverse (BA) may have plaintexts UR and RU).

Transposition Techniques – Rail Fence

• Involves permutation of plaintext letters.
• Simplest technique: Rail fence.
• Plaintext is written down as a sequence of diagonals and then read off as a sequence of rows.
• Example: meet me after the toga party, rail fence of depth 2
  • m e m a t r h t g p r y
  • e t e f e t e o a a t
• Encrypted message: MEMATRHTGPRYETEFETEOAAT

Transposition Techniques – Rail Fence (Modified)

• A more complex scheme involves writing the message in a rectangle, row by row, and reading it off column by column, but permuting the order of the columns.
• 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

Transposition Techniques – Complex Permutation

• Key: 4 3 1 2 5 6 7
• Input:
  • t t n a a p t
  • m t s u o a o
  • d w c o i x k
  • n l y p e t z
• Output: NSCYAUOPTTWLTMDNAOIEPAXTTOKZ

Introduction to Public-Key Cryptosystem (Asymmetric Key Encryption)

• Public-key algorithms are based on mathematical functions rather than substitution and permutation.
• It is asymmetric, using two separate keys for encryption and decryption.
• Security relies on the key and algorithm.
• The use of two keys has significant implications for confidentiality, key distribution, and authentication.

Encryption with Public Key

• Ingredients:
  • Encryption algorithm
  • Public and Private Keys
  • Ciphertext
  • Decryption Algorithm
• Steps:
  1. Each user generates a pair of keys.
  2. One key is placed in a public register (public key), and the other is kept private.
  3. To send a message to Alice, Bob encrypts it using Alice’s public key.
  4. Alice decrypts the message using her private key.

RSA - Introduction

• The first algorithm to meet the requirements of public-key cryptosystems.
• Developed in 1977 by Ron Rivest, Adi Shamir, and Len Adleman at MIT.
• Plaintext and ciphertext are integers between 0 and n - 1 for some n.
• A typical size for n is 1024 bits.

The RSA Algorithm: Public and Private Key Generation

1. Select two large prime numbers, p and q.
2. Multiply these numbers to find n = p \times q, where n is the modulus.
3. Calculate \varphi(n) = (p - 1)(q - 1).
4. Choose a number e < n such that gcd(e, \varphi(n)) = 1, i.e., 1 < e < \varphi(n).
5. Calculate d, where d \cong e^{-1} (mod \varphi(n)).
6. Public key PU = {e, n}.
7. Private key PR = {d, n}.

The RSA Algorithm: Encryption and Decryption

• Encryption:
  • Plaintext: M < n
  • Ciphertext: C = M^e \mod n
• Decryption:
  • Ciphertext: C
  • Plaintext: M = C^d \mod n

Example - RSA

• Plaintext: 9
• Key Generation:
  1. Select primes p = 7, q = 11.
  2. n = 7 \times 11 = 77.
  3. \varphi(n) = (7-1)(11-1) = 60.
  4. Select e = 7 (relative prime of 60).
  5. Calculate d, 7d \mod 60 = 1, which gives d = 43.
  6. Public Key {e,n} => { 7,77}
  7. Private Key {d,n} => {43, 77}

Example – RSA Encryption and Decryption

• Encryption:
  • Ciphertext: C = 9^7 \mod 77 = 37
• Decryption:
  • Plaintext: M = 37^{43} \mod 77 = 9

Diffie – Hellman Key Exchange

• Presented by Whitfield Diffie and Martin Hellman in 1976.
• Alice and Bob want to securely communicate over an insecure channel (Eve is eavesdropping).
• How can they share a secret key without Eve's knowledge?

The Diffie-Hellman Key Exchange

• Alice and Bob share a prime number q and an integer \alpha, where \alpha < q and \alpha is a primitive root of q.
• Alice generates a private key X_A < q.
• Alice calculates a public key YA = \alpha^{XA} \mod q.
• Alice receives Bob's public key Y_B in plaintext.
• Alice calculates the shared secret key K = (YB)^{XA} \mod q.
• Bob does the symmetric to compute the same secret key K.

Primitive Numbers

• A primitive root of a prime number p is one whose powers modulo p generate all the integers from 1 to p - 1.

Diffie-Hellman Key Exchange - Example

• Alice:
  • Shares q = 23 and \alpha = 9.
  • Chooses private key X_A = 4.
  • Calculates public key Y_A = 9^4 \mod 23 = 6.
  • Shares Y_A to Bob.
  • Knows Bob's public key Y_B = 16.
  • Finds the secret key K = 16^4 \mod 23 = 9.
• Bob:
  • Shares q = 23 and \alpha = 9.
  • Chooses private key X_B = 3.
  • Calculates public key Y_B = 9^3 \mod 23 = 16.
  • Shares Y_B to Alice.
  • Knows Alice's public key Y_A = 6.
  • Finds the secret key K = 6^3 \mod 23 = 9.