---
tags: revision, CRYPI
title: Cours 2
---

# Formalisation de schémas asymétrique
## Schémas de signature
### Génération des paramètres du système :
entrée $l$ -> paramètres de sécurité
sortie -> paramètres du système(**SysParam**)

### Key Gen :
Entrée -> $l$, SysParam
Sortie -> ($\mathcal{KPriv}$, $\mathcal{KPub}$)

### Génération de la signature
$(\mathcal{KPriv}$ $\times$ $\mathcal{M}) \rightarrow \mathcal{C}$
$(\mathcal{KPriv},\mathcal{m}) \mapsto \sigma$

### Vérification de la signature
$(\mathcal{KPub}$ $\times$ $\mathcal{M}$ $\times$ $\mathcal{C}) \rightarrow \{0,1\}$
$(\mathcal{KPub},\mathcal{m}, \sigma) \mapsto$ **OK/KO**

## Schéma de chiffrement RSA
### Génération des paramètres du système
entrée $l$ -> paramètres de sécurité
Génération de deux nombre premiers $p$ et $q$, détermination du produit $n = pq$, détermination de $\Bbb Z/n\Bbb Z$ (multiplication possible)
Sortie -> paramètres du système (**SysParam**)
La génération des nombres premier n'a lieu qu'à la première étape

### KeyGen :
Entrée -> $l,p,q,\phi (n)$
:::info
$\phi (n)$ -> indicatrice d'Euler
:::
Génération de $e$ tel que $e \wedge \phi (n) = 1$
Détermination de $d$ tel que $d \times e = 1[\phi (n)]$
Sortie -> $\mathcal{KPriv} = (p,q,d)$, $\mathcal{KPub}=(n,e)$

### Génération du message chiffré
$(\mathcal{KPub} \times \mathcal{M}) \rightarrow \mathcal{C}$
$((n,e),m) \mapsto m^e[n] = c$

### Déchiffrement du message
$(\mathcal{KPriv} \times \mathcal{C}) \rightarrow \mathcal{M}$
$((p,q,d),c) \mapsto c^d = m$

## Schéma de signature RSA

### Génération de la signature
$(\mathcal{KPriv}$ $\times$ $\mathcal{M}) \rightarrow \mathcal{C}$
$((p,q,d),\mathcal{m}) \mapsto m^d[n] = \sigma$

### Vérification de la signature
$(\mathcal{KPub}$ $\times$ $\mathcal{M}$ $\times$ $\mathcal{C}) \rightarrow \{0,1\}$
$((n,e),\mathcal{m}, \sigma) \mapsto \{0$ si $m\neq \sigma^e[n],1$ si $m = \sigma^e[n]\}$

### Problèmes
Signature déterministe
Détermination possible de couples (messages, signature)
Signature malléable

## Schéma signature El Gammal 1985
### Génération des paramètres du système
entrée $l$ -> paramètres de sécurité
Génération d'un nombre premier $p$
Sortie -> $p$

### KeyGen :
Entrée -> $l,p$
Choisir aléatoirement un élément primitif de $(\Bbb Z/p\Bbb Z)^*$
Choisir aléatoirement un entier naturel $x$ avec $1 \leq x \leq p-1$

Sortie -> $\mathcal{KPriv} = (g,x)$, $\mathcal{KPub}=(g, g^x)$

### Génération de la signature
Génération aléatoire d'un élément $r$ de $(\Bbb Z/p\Bbb Z)^*$
$(\mathcal{KPriv} \times \mathcal{M}) \rightarrow \mathcal{C}$
$((g,x),m) \mapsto (g^r, \frac{(m-xg^r)}{r}) = (A,B)$

### Vérification de la signature
$(\mathcal{KPub} \times \mathcal{C}, \mathcal{M}) \rightarrow \{0,1\}$
$(\mathcal{Kpub} = g^x,(A,B),m) \mapsto C^B((g^x)^A)$
Si $C^B((g^x)^A)[p] = g^m$ alors OK

### Avantages
Sécurité repose sur les logs discrets
Efficacité de la signature
Signature randomisée

### Inconvénients
Signature longue
Signature couteuse
Signature malléable

## Eviter la malléabilité des signatures
Pour éviter malléabilité -> fonctions de hachages
Principe :
1) Application d'une fonction de hachage
2) Application d'un algo de signature