1.3.1 compression encryption and hashing

compression

• process used to reduce storage space

• meaning you can store more files with the same amount of storage space

• The larger a file, the longer it takes to transfer and so compressing files increases the number of files that can be transferred in a given time.

lossy compression

• reduces the size of a file while also removing some of its information

• could result in a more pixelated image or less clear audio recording

• original file cannot be recovered - as it reduces file size by completely disregarding information

lossless compression

• reduces file size without losing any information

• original file can be recovered from from the compressed version

run length encoding

• method of lossless compression

e.g. AAAAAABBBBBCCC could be represented as A6B5C3

• relies on consecutive pieces of data being the same if there’s little repetition, run length encoding doesn’t offer a great reduction in file size.

dictionary encoding

• lossless compression

• Frequently occurring pieces of data are replaced with an index and compressed data is stored alongside a dictionary which matches the frequently occurring data to an index. The original data can then be restored using the dictionary

data compressed using dictionary compression must be transferred alongside its dictionary. Without a dictionary, the data cannot be used.

encryption

• used to keep data secure when its transmitted

symmetric/asymmetric encryption

symmetric encryption

• both the sender and receiver share the same private key

• they distribute to each other in a process called a key exchange

• This key is used for both encrypting and decrypting data.

important that private key is kept secret

• If key is intercepted during the key exchange then any communications sent can be intercepted/decrypted using the key.

• Asymmetric encryption gets around this issue.

asymmetric encryption

• public and private key used

• public key published anywhere - private key is kept secret

• together = key pair

Asymmetric vs Symmetric

Asymmetric = a single key cannot be used to both encrypt and decrypt communication

• Instead, messages encrypted with the recipient’s public key can only be decrypted with the recipient’s private key, which should only be in the possession of the recipient.

symmetric

• messages can be encrypted with the same key

hashing

process in which an input (called a key) is turned into a fixed size value (called a hash).

how is hashing used

A hash table

• data structure which holds key-value pairs. Formed from a bucket array and a hash function

• used to lookup data in an array in constant time. When data needs to be inserted, used as the key for the hash function and stored in the bucket corresponding to the hash.

• used extensively in situations where a lot of data needs to be stored with constant access times.

e.g. in caches and databases

hash collision

• If two pieces of data (keys) produce the same hash, a collision is said to have occurred.

e.g. in the image above the keys John and Sandra both hash to 02.

to overcome collisions

• storing items together in a list under the hash value,

• or using a second hash function to generate a new hash.

diff between hashing and encryption

in hashing the output of a hash function can’t be reversed to form the key.

• This quality makes hashing useful for storing passwords.

• A password entered by a user can be hashed and checked against the key to see if it is correct,

• successful hacker would only gain access to the keys, which can’t be reversed to gain the passwords.

what should a good hash function have

• low chance of collision

• should provide an output which is smaller than the input it provided - or searching for the hash could take longer than simply searching for the key.