Compression, Encryption and Hashing
Run length and dictionary encoding, symmetric and asymmetric encryption, and what a hash is actually for.
Compression
Lossy and lossless
Lossy permanently discards data judged least perceptible, giving very large reductions but no way back to the original. Used for images, audio and video.
Lossless reduces size by encoding the data more efficiently, and the original is restored exactly. Essential for text, program files, spreadsheets and anything where every byte matters.
Run length encoding
Consecutive identical values are replaced by the value and a count.
AAAAABBBCCCCCCCC becomes 5A 3B 8C
- Extremely effective on data with long runs, such as simple graphics with large blocks of one colour
- Can make a file larger if there are few runs, because each single value now needs a count as well
- Lossless
Dictionary encoding
Repeated sequences are replaced with references to an index, and the dictionary is stored with the compressed data so it can be reversed.
the cat sat on the mat, the cat sat Dictionary: 1=the 2=cat 3=sat 1 2 3 on 1 mat, 1 2 3
- Very effective on text, which is full of repeated words
- The dictionary itself takes space, so short files may not benefit
- Lossless, and the basis of ZIP and PNG
Run length encoding suits data with long runs of identical values. Dictionary encoding suits data with repeated sequences that are not adjacent, such as natural language.
- The original file: every byte of the data, nothing thrown away.
- Lossless finds repetition and records it more briefly.
- Unpack it and you get back exactly what you started with.
- Lossy throws data away permanently, and gets much smaller.
- Lossless: the file gets smaller, and decompressing gives back exactly the original.
- Lossy: the file gets much smaller, but detail is thrown away for good, so it cannot be restored exactly.
- Choose lossless when the data must be exact, and lossy when small losses do not matter.
Encryption and hashing
Symmetric encryption
The same key encrypts and decrypts.
- Fast, so suitable for large volumes of data
- The problem is key distribution: the key must reach the recipient securely, and if it is intercepted the encryption is worthless
- With n people all communicating, the number of keys required grows as n(n-1)/2
Asymmetric encryption, public key
Two mathematically related keys. The public key may be distributed freely. The private key is never shared.
- Anything encrypted with the public key can only be decrypted with the private key, so anyone can send you a secure message
- Anything encrypted with the private key can be decrypted with the public key, which proves it came from the holder of the private key. This is a digital signature
- Solves key distribution completely
- Considerably slower than symmetric encryption
How they are used together
In practice HTTPS uses both. Asymmetric encryption is used at the start of the connection to exchange a symmetric session key securely, and all the actual data is then encrypted symmetrically because it is far faster. This takes the security of asymmetric key exchange and the speed of symmetric encryption.
Digital signatures and certificates
- The sender produces a hash of the message.
- The hash is encrypted with the sender's private key, producing the signature.
- The recipient decrypts it with the sender's public key and independently hashes the message.
- If the two hashes match, the message is unaltered and came from the holder of that private key.
A digital certificate issued by a certificate authority binds a public key to an identity, which is what stops an attacker simply publishing a public key claiming to be your bank.
Hashing
A hash function takes an input of any size and produces a fixed size output.
Properties of a good hash function:
- Deterministic. The same input always gives the same output.
- Fast to compute.
- One way. It must be computationally infeasible to recover the input from the hash.
- Avalanche effect. A tiny change to the input produces a completely different hash.
- Collision resistant. It should be extremely difficult to find two inputs with the same hash.
Uses
- Password storage. Store the hash rather than the password. A stolen database does not reveal the passwords. A salt, a random value added before hashing, ensures two identical passwords produce different hashes and defeats precomputed rainbow tables.
- Hash tables. The hash of a key determines the storage index, giving average constant time lookup.
- Integrity checking. Rehash a downloaded file and compare with the published hash to confirm nothing changed.
- Digital signatures, as above.
Encryption is two way and reversible with a key. Hashing is one way by design. You never decrypt a hash, you hash the new input and compare.
- You start with plaintext: the message as anyone could read it.
- A key and an algorithm turn it into ciphertext.
- The ciphertext is what travels, and it is what an attacker sees.
- The right key reverses it. The wrong key gives nothing useful.
- Hashing is different: it is one way, and there is no way back.
- The same hash function turns hello, Hello and a whole book into hashes of the same length. A tiny change gives a completely different hash.
- A hash is the same every time for the same input, cannot be reversed, and is a fixed length.
- Store only the hash of a password. When someone logs in, hash what they typed and compare it with the stored hash.
Key terms you must be able to define
- Lossy compression
- Compression that permanently discards data, giving large reductions but no exact recovery.
- Lossless compression
- Compression that allows the original data to be restored exactly.
- Run length encoding
- Replacing runs of identical consecutive values with the value and a count.
- Dictionary encoding
- Replacing repeated sequences with references to an index stored with the data.
- Symmetric encryption
- Encryption using the same key to encrypt and decrypt.
- Asymmetric encryption
- Encryption using a public key to encrypt and a matching private key to decrypt.
- Key distribution problem
- The difficulty of getting a symmetric key to the recipient securely.
- Digital signature
- A hash encrypted with a private key, proving authorship and that the message is unaltered.
- Digital certificate
- A document from a certificate authority binding a public key to a verified identity.
- Hash function
- A function producing a fixed size output from an input of any size, designed to be one way.
- Salt
- A random value added to a password before hashing so identical passwords hash differently.
- Collision
- Two different inputs producing the same hash value.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
- Explain why run length encoding can increase file size, and on what data it works well
- State the key distribution problem as the reason asymmetric encryption exists
- Explain how HTTPS uses both types together, and why
- Describe the digital signature process in four ordered steps
- Never describe hashing as reversible, and explain salting as defeating rainbow tables
Mistakes that cost marks here
- Saying hashing is a form of encryption. It is one way and cannot be reversed.
- Claiming run length encoding always reduces size. On data with few runs it makes files larger.
- Saying asymmetric encryption is better than symmetric. It is much slower, which is why both are used together.
- Forgetting the salt when discussing password storage.
- Confusing which key does what. Encrypt with the public key for secrecy, with the private key for a signature.
In asymmetric encryption you can publish your public key to the entire world and it still cannot be used to read messages sent to you. Only the matching private key can decrypt them, and deriving one from the other is computationally infeasible.
Knowledge check
Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LRuns of identical consecutive values are replaced by the value and a count
- LGives a valid example of the encoding
- LIt is lossless, so the original is restored exactly
- LIt is unsuitable for data with few runs, such as a photograph, where it may increase size
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.
- LSymmetric uses the same key to encrypt and decrypt
- LAsymmetric uses a public key to encrypt and a matching private key to decrypt
- LSymmetric is faster but the key must be distributed securely
- LAsymmetric solves key distribution because the public key can be shared openly, but it is slower
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.
- LA hash of the message is calculated
- LThe hash is encrypted with the sender's private key to form the signature
- LThe recipient decrypts the signature using the sender's public key
- LThe recipient independently hashes the received message
- LIf the two hashes match, the message is unaltered and came from the private key holder
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.
- LHashing is a one way function that cannot be reversed
- LEncryption is reversible, so an attacker who obtains the key recovers every password
- LLogin works by hashing the entered password and comparing the hashes
- LA salt is a random value added before hashing
- LThe salt ensures identical passwords hash differently and defeats precomputed rainbow tables
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.
- LEvery byte of a program file is a meaningful instruction or data value
- LLossy compression permanently discards data
- LRemoving any part would corrupt the program so it would not run correctly
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.