3.1 Compression, Encryption & Hashing

Question 1

What is compression?

Answer 1

The process used to reduce the storage space required by a file by removing unnecessary or insignificant detail.

Question 2

What are the 2 main advantages of compression?

Answer 2

Increases the number of files that can be stored in the same amount of storage space

Increases the number of files that can be transferred in a given amount of time

Question 3

What are the 2 types of compression?

Answer 3

lossy
lossless

Question 4

What is the difference between lossy/lossless compression?

Answer 4

Lossy compression reduces the size of a file while removing some information whereas lossless compression reduces file size without removing any information.

Question 5

What are the advantages/disadvantages of lossy compression?

Answer 5

advantages -
- reduces file size more than lossless

disadvantages -
- original file can not be restored
- some quality may be lost

Question 6

What are the advantages/disadvantages of lossless compression?

Answer 6

advantages -
- no quality lost
- original file can be restored

disadvantages -
- reduces file size less than lossy

Question 7

What are 2 methods of lossless compression?

Answer 7

run length encoding
dictionary encoding

Question 8

What is run length encoding?

Answer 8

A method of lossless compression in which repeated values are removed and replaced by 1 occurrence of the value followed by the number of times it repeats.

Question 9

What would happen to AAAAAABBBBBCCC with RLE?

Answer 9

It would become A6B5C3

Question 10

What is dictionary encoding?

Answer 10

A method of lossless compression in which frequently occurring pieces of data are replaced with an index. Each piece of data is matched to its index in a dictionary.

Question 11

What is the disadvantage of run length encoding?

Answer 11

Relies on consecutive pieces of data being the same i.e. lots of repetition, otherwise there is little reduction in file size.

Question 12

What is the disadvantage of dictionary encoding?

Answer 12

If the data is transferred, its dictionary must be transferred alongside it for the original file to be obtained.

Question 13

What is encryption?

Answer 13

Scrambling data with a specific cipher algorithm so that it can not be understood unless reverted back to the original data with the correct decryption key/algorithm.

Question 14

What are 2 types of encryption?

Answer 14

symmetric
asymmetric

Question 15

How does symmetric encryption work?

Answer 15

The sender and receiver share the same private key which is distributed between them in a key exchange. This key is used to encrypt and decrypt the data.

Question 16

What is the problem with symmetric encryption?

Answer 16

It requires the sender to transfer the key to the receiver. If the key is intercepted alongside the data, then it can be unscrambled and made sense of.

Question 17

How does asymmetric encryption work?

Answer 17

The receiver has a public key that can be used to encrypt data and a private key that can be used to decrypt data. The sender can use their public key to encrypt data before sending it but only the receiver has the private key to unscramble the data.

Question 18

How can asymmetric encryption be used to prove that you sent a message? (digital signatures)

Answer 18

If you encrypt a message with your private key, then anybody can decrypt that message with your public key proving that you sent it.

Question 19

What is hashing?

Answer 19

When an irreversible hash function/algorithm is applied onto a key/input to produce a fixed size value known as a hash.

Question 20

What are 3 uses of hashing?

Answer 20

hash tables
password storage
digital signatures

Question 21

How is hashing useful for password storage?

Answer 21

Only hashes of the passwords should be stored. When a user enters their password, the hash function should be applied onto it and then the hash produced should be checked against the hash that is stored to see if they match. However, a hacker can’t find the users passwords as the hashes can’t be reversed back to the original input.

Question 22

What is a hash table?

Answer 22

An abstract data structure which holds key value pairs and is used for indexing/retrieval of data.

Question 23

What is a collision?

Answer 23

When 2 different pieces of data produce identical hashes.

Question 24

How can collisions be overcome?

Answer 24

Store items together in a linked list at the location of that hash. (chaining)

Store the item in the next available location in the hash table. (linear probing)

Use another hash function to generate a new hash whenever there is a duplicate.

Question 25

What are 2 features of a good hash function?

Answer 25

low chance of collision
quick to produce/calculate hashes

also -
hash should be smaller than the original input

Question 26

How is hashing used for digital signatures alongside asymmetric encryption?

Answer 26

A encrypts the message with B’s public key

A generates a hash of the message

A encrypts the hash with A’s private key

B decrypts the message with B’s private key

B decrypts the hash with A’s public key

B hashes the message and checks if it matches with the decrypted hash

This proves that the message is uncorrupted and that the sender is who they claim they are.