Here are presented two conceptually simple ways to communicate securely with a friend over the Internet or some other channel. The first method assumes you are able to share with your friend a common secret key, and thus combines this private key with the message to produce an encrypted stream, hence the appellation of "private key cryptography". The second one relies on a public but authenticated channel (i.e. everyone has access to what is sent and knows for sure the author of every message), for this reason scientists talk about "public key cryptography".

1. Private Key Cryptography in a Nutshell

This pseudo-protocol is based on the one-time-pad (aka Vernam) encryption.

First of all, you need a secret key. To be efficient, it has to be long (because to each byte of the key will be associated one byte of one of your future messages), and white (i.e. the knowledge of some bytes shouldn't provide any information about any other one).

The secret shared key may be generated by something like :

dd if=/dev/urandom of=our-key bs=1024k count=666

Then, you give your friend mano a mano a copy of the file/cd.

Another way to generate a common private key is quantum key distribution, but it won't be discussed here.

An encrypted message is basically :
- a header : the offset o (where to begin to read the key)
- encrypted data, where the i-th character is e.g.
e_i=c_i xor k_o+i

And the decrypted data is consequently :
d_i=e_i xor k_o+i

To summarize : Encrypted = Key xor Message ---> Message = Encrypted xor Key

Once a key is completely used, you need to create another one and transmit it by what I called previously the mano a mano way.

Now how can m friends communicate securely ?
Typically, for peer to peer communication, a total of m(m-1)/2 keys should be created, one for each pair of friends.

For "multicommunication", a total of 2^m-m-1 keys should be created, one for each subset of at least two friends. Each member gets the keys corresponding to the subsets he belongs to, and that makes 2^m-1-1 keys.
A message consists in :
- an identifier telling which key is used (it defines who will be able to read the message)
- the offset
- the encrypted data
The difficulty here is to prevent the same bytes of the key to be used more than once.

If you are not able to share securely a secret key, you may consider asymmetric encryption, but be aware that none of the algorithms relying on it has been proven time-resistant.


Is this some kind of a joke ?

2. Public Key Cryptography in a Nutshell

The concepts behind asymetric cryptography are not intuitive and obvious. Basically, the idea is that if you want to send a private message to Jonas, you will need his public key ; by combining his public key with your clear message, you will produce a box you can make available to everyone, but only he will be able to open it. Conversely, if you want Jonas to send you a private message, you have to communicate him your public key (completely different from his own). He will then send you a box, and only you will be in measure to open it, with your own private key.

Asymetric cryptography : RSA in a nutshell

The RSA algorithm (Rivest-Shamir-Adleman) assumes it is difficult to factorize large numbers.
The goal of this section is to understand the following illustration :


"RSA in a nutshell"
in a nutshell

Two words about arithmetic modulo n

RSA algorithm is based on basic arithmetic. Using Euclid's algorithm, you can show that : ∀ (a,b) ∈ Z² : ∃ (m,n) ∈ Z² / a.n+b.m=1 <=> gcd (a,b)=1 (Bézout's theorem).
Now let's consider the ring (Z/nZ,+,*). The invertible elements for * constitute its group of unities ; we write it (Z/nZ)^*.
A way to characterize the unities is the following. Let â be a member of (Z/nZ).
â∈(Z/nZ)^* <=> ∃ û ∈ Z/nZ / â*û = û*â = 1_n
<=> ∃ (u,k) ∈ Z² / a*u = 1 + k*n
<=> ∃ (u,k') ∈ Z² / a*u + n.k' = 1
<=> gcd (a,n) = 1 In other words, the unities of (Z/nZ,+,*) are the classes for which the representant in [|1,n-1|] is relatively prime with n. A remark is that when n is prime, (Z/nZ)^* = Z/nZ\{0_n} ; in this case (Z/nZ,+,*) is a field, called the Galois field of order n.

We define now Euler's totient function φ on natural integers by saying that φ(n) is the number of natural integers smaller than n and relatively prime with n.
For example, div(12)={1,5,7,11} so φ(12)= 4, if n is prime then φ(n)=n-1, if m and n are coprime, φ(mn) = φ(m) φ(n).
From above, you should get that #(Z/nZ)^*=φ(n).
Therefore we can label the elements of (Z/nZ)^* â₁, â_2,...â_φ(n).
By using the fact that for any â, â(Z/nZ)^* = â{â₁, â₂, ..., â_φ(n)}= {ââ₁, ââ₂, ..., ââ_φ(n)} = (Z/nZ)^*
â₁ â₂ ... â_φ(n) = ââ₁ ââ₂ ... ââ_φ(n) = (â)^φ(n) â₁ â₂ ... â_φ(n)
So : ∀ â ∈ (Z/nZ)^* : â^φ(n) = 1_n

Manufacturing keys

1. Take p and q prime, and compute N = pq.
2. Choose e prime with (p-1)(q-1)
3. From Bézout's theorem, you can find d and k s.t. ed=1+k(p-1)(q-1)

The couple (e,N) is your public key.
If someone wants to send you an encrypted message x, he sents y = x^e mod N.
Using ed = 1+k(p-1)(q-1), you see easily that x^ed = x^{1+k(p-1)(q-1)} = x*(x^(p-1)(q-1))^k
Because φ(N) = φ(pq) = (p-1)(q-1), x^(p-1)(q-1) mod N = 1, that is : x^ed mod N = x.
To decrypt y, you use your private key d, by computing : y^d mod N = x^ed mod N = x
That's it !

Most of the secure requests on the internet are transmitted via Secure Socket Layer (SSL), a protocol based on asymmetric cryptography.
An interesting exercise for the reader is to derive a way to create digital signatures from the RSA cryptosystem (really, try it!).
That's all, folks.

Little Neo, 2005-2007