Compression, Encryption and Hashing

1 Explain how run length encoding compresses data and state one type of data for which it is unsuitable. 4

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

• Runs of identical consecutive values are replaced by the value and a count
• Gives a valid example of the encoding
• It is lossless, so the original is restored exactly
• It is unsuitable for data with few runs, such as a photograph, where it may increase size

Model answer. Run length encoding works by scanning the data for runs of identical consecutive values and replacing each run with a single copy of the value together with a count of how many times it repeated, so a sequence of five As followed by three Bs is stored as 5A3B. It is lossless, because the count contains everything needed to reconstruct the original sequence exactly. It is unsuitable for data that contains few runs of identical adjacent values, such as a photograph, where neighbouring pixels almost always differ slightly. In that case almost every value would be stored with a count of one, so the encoded file would actually be larger than the original.

2 Explain the difference between symmetric and asymmetric encryption. 4

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

• Symmetric uses the same key to encrypt and decrypt
• Asymmetric uses a public key to encrypt and a matching private key to decrypt
• Symmetric is faster but the key must be distributed securely
• Asymmetric solves key distribution because the public key can be shared openly, but it is slower

Model answer. Symmetric encryption uses a single shared key for both encryption and decryption, so both parties must possess the same secret. Asymmetric encryption uses a mathematically related pair of keys: a public key that may be distributed openly and a private key that is never shared, where data encrypted with the public key can only be decrypted with the private one. The practical difference is a trade off between speed and key distribution. Symmetric encryption is considerably faster and therefore suited to encrypting large volumes of data, but it requires the key itself to be transmitted to the recipient by some secure means, and if that transmission is intercepted the encryption is worthless. Asymmetric encryption removes that problem entirely, since the public key can be published without compromising anything, but it is significantly slower, which is why real systems use asymmetric encryption to exchange a symmetric session key and then use that faster symmetric key for the actual data.

3 Describe how a digital signature is created and used to verify a message. 5

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

• A hash of the message is calculated
• The hash is encrypted with the sender's private key to form the signature
• The recipient decrypts the signature using the sender's public key
• The recipient independently hashes the received message
• If the two hashes match, the message is unaltered and came from the private key holder

Model answer. To create a digital signature, the sender first passes the message through a hash function to produce a fixed size digest. That digest is then encrypted using the sender's private key, and the result is attached to the message as the signature. To verify it, the recipient decrypts the signature using the sender's public key, which recovers the original hash value, and separately calculates the hash of the message they actually received using the same hash function. If the two hashes are identical then two things are proven at once: the message has not been altered in transit, since any change would produce a completely different hash because of the avalanche effect, and it genuinely came from the holder of the private key, since no one else could have produced a signature that decrypts correctly with that public key.

4 Explain why passwords should be stored as salted hashes rather than as encrypted values. 5

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

• Hashing is a one way function that cannot be reversed
• Encryption is reversible, so an attacker who obtains the key recovers every password
• Login works by hashing the entered password and comparing the hashes
• A salt is a random value added before hashing
• The salt ensures identical passwords hash differently and defeats precomputed rainbow tables

Model answer. Hashing is a one way function: it is computationally infeasible to recover the original input from the hash, so an attacker who steals the database obtains only hashes and not the passwords themselves. Encryption, by contrast, is reversible by design, which means the system must hold a decryption key somewhere, and an attacker who obtains both the database and that key recovers every password in plain text at once. Authentication does not require the original password to be recoverable: when a user logs in, the system hashes what they typed and compares the result with the stored hash, and a match proves they supplied the right password. Salting adds a random value, unique to each user, to the password before it is hashed, and that salt is stored alongside the hash. This matters because without it two users who chose the same password would produce identical hashes, which is visible information, and an attacker could use a precomputed rainbow table mapping common passwords to their hashes to crack thousands of accounts instantly. With a unique salt per user, every hash is different even for identical passwords, precomputed tables are useless, and the attacker must mount a separate brute force attack against each account individually.

5 Explain why lossless compression must be used for a program file. 3

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

• Every byte of a program file is a meaningful instruction or data value
• Lossy compression permanently discards data
• Removing any part would corrupt the program so it would not run correctly

Model answer. A program file consists entirely of machine instructions and the data they operate on, and every single byte is significant, since there is no redundant detail that a human observer would fail to notice. Lossy compression achieves its size reduction precisely by permanently discarding information judged to be imperceptible, which is a reasonable trade for an image or a piece of audio but is meaningless for executable code. Discarding any portion of a program would corrupt the instruction stream, so the program would either fail to start, crash during execution or, worse, run while behaving incorrectly. Lossless compression must therefore be used, since it reduces the file size by encoding the same information more efficiently and restores it byte for byte on decompression.