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**^{2} :
∃ (m,n) ∈ **Z**^{2} / a.n+b.m=1 <=> gcd (a,b)=1 (Bézout's theorem).

Now let's consider the ring (**Z**/n**Z**,+,*). The invertible elements for * constitute its group
of unities ; we write it (**Z**/n**Z**)^{*}.

A way to characterize the unities is the following. Let â be a member of (**Z**/n**Z**).

â∈(**Z**/n**Z**)^{*} <=> ∃ û ∈ **Z**/n**Z** /
â*û = û*â = 1_{n}

<=> ∃ (u,k) ∈**Z**^{2} / a*u = 1 + k*n

<=> ∃ (u,k') ∈**Z**^{2} / a*u + n.k' = 1

<=> gcd (a,n) = 1
In other words, the unities of (**Z**/n**Z**,+,*) 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**/n**Z**)^{*} =
**Z**/n**Z**\{0_{n}} ; in this case (**Z**/n**Z**,+,*) 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**/n**Z**)^{*}=φ(n).

Therefore we can label the elements of (**Z**/n**Z**)^{*}
â_{1}, â_{2,...}â_{φ(n)}.

By using the fact that for any â, â(**Z**/n**Z**)^{*} = â{â_{1}, â_{2}, ..., â_{φ(n)}}=
{ââ_{1}, ââ_{2}, ..., ââ_{φ(n)}}
= (**Z**/n**Z**)^{*}

â_{1} â_{2} ... â_{φ(n)}
= ââ_{1} ââ_{2} ... ââ_{φ(n)}
= (â)^{φ(n) }â_{1} â_{2} ... â_{φ(n)}

So :
∀ â ∈ (**Z**/n**Z**)^{*} : â^{φ(n)} = 1_{n}

#### Manufacturing keys

*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

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

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

And the decrypted data is consequently :

d

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

Now how can

Typically, for peer to peer communication, a total of

For "multicommunication", a total of 2

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.

The goal of this section is to understand the following illustration :

"RSA in a nutshell"

in a nutshell

Now let's consider the ring (

A way to characterize the unities is the following. Let â be a member of (

<=> ∃ (u,k) ∈

<=> ∃ (u,k') ∈

<=> gcd (a,n) = 1

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 #(

Therefore we can label the elements of (

By using the fact that for any â, â(

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

If someone wants to send you an encrypted message x, he sents y = x

Using ed = 1+k(p-1)(q-1), you see easily that x

Because φ(N) = φ(pq) = (p-1)(q-1), x

To decrypt y, you use your

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

Accueil