1. 3. 1 Compression, Encryption and Hashing

Question 1

Lossy Vs Lossless Compression

Answer 1

• Compression is a process to reduce storage space of a file
• Allows for more files in the same amount of storage space
• More files can be shared at a given time, quicker share times
• Lossy reduces the file size by permanently removing some info
• Leads to lower quality of image but a lot smaller file size
• Lossless reduces the file size without losing any information
• The original file can be recovered when lossless is used, not possible when lossy used

Question 2

Run Length Encoding (Lossless Method of Compression)

Answer 2

• Repeated values are removed and replaced with one occurrence followed by number of times it should be repeated
• AAABBBBCC –> A3B4C2
• Relies upon repeated data to work well, little repetition smaller reduction of file size

Question 3

Dictionary Encoding (Lossless Method of Compression)

Answer 3

• Frequently occurring data replaced with index, compressed data stored in dictionary
• Dictionary matches stored data to index, used to restore original data
• Example shown in image
• Compressed data must be transferred alongside its dictionary, without it, it cannot be used

Question 4

Encryption

Answer 4

We encrypt data to keep it secure as it is being transmitted. Two types symmetric and asymmetric encryption.

Question 5

Symmetric Encryption

Answer 5

• Sender and receiver share same private key
• Distribute to each other in key exchange process
• Key used for both encryption and decryption of the data being transmitted
• Private key must be kept secret
• If key intercepted during key exchange, any communications sent can be intercepted and decrypted using the key

Question 6

Asymmetric Encryption

Answer 6

• Two keys are used, public and private key
• Public available to everyone, private is kept secret
• Together known as key pair, mathematically related
• Messages are encrypted with recipient’s public key, only decrypted with recipient’s private key
• Private key is only in possession of the recipient
• If someone wants to send you a message they encrypt it with your public key, this means only you can decrypt it
• To prove message sent by you, can encrypt it using private key
• Anyone can therefore decrypt it, guarantees you encrypted that message
• This forms basis of digital footprint

Question 7

Hashing

Answer 7

• Process in which an input (key) is turned into a fixed size value (hash)
• Remember hashes are as seen below in image (02 not 2)
• Some algorithm called Hash functions do this process (hashing)
• A hash function cannot be reversed to form the key
• Useful for storing passwords
• Password entered by user (Key) can be hashed and checked against stored key to see if its correct
• Successful hacker would only gain access to keys (useless) therefore good security
• A good hash function should have low chances of collision and should be quick to calculate
• Hash function should also provide an output smaller than the input, otherwise searching for hash could take longer than searching for the key

Question 8

Hash tables

Answer 8

• Hash tables are data structures which hold key value pairs, used to look up data in constant time
• They are formed using a bucket array and a hash function
• When data needs to be inserted, it is used as the key for the hash function, stored in bucket corresponding to the hash
• Used in situations where lots of data is stored with constant access times, for example caches and databases
• If two pieces of data (keys) produce the same hash value a collision has occurred
• Collision showed in image below (Jon and Sandra both have the hash value 02)
• To overcome collisions, items may be stored in a list under the same hash value
• Another method is using a second hash function to generate a new hash