CS P1 - 1.3.1 - Compression, Encryption and Hashing

What is compression?

Compression is when we reduce the size of a file. This is so that the file takes up less storage capacity, transfer quicker and take up less bandwidth.

What is lossy compression?

These algorithms reduce the file size by selectively permanently deleting some of the data. This means that the original version is different from the compressed version.

What is lossless compression?

This algorithm rearranges the way the file is represented to make it be more efficient. No info. is lost in this process.

Generally not as effective as lossy but required for text and program files.

What are the two types of lossless compression?

Run-length encoding and Dictionary coding

What is run length encoding?

RLE:

- works on the principle that consecutive data being used repeatedly stored is redundant

- A "run" is a sequence of consecutive values

- RLE represents the data using frequency-value pairs

e.g:

aaaaahhh! --> (5,a)(3,h)(1,!)

When is RLE not recommended?

When the data set doesn't have many substantial sequences of consecutive characters (runs). If RLE is used, it will create a frequency-value pair for each character, which causes unnecessary extra space to be taken up.

What is Dictionary coding?

-Works on the principle that groups of values can be substituted with shorter binary codes. A dictionary is also stored with the file, so the decompression can reverse the substitution.

Works best when blocks of data are repeated throughout the file. If not it could increase the file size as the dictionary also needs to be stored.

What are the two types of encryption?

Symmetric and assymetric

What is symmetric encryption?

Symmetric encryption is when the same key is used to both encrypt and decrypt the data being transferred.

remember "Plain text" and "Cipher text"

How can u decrypt without having access to the key?

- Looking for patterns

- Brute forcing -> trying all possible values of the key

What is an encryption algorithm?

The algorithm scrambles data using a key that produces an unintelligible output that, ideally, only those who have the key can reverse.

What is Asymmetric encryption?

Asymmetric encryption uses a key-pair, one key is used to encrypt and the other one is used to decrypt. One key is private and another is public.

The keys are generated by finding 2 random prime numbers, then multiplies them together --> private key. Public key is much shorter, and is mathematically linked to the public key.

You can encrypt using the public key and only decrypt using that private key, and vice versa. If someone else tries then there will be an error.

Symmetric vs Asymmetric

- Symmetric is faster to encrypt/decrypt

- Asymmetric also takes time to generate the keys

- Asymmetric requires a longer key than symmetric to be secure

- However, asymmetric does not require a key to be shared securely.

Often use a hybrid, first generate a symmetric key, use asymmetric to exchange it securely, switch to symmetric now the key is known.

What is hashing?

An algorithm that scrambles data in a way that can't be easily reversed. They should be one-way functions.

Whats a salt in hashing?

A random value that may be also input to reduce predictability.

What are the desirable characteristics of a hashing algorithm?

- Fast to execute

- A variable-length input is mapped to a fixed-length output

- Collision resistant: collision is when 2 different inputs lead to the same output

- Deterministic: same hash from the same input

- Exhibits the avalanche effect: tiny change in the input results in a large change in the output.

What are the uses of hashing algorithms?

- Password verification:

Passwords should be stored as hash values (in a DB), when first entered. The next time the password is entered, it is hashed and verified against the stored hash value.

But an attacker could pre-compute hashes of common passwords. They could also compare them against the hashes in the DB if they got access to it.

- Anti-malware:

Known malware can be hashed and have its hashes stored in a DB. This DB is then sent to the users anti-malware software. Users have safe access.

When a program is detected, its hashed and compared to the DB, if found the malware is deleted. Here the avalanche effect may not be desirable - if the malware changes by a little, we dont want a drastic new hash, we want it to remain similar.