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 are about 40%
- 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


One-time pad
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