main page

Introduction to Cryptography
```Cryptography comes from the ancient greek meaning: "crypto" = secret, "graphy" = writing.

Let's say that Messi wants to send Pelé a message, but he doesn't want anyone else to see the content of the message.
Messi must send the message to Pelé via a non secure way, like the Internet or via Radio.
However, he is not sure that the message won't be seen by any other person. What if there is a middleman trying to read the secret message?
The solution for Messi is simple: use cryptography!
If he encrypts the message he won't have to worry if someone will get it.
Pelé then needs to decrypt the message to read it.

Some terminology
cryptography: method to send secret messages using a code
crytanalysis: trying to break the code and read those messages
plaintext: message in its original form. very easy to understand its contents
ciphertext: message in coded form
key: mathematical operations we can perform on a value
encryption: transforming PT to CT
decryption: transforming CT to PT
cipher: the method used for encryption
steganography: the practice of hiding information

How do we know if a cryptographic technique is "secure"?
We let lots of smart people try to break it (cryptanalysis).
If they can't, we assume it is secure.

Frequency analysis
Cryptanalysis technique described in the 9th century by Al-Kindi in Iraq.
Not all letters in a language occur with the same frequency.
Some languages have certain characteristics. For example, here are some patterns of the English language:
- E is most common letter
- vowels tend to be separated by consonants
- Q tends to be followed by U
- etc.

Caesar algorithm
Substitute letters by N letters away (e.g. N = 3. A is D, B is E, C is F...)
How do we break it? try all possible values for N.
Example:
A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   X   Y   Z
0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25

Plaintext: 	ATTACK AT DAWN
Key: 		3
Ciphertext:	DWWDFN DW GDZQ

If we try here all the 26 letters we will easily get to the key 3.

Try this cipher here

Vigenére
It's a poly-alphabetic cipher where one plaintext letter can become different ciphertext letters.
It uses a text based key and a modulo arithmetic to perform the encryption.
Using frequency analysis is possible, but much more difficult.
Example:
A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   X   Y   Z
0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25

A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   X   Y   Z
26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51

let's choose a key: MONKEY

Plaintext:	ATTACK AT DAWN
Key		MONKEY MO NKEY

We now add the numbers of the letters and get the result letter
A + M = 0 + 12 = 12	-->>	M
T + O = 19 + 14 = 33	-->>	H
T + N = 19 + 13 = 32	-->>	G
A + K = 0 + 10 = 10	-->>	K
...

Message:	ATTACK AT DAWN
Key:		MONKEY MO NKEY
Ciphertext:	MHGKGI MH QKAL

Vigénere cipher with a randomly chosen key as long as the message.
The key needs to be shared between parties beeforehand and can NEVER be re-used.
Provable unbreakable without the key.
This is the only perfect cryptography.

Example:
A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   X   Y   Z
0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25

A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   X   Y   Z
26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51

Random key: 	FOWIFOZMQOAF

Message:	ATTACK AT DAWN
Key:		FOWIFO ZM QOAF
Ciphertext:	FHPIHY ZF TOWS

All of the previous techniques have two basic components:
- algorithm (what you do to the message)
- key (the secret that you need in order to encrypt/decrypt properly)
When using these algorithms, the key is the secret. The algorithm is public.

More details:
Cryptography (Wikipedia): here
```