Data compression and encryption – A-level Computer Science exam questions with mark scheme

1Core3 marks

A Caesar cipher replaces each letter with the letter a fixed number of places further along the alphabet, wrapping round from Z to A. Spaces are left unchanged.

(a) State what is meant by the term ciphertext. [1]

(b) Encrypt the plaintext HARBOUR using a Caesar cipher with a shift of 5. [1]

Plaintext/the message after it has been encrypted (accept: the encrypted/scrambled form of the data that cannot be understood without the key; ignore references to a specific cipher)(1)
MFWGTZW (all seven letters correct)(1)
MEET AT NOON (ignore spacing errors)(1)
Answer: (a) the encrypted form of the plaintext (b) MFWGTZW (c) MEET AT NOON
Examiner tip: Remember to wrap round: shifting U by 5 gives Z, but shifting W by 5 gives B, not a symbol after Z.

2Core4 marks

The diagram shows a 12 × 5 monochrome bitmap image. Each pixel is either white (W) or black (B).

The image is compressed using run-length encoding (RLE), storing each run as a frequency followed by a colour, e.g. 5W.

(a) Give the RLE for Row 3. [1]

(b) Give the RLE for Row 4. [1]

3W 6B 3W (accept equivalent notation, e.g. 3 W, 6 B, 3 W or (3,W)(6,B)(3,W))(1)
12B (accept 12 B or (12,B))(1)
The colour changes at every pixel / there are no consecutive pixels of the same colour / each run has length 1(1)
So 12 frequency–colour pairs would be needed, which takes more space than the 12 original pixels (accept: the compressed version would be larger than the original)(1)
Answer: (a) 3W 6B 3W (b) 12B (c) every run has length 1, so 12 pairs are needed: more data than the original
Examiner tip: RLE only helps when the data contains long runs of repeated values; say what happens to the size, not just that it 'does not work'.

3Standard4 marks

A Vernam cipher is used to encrypt the single character K, whose 8-bit ASCII code is 01001011.

The key for this character is 11010110.

(a) Calculate the 8-bit ciphertext. Show your working. [2]

(b) Show how the recipient obtains the plaintext from the ciphertext. [1]

(c) State one requirement of the key, other than being used only once, needed for the Vernam cipher to have perfect security. [1]

Plaintext XORed with the key bit by bit (method shown, e.g. bits aligned with XOR / ⊕ stated)(1)
10011101(1)
XOR the ciphertext 10011101 with the same key 11010110 to give 01001011 (= K) (must show/state the same key is used)(1)
The key must be truly random (accept: generated from a truly random source, e.g. physical/natural phenomenon; reject: pseudo-random) or at least as long as the plaintext(1)
Answer: (a) 10011101 (b) 10011101 XOR 11010110 = 01001011 = K (c) key truly random / at least as long as the message
Examiner tip: XOR gives 1 only when the two bits differ; students who 'add' the bits lose both marks in (a).

Stuck on Data compression and encryption?

Get it sorted in a free 30-minute session

We work through your weakest questions on this topic on Zoom. I reply the same day.

Free 30-min session on this topic Send me 5 questions a day

4Standard5 marks

A dictionary-based compression method replaces each word in a message with its index in a dictionary. Spaces are not stored in the compressed data because every word is separated by a single space.

The message is:

RED CAR RED VAN BLUE CAR RED VAN

The dictionary is:

Index	Word
0	RED
1	CAR
2	VAN
3	BLUE

(a) Give the compressed message as a sequence of indices. [1]

(b) The uncompressed message is stored using 8-bit ASCII, including the spaces. Calculate its size in bits. [1]

(c) Each index is stored using the minimum number of bits. The dictionary must be sent with the data, with each letter of each word stored in 8-bit ASCII (ignore any separators). Calculate the total size of the compressed data plus dictionary, in bits. [2]

(d) Explain why dictionary-based compression usually achieves a greater saving on longer files. [1]

0 1 0 2 3 1 0 2(1)
32 characters × 8 = 256 bits(1)
Indices: 2 bits each × 8 words = 16 bits (accept 4 values so 2 bits per index)(1)
Dictionary 13 characters × 8 = 104 bits, total = 120 bits (follow through from incorrect bits per index)(1)
The dictionary is a (fixed) overhead that is only stored once, but words are repeated more often in longer files, so each repetition saves more data overall (accept: more repeated patterns/words to replace with short indices)(1)
Answer: (a) 0 1 0 2 3 1 0 2 (b) 256 bits (c) 120 bits (d) dictionary overhead stored once; more repeats in longer files
Examiner tip: Do not forget to count the spaces in the original message, and to include the dictionary in the compressed size.

5Standard4 marks

Four files were compressed and then decompressed. The table shows the results.

File	Contents	Original size	Compressed size	Decompressed file identical to original?
A	song.wav	42.0 MB	3.8 MB	No
B	game.py (source code)	96 KB	31 KB	Yes
C	scan.bmp	6.0 MB	1.5 MB	Yes
D	clip.mov	250 MB	40 MB	No

(a) Identify the files that were compressed using lossy compression. [1]

(b) Calculate the percentage reduction in size for file C. [1]

A and D (both needed, no extras)(1)
75% ((6.0 − 1.5) ÷ 6.0 × 100)(1)
Lossy compression permanently removes some data / the decompressed file would not be identical to the original(1)
Any change to source code (e.g. a missing or altered character) would change its meaning / cause syntax errors so the program would not run or would behave incorrectly (accept: every character of a program is significant)(1)
Answer: (a) A and D (b) 75% (c) lossy removes data permanently; any altered character would stop the program working correctly
Examiner tip: The column showing whether the decompressed file is identical is the evidence: lossless always reproduces the original exactly.

6Hard4 marks

A monochrome bitmap image is 64 pixels wide and 48 pixels high. Uncompressed, each pixel is stored using 1 bit.

The image is compressed using run-length encoding. Each run is stored in one byte: 1 bit for the colour followed by a 7-bit unsigned integer for the run length.

(a) Calculate the size of the uncompressed image in bytes. [1]

(b) After compression the image is stored as 150 runs. Calculate the percentage reduction in file size. Give your answer to 1 decimal place. [2]

(c) One part of a different image contains 300 consecutive white pixels. State the minimum number of runs needed to store these pixels. [1]

64 × 48 ÷ 8 = 384 bytes(1)
Compressed size = 150 bytes and reduction = 384 − 150 = 234 bytes (or 150 ÷ 384 × 100 = 39.06%) (follow through from (a))(1)
60.9% (accept 60.94%; follow through from (a))(1)
3 (maximum run length is 2⁷ − 1 = 127, so 127 + 127 + 46)(1)
Answer: (a) 384 bytes (b) 60.9% (c) 3 runs
Examiner tip: Read the encoding format carefully: a 7-bit count can store at most 127, so long runs must be split.

7Hard4 marks

A messaging app currently encrypts data using a cipher whose security relies on computational security. A developer suggests replacing it with the Vernam cipher.

Compare the security provided by the Vernam cipher with that provided by ciphers that rely on computational security. [4]

The Vernam cipher (with a truly random key, at least as long as the message, used only once) is perfectly secure / mathematically proven to be unbreakable(1)
Because every possible plaintext of that length is equally likely for a given ciphertext / the ciphertext gives no information about the plaintext / there is no pattern for cryptanalysis to exploit(1)
Computationally secure ciphers could in theory be broken (e.g. by brute force/trying every key) given enough time and processing power(1)
They are considered secure only because breaking them would take an impractically long time with current computing power (accept: may become breakable as computers/algorithms improve, e.g. quantum computing)(1)
Answer: Vernam: perfect security, ciphertext reveals nothing; computational: breakable in principle, secure only because cracking is infeasible in a reasonable time
Examiner tip: A 'compare' answer must say something about both types; 'Vernam is more secure' alone earns nothing.

8Standard4 marks

An attacker intercepts the following message, which was encrypted using a Caesar cipher (spaces were left unchanged):

UNJEN CQN PJCN XYNW

The attacker knows that the plaintext begins with the word LEAVE.

(a) Determine the shift used and decrypt the whole message. [2]

(b) Explain why the attacker could have decrypted the message even without knowing any of the plaintext. [2]

Shift of 9 (accept 9 forward/right to encrypt, i.e. shift back 9 or forward 17 to decrypt; e.g. L → U)(1)
LEAVE THE GATE OPEN(1)
(b) Identifies a method that needs no plaintext: brute force (trying every shift) or frequency analysis(1)
(b) Explanation of why it works: there are only 25 possible (useful) shifts, so all can be tried quickly and the one giving readable English chosen; or letter frequencies are preserved, so the most common ciphertext letter (here N) is likely to be E, which reveals the shift (accept: patterns such as repeated letters/word lengths are preserved)(1)
Answer: (a) shift 9: LEAVE THE GATE OPEN (b) brute force: only 25 possible shifts, try them all and pick the readable one (or frequency analysis: most common letter N likely to be E)
Examiner tip: Brute force works because the key space is tiny: say the number of possible keys (25).

9Stretch4 marks

Two 2-character messages, P1 and P2, were encrypted with a Vernam cipher, but by mistake the same key was used for both. The ciphertexts are:

C1 = 11110010 00100011
C2 = 11111101 00100101

An attacker discovers that P1 is GO. The ASCII code for A is 65 (01000001) and letters are in alphabetical order.

(a) Recover the key, showing your working. [2]

(b) Use the key to find P2. [1]

P1 in binary: G = 01000111, O = 01001111, XORed with C1 (method)(1)
Key = 10110101 01101100(1)
P2 = C2 XOR key = 01001000 01001001 = HI (accept binary with correct letters; follow through from incorrect key for binary only)(1)
C1 XOR C2 = P1 XOR P2 (the key cancels out), so knowing one plaintext (or patterns in the plaintexts) reveals the other / the key is no longer secret for the second message (accept: perfect security requires each key to be used only once)(1)
Answer: (a) key 10110101 01101100 (b) HI (c) C1 XOR C2 = P1 XOR P2, so knowing P1 reveals P2
Examiner tip: XOR is its own inverse: ciphertext XOR plaintext gives the key, which is why a one-time pad must be used only once.

10Stretch5 marks

The algorithm below performs run-length encoding on a string. Strings are indexed from 0 and + concatenates strings.

Text ← "KKKZZWWWW"
Output ← ""
Count ← 1
FOR i ← 1 TO LEN(Text) - 1
  IF Text[i] = Text[i - 1] THEN
    Count ← Count + 1
  ELSE
    Output ← Output + INT_TO_STRING(Count) + Text[i - 1]
    Count ← 1
  ENDIF
ENDFOR
Output ← Output + INT_TO_STRING(Count) + Text[LEN(Text) - 1]
OUTPUT Output

(a) Complete a trace table with columns i, Text[i], Count and Output, showing the values at the end of each iteration of the FOR loop, and state the value that is output. [3]

(b) When the same algorithm is run on the string "111222" it outputs "3132". Explain why this is a problem, and suggest how the output format could be changed to fix it. [2]

Count column correct: 2, 3, 1, 2, 1, 2, 3, 4 for i = 1 to 8(1)
Output column correct: "" for i = 1–2, "3K" for i = 3–4, "3K2Z" for i = 5–8 (ignore repeated values written only on change)(1)
Output: 3K2Z4W(1)
The encoded data cannot be decoded unambiguously because counts can have more than one digit and digits in the data cannot be distinguished from counts, e.g. 3132 could mean three 1s then three 2s, or 313 copies of the character 2 (accept: decoding may give the wrong string)(1)
Suitable fix, e.g. use a separator/delimiter between count and character, store the count in a fixed-length field (e.g. one byte), or always put the character before a fixed-width count(1)
Answer: (a) i=1..8; Count 2,3,1,2,1,2,3,4; Output '', '', 3K, 3K, 3K2Z, 3K2Z, 3K2Z, 3K2Z; output 3K2Z4W (b) digits in the data cannot be told apart from (multi-digit) counts, e.g. 3132 could be 111222 or 313 2s; use a delimiter or fixed-length count
Examiner tip: Trace only the values at the end of each iteration and remember the final run is added after the loop ends.

Stuck on this topic?

Book a free 30-minute session on WhatsApp and we'll find exactly which step is costing you the marks. Or build a timed paper on it.

Free 30-minute session