Résistance aux attaques

D'après le théorème d'Euler, pour tout $M$ premier avec $N$,

$$M^{\phi(N)} \equiv 1 \pmod N$$

Plus généralement, pour tout $k$ entier relatif,

$$M^{k\phi(N)} \equiv 1 \pmod N$$

Ce qui s'écrit aussi

$$M^{k\phi(N)}M \equiv M \pmod N$$

et de ce fait

$$M^{k\phi(N)+1} \equiv M \pmod N$$

Comme

$$M^{CC^\prime} \equiv M \pmod N$$

il convient de déterminer $C^\prime$ tel que

$$CC^\prime = k\phi(N) + 1$$

ce qui s'écrit plus simplement comme une relation de Bezout

$$CC^\prime - k\phi(N) = 1$$

Notez que la connaissance de $\phi(N)$ est indispensable si on souhaite trouver $C^\prime$. Etant donné $N = PQ$ le produit de nombres premiers $P$ et $Q$, on a $\phi(N) = (P-1)(Q-1)$. Donc pour connaître $\phi(N)$, il est nécessaire de connaître la décomposition de $N$ en produit de facteurs premiers. Donc, retrouver $C^\prime$ à partir de $C$ oblige le cryptanalyste à passer par une factorisation de $N$, problème connu pour être difficile.