1.3.1 Compression, Encryption and Hashing

what is compression?

the process used to reduce the amount of storage space required by a file

why is compression useful?

• can store more files with less space

• can transfer more files over the Internet in a shorter amount of time

what is lossy compression?

• reduces file size by removing some of its information

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

• not possible to recover original file

what is lossless compression?

• reduces file size without removing any information

• possible to recover original file

what is Run Length Encoding (RLE)?

• a method of lossless encryption in which repeated values are removed and replaced with one occurrence of the data followed by how many times it should be repeated e.g. AAAAAABBBBBCCC becomes A6B5C3

• doesn’t offer great size reduction in files with little repetition

what is Dictionary Encoding?

• a method of lossless compression

• frequently occurring pieces of data are replaced with an index

• compressed data is stored alongside a dictionary which matches the frequently occurring data to an index

• original data can then be restored using the dictionary

what is the purpose of encryption?

keeping data secure when it’s being transmitted

what is the process of symmetric encryption?

• both the sender and receiver share the same private key that they distribute to each other in a key exchange (used for encrypting and decrypting data)

• key must be kept secret as if it is intercepted then any communications sent can be intercepted and decrypted using it

what is the process of asymmetric encryption?

• two keys are used - one public and one private (they are mathematically related to each other)

• public key can be published anywhere for anyone to use, private key must be kept secret

• messages encrypted with the public key can only be decrypted by the private key (private key should only be in possession of recipient)

• to prove a message has been sent by you, you can do the inverse - encrypt with private key so that anyone can decrypt it with the public key (proves it was you because only you have the private key)

• the basis of digital signatures

what is hashing?

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

• done by hash functions

why is hashing different to encryption?

the output of a hash function can’t be reversed to form the key (makes hashing useful for storing passwords)

what are hash tables?

• a data structure that holds data pairs

• formed from a bucket array and a hash function

what are hash tables used for?

• looking up data in an array in constant time

• caches

• databases

what is a collision?

when two pieces of data produce the same hash

how are collisions overcome?

• storing items together in a list under the hash value

• using a second hash function to generate a new hash

what are qualities of a good hash function?

• low chance of collision to prevent two pieces of data having the same value

• quick to calculate to get through more data in less time

• should produce output that is smaller than input provided, otherwise searching for the hash could take longer than searching for the key