Encryption Basics & History
Issues that encryption aims to solve:
- Incorrect relaying of information.
- This has partial solutions.
- Eavesdropping on information.
- This has many solutions.
Solutions to Eavesdropping
- Control your environment such that there is no possibility of eavesdropping.
- Use a different language.
- Speak in code (using different keywords to create plausible deniability).
Solutions for Written Text
- Sealing the message using a seal (not suitable for electronic communications).
- Prevent messages being read by non-recipients:
- Hide the message.
Steganography
This is the hiding of messages in non-secret messages.
- Hide information in the least significant bits of an image or audio file.
Obscurity
Hiding the message is just security through obscurity:
- This is not suitable for e-commerce.
Cryptography
Historical encryption schemes usually fall into two categories:
-
Transposition - change the order and location of symbols.
This technique is not used in modern methods as it often has significant redundant data and involves moving the letters physically.
-
Substitution - replace symbols by other symbols.
Transposition
Scytale
- Make two sticks with the same diameter:
- One for sender, one for receiver.
- To encrypt - wrap the strip of paper around the stick and write on surfaces next to each other:
- Fill other surfaces with random letters or place multiple messages at different starting points.
- To decrypt - wrap the strip of paper around the stick and read the surfaces next to each-other.
Grille
Similar to Scytale:
- Cut pieces out of paper, making two copies:
- One for sender and receiver.
- Encrypt by placing the paper with holes on top of the empty paper and write on exposed surfaces.
- Continue on open spaces or fill with random letters.
- Decrypt by placing the holes on top of the message and reading the correct letters.
Substitution
Caesar Cipher
- Replace every letter by the same letter shifted by $n$.
This has the following weaknesses:
- Brute-force as there are only 26 encryption keys.
- Known plain-text attack if you know one plain-text, cipher-text, pair then you can find the key.
- Chosen plain-text attack if you can trick the key-holder to encrypt plain-text of your choosing.
- Cipher-text only attack by using frequency analysis.
Information Leakage
Even if you can’t decrypt it you can still see the following:
- Length of the message:
- Can be avoided if you use padding.
- You will always know an upper-bound message of the length even with padding.
- Similar plain-text gives similar cipher-text.
Mono-alphabetic Ciphers
This method replaces every letter with some other letter.
The benefit over Caesar cipher is that:
-
It is not nearly as easy to brute force:
\[\text{keys}=26!\]This is still very easy to brute force with a computer.
Polygraphic/alphabetic Ciphers
- Polygraphic Cipher
- Operate on groups of symbols.
- Polyalphabetic Ciphers
- May encrypt one (group of) symbol(s) into multiple different ones.
Polygraphic Cipher
They encrypt groups of symbols like so:
th is is th em es sa ge
Each grouping of two letter maps onto:
- Different groups of 2 letter.
- A dedicated symbol
The key size for a cipher with group size $n$ is:
\[26^n\]as opposed to 26 for mono-alphabetic.
Compared to the previous ciphers:
- Less vulnerable to known plain-text attack.
- Significantly less vulnerable to cipher text only attacks.
- Less vulnerable to brute force.
- Far more inconvenient.
Many current encryption schemes can be classed as polygraphic ciphers. With RSA $n>512$.
Polyalphabetic Ciphers
Replace one symbol by one other symbol, but not always the same one (like multiple mono-alphabetic ciphers at the same time).
You can create a password by using 26 preset alphabets (schema). The password of length 26 then indicates where to start on each line.
Vignère cipher is an example of this where 26 Caesar ciphers are used in order.
Compared to previous ciphers:
- Brute force is not feasible.
- Known plain-text is somewhat vulnerable.
- Vulnerable to chosen plain-text.
- Practically invulnerable to frequency analysis.
To be secure we need to change the password often otherwise the scheme is only as secure as the key-length of the password.