# TP1
## Ex1
L’objectif de cet exercice est de chiffrer une image en ligne de commande  à
l’aide des outils fournis par la librairie openssl.

1. Prenez une image de votre choix et convertissez la dans le format ppm à l’aide de la commande
`convert`.

2. Avec la commande `head`, mettez les 3 premières lignes de votre fichier ppm dans un fichier
header.txt.

3. Avec la commande tail mettez tout le fichier ppm sauf les 3 premières lignes dans un fichier
body.bin.

4. Chiffrez avec openssl en AES-ECB le fichier body.bin.
5. Remettez l’en-tête header.txt au début du fichier obtenu à la question précédente pour avoir
une image chiffrée, et observez le résultat.

## EX2
Le but est d'implanter un registre à décalage linéaire, sur un octet. 


À chaque étape, le registre (un octet) $(b_7,b_6,b_5,b_4,b_3,b_2,b_1,b_0)$ est décalé à gauche, et 
le bit $b_0$ est remplacé par un bit,  calculé par une fonction linéaire $f$.



Vous disposez d'un  [fichier](src/ex1/file.crypt) crypté avec un  lfsr, en faisant
un XOR  de chacun des  octets avec les  valeurs successives du  registre. L'état
initial du registre était `0xa7`, et la fonction utilisée



$$	f(b_7,b_6,b_5,b_4,b_3,b_2,b_1,b_0) = b_7\oplus b_6\oplus b_5\oplus b_4\oplus b_3\oplus b_1 $$

Retrouver le fichier initial.

Vous pouvez utiliser la fonction interne `__builtin_parity` de `gcc`.


## EX3 (si vous avez tout fini)

eXtended Tiny  Encryption  Algorithm est  un  algorithme  de chiffrement  symétrique  par
bloc. les  algorithmes de chiffrement  sysmétrique par bloc  crypte/decrypte des
**blocs** entiers,  en utilisant la  même clé  secrète (symétrique). XTEA  est un
exemple simple de  tels algorithmes (DES, AES, Blowfish) facile  à implanter. La
plupart de ces algorithmes utilise ce que l\'on appelle un réseau de Feistel.

##### Réseau de Feistel

Désignons par $K$ la clé (un mot binaire). On décompose le bloc à
crypter en 2 moitiés $(L_0,R_0)$ On lui applique une
transformation de la forme  :

\[
(L_0,R_0) \rightarrow (L_1,R_1)
 \, où  \,
\left\{\begin{matrix} L_1 & = & R_0 \\ 
R_1 & = & L_0 + f(R_0,K) 
\end{matrix}\right.
\]


-   La loi $+$ doit simplement être "réversible" (une loi de
    groupe). Dans la pratique, il s'agit souvent d'un xor, mais pour
    TEA, il s\'agit de l'addition binaire.
-   La fonction $f$ n'a pas besoin d'être inversible pour que la
    transformation précédente soit réversible. 

	Pourquoi ? Comment fait-on ?
-   Le chiffrement consiste alors à itérer la transformation (appelée
    round) un certain nombre de fois.

<div align="center">
<img src="./img/feistel.png">
</div>

##### XTEA

XTEA (cf cours) crypte des blocs de 8 octets, en utilisant une clé de 16 octets.

Un cycle (2 rounds, itéré 32 fois) de XTEA est donné par le réseau
suivant :
<div align="center">

<img src="./img/xtea.png">
</div>

En vert, il s'agit de l'addition binaire sur 32 bits, en rouge le xor.

-   la clé est décomposée 4 sous-clés $K[0],K[1],K[2],K[3]$.
-   chaque round utilise un multiple de $\delta = ( \sqrt{5} - 1 ) * 2^{31}$  pour rendre les rounds non symétriques.

Voici un exemple de code correspondant :
```c
void encrypt(uint32_t v[2], uint32_t const key[4]) 
{
	unsigned int i;
	uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
	for (i=0; i < 32; i++) {
		v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
		sum += delta;
		v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
	}
	v[0]=v0; v[1]=v1;
}
```


##### Padding (bourrage)

Lorsque l'on cherche à crypter un fichier, sa taille n'est pas
toujours un multiple de la longueur des blocs chiffrés par
l'algortihme. Il existe différentes techniques dites de padding. Nous
utiliserons celle-ci :

-   Si le dernier bloc à chiffer du fichier n'est pas entier, on écrit
    dans son dernier octet le nombre d'octets manquants. Les octets
    précédents peuvent être zéroifiés, ou remplis aléatoirement.
-   Si le dernier bloc est entier, on rajoute tout un bloc pour qu'il
    n'y est pas d'ambiguité.

Voici un exemple avec des blocs de taille 8 octets. Le fichier en entrée
est
```
ascii : hello word!
hex : 68 65 6c 6c 6f 20 77 6f 72 6c 64 21
```

Le dernier bloc est
```
ascii : ord!
hex : 72 6c 64 21 00 00 00 04
```

On ajoute des zéros (ou des octets aléatoires), et le dernier est le
nombre d'octets ajoutés (ici, 4). Si le dernier bloc est complet, on
rajoute tout un bloc.

```
hex : 00 00 00 00 00 00 00 00 08
```

##### Votre travail

1. Ecrire une fonction qui decrypte un bloc.
2. Ecrire une commande **xtea** qui permet de (dé)chiffrer un fichier.

    ```bash
    xtea -e|-d filekey file1 file2
    ```

   - `filekey` est le fichier ou est stocké la clé. Vous pouvez en
       générer en utilisant le pseudo fichier `/dev/urandom`, et la
       commande `dd`.
   - l'option `-e` crypte. `file1` est alors le fichier à crypter,
      `file2` le fichier crypté.
   - l'option `-d` decrypte. `file1` est alors le fichier crypté, `file2`
      le fichier decrypté.  
3. Testez avec cette [clé](./src/ex2/key1.k), et ce [fichier
    crypté](./src/ex2/fichier.crypt) sur une architecture little-endian.

4. Écrire une version de tea en mode CBC :

    ```bash
    xtea_cbc -e|-d iv filekey file1 file2
    ```
    
   `iv` est le vecteur d'initialisation (8 octets) donné sur la ligne de commande.

   **Rappel** : en mode CBC, le bloc à chiffrer subit un XOR avec le chiffré du bloc précédent. Le vecteur d'initialisation sert 
   pour le premier bloc.

## Ex4: une fonction de hachage cryptographique avec XTEA

Une fonction de hachage cryptographique  permet de "résumer" un
fichier, message en calculant une empreinte. Une telle fonction,
mathématiquement, peut-être formalisée par 

\[
	\begin{matrix}
\{0,1\}^{*} & \rightarrow & \{0,1\}^n \\ 
m &\rightarrow & f(m) \end{matrix}

\]

$n$ est la taille de l'empreinte. Elle vaut 128 par exemple pour MD5 et SHA-1.

Grâce à XTEA, on va construire une telle fonction pour avec $n=64$.

Voici le principe.

-   Le message ou fichier est décomposé en bloc de 24 octets (on bourrera
    le dernier bloc suivant le pricincipe déjà vu en ajoutant des octets
    avec la valeur du nombre d'octets ajoutés).
-   Chaque bloc est vu comme un bloc suivi d'une clé de XTEA $x,k$
    (bloc $x$ de 8 octets, clé $k$ de 16 octets). On calcule
    $hash = xtea(x,k) \oplus x$.
-   On combine le hash du bloc courant avec le hash du bloc précédent à
    l'aide d'un xor. Le hash finale est l'empreinte.

##### Votre travail

1. Implantez le fonction prédente. Testez-là. Vérifiez que pour un message
"assez proche", l'empreinte est "vraiment" différente.


