Compression and Encryption

Question 1

What is the advantages of compression?

Answer 1

• less space required to store information
• more files can be stored
• less bandwidth used in transmission
• reduce congestion
• increased transmission speed
• improves playback with less buffering
• multiple files can be stored in a single archive

Question 2

What is data compression?

Answer 2

Compression software uses algorithms to remove repeated or unnecessary data, to reduce the number of bits/bytes to store the file

Question 3

What files can and cannot be compressed?

Answer 3

• All can be compressed but only some use lossy compression e.g. audio, images
• Text files can be compressed

Question 4

What is the difference between lossy and lossless compression?

Answer 4

Lossy: permanently losing information in order to reduce file size, e.g. reduce resolution in images or sound

Lossless: using algorithms to efficiently represent repeating patterns without losing data e.g. in text and EXE

Question 5

What is run-length encoding?

Answer 5

• reduce file size of a file by removing repeated information by replacing it with one example of what needs to be run followed by the number of times it needs to be run
• not all data suitable if no repeating patterns

Question 6

What are dictionary-based methods?

Answer 6

• Words are stored in a dictionary, each with an index number pointing to it
• The text is then encoded using the dictionary index values to represent each word
• Dictionary must also be sent with the original file
• Works best for long documents with many common words (not short texts with little repetition)

Question 7

What is encryption?

Answer 7

• process of converting plaintext to ciphertext so it is not understandable if intercepted during transmission without the key

Question 8

Define plaintext, ciphertext and cipher.

Answer 8

Plaintext: unencrypted information

Ciphertext: encrypted information

Cipher: encryption algorithm used

Question 9

How does Caesar ciphers work?

Answer 9

• substition cipher / shift cipher where key is distance that each letter is shifted by
• e.g. key of +8 shifts it right 8, with loop from Z to A

Question 10

Why are Caesar ciphers bad?

Answer 10

• not computationally secure
• frequency analysis used to find common letters e.g. many E’s
• finding one gives you whole key
• can use crypt analysis (brute force) to break quickly

Question 11

How do Vernam ciphers work?

Answer 11

1) Align plaintext and key (both in binary and key.Length >= plaintext.Length)
2) Apply logical XOR bitwise on each
3) Convert binary back to characters

Question 12

Why is a Vernam cipher secure?

Answer 12

• key is generated randomly
• cannot be cracked in a reasonable timeframe with current computing power (computationally secure), perfectly secure
• only known computationally secure cipher

Question 13

What is computational security?

Answer 13

If a cipher cannot be cracked within a reasonable timeframe with current computing power, it is computationally secure.

Question 14

Why is the Vernam cipher perfectly secure?

Answer 14

MARK SCHEME:
- Brute force would not work as key is randomly generated, too many possible keys to try all of them (and multiple plaintexts can be derived)
- Different plain text letters can map onto the same ciphertext letter, so frequency analysis does not happen as cipher text letters have uniform probability

Question 15

What is run-length encoding in images?

Answer 15

• Stores the colour of a pixel and a count, where the count is the total numbers of pixels of that pixel’s colour in a run until the next different coloured pixel

Question 16

What conditions must be satisfied for the Vernam cipher to offer perfect security?

Answer 16

1) key must be generated completely at random
2) key must be greater than or equal to the length of the plaintext
3) key must be used only once

Question 17

Describe how run length encoding can be used. (2 marks)

Answer 17

• A run is a sequence/series of pixels of the same colour // the number of consecutive pixels of the same colour would need to be counted;
• (Pairs of values would be stored), which would consist of a run length and the colour of the pixels in the run;
  Example of how the specific row of pixels would be compressed eg 7 Yellow, 4 Blue, 9 Yellow;
  A. assignment of numeric values to colours

Question 18

Explain why run length encoding is not able to compress a photo-realistic image as much as a simple image.

Answer 18

• Photo-realistic images have a larger colour depth meaning each individual run is shorter as colour varies from pixel-to-pixel
• The additional bits required to store the length of each run in the photo-realistic image negate the compressing effect

Question 19

Explain why RLE is more suitable for compressing images and dictionary-based methods are more suitable for compressing text. (2 marks)

Answer 19