Compression, encryption and hashing

Run length and dictionary coding, the Caesar and Vernam ciphers, symmetric and asymmetric encryption, and hashing.

A7.9Data representationA level40 min

All three of these transform data with an algorithm. Compression makes data smaller, encryption makes it unreadable without a key, and hashing turns it into a short fixed-size value that cannot be turned back. At GCSE you met lossy and lossless compression, run length encoding and Huffman coding (F8.9), the Caesar cipher (F11.6) and hashed passwords (F11.5). A level adds dictionary coding, the one cipher that cannot be broken, the difference between perfect and computational security, and what hashing is used for.

Lossy and lossless

• Lossless compression reduces the size and lets the exact original be rebuilt. It is essential for text, program code, spreadsheets and the robot's commands: one changed character in LEFT 90 is a different instruction.
• Lossy compression throws away data that people are unlikely to notice, such as detail the eye cannot see in a photo (JPEG) or sounds masked by louder ones (MP3). The original can never be rebuilt, but files become far smaller than lossless methods can manage.

Lossy suits images, sound and video meant for people. Lossless suits anything where every bit matters.

Run length encoding

Run length encoding (RLE) replaces a run of repeated values with one copy of the value and a count. It is lossless.

def rle(row):
    runs = []
    i = 0
    while i < len(row):
        j = i
        while j < len(row) and row[j] == row[i]:
            j = j + 1
        runs.append(str(j - i) + row[i])
        i = j
    return "".join(runs)

for row in ["WWWWWWWWWWBBBWWWWWWWWWWWWB", "WBWBWB"]:
    packed = rle(row)
    print(row, "->", packed, len(row), "->", len(packed))

Run this in the simulator

The first row of a 1-bit image shrinks from 26 characters to 10. The second grows from 6 to 12, because every run has length 1 and each still costs a count. RLE works only when data has long runs: simple graphics, scanned documents, the black background of a robot camera frame. Photos rarely have runs, because neighbouring pixels differ slightly.

Dictionary coding

Dictionary-based compression replaces repeated patterns, not just repeated single values. Each pattern is stored once in a dictionary, and the data becomes a list of references to dictionary entries.

For the text GO LEFT GO RIGHT GO LEFT GO LEFT:

the data is 0 1 0 2 0 1 0 1. Decompression looks each index up and puts the words back, so it is lossless.

Two points examiners like. First, the dictionary must be stored or sent with the data, so it counts towards the compressed size; on a short message it can make the result bigger. Second, the more often a pattern repeats, the bigger the saving, because each repeat costs only one short reference. Real methods such as LZW (used in GIF images) build the dictionary as they go, so the decoder can rebuild the same dictionary without it being sent.

Task: a compressed route

route is a string of words separated by single spaces: FWD <cm> and LEFT <degrees> commands.

1. Write encode(text). The parameter text is a string of words separated by single spaces. It returns a pair: a list of the different words in the order they first appear (the dictionary), and a string of each word's index in that list, separated by single spaces.
2. Write decode(dictionary, encoded), which takes those two values and returns the original string.
3. Print dictionary: <the words separated by spaces>, then encoded: <the encoded string>, then original: <n> characters, encoded: <m> characters using len of route and of the encoded string, then decoded matches: <True or False> comparing the decoded string with route.
4. Drive the decoded route: FWD n is forward(50, distance=n) and LEFT n is turn_left(angle=n), where n is the number after the word.

Build the encoded string with your function; do not type it in.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

route = "FWD 20 LEFT 90 FWD 20 LEFT 90 FWD 20 LEFT 90 FWD 20 LEFT 90"

def encode(text):
    dictionary = []
    codes = []
    return dictionary, " ".join(codes)

def decode(dictionary, encoded):
    return ""

Breaking the Caesar cipher

A cipher's key space is the number of possible keys. The Caesar cipher has only 25 useful keys, so an attacker can simply try them all, a brute force attack:

def caesar(text, key):
    out = ""
    for ch in text:
        if ch.isalpha():
            out = out + chr((ord(ch) - ord("A") + key) % 26 + ord("A"))
        else:
            out = out + ch
    return out

intercepted = "EFCY WPQE LE ESP HLWW"
for key in range(1, 26):
    print(key, caesar(intercepted, -key))

Run this in the simulator

Only key 11 gives English. Even with a larger key space, a cipher that always turns the same letter into the same letter falls to frequency analysis: E is the most common letter in English, so the most common ciphertext letter is probably E.

The Vernam cipher

The Vernam cipher, or one-time pad, combines each character of the plaintext with a character of the key using XOR (lesson A7.5). XOR with the same key byte again restores the original, so the same operation decrypts.

The Vernam cipher offers perfect security, provided the key:

• is truly random,
• is at least as long as the plaintext,
• is used only once, then destroyed,
• is kept secret and shared securely in advance.

Perfect security means the ciphertext gives an attacker no information at all. For any plaintext of the same length there is a key that would produce this ciphertext, so every message is equally likely, and trying every key just produces every possible message. No amount of computing power helps. Reuse the key, and XORing two ciphertexts cancels the key and leaks the XOR of the plaintexts.

Every other cipher in use offers computational security: it could in principle be broken, by trying every key, but it would take so long with current computers that the data would be worthless by then.

Symmetric and asymmetric encryption

• Symmetric encryption uses the same key to encrypt and decrypt (Caesar, Vernam, AES). It is fast. The problem is key exchange: the key must reach the receiver without being intercepted.
• Asymmetric encryption uses a key pair. Data encrypted with someone's public key can be decrypted only with their private key. The public key can be published, so there is no secret to exchange. It is much slower.

In practice they are combined: asymmetric encryption is used to send a randomly chosen symmetric key, and that fast symmetric key encrypts the rest of the session. This is how HTTPS works.

Hashing

A hash function turns data of any length into a fixed-size value, the hash (or digest). A good one is quick to calculate, always gives the same hash for the same input, gives a completely different hash for a tiny change, and is one-way: you cannot work back from the hash to the data. Hashing is not encryption, because there is no key and no way back.

import hashlib

for password in ["bugbot", "Bugbot"]:
    print(password, hashlib.sha256(password.encode()).hexdigest())

Run this in the simulator

Uses of hashing:

• Storing passwords. The system stores only the hash. At login it hashes what was typed and compares hashes. A stolen table of hashes does not reveal the passwords. A random salt added to each password first means two users with the same password get different hashes.
• Checking integrity. A download site publishes a file's hash; if your copy's hash matches, the file was not corrupted or altered.
• Hash tables. Hashing a key gives the position to store it in an array, so it can be found again in one step instead of by searching.

Because many inputs map to a limited number of hashes, two inputs can give the same hash, a collision. With a toy hash into 16 slots, LEFT and BACK collide:

def toy_hash(text, size=16):
    h = 0
    for ch in text:
        h = (h * 31 + ord(ch)) % size
    return h

for word in ["GO", "STOP", "LEFT", "RIGHT", "BACK", "WAIT"]:
    print(word, toy_hash(word))

Run this in the simulator

A hash table must handle collisions; a cryptographic hash is designed so that finding one is computationally infeasible.

Task: a one-time pad

KEY is a list of 10 whole numbers from 0 to 255.

1. Write vernam(data, key). Both parameters are lists of whole numbers from 0 to 255. If key is shorter than data, raise a ValueError. Otherwise return a new list, the same length as data, in which each item is data[i] XOR key[i].
2. Turn "MEET AT B4" into a list of character codes with ord, encrypt it with KEY, and print cipher: followed by each byte as two uppercase hex digits (for example format(b, "02X")), separated by single spaces.
3. Decrypt the ciphertext with the same function and key, turn the codes back into text with chr, and print decrypted: <text>.
4. Call vernam on the message with only the first 4 key bytes, KEY[:4]; catch the ValueError and print short key refused.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

KEY = [0x5A, 0x13, 0xC7, 0x88, 0x2E, 0x71, 0xB0, 0x09, 0xF4, 0x3D]

def vernam(data, key):
    return data

Challenges

1. Write an RLE decoder for the format above. What goes wrong if a run is longer than 9?
2. Encrypt two different messages with the same KEY, XOR the two ciphertexts, and compare with the XOR of the two plaintexts. What does this tell an attacker?
3. Use toy_hash as a hash table of 16 slots for ten commands. How will you store two commands that collide?