---
tags: revision, CRYPI
title : Introduction à la crypto
---

# Introduction
## Lexique
Cryptologie : Science du secret
Cryptographie : Art de rendre inintelligible un message excepté pour son destinataire
Cryptosystème : système permettant la mise en oeuvre de la cryptographie
Cryptanalyse : Analyse de la sécurité d'un cryptosystème

# Prérequis
## Objectifs
Confidentialité -> **Chiffrement**
Intégrité : Aucune altération (volontaire ou non), involontaire -> codes correcteurs d'erreurs, volontaire -> **crypto HMAC (hash message authentication code)**
Authentification : la personne est bien ce qu'elle prétend être -> **protocole d'authentification**
Non-répudiation : l'expéditeur ne peut pas nier être à l'origine d'un message qu'il a envoyé et il peut prouver être l'émetteur du message -> **signature**

## Formalisation
$\mathcal{M}$ -> espace des message en clair (Plain text)
$\mathcal{C}$ -> espace des messages chiffrés
$\mathcal{K}$ -> espace des clefs
KeyGen ou $\mathcal{KG}$ -> algo de génération de clefs
$\mathcal{E}$ -> fonction de chiffrement
$\mathcal{D}$ -> fonction de déchiffrement

### Chiffrement
$\mathcal{E}$ : $(\mathcal{M}, \mathcal{K}) \rightarrow \mathcal{C}$

### Déchiffrement
$\mathcal{D}$ : $(\mathcal{C}, \mathcal{K}) \rightarrow \mathcal{M}$

## Passage des mathématiques à l'informatique
Domaine mathématiques : $\mathcal{M},\mathcal{C}$ peuvent être infinis.

**Preuve de sécurité** : modélisation qui permet d'évaluer la sécurité d'une brique crypto, nécessite que les ensembles soient finis

Domaine informatique : $\mathcal{M},\mathcal{C}$ et $\mathcal{K}$ sont finis, les fonctions sont des algo

# Histoire
## Trois périodes
Âge artisanal : antiquité à 1918
Âge technique : 1919-1975
Âge paradoxal : depuis 1976

## Âge artisanal
Chiffrement de césar : décalage des lettres de l'alphabet
Chiffrement de Vigenère : on enroule un ruban autour d'un baton, on écrit le texte puis on déroule le ruban
Chiffrement "marathonien" : on tatoue un message sur le crane rasé d'un homme et on attend que ses cheveux repoussent

### Formalisation du chiffrement de césar
$\mathcal{M} = \{0,1,...,25 \}$
$\mathcal{C} = \{0,1,...,25 \}$
$\mathcal{K} = \{0,1,...,25 \}$
$\mathcal{KG} : () \rightarrow rand(\mathcal{K})$
$\mathcal{E} : (\mathcal{M}, \mathcal{K}) \rightarrow (\mathcal{M} + \mathcal{K}) \mod{26}$
$\mathcal{D} : (\mathcal{C}, \mathcal{K}) \rightarrow (\mathcal{C} - \mathcal{K}) \mod{26}$

Cryptanalyse possible avec fréquence des lettres en fonction des langues

## Äge paradoxal
1978 : RSA -> début racines modulaires, décomposition en facteurs premiers
1978 : MacEliece -> codes correcteurs d'erreurs
1978 : Merkle-Helmann -> problème du sac à dos
1984 : ElGammal log discret

Plus récemment : chiffrement homomorphique (utilisation dans le cloud)

# Principes mathématiques
## Génération d'aléas
Objectif : Génération de clefs secrètes, couples de clefs, génération de padding, chiffrement type One-time pad : besoin d'un échange sécurisé de l'aléa

### Générateur de pseudo-aléas
Fonction déterministe : $\mathcal{g} : \{0,1\}^{n} \mapsto \{0,1\}^{nc}$ pour un réel $\mathcal{c} \gt 1$ de telle sorte que si $x \in \{0,1\}$ choisi aléatoirement alors $g(x)$ semble aléatoire. Probabilité de pouvoir prédire le bit suivant de 1/2

### pseudo-aléa et FSU (fonction à sens unique)
Un générateur de pseudo-aléas est une FSU

### Construction d'un GPA (générateur de pseudo-aléas)

Méthode :
* souce physique (ex : temps)
* retraitement de la sortie de la source physique -> algo de chiffrement symétrique

Comment tester la qualité ? Besoin de passer de nombreux tests

## FSU
Principe :
* facilement calculable
* "difficile" à inverser (temps de calcul long) sans connaissance d'un "secret"
* facile à inverser en connaissant un "secret"

### Définition
On appelle une FSU :
$f : \{0,1\}^* \rightarrow \{0,1\}^*$
Elle vérifie les propritétes suivantes :
* $\forall x \in \{0,1\}^*, f(x)$ est calculable en un temps polynomial en $|x|$
* Il n'existe pas d'algo qui, $\forall$ $y$ donne en temps polynomial $|y|$ un antécédent $x$ tel que $f(x)=y$
* Il existe un polynôme $p$ tel que $\forall$ $y \in \{0,1\}^*$ dans l'image de $f$, $\exists$ $x \in \{0,1\}^*$ tel que
* $f(x) = y$
* $|x| \leq p(|y|)$

Résultat théorique : l'existence des FSU est équivalente au problème $P \neq NP$

### Fonctions à trappe
FSU faciles à inverser avec un secret
Ex : RSA

## Fonction de hachage
Obtention de l'empreinte d'un message
Objectif : assurer l'intégrité d'un message, éviter la modification involontaire (transmission) ou volontaire (cryptographie)

Efficacité : compression et facile à calculer
Sécurité :
* Première pré-image (FSU) : Soit $y \in Im(\mathcal{H})$, il est diffice de trouver $x$ tel que $\mathcal{H}(x) = y$
* Seconde pré-image : Soit $x$ donné, il est difficile de trouver $x' \neq x$ tel que $\mathcal{H}(x) = \mathcal{H}(x')$. Objectif : éviter ré-utilisation du haché

Dimension faible de l'espace d'arrivée par rapport à celle de l'espace de départ

Exemples : MD5, SHA1, SHA2, SHA3 (nouveau paradigme par rapport à SHA1 et SHA2)

# Théorie de la complexité
## Problèmes utilisés en cryptographie
Test de primalité, générer des nombres premiers
### Log discret
Entrées : $p$ premier, $\alpha$ primitif dans $\Bbb F_{p^*}$, $\beta \in F_{p^*}$
Question : trouver $k$ entier tel que $\alpha^k = \beta$

## Motivations
Tester les cryptosystèmes : dimensionner ces systèmes :
* Durée de vie prévue du système
* complexité du ou des problèmes sous-jacents
* Hypothèse d'évolutions techniques
* Nouvelles attaques