1.3.1 Compression, Encryption and Hashing

Compression

Reduces size by removing redundancy - saves storage, optimises bandwidth range and speeds up data transfer

Lossy Compression

A compression scheme where their generally involves a loss of resolution in parts of the image where experiences shows that it will be least noticed

Lossless Compression

A compression scheme that allows the original images to be recreated

Run Length Encoding

A very simple form of Lossless data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run (best suited to simple images with large areas of the same colour - poor for photographs. Requires enough bits to store the max run length)

Dictionary Coding

A class of lossless data compression algorithms which operate by searching for matches between the text to be compressed and a set of strings contained in a data structure (called the ‘dictionary’) maintained by the encoder (effective for texts with repeated words)

Symmetric Encryption

The oldest and best-known encryption technique. A secret key, which can be a number, a word, or just a string of random letters, is applied to the text of a message to change the content in a particular way. This might be as simple as shifting each letter by a number of places in the alphabet (key must be shared securely, fast and efficient)

Asymmetric Encryption

This method of encryption involves using a pair of keys to encrypt and decrypt a message so that it arrives securely. Initially, a network user receives a public key from a certificate authority (no need to share private key, slower than symmetric encryption)

Hashing

The process of calculating a numeric value from one or more data items. While this value obviously depends on the value of the data items, it need not depend on the meaning attached to them, simply producing a number that is used within the computer

Hashing uses

password storage, indexing and fast searching

Hashing time complexity

O(1)

Hash tables

Stores data as key-value pairs. It is implemented using an array where each array position is a bucket storing the data. It allows direct access to data

Load factor equation

occupied buckets/ total buckets (ideally 0.75)

A good hash function must

Always give the same output for the same key, distribute values evenly, minimise collisions and be fast to compute

Collisions

Occur when different keys produce the same hash value, it is unavoidable in hash tables

Chaining (closed addressing)

A collision resolution where each bucket stores a linked list which store the collided data items, reduces clustering

Linear probing (open addressing)

A collision resolution which stores data in the next free bucket, this can cause clustering

Password hashing

Passwords are stored as hash values, not plain text. The entered password is hashed and compares

Salting

Random data is added before hashing - this prevents rainbow table attacks. The Same passwords would produce different hash values

Rehashing

Creates a larger table and rehashed all keys, reducing collisions. Used when the performance of searching degrades

Plain text

Readable data

Cipher text

encrypted data

Cipher

encryption algorithm

Key

Additional data used by an encryption algorithm

Decryption

converting cipher text back to plain text