Inscription / Connexion Nouveau Sujet
La cryptographie a clés publiques : le système RSA
Bonjour à tous 
Cet exercice est un peu plus coriace que le précédent. (CF cryptage affine ^^)
C'est pourquoi je viens vous demander de l'aide
1. Propriété fondamentale
n=pq est le produit de deux nombres premiers p et q distincts.
ON pose m=(p-1)(q-1) et on note c un nombre premier avec m. ON note x un entier naturel.
a) Démontrer qu'il existe des entiers d et k tels que : cd=km+1 (c'est à dire cd
1 modulo m)
b) Cas où x est non divisible par p.
Demontrer que xp-11 modulo p
EN déduire que xkm1 modulo p puis que xcdx modulo p.
Cas où x est divisble par p.
Demontrer que xcdx modulo p.
c) démontrer de façon analogue que pour tout x entier naturel, xcdx modulo q
d)en déduire que pour tout entier naturel x, xcdx modulo n
J'ai traité la question a). C'est pour la suite que je bloque. JE vous remercie d'avance
Bonjour,
1)a) Est une conséquence directe de Bezout.
1)b) C' est effectivement le petit théorème de Fermat:
si n' est pas divisible par
premier, alors
est premier avec
donc d' après Fermat.
et
puis
C' est un début...
Si est divisible par
, alors
et
On a donc bien
Finalement pour tout entier naturel (que
soit ou non multiple de
), on a:
c)Même démonstration...
d) est donc un multiple de
et de
et
étant premiers,
est un multiple de
donc
En fait, je suis passé à côté des questions. J'essaie de faire la démonstration du PTF -.-
Merci beaucoup Cailloux en tout cas ! Je repasse peut-être plus tard si j'échoue dans l'application 
Application.
Alexandre veut choisir une clé publique (n,c) et sa clé privée d
Il prend p=5 q=11 et donc n=55
a) démontrer qu'il peut choisir c=3 et d=27
Si je calcule m=(p-1)(q-1)=40 donc 40 et 40 premier avec 3 donc ok
D'autre part, il existe k entier (k=2) tel que cd=km+1 soit 81=2*40+1
Selon moi, ce sont les deux seules conditions.
Les lettres de l'alphabet sont chiffrées par A=01 B=02 Z=26
Paul connait la clé d'Alexandre et crypte le message : "vive la cryptographie"
Quel message crypté Alexandre recoit-il et comment le décode-t-il ?!
Je remercie d'avance celui qui me répondra car je ne suis pas sûr de ma justification et j'ai du mal pour la 2.
Aide :Le codage consiste à calculer C(x)xc modulo n
Le décodage consiste à calculer D(y)yd modulo n
Merci ^^
Re,
a) Démontrer qu'il existe des entiers d et k tels que : cd=km+1
Avec avec
Pour le codage:
Par exemple
Et
Pour le décryptage:
On retombe bien sur
Par exemple pour décrypter
et 2 correspond à
Super! Merci.
Quand c'est expliqué clairement, c'est beaucoup plus facile à comprendre.
Je repasse plus tard poster les réponses car j'ai vu que je n'étais pas le seul à avoir cet exercice.
Merci encore cailloux 
Oui mais dans ce cas là :
Pour le V 33 223 modulo 55 or il n'y a que 26 lettres donc j'affectue le 33 d'un modulo 26 ce qui donnerait 7 soit G ?
Pour l'application 1 j'ai trouvé pour "VIVE LA CRYPTOGRAPHIE":
33143315 2301 27020526252013020126171415
...
J'espere que c'est bon et merci cailloux
(pour ceux qui veulent verifier c=3 et n=55, il fallait crypter "VIVE LA CRYPTOGRAPHIE")
Que veux-tu dire ? On ne peux pas décrypter ça facilement ?
En tout cas, sur la calculatrice, j'entre la fonction reste(x27,55) !
Je fais comme ça pour les congruences, sauf que là, elle est pas d'accord
En tout cas, sur la calculatrice, j'entre la fonction reste(x27,55) !
Sur la mienne (TI89): mod(33^27,55)
sauf que là, elle est pas d'accord
La mienne l' est
Niquel Moi aussi j'ai une TI89.
Mais l'énoncé ne précise pas qu'Alexandre a une TI 89 ^^ donc je suis toujours bloquer pour décrypter :s
Quel message crypté Alexandre recoit-il et comment le décode-t-il ?!
A mon avis, pour le décryptage, on ne te demande que la méthode, à savoir, à partir de
De rien scientifique
D' ailleurs l' énoncé s' est arrangé pour qu' on aie une clé de cryptage: "petite" pour qu' on puisse faire les caculs de cryptage modulo 55 facilement.
Evidemment, pour le décryptage, avec , c' est une autre chanson...
Annuler
connectez vous