Besoin d'aide pour la cryptographie RSA

Baptiste35
Baptiste35
dans Arithmétique
Bonjour, Bonsoir
Je suis actuellement en terminale et je m'intéresse au protocole de chiffrement RSA qui fait intervenir l'arithmétique modulaire (au programme de Mathématiques Expertes).
Malgré le suivi des instructions depuis ce site https://www.dcode.fr/chiffre-rsa pour chiffrer un nombre quelconque avec cette méthode de chiffrement je ne retombe pas sur le nombre en clair lors du déchiffrement.
Je sollicite donc votre aide pour m'aiguiller sur ce problème, sur ce que j'aurais malencontreusement oublié de faire !
Je vous remercie d'avance de l'attention que vous porterez à ce message !

Voici mes paramètres :
$p=391$
$q=402$
donc $n=157182$
je pose $m=(p-1)\times(q-1)$ donc $m=156390$
je choisis $e=217$ car $PGCD(m;e)=1$ et $e<m$
Je trouve $d=107383$ car $e.d\equiv1\,[m]\,\Rightarrow\, 107383\times217=1\,[156390] $

En prenant par exemple le nombre en clair: $37084$

A) Chiffrement du nombre $37084$
$C\equiv\,M^{e}\,[n]\,\Rightarrow\,C\equiv37804^{217}\,[157182]\,\Rightarrow\,C\equiv\,106348\,[157182]$

B) Déchiffrement du nombre chiffré : $106348$
$M\equiv\,C^{d}\,[n]\,\Rightarrow\,M\equiv\,106348^{107383}\,[157182]\,\Rightarrow\,M\equiv\,69364\,[157182]$
Alors que je devrais normalement retomber sur le nombre en clair $37084$.

Réponses

  • Dreamer
    Dreamer
    Bonsoir.

    Si je peux me permettre, il me semble que les nombres à utiliser comme paramètres doivent être premiers, ce qui n'est le cas d'aucun de ceux que vous présentez.

    À bientôt.

    Cherche livres et objets du domaine mathématique :

    Intégraphes, règles log et calculateurs électromécaniques.

  • Sneg
    Sneg
    Bonjour,

    Soient :
    1) Ton "numéro" : $157182$ $(=391\times402)$. Ce numéro est public, mais tu es censé être le seul à pouvoir le factoriser.
    2) Ta "clef" : $217$ $(=7\times31)$. Cette clef est publique également.
    Et supposons que je veuille t'envoyer le message $37084$.

    Quelque chose m'intrigue dans ton message.
    Tu poses : $m=(p-1)\times(q-1)$. Etrange.
    Etant donné que $391=17\times 23$ et que $402=2\times3\times67$, si tu cherches en réalité à calculer $\phi(391\times402)$, où $\phi$ est l'indicatrice d'Euler, alors tu obtiens : $(17-1)\times(23-1)\times(2-1)\times(3-1)\times(67-1)=46464$.

    Ici, bien que tes nombres $p$ et $q$ ne soient pas premiers, tout fonctionne quand même grâce au fait que ta clef est première aussi bien avec ton numéro qu'avec $46464$. Voyons ça :

    Puisque $37084^{217}\equiv 47338\pmod{157182}$, le message initial $37084$ est maintenant crypté sous la forme $47338$.

    Etant donné que tu peux décomposer ton "numéro" en facteurs premiers et donc calculer $\phi(157182)=46464$, tu peux décrypter le message $47338$ comme ceci : $47338^x\equiv 37084 \pmod{157182}$. Et hop ! On retrouve bien le message initial $37084$.

    Le meilleur étant toujours pour la fin, on calcule $x$ comme ceci (équation diophantienne) :
    $217x+46464y=1$ (C’est ici qu’apparaît $\phi(157182)=46464$, obtenu par la décomposition de $157182$ en facteurs premiers, opération que tu es le seul à pouvoir faire, par hypothèse.)
    Sur Wolfram Alpha, il suffit d'introduire la commande (sans les guillemets) : "solve 217x+46464y=1 for x and y integers".
    La réponse ne se fait pas attendre : $x=-46464n-41111$...(for $n\in\mathbb{Z}$).
    En donnant à $x$ la plus petite valeur strictement positive, on obtient $x=5353$.

    Ajout :
    Visiblement, Baptiste35, nous n’utilisons pas le même vocabulaire. Je reviendrai dès que possible pour accorder nos violons.
  • Sneg
    Sneg
    Bonjour, Baptiste35,
    Me revoilà, avec des notations semblables aux tiennes !

    $p=391$ $(=17\times23)$
    $q=402$ $(=2\times3\times67)$
    Tu as fait là une entorse à la règle qui demande que l'on choisisse deux nombres premiers. C'est ce qui t'empêche d'utiliser dCode.
    Qu'à cela ne tienne, continuons.

    $n=p\times q=157182$
    $m=156390$. Première erreur. En réalité, $m=\phi{(157182)}=(17-1)\times(23-1)\times(2-1)\times(3-1)\times(67-1)=46464$.
    $e=217$. Coup de chance, $217$ est premier avec $46464$. Sans cela, tout serait parti en vrille.
    $d=107383$. Seconde erreur, causée par un mauvais calcul de $m$. En réalité, $d=5353$.

    Donc, la clef publique (de chiffrement) est $(157182, 217)$, tandis que la clef privée (de déchiffrement) est $(5353, 157182)$.

    Vérification "à la main", à partir du message en clair $37084$ :
    Chiffrement :
    $37084^{217}\equiv 47338\pmod{157182}$.
    Le message initial $37084$ est maintenant crypté sous la forme $47338$.
    Déchiffrement :
    $47338^{5353}\equiv 37084 \pmod{157182}$
    Le message initial $37084$ a bien été récupéré.
  • noradan
    noradan
    Il faut absolument que $p$ et $q$ soient premiers puisque tout repose sur le petit théorème de Fermat qui nécessite des nombres premiers.

    Si la chose t'intéresse alors complète le travail en examinant l'exponentiation rapide afin de calculer ces puissances gigantesques intelligemment.

    Si d'aventure tu fais aussi de l'info le tout est très intéressant et fait un joli programme.
    (je le fais faire à mes élèves !)
  • Sneg
    Sneg
    La règle (ou la tradition ?) dit, en effet, à propos du module de chiffrement $n$ :
    $n=p\times q$, où $p$ et $q$ sont des nombres premiers «grands».

    Mais qu’est-ce qui interdit d’écrire :
    $n=p\times q\times r$, où $p$, $q$ et $r$ sont des nombres premiers «grands» ?
    [À part le fait qu’on en arrive à créer un nombre « trop grand » à manipuler.]

    L’argument du petit théorème de Fermat ne me convainc pas. Euler l’a heureusement généralisé.
  • aléa
    aléa
    A taille du produit égal; je dirais que plus il y a de facteurs, plus c'est facile à craquer.
  • Sneg
    Sneg
    Hypothèse que je n’ai volontairement pas envisagée, en ajoutant un facteur premier $r$ au produit $p\times q$.
  • Dreamer
    Dreamer
    Bonsoir.

    C'est ce qu'il fallait faire.

    Baptiste35 utilisait la procédure applicable aux nombres premiers avec des nombres qui ne l'étaient pas.
    Avec l'explication de Sneg et de Noradan, il a tout ce qu'il faut pour comprendre la raison derrière le fait que cela ne fonctionnait pas.

    À bientôt.

    Cherche livres et objets du domaine mathématique :

    Intégraphes, règles log et calculateurs électromécaniques.

  • Sneg
    Sneg
    Ben oui.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 30

BouzarCidrolinVassilliachaniggai requinjelobreuil +24 Invités