BUT2FI_R4.B.10/td_tp/tp3/README.md

## TP3 

> Le but du tp est de mettre en oeuvre une communication sécurisée entre
> un client et un serveur, en deux phases :
> - Echange d'une clé.
> - Cryptage de la communication par un algorithme de chiffrement
>   symétrique à l'aide de la clé echangée. (XTEA pour ce tp)

[Rappel de cours](../cours/crypto.pdf)

### Diffie-Hellman
<div align="center">
<img src="./dh.png">
</div>



Le système (et sa sécurité) de Diffie-Hellman repose sur la difficulté
pratique, pour des grands nombres, de calculer le logarithme discret
dans un groupe multiplicatif $\mathbb{Z}_{p}^{*}$ avec $p$
premier.

On rappelle que lorsque $p$ est premier, $\mathbb{Z}_{p}^{*}$ est cyclique. Si $g$ est un générateur,
tout élément $x\in \mathbb{Z}_{p}^{*}$ s'écrit (de manière
unique) sous la forme 
\[
x=g^a,\ \ 1\leq a \leq p-1
\]

<!--\\((\\mathbb{Z}_{p}^{\*},.)\\) est ismorphe au groupe additif
\\((\\mathbb{Z}_{p-1},+)\\)-->

Par définition, $a$ est le logarithme (discret) de $x$ dans la
base $g$ noté 
\[
a=\log_{g}(x)
\]

Le schéma en haut de la page illustre comment deux entités peuvent
échangés une clef. Alice génére $p$, un générateur $g$. Il
choisit un nombre aléatoire $a$  ($2\leq a\leq p-2$), et envoie
à Bob le triplet $((p,g,g^a)$. Bob recoit le triplet, et choisit un
nombre $b$. Il envoie à Alice $g^b$. La clé calculée par Alice,
et Bob est 

\|
(g^a)^b = (g^b)^a= g^{ab}
\]

Pour calculer la clé, il faut connaître $ab$. Or seuls $g^a$ et
$g^b$ ont été échangés. Ce qui nous ramène au problème du
logarithme discret qui est difficile en pratique pour des grands
nombres.

##### Votre travail

Le but du tp est d'écrire un client/serveur TCP :

-   Le client et le serveur utilise Diffie-Hellman pour échanger une clé
    sur 16 octets. On utilisera des nombres premiers de Sophie Germain.
-   Le client saisit un message de l'utilisateur, le chiffre avec XTEA,
    et envoit le message chiffré.
-   Le serveur reçoit le message chiffré, le déchiffre, et l'affiche.

1.  Trouver un générateur peut-être long. En effet, tout ce qu'on l'on
    sait sur l'ordre d'un élément de $\mathbb{Z}_p^{*}$, c'est
    qu'il divise l'ordre du groupe, i.e $p-1$. Pour que la
    vérification soit plus rapide, on s'interesse aux nombres premiers
    dit de Sophie Germain. Ils ont la particularité d'être sous la
    forme $2q+1$, avec $q$ premier. Ainsi, l'ordre de
    $\mathbb{Z}_{p}^{*}$ est $2q$. L'ordre possible d'un
    élément ne peut être que $2$, $q$ ou $2q$. Ce qui fait peu (combien) de
    test à effectuer quand on cherche un générateur.

    Ecrire un script à l'aide de la commande `primesieve` qui donne
    tous les nombres premiers de Sophie Germain dans
    $[2^{62},2^{62}+20000]$. (il faut quelques minutes. Assurez-vous
	que votre shell permet de représenter de tels nombres. Comment ?)

2.  Ecrire les [fonctions](src/df.c) suivantes :
	```c
	typedef unsigned __int128 uint128;
	typedef unsigned long long int uint64;

	uint64 expm(uint64 m, uint64 e, uint64 n);
	// calcule m^e modulo n
	uint64 generateur(uint64 p);
	// calcule un generateur de (Zp)*
	// en supposant que p est un nombre premier 
	// de Sophie Germain
	```
    Testez ([test_df.c](src/test_df.c)) avec $p = 4611686018427402023$ pour trouver un
    générateur.



Remarque : pour la génération d'un grand nombre
premier, utilisez le programme `primesieve` qsui se trouve dans

```
/export/documents/info/is1+2/asr
```
.