Inscription / Connexion Nouveau Sujet
DM Spé Congruences et Cryptage : Systeme RSA
Boinsoir^^
Alors voila j ai un devoir maison pour dans pas longtemps sur le cryptage et j éprouve quelques difficultés sur certaines questions.Je ne mets que l'énoncé partiel:
I)Etude mathématique:
Soit p et q deux nombres premiers distincts et n = pq
1) a
tel que a
n=1
a) j ai montré que ap=1 et aq=1 par le théoreme de Bezout
b) puis a l aide du fameux théoreme de Fermat j ai trouvé ap-1
[p]
...
enfin au petit f)on en déduit que pour k on a ak(p-1)(q-1)+1 a [n]
2) a avec a multiple de p et tel que a < n
a) j ai montré que ak(p-1)(q-1)+1 a [p]
ensuite on montre que a et q sont premiers entre eux
...
en fait on refait la meme chose pour conclure dans le petit d) que ak(p-1)(q-1)+1 a [n] pour tout k
dans cette partie toutes les questions mènent a la conclusion:
si a < n, alors ak(p-1)(q-1)+1 a [n]
j ai réussi à faire cette parie sans trop de soucis mais bon je l avoue, c est très répétitif
II) Application au codage
on a p et q des nombres premiers distincts,
n=pq,
et e un entier naturel premier avec (p-1)(q-1)
1) Monter ed=k(p-1)(q-1)+1 avec d et k des entiers naturels
j ai utilisé le théoreme de Bezout pour trouver eu = -v(p-1)(q-1)+1 avec u et v 
puis j ai pris d=u et k= -v
2)a tel que a < n
a)c tel que 0
c<n et c ae [n]
j ai utiliser la II) 1) puis la conclusion du I)
b)justifier alors que c permet de coder a
et voila c'est cette 2 b) qui me pose probleme si vous pouviez m aider je vous en serais très reconnaissant
le dm comporte une 3e grande partie que j ai bien avancé aussi sachant que je bloque aussi sur des questions de logiques si on peut les appeler comme ca!
Hello,
montres que la connaissance de c permet de retrouver a. Pour cela on fait :
et je crois que tu peux savoir à quoi est congru modulo n.
Bonsoir
merci de ta réponse^^
je viens juste de remarquer que j avais oublié une partie de la question...
autant pour moi!
II) 2) b) Soit c tel que 0c<n et cae [n]
et il fallait montrer que cda [n]
et j ai donc fait comme tu as dis:
cae [n]
par propriété on a alors cdaed [n]
or d apres II) 1) ed=k(p-1)(q-1)+1
donc cdak(p-1)(q-1)+1
or d apres la conclusion du I)
si a<n on ak(p-1)(q-1)+1a [n]
d ou cda [n]
et la je ne comprend pas comment ils veulent qu on demontre que c peut coder a
hé bien parce que si on nous donne c ( on nous l'envoie par exemple ) on peut retrouver a en calculant cd.
Pour comprendre à fond tu devrais aller voir un site qui parle du système de cryptage RSA. Pour comprendre ce qui est publique, ce qui est secret, ce qu'on calcule.
Grosso modo, est plublique n et e ( sont secret d et p et q et bien sûr le nombre a qui est à coder ). Donc publiquement on peut envoyer c si on ne connait pas d on ne peut pas retrouver a, seule la personne qui connait d peut retrouver le nombre a.
Plus les nombres premiers p et q sont grands et plus il est difficile, voire impossible de casser le code.
Donc en fait je n ai rien de particulier a demontrer avec les congruences?
Et oui j adore les congruences!!
cela me parait un peu léger de le justifier comme ca...
je suis aller sur ce site et ca m'a pas mal aidé si quelqu'un est interessé
Donc en fait je n ai rien de particulier a demontrer avec les congruences?
hé bien non
dommage 
Bon choix de site...c'est une mine
justement,dans la derniere partie on passe au codage avec les formules qu on a demontrées:
On code un entier a<n par cae [n] avec 0c<n
On décode en calculant cda [n]
1) n=2759 et e=7
a)coder les lettres du mot MATIN
en prenant M=12, A=0, T=19, I=08, et N=13
j ai donc trouvé
M=>675 A=>0 T=>2642 I=>312 N=>580
b)Coder le meme mot en codant les nombres 1200 1908 et 1326: ces nombres sont obtenus en regroupant les lettres deux par deux et 26 représente l espace apres le mot.
On pourra commencer par décomposer les mots a coder en produit de nombres prmiers
et la j ai trouvé:
1200=24
352
1908=223253
1326=231317
mais bon je vois pas trop ou ca nous mene...
voila la fin de l'enoncé:
c) Peut on dans ce cas particulier regrouper les lettres 3 par 3 pour coder un mot?
d)trouver les nombres premiers p et q et en déduire une clé de décodage d convenable
pour celle la j ai dit que n=pq et n=2759
comme p et q sont premiers cela revient a décomposer 2759 en produit de nombres premiers
ainsi 2759= 3189
2) expliquer pourquoi si p et q sont tres grands et inconnus du public la clé de codage (n,e) peut etre connue de tous d ou son nom de clé publique.
On pourra commencer par décomposer les mots a coder en produit de nombres prmiers....mais bon je vois pas trop ou ca nous mene...
Oui moi non plus...simplifier les calculs ????
c) Peut on dans ce cas particulier regrouper les lettres 3 par 3 pour coder un mot?
Non, le premier nombre à coder serait 12019 mais il est supérieur à 2759.
d)trouver les nombres premiers p et q et en déduire une clé de décodage d convenable
pour celle la j ai dit que n=pq et n=2759
comme p et q sont premiers cela revient a décomposer 2759 en produit de nombres premiers
ainsi 2759= 31
89Ok reste à trouver e et d.
2) expliquer pourquoi si p et q sont tres grands et inconnus du public la clé de codage (n,e) peut etre connue de tous d ou son nom de clé publique.
difficile de trouver la décomposition en facteurs premiers...voire impossible avec la capacité de calcul des ordinateurs actuels..mais bon est-ce que cela durera ?
Alors voila, j'ai le même exercice à faire que Pokerface, et je bloque sur la question 2 de la partie A. En effet pour la question 1 on par avec l'hypothèse selon laquelle a^n = 1. Or cette fois ci on nous dit seulement que a=rp avec r comme entier naturel, et que a<n . Je sais pas trop comment faire pour commencer.. Aidez moi s'il vous plaît!!
Annuler
connectez vous