Description formelle

$p \in \{premiers\}$ de 1024 bit

$q \in \{premiers\}$ de 160 bit, tel que $q \; \vert \; p - 1$

$\alpha \in \mathbb{F}_p^{*}$ tel que $\alpha^{q} \equiv 1 \;mod\; (p)$

nota : l'ordre de $\alpha$ dans $\mathbb{F}_p^{*}$ est un diviseur de $q$, comme $q$ est premier, on cherche pour $\alpha$ un élément de $\mathbb{F}_p^{*}$ d'ordre $q$ (il y en a $q - 1$).

$\EuScript{P} = \mathbb{F}_p^{*}$

$\EuScript{A} = \mathbb{F}_q \times \mathbb{F}_q$

$\EuScript{K} = \{(p,q,\alpha,a,\beta)\; \vert\; \beta \equiv \alpha^{a} (p) \}$

Public : [ $p, q, \alpha, \beta$]

Privé : [$a$]

Soit $K = (p,q,\alpha,a,\beta) \in \EuScript{K}$ et $k \in {\mathbb{F}_q}^{*}$ aléatoire et secret, alors:

$sig_k(x, k) = (\gamma, \delta)$ :

$\gamma \equiv (\alpha^{k} \; mod \; (p))\; mod \; (q)$

$\delta \equiv (x + a \gamma)k^{-1}\; mod \; (q)$

Nota :

• il n'existe pas de surjection canonique de $\mathbb{F}_p$ sur $\mathbb{F}_q$ car $q$ ne divise pas $p$.
• si $\delta \equiv 0 \; mod \; (q)$, Alice choisit un autre $k$ et recommence.
  

Comme $x \in \mathbb{F}_p^{*}$, $(\gamma,\delta) \in \mathbb{F}_q$, posons :

$e_1 \equiv x \delta^{-1} \;mod \; (q)$

$e_2 \equiv \gamma \delta^{-1} \;mod \; (q)$

alors :

$ver_K(x, \gamma, \delta) = 1 \Leftrightarrow (\alpha^{e_1}\beta^{e_2} \; mod \; (p)) \; mod \; (q) = \gamma$