Cryptage RSA - Calcul d'un modulo

par **Naddx0** » 21 Aoû 2008, 23:36

Bonjour,
Je me penche actuellement sur le cryptage de nombres au moyen de l'algorithme RSA.

Je suis coincé au calcul suivant pour le décryptage de l'entier codé :

Code: Tout sélectionner: [B](76^59) mod 91[/B] sachant que 59 est la clé de décryptage, 79 le résultat du cryptage du nombre 6 (obtenu en faisant 6^11 mod 91), 91 est n = pq (où p = 7 et q = 13).

Existe-t-il un moyen de calculer ce modulo ? (Petit théorème de Fermat ?)

En vous remerciant d'avance,

Nicolas :we:

par **Clembou** » 21 Aoû 2008, 23:51

Naddx0 a écrit:Bonjour,
Je me penche actuellement sur le cryptage de nombres au moyen de l'algorithme RSA.

Je suis coincé au calcul suivant pour le décryptage de l'entier codé :

Code: Tout sélectionner
[B](76^59) mod 91[/B] sachant que 59 est la clé de décryptage, 79 le résultat du cryptage du nombre 6 (obtenu en faisant 6^11 mod 91), 91 est n = pq (où p = 7 et q = 13).

Existe-t-il un moyen de calculer ce modulo ? (Petit théorème de Fermat ?)

En vous remerciant d'avance,

Nicolas :we:

Hmmm ! J'ai un cours sur ça :

http://clement-boulonne.123.fr/cours/AteliersMath.pdf

Je ne sais pas si ça pourra t'aider...

par **Doraki** » 22 Aoû 2008, 12:01

Il ne faut surtout pas tenter de calculer 76^59 puis de regarder ce que ça donne modulo 91.

D'abord (x * y) mod 91 c'est pareil que ((x mod 91) * (y mod 91)) mod 91.
donc tu peux ne travailler qu'avec des nombres inférieurs à 91 pendant ton calcul, c'est pas nécessaire de se coltiner des nombres énormes.

Ensuite c'est juste un calcul de puissance et ça se peut se faire en quelques multiplications modulo 91.

par **yos** » 22 Aoû 2008, 17:09

Bonjour.
Il est facile de trouver

(-1 à vue de nez) et

(6 je dirais). On en déduit ensuite

(6 je pense : à vérifier).

par **Naddx0** » 22 Aoû 2008, 19:32

Merci pour toutes vos réponses :) Je vais me pencher là-dessus sous peu !

Amicalement,

Nicolas.

par **Naddx0** » 23 Aoû 2008, 14:37

Bonjour,

yos a écrit:Bonjour.
Il est facile de trouver (-1 à vue de nez) et (6 je dirais). On en déduit ensuite (6 je pense : à vérifier).

Je vois bien ici l'opération effectuée : 7 * 13 = 91, mais je ne comprends pas comment arriver à la bonne réponse, qui est, en effet, le nombre 6.

par **Quidam** » 23 Aoû 2008, 17:16

Du fait que

et que

,
il est clair que l'on a avantage à décomposer l'exposant en binaire.
Donc

Et

d'où :

Et ainsi de suite... Il revient au même de décoposer l'exposant en binaire.

Ainsi,

Pour les valeurs de i telles que

cela se traduit par le calcul de

. Donc on peut simplifier l'expression par :

Tu n'as donc qu'à calculer :

Comme

,

Tous ces calculs étant bien entendu faits modulo 91

par **Naddx0** » 23 Aoû 2008, 17:38

D'accord. Je perçois bien la décomposition en binaire. Mais à partir de cette décomposition, comment obtenir le résultat souhaité ?

À partir de celà, comment retrouver le reste de la division de

par 91 ?

Désolé de vous paraître un peu lent à la détente, mais je ne suis pas vraiment à l'aise avec tout ceci :\

Cordialement,

Nicolas.

par **leon1789** » 23 Aoû 2008, 17:59

Naddx0 a écrit:À partir de celà, comment retrouver le reste de la division de par 91 ?

Il y a l'exponentiation dichotomique comme l'explique Quidam, mais cela demande une machine pour moi.

Une autre méthode (cf yos) :

91 = 7*13 (on va faire du chinois, c'est les JO en ce moment !)

Or

donc

De plus

et

donc

Ainsi, avec le théo des JO, le reste de la division de

par 91 est congru à

et congru à

: il ne peut s'agir que de 6 !!! :zen:

par **Naddx0** » 23 Aoû 2008, 19:04

Hmmmm,

Les exposants se "communiquent-ils" ?

Par exemple :

devient-il

?

Pour le

, je reconnais le Petit Théorème de Fermat (sauf erreur).

Mais pourquoi peut-on substituer le

par

et comment ce

ce qui fait normalement -1/2 devient-il 6 ?

Aussi, comment utiliser ceci

pour trouver la solution ?

Encore une fois, veuillez m'excuser de la lenteur à laquelle fonctionne mon cerveau :\

Amicalement,

Nicolas.

par **leon1789** » 23 Aoû 2008, 19:17

Naddx0 a écrit:Hmmmm,

Les exposants se "communiquent-ils" ?

Par exemple : devient-il ?

oui

Naddx0 a écrit:Pour le , je reconnais le Petit Théorème de Fermat.

:++:

Naddx0 a écrit:Mais pourquoi peut-on substituer le par

écrire

Naddx0 a écrit:et comment ce ce qui fait normalement -1/2 devient-il 6 ?

Ne pas oublier qu'on travaille modulo 13 :
-2 est inversible modulo 13 (car ...) donc

existe, et vaut 6 (car -2 * 6 = ... )

par **Naddx0** » 23 Aoû 2008, 19:36

Bien, je vais essayer d'assimiler tout ça. Sinon, existe-t-il d'autres méthodes autres que celle que vous venez de présenter ?

Amicalement, et en vous souhaitant une bonne soirée,

Nicolas.

par **yos** » 24 Aoû 2008, 08:21

Naddx0 a écrit:existe-t-il d'autres méthodes autres que celle que vous venez de présenter ?

Qui sait? Je crois pas qu'on puisse faire beaucoup mieux que la méthode chinoise. Elle est élémentaire (propriétés des congruences) : c'est même plus élémentaire qu'avec Fermat.

Merci à Léon1968 d'avoir détaillé ce que je suggérais.

par **Quidam** » 24 Aoû 2008, 16:10

leon1789 a écrit:Il y a l'exponentiation dichotomique comme l'explique Quidam, mais cela demande une machine pour moi.

Ouais, peut-être bien !

Mais, avec la calculatrice de mon PC, je fais, manuellement :

Pas besoin d'un ordinateur donc.

Sauf erreur !

par **leon1789** » 24 Aoû 2008, 18:04

Quidam a écrit:Mais, avec la calculatrice de mon PC, je fais, manuellement :
(...)
Pas besoin d'un ordinateur donc.

Sauf erreur !

:ptdr:
oui, ok, il n'y a pas d'erreur mathématique mais il y a quand même un petit quelque chose qui me chagrine dans cette phrase

avec la calculatrice de mon PC, je fais, manuellement

...) Pas besoin d'un ordinateur donc.

par **Quidam** » 25 Aoû 2008, 13:37

leon1789 a écrit::ptdr:
oui, ok, il n'y a pas d'erreur mathématique mais il y a quand même un petit quelque chose qui me chagrine dans cette phrase

avec la calculatrice de mon PC, je fais, manuellement ...) Pas besoin d'un ordinateur donc.

Faut-il tout préciser ? J'ai utilisé la calculatrice du PC par pure paresse, pour éviter de sortir ma calculatrice de mon tiroir. Mais j'ai utilisé mon PC manuellement en entrant chacun des nombres indiqués comme opérandes à la main :
pour calculer 76 fois 76, j'ai tapé sur 7 puis 6 puis *... ensuite j'ai cherché le modulo en otant du résultat de la multiplication le produit de 91 et de de la partie entière du résultat de la division par 91. Et ainsi de suite,..., exactement comme je l'aurais fait avec ma calculatrice.

!!!!

par **leon1789** » 25 Aoû 2008, 13:46

leon1789 a écrit:Il y a l'exponentiation dichotomique comme l'explique Quidam, mais cela demande une machine pour moi.

Quidam a écrit:Faut-il tout préciser ? J'ai utilisé la calculatrice du PC par pure paresse, pour éviter de sortir ma calculatrice de mon tiroir. Mais j'ai utilisé mon PC manuellement en entrant chacun des nombres indiqués comme opérandes à la main :
pour calculer 76 fois 76, j'ai tapé sur 7 puis 6 puis *... ensuite j'ai cherché le modulo en otant du résultat de la multiplication le produit de 91 et de de la partie entière du résultat de la division par 91. Et ainsi de suite,..., exactement comme je l'aurais fait avec ma calculatrice.

!!!!

Je comprends, je comprends : tu fais des calculs à la main quoi... même au doigt :ptdr:
Encore une dernière précision stp : une calculatrice, n'est-ce pas une machine ?

Cryptage RSA - Calcul d'un modulo

Cryptage RSA - Calcul d'un modulo

Qui est en ligne