Compute science—A Level—Comp 1 Topic 14—Compression, Encryption and Hashing
Compression Encryption—Symmetric and Asymmetric
Compression is used to cut down the size of the file which Encryption is used to keep data secure when its being transmitted,
serves multiple benefits such as storing more files with the it works by encoding a message so that it is unreadable by anyone
same amount of storage and for sharing files across the in- except the recipient who will have the key to decrypt the message
ternet as longer files take longer to transfer. back into a readable form.
There are two forms of compression: Lossy and Lossless.
Lossy: Reduces size of the file as well as removing some of its
information which can not be recovered. Used on things
where the loss of some details aren’t impactful such as the
quality of an image.
Lossless: Reduces the size of a file without losing any infor-
mation. When using lossless, the original file can be recov-
ered from the compressed version. Used on things where the
file must have all its information such as word documents.
In symmetric encryption, both the sender and receive share the
same private key, which they distribute to each other in a process
called key exchange. The key is used for both, encrypting and de-
crypting data therefore it is important it is kept secret.
In asymmetric encryption, two keys are used: a public and a pri-
vate key. The public key can be distributed anywhere for anyone to
see while the private key must be kept secret, together they are
known as key pairs. In contrast to symmetric encryption, one key
cannot encrypt and decrypt data.
Run length encoding (RLE) and dictionary encoding To send a message, you would use your private key and
RLE is a form of lossless compression in which repeated val- the recipient's public key, known as a combined encryption key.
ues are removed and replaced with one occurrence of the This can then be used to encrypt the message and then send it.
data followed by how many times it should be repeated. For To decrypt the message, the recipient would then need to use their
example AAABBB can be simplified to A3B3. It relies on con- private key and the copy of the senders public key.
secutive pieces of data being the same, if there is little repe-
tition then it doesn’t reduce the size by much.
Dictionary encoding is a form of lossless compression, fre-
quently occurring pieces of data are replaced with an index
and compressed data is stored alongside a dictionary which
matches the frequently occurring data to the index, the origi-
nal data can then be restored using the dictionary. For exam-
ple: “I will win, I will not lose, I will not give up, I will be the Hashing
best” could be represented as:
Hashing is the name given to a pro-
Index Phrase cess in which an input (called a key)
1 win, 2 lose, 2 give up, 1 be the best is turned into a fixed size value
1 I will (called a hash).
Unlike encryption, the output of a
2 I will not hashing function cannot be re-
versed to form the key.
Data compressed with Dictionary encoding must be trans-
ferred alongside its dictionary otherwise the data cannot be This makes it useful for storing
used. passwords, a password entered by
a user is hashed and checked
against the hash to see if its correct.
A successful hacker will only gain access to the hashes which cannot
be reversed back into the key (passwords).
Hash tables
Hash tables are a data structure with the goal to immediately find an item in a sorted/unsorted list, it uses a hashing function
on a data item to determine its position in a hash table.
Hash tables are used extensively in situations where a lot of data needs to be stored with constant access times. For example, in
caches and databases due to its fast searching speeds.
If two pieces of data (keys) produce the same hash, a collision is said to have occurred. For example, in the image above the
keys John and Sandra both hash to 02. There are a variety of methods to overcome collisions such as storing items together in a
list under the hash value.
A good hash function should have a low chance of collisions and be quick to calculate. Additionally, a hashing function should
produce an output smaller than the input it was provided with otherwise it would take longer than finding the key itself.
Compression Encryption—Symmetric and Asymmetric
Compression is used to cut down the size of the file which Encryption is used to keep data secure when its being transmitted,
serves multiple benefits such as storing more files with the it works by encoding a message so that it is unreadable by anyone
same amount of storage and for sharing files across the in- except the recipient who will have the key to decrypt the message
ternet as longer files take longer to transfer. back into a readable form.
There are two forms of compression: Lossy and Lossless.
Lossy: Reduces size of the file as well as removing some of its
information which can not be recovered. Used on things
where the loss of some details aren’t impactful such as the
quality of an image.
Lossless: Reduces the size of a file without losing any infor-
mation. When using lossless, the original file can be recov-
ered from the compressed version. Used on things where the
file must have all its information such as word documents.
In symmetric encryption, both the sender and receive share the
same private key, which they distribute to each other in a process
called key exchange. The key is used for both, encrypting and de-
crypting data therefore it is important it is kept secret.
In asymmetric encryption, two keys are used: a public and a pri-
vate key. The public key can be distributed anywhere for anyone to
see while the private key must be kept secret, together they are
known as key pairs. In contrast to symmetric encryption, one key
cannot encrypt and decrypt data.
Run length encoding (RLE) and dictionary encoding To send a message, you would use your private key and
RLE is a form of lossless compression in which repeated val- the recipient's public key, known as a combined encryption key.
ues are removed and replaced with one occurrence of the This can then be used to encrypt the message and then send it.
data followed by how many times it should be repeated. For To decrypt the message, the recipient would then need to use their
example AAABBB can be simplified to A3B3. It relies on con- private key and the copy of the senders public key.
secutive pieces of data being the same, if there is little repe-
tition then it doesn’t reduce the size by much.
Dictionary encoding is a form of lossless compression, fre-
quently occurring pieces of data are replaced with an index
and compressed data is stored alongside a dictionary which
matches the frequently occurring data to the index, the origi-
nal data can then be restored using the dictionary. For exam-
ple: “I will win, I will not lose, I will not give up, I will be the Hashing
best” could be represented as:
Hashing is the name given to a pro-
Index Phrase cess in which an input (called a key)
1 win, 2 lose, 2 give up, 1 be the best is turned into a fixed size value
1 I will (called a hash).
Unlike encryption, the output of a
2 I will not hashing function cannot be re-
versed to form the key.
Data compressed with Dictionary encoding must be trans-
ferred alongside its dictionary otherwise the data cannot be This makes it useful for storing
used. passwords, a password entered by
a user is hashed and checked
against the hash to see if its correct.
A successful hacker will only gain access to the hashes which cannot
be reversed back into the key (passwords).
Hash tables
Hash tables are a data structure with the goal to immediately find an item in a sorted/unsorted list, it uses a hashing function
on a data item to determine its position in a hash table.
Hash tables are used extensively in situations where a lot of data needs to be stored with constant access times. For example, in
caches and databases due to its fast searching speeds.
If two pieces of data (keys) produce the same hash, a collision is said to have occurred. For example, in the image above the
keys John and Sandra both hash to 02. There are a variety of methods to overcome collisions such as storing items together in a
list under the hash value.
A good hash function should have a low chance of collisions and be quick to calculate. Additionally, a hashing function should
produce an output smaller than the input it was provided with otherwise it would take longer than finding the key itself.
