Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#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
Pages : 1