3.18 - Data Compression and Encryption Algorithms

Why use compression?

• Reduce the storage space of files on disk

• Allow images to be loaded quickly on a webpage

• Reduce costs on mobile data and ISPs where you are charged for how much data used

• Reduce buffering when streaming videos or music

How does lossy compression generally work?

Removes non-essential information from the data.

How does lossless compression generally work?

Records patterns in data rather than the actual data.

How does Run Length Encoding (RLE) work?

• Instead of storing every value individually, it stores pairs of (frequency, value)

• e.g. for an image: (3, Green), (2, Red), (5, Blue) rather than Green Green Green Red Red Blue Blue Blue Blue Blue

Is Run Length Encoding a form of lossless or lossy compression?

Lossless

When is Run Length Encoding most effective and least effective?

• Most effective when there are long runs of repeated values, such as simple graphics

• Less effective on photographs where pixel colours change frequently

How does Dictionary-Based Compression work?

1. A dictionary is built containing frequently occurring patterns or strings found in the data

2. Each pattern in the dictionary is assigned a shorter code/index

3. The original data is then replaced with these shorter codes, reducing file size

4. The dictionary is stored alongside the compressed data so it can be used to decompress

   e.g. In a text file, the word "the" might appear 500 times - it gets replaced with a short code like 37, saving space each occurrence

Is Dictionary based compression lossy or lossless?

Lossless

What is encryption?

The transformation of data from one from to another to prevent an unauthorised third parry from being able to understand it.

In the context of encryption, what is the original data know as?

plaintext

In the context of encryption, what is the encrypted data know as?

ciphertext

In the context of encryption, what is the encrypted method or algorithm know as?

cipher

In the context of encryption, what is the secret information to lock or unlock the message know as?

key

What is Caesar Cipher also know as?

Shift Cipher

What type of cipher is Caesar Cipher

Substitution Cipher

How does a Caesar Cipher work?

• Shifts each letter in the plaintext by a fixed number of positions along the alphabet

• The number of positions shifted is the key

Decrypt “abq” which has been encrypted with Caesar Cipher with a key of -1.

zap

What is meant by symmetric encryption?

When the same key used to both encrypt and decrypt the data.

What’s the difference between Run Length Encoding and Dictionary-Based Compression?

• RLE exploits repeated consecutive values

• Dictionary compression exploits frequently occurring patterns anywhere in the data, making it more versatile and effective on text files

What are disadvantages of using a Caesar Cipher?

• Only 25 possible keys, making it trivially easy to crack by brute force

• Vulnerable to frequency analysis, a form of cryptanalysis

What class of ciphers is a Vernam Cipher?

one-time pad ciphers

What are the requirements for a one-time pad and how should it be used for perfect security?

• Must be equal to or longer in characters than the plaintext

• Be truly random

• Used once

• Shared in person

• Destroyed after encrypting/decrypting data

Why is a Vernam Cipher not susceptible to cryptanalysis?

• Since the key is random, so will be the distribution of the characters meaning that no amount of cryptanalysis will produce meaningful results

• The key is at least as long as the plaintext, so there are no repeating patterns to exploit

How do do you perform the Vernam Cipher?

• Convert both the plaintext and key into binary

• Align the bits and perform XOR on each pair of bits

• The result is the ciphertext