Ceci forme-t-il un crypto-système ?

Vérifions (1) (montrons que $D_{K}oE_{K}(x) = id_{\EuScript{P}}$) :

nota :

• soit $f : x \rightarrow x^{b} \; mod \; (n)$, pour résoudre $y = x^{b} \; mod \; (n)$ avec $x$ inconnu il suffit de connaître $a$. On connait $(n, b, y)$, il suffit donc de connaître $\varphi(n) = (p - 1)(q - 1)$. Ce qui signifie pour un attaquant : ``connaître la factorisation de $n$'', ce qui est impossible pour un $n$ convenable.

Question : $\forall x \in \frac{\mathbb{Z}}{n\mathbb{Z}}, \; x^{ab}\equiv x \; mod \; (n)$ ?

$1^{er}$ cas : $x \in (\frac{\mathbb{Z}}{n\mathbb{Z}})^{*}$

$ab \equiv 1\;(\varphi(n)) \Leftrightarrow ab = 1 + k\varphi(n),\;\; k \in \mathbb{Z}$

on a $x^{ab} = x^{1 + k\varphi(n)} = x.(x^{\varphi(n)})^k \equiv x.1 \equiv x \; mod \; (n)$

$2^{ème}$ cas : $x \in \frac{\mathbb{Z}}{n\mathbb{Z}},\; x \notin (\frac{\mathbb{Z}}{n\mathbb{Z}})^{*},\; x \neq 0$

$x \wedge n = \left\{ \begin{array}{l} p\\ q\\ \end{array}\right.$

supposons $x \wedge n = p$ (on fera le même raisonnement pour $x \wedge n = q$) :

alors $x = px',\;$ $q \wedge x' = 1 \Leftrightarrow q \nmid x'$ et

$x^{ab} - x = (x'p)^{1+k\varphi(p)\varphi(q)}-x'p = (x'p)[(x'p)^{k\varphi(p)\varphi(q)} - 1]$

montrons que $(x'p)^{k\varphi(p)\varphi(q)} - 1$ est divisible par $q$.

On a $x'p \wedge q = 1 \Leftrightarrow x'p \in (\frac{\mathbb{Z}}{n\mathbb{Z}})^{*}$, donc $(x'p)^{\varphi(q)} \equiv 1 \; mod \; (q)$.

Finalement $(x'p)^{k\varphi(p)\varphi(q)} - 1 \equiv ((x'p)^{\varphi(q)})^{k\varphi(p)} - 1 \equiv 0 \; mod \; (q)$.

Ainsi on a bien : $\forall x \in \frac{\mathbb{Z}}{n\mathbb{Z}}, \; x^{ab}\equiv x \; mod \; (n)$, ce qui vérifie (1).