J'ai un exercice a résoudre. Je voulais savoir si ce que j'ai écrit était juste.
N'ayant pas le signe de la congruence je vais poser*:
a#b[n] veut dire a est congru à b modulo n
Énoncé
p et q sont deux nombres premiers distincts et n=pq
on pose m=(p-1)(q-1) et on choisit a premier avec m
on a montre qu'il existe a et b tels que ab=1+mc
on a aussi montre que pour tout entier x, x^(ab)#x[p] et x^(ab)#x[q]
1. Il faut montrer que x^(ab)#x[n]
on sait que x^(ab)#x[p] , soit x^(ab)-x=k1*p (1)
on sait que x^(ab)#x[q] , soit x^(ab)-x=k2*q (2)
donc k1*p=k2*q
donc p divise k2*q. Comme p et q sont des nombres premier, ils sont premiers entre eux. D’après le théorème de gauss, p divise k2. Soit k2=k3*p.
En remplaçant dans l’équation (2) , x^(ab)-x=k3*p*q=k3*n. Ce qui veut dire que x^(ab)x^(ab)#x[q]#x[n].
le but est de crypter un message. Avec m, n, p, q, a et b ayant les mêmes propriétés qu'au début de l'énoncé
Cryptage
on choisit a et n. Ce qui donne la clé publique (n*; a). Le message crypte sera*:
C(x)#x^a[n]
Décryptage
avec la clé publique on décrypte avec la formule:
D(y)#y^b[n]
la personne qui décrypte connaît la valeur de b (clé privée)
Le but est de crypter une numéro de téléphone. Les numéros sont crypte deux par deux.
a. Justifier que n supérieur ou égal a 100.
On sait que D(y) est un chiffre compris entre 0 et 99 puisque les numéros sont cryptes deux par deux.
Comme D(y)#y^b[n], ça veut dire que le reste r de la division euclidienne de y^b par n est compris entre 0 et 99. Donc r vaut au maximum 99. Comme r<n (définition de la division euclidienne) l'entier qui vient après 99 est 100.
Donc n>=100
b. montrer que la plus petite clé publique possible est (106,3)
on sait que n>=100
*Supposons que n=100 (n est un produit de deux nombres premiers)
n=2*50=100. Or 50 n'est pas premier donc n est différent de 100
*supposons que n=101. 101 ne peut pas se décomposer en produit de nombre premiers car il est premier. Donc n différent de 101
*Supposons que n=102. 102=51*2 . Or 51 n'est pas premier donc n différent de 102
*Supposons que n=103. 103 ne peut pas se décomposer en produit de nombre premiers car il est premier. Donc n différent de 103
*Supposons que n=104. 104=52*2. 52 n'est pas premier donc n différent de 104
*Supposons que n=105. 105=3*35. 35 n'est pas premier donc impossible
* Supposons que n=106. 106=2*53. 2 et 53 sont premier donc n=106 est une cle possible.
Donc m=(2-1)*(53-1)=52
On choisit a premier avec 52. Le plus petit entier premier avec 52 est 3. donc a=3
c. il faut crypter 06 13 87 11 45 (si mes calculs sont bons)
c(06)#6^3[106]=04
c(13)#13^3[106]=77
c(87)#87^3[106]=31
c(11)#11^3[106]=59
c(45)#45^3[106]=71
-----