Compression, Encryption and Hashing

1 The data AAAAABBBCCDDDDDD is stored using run length encoding. Show the result of encoding it, and state one disadvantage of run length encoding. 4

One mark for each of the following, to a maximum of 4.

• Counts the runs correctly: 5 A, 3 B, 2 C, 6 D
• Encoded result 5A3B2C6D (a count and a character for each run)
• Disadvantage: where there are few or no repeated characters the data can become larger
• So it is only effective on data containing long runs of the same value

Model answer. The data has a run of 5 As, then 3 Bs, 2 Cs and 6 Ds, so it is encoded as 5A3B2C6D. One disadvantage is that where the data has few or no repeated characters, each single character is replaced by a count and the character, so the encoded data can be larger than the original. It is only effective for data that contains long runs of the same value.

2 Explain two differences between lossless compression and lossy compression. Give an example of a file type for which each is suitable. 4

One mark for each of the following, to a maximum of 4.

• Lossless allows the original data to be rebuilt exactly, but lossy permanently removes some data
• Lossy files are usually much smaller than lossless
• An example where lossless is needed: text, program or data files (or PNG)
• An example where lossy is suitable: photographs, music or video (JPEG, MP3, MP4)

Model answer. Lossless compression allows the original data to be rebuilt exactly, whereas lossy compression permanently discards some of the data so that the original cannot be recovered. Lossy compression can usually reduce a file to a much smaller size than lossless compression. Lossless compression is needed for files such as text documents and programs, where any change to the data would damage them. Lossy compression is suitable for photographs, music and video, as in JPEG and MP3 files, where the detail removed is hard for people to notice.

3 The table shows how often each of four characters appears in a message of 8 characters. Describe how a Huffman tree is built for this data, and calculate the total number of bits needed to store the message using Huffman codes of A = 0, B = 10, C = 110 and D = 111. 5

One mark for each of the following, to a maximum of 5.

• The two characters with the lowest frequencies (C and D) are joined first, to make a node with frequency 2
• The process is repeated, always joining the two lowest frequencies, until there is one tree
• Left branches are labelled 0 and right branches 1, and the path from the root gives the code
• Bits used: A 4 x 1 = 4, B 2 x 2 = 4, C 1 x 3 = 3, D 1 x 3 = 3
• Total = 14 bits

Model answer. The two characters with the lowest frequencies, C and D, are joined under a new node with a frequency of 2. The process is repeated, each time joining the two lowest frequencies (B with the CD node, giving 4, then A with that node, giving 8), until there is a single tree. The branches are labelled 0 and 1, and the code for each character is the path from the root to it. The message needs A: 4 x 1 = 4 bits, B: 2 x 2 = 4 bits, C: 1 x 3 = 3 bits and D: 1 x 3 = 3 bits, a total of 14 bits.

4 Explain the difference between symmetric and asymmetric encryption, and describe how asymmetric encryption can be used to send a message that only the receiver can read. 5

One mark for each of the following, to a maximum of 5.

• Symmetric: the same key is used to encrypt and to decrypt
• Asymmetric uses a pair of keys, a public key and a private key
• The sender encrypts the message using the receiver's public key
• Only the receiver's private key can decrypt it
• The private key is never shared, so the problem of sending a key securely is avoided

Model answer. In symmetric encryption the same key is used to encrypt and to decrypt the message, so the key has to be shared securely first. In asymmetric encryption there is a pair of keys, a public key and a private key. To send a message only the receiver can read, the sender encrypts it using the receiver's public key, which anyone is allowed to have. Only the receiver's private key can decrypt the message. The private key is kept secret and never shared, so there is no need to send a secret key across the network.

5 A website stores the passwords of its users. Discuss how the website should protect the passwords in case its database is stolen. 6

One mark for each of the following, to a maximum of 6.

• The passwords should not be stored as plain text, but as a hash
• A hash cannot be reversed, so a thief cannot read the passwords; at login the typed password is hashed and compared
• A unique random salt should be added before hashing, so that identical passwords have different hashes
• The salt defeats precomputed tables of hashes (rainbow tables)
• A slow hashing method (key stretching, such as bcrypt or PBKDF2) makes each guess take longer, slowing brute force attacks
• A reasoned conclusion, such as also requiring strong passwords or two factor authentication

Model answer. The website should not store the passwords as plain text, because a thief with the database could read every one. It should store only a hash of each password. A hash cannot be reversed, and when a user logs in the password they type is hashed and compared with the stored value. A unique, random salt should be added to each password before it is hashed, so that two users with the same password have different hashes and a precomputed table of hashes of common passwords is of no use. A slow hashing method such as bcrypt or PBKDF2, which repeats the hash many times, should be used so that each guess takes a long time and brute force attacks are impractical. To strengthen this further the site should insist on long passwords and offer two factor authentication, because even a well hashed weak password can be guessed.