Worksheet

A7.9 Compression, encryption and hashing

Data representation · A level · OCR H446 1.3.1, AQA 7517 4.5.6.9 · about 40 min

What this lesson is about

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

• Lossy and lossless
• Run length encoding
• Dictionary coding
• Breaking the Caesar cipher
• The Vernam cipher
• Symmetric and asymmetric encryption
• Hashing

Questions 6 marks in all

1. [1 mark]A program's source code is compressed to send it by email. Which kind of compression must be used, and why?

   1. ALossless, because the exact original must be rebuilt
   2. BLossy, because it gives smaller files
   3. CLossy, because nobody reads every character
   4. DEither, because code is text

2. [1 mark]What does this program print?

   row = "AAAABBBCCD"
   out = ""
   i = 0
   while i < len(row):
       j = i
       while j < len(row) and row[j] == row[i]:
           j = j + 1
       out = out + str(j - i) + row[i]
       i = j
   print(out)

3. [1 mark]Which conditions must a Vernam cipher key meet for perfect security?

   Tick every answer that is true.

   1. AIt is truly random
   2. BIt is at least as long as the plaintext
   3. CIt is used only once
   4. DIt is a prime number

4. [1 mark]What does it mean for a cipher to be computationally secure?

   1. AIt could be broken in theory, but not in a useful amount of time with current computers
   2. BIt can never be broken, whatever the computing power
   3. CIt uses a computer to generate a random key
   4. DIt is secure only when run on a computer

5. [1 mark]Why are passwords stored as hashes rather than encrypted?

   1. AA hash is one-way, so a stolen table does not reveal the passwords
   2. BA hash is shorter to type
   3. CA hash can be decrypted by the server when needed
   4. DA hash never has collisions

6. [1 mark]Alice wants to send Bob a message using asymmetric encryption. Which key does she encrypt it with?

   1. ABob's public key
   2. BBob's private key
   3. CAlice's private key
   4. DA key they have both kept secret

The 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 ""

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/a7-9-compression-encryption-and-hashing/
The simulator checks it and tells you when it passes. Nothing to install, no account.

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?