Data compression and encryption

Welcome to Data Compression and Encryption!

In this chapter, we are going to look at two vital ways we manipulate data. First, we'll learn how to make files smaller so they can be stored and sent more easily (Compression). Then, we'll look at how to scramble data so that only the intended person can read it (Encryption).

These topics are part of the Fundamentals of Data Representation section. This means we are focusing on how bit patterns are changed to be more efficient or more secure.

1. Data Compression

Compression is the process of reducing the size of a file. Why do we do this? Smaller files take up less storage space and, more importantly, they travel faster across the internet!

Lossy vs. Lossless Compression

There are two main "flavours" of compression you need to know:

Lossy Compression: This method reduces file size by permanently removing some of the data. Usually, it removes things that the human eye or ear won't notice.
Example: A JPEG image or an MP3 file. Once you "lose" that data, you can never get the original, perfect version back. Use this when file size is more important than perfect quality.

Lossless Compression: This method reduces file size without losing any information. When you decompress the file, it is bit-for-bit identical to the original.
Example: A ZIP file or a program's source code. You definitely don't want "lossy" compression on a computer program, or it wouldn't run! Use this when every single bit is essential.

Run Length Encoding (RLE)

RLE is a simple form of lossless compression. It works by looking for "runs" of the same data value and replacing them with a single value and a count.

Imagine a simple black and white image represented by bits (where \(0\) is black and \(1\) is white):
\(0000000011111000\)
Instead of storing all 16 bits, RLE would store:
\((8, 0), (5, 1), (3, 0)\)

Key Takeaway: RLE is great for data with lots of repeating patterns (like simple icons or basic diagrams), but it can actually make a file larger if there are no repeating patterns!

Dictionary-Based Methods

This is another lossless technique. The compressor builds a "dictionary" of frequently occurring patterns (like words or phrases) and replaces them with a short binary code or index.

Analogy: Imagine you are texting a friend. Instead of typing "See you later", you type "SYL". Your friend has a "dictionary" in their head that knows "SYL" means "See you later". You've compressed the message!

In a computer, a text file might replace the word "the" (which takes 24 bits in ASCII) with a short index like \(12\). Every time "the" appears, we just store the number \(12\). This saves a massive amount of space in long documents.

2. Encryption

Encryption is the process of encoding a message so that it can only be read by someone who has the correct key to decode it. We start with plaintext (the message you can read) and turn it into ciphertext (the scrambled mess).

The Caesar Cipher

The Caesar cipher is the most basic type of encryption. It works by "shifting" every letter in the alphabet by a fixed number of places.

If our key is a shift of \(n = 3\):
A becomes D
B becomes E
C becomes F ... and so on.

Why is it weak? It is very easy to "crack" using frequency analysis. In English, the letter 'E' is the most common. A hacker can look at your ciphertext, find the most common letter, and guess that it represents 'E', revealing the shift key!

The Vernam Cipher (One-Time Pad)

The Vernam cipher is the "gold standard" of security. It is the only cipher that is mathematically unbreakable, provided it is used correctly.

To be truly secure, the Vernam key (called a one-time pad) must meet these rules:
1. The key must be truly random.
2. The key must be at least as long as the plaintext.
3. The key must never be reused (use once and destroy).
4. The key must be kept completely secret.

How it works (The XOR Operation)

The Vernam cipher uses the XOR (\(\oplus\)) logic gate to combine the bits of the plaintext with the bits of the random key.

If your plaintext bit is \(P\) and your key bit is \(K\), the ciphertext bit \(C\) is calculated as:
\(C = P \oplus K\)

To decrypt it, the receiver simply XORs the ciphertext with the same key again:
\(P = C \oplus K\)

Example:
Plaintext: \(0110\)
Key: \(1010\)
Ciphertext: \(1100\) (Because \(0 \oplus 1 = 1\), \(1 \oplus 0 = 1\), \(1 \oplus 1 = 0\), \(0 \oplus 0 = 0\))

Key Takeaway: Because the key is perfectly random, the resulting ciphertext is also perfectly random. There are no patterns for a hacker to find, making frequency analysis useless!

Quick Review Tips

Don't get confused: Remember that RLE is about repeating data, while Dictionary methods are about frequently occurring data.

Common Mistake: Students often think the Caesar cipher is secure because there are 25 possible shifts. However, a computer can try all 25 shifts in a fraction of a second (this is called a "brute force" attack).

The "Magic" of XOR: Remember that in XOR, if the two bits are the same, the result is \(0\). If the two bits are different, the result is \(1\). This simple logic is what powers the unbreakable Vernam cipher!

Note: For more information on how data is stored before it is compressed, see the chapters on "Information coding systems" and "Representing images and sound".