Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 28-12-2016 17:39:23

AmineRiina
Invité

System de chiffrement

bonjour tout le monde ,
donc voila :
j'ai un exercie avec sa repense et je voudrais comprendre ce qui m'echape
j'ai le n et Φ(n)
n=143 
Φ(n)=120

système de chiffrement dans Z143 :
La clé de chiffrement est K=(k1,k2) //k1,k2 ϵ Z143
Pour un x dans Z143, la fonction de chiffrement est donnée par : Ek(x)=k1x+k2
1.    Quel est le nombre de valeurs que peut prendre K pour avoir un chiffrement ?


la repense est :
valeurs possibles de k2 égale à 143 ;
valeurs possibles de k1 est le nombre d’éléments inversibles dans Z143, donc Φ(143)=120.

Il y a donc 120 possibilités pour k1 et 143 pour k2, ce qui donne 143x120=17160, mais il faut enlever le couple(1,0) avec lequel on n’a aucun chiffrement. Il y a donc 17159 valeurs possibles pour K.

je ne comprend pas pour le k2=n=143 et le k1 ils disent que c le nombre est d’éléments inversibles et donc Φ(143)=120
voila j'ai pas compris pour quoi il ont résonner ainsi

je vous remercie d'avance ^^

#2 29-12-2016 13:04:54

Rossignol
Membre
Inscription : 19-06-2015
Messages : 290

Re : System de chiffrement

Bonjour,

On pose $n=143=11\times13$

Tout revient à déterminer les $k = (k_1, k_2)\in \mathbb{Z}/n\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}$ tels que la fonction affine $E_k$ de $\mathbb{Z}/n\mathbb{Z}$ dans $\mathbb{Z}/n\mathbb{Z}$ définie par $E_k(x) = k_1x+k_2$ soit bijective.

Puisque l'ensemble de départ et l'ensemble d'arrivée de $E_k$ est le même ensemble fini $\mathbb{Z}/n\mathbb{Z}$, il suffit de chercher quand $E_k$ est injective.

Quels que soient $u$ et $v$ dans $\mathbb{Z}/n\mathbb{Z}$
$$E_k(u)=E_k(v) \Rightarrow k_1u+k_2 = k_1v+k_2 \Rightarrow k_1u+k_2-k_1v-k_2 = 0 \Rightarrow k_1(u-v) = 0$$

Si $k_1$ est premier avec $n$ alors $k_1$ est inversible d'après l'identité de Bézout  : il existe $k_1^{-1}$ tel que $k_1^{-1}k_1=1$
$$E_k(u)=E_k(v) \Rightarrow k_1(u-v) = 0 \Rightarrow k_1^{-1}k_1(u-v) = 0 \Rightarrow (u-v) = 0\Rightarrow u=v$$
donc $E_k$ est injective et donc bijective.

Si $k_1$ n'est pas premier avec $n$ alors, soit $k_1=0$, soit $k_1$ est un diviseur de zéro.

En effet, si $k_1 \neq 0$ et si $k_1$ n'est pas premier avec $n$ alors ils ont un diviseur commun $d > 1$.

Autrement dit, il existe des entiers $k_1^{\prime}$ et $n^{\prime}$ tels que $k_1 = k_1^{\prime}d$ et $n = n^{\prime}d$.

On a alors $k_1n^{\prime} = (k_1^{\prime}d)n^{\prime} = k_1^{\prime}(n^{\prime}d) = k_1^{\prime} n \equiv 0$

Comme $d>1$ on a $n^{\prime}\neq 0$ donc $k_1$ et $n^{\prime}$ sont des diviseurs de zéro.

Si $k_1=0$ alors $E_k$ est constante donc non bijective.

Si $k1$ est un diviseur de zéro associé à $n^{\prime}$
$$E_k(n^{\prime}) = k_1n^{\prime}+k_2=0+k_2=k_2$$
On a donc $E_k(n^{\prime}) = E_k(0)$ avec $n^{\prime}\neq 0$ : $E_k$ n'est pas injective.

Conclusion : $E_k$ est un chiffrement affine si et seulement si $k_1$ est premier avec $n$ (pas de condition sur $k_2$).

Le nombre d'entiers naturels inférieurs à $n$ et premiers avec $n$ est $\varphi(n)$ l'indicatrice d'Euler.

Le nombre de chiffrements affines sur $\mathbb{Z}/n\mathbb{Z}$ est donc $n\varphi(n)$.

Pour $n=143=11\times 13$ on a $\varphi(143)=(11-1)(13-1)=10\times12 = 120$

Le nombre chiffrements affines sur $\mathbb{Z}/143\mathbb{Z}$ est donc $143\times 120 = 17\,160$, ou $17\,159$ si on retire l'identité.

@+

Hors ligne

#3 29-12-2016 14:14:59

AmineRiina
Invité

Re : System de chiffrement

je vous remercie enormement pour le temps que vous m'avez accordé et pour votre explication très détailles.
je voudrais m’exerce ,vous avez pas un site ou des documents avec des exercices corrigé a me suggéré ?   car je bug sur 3 exercices et je voudrais faire des exercices pour essayer de comprendre
merci d'avance

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
soixante sept moins dix-huit
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums