Modulo de très grands nombres [Résolu/Fermé]

Signaler
Messages postés
395
Date d'inscription
vendredi 1 mai 2009
Statut
Membre
Dernière intervention
8 novembre 2019
-
tomsawyer1311
Messages postés
395
Date d'inscription
vendredi 1 mai 2009
Statut
Membre
Dernière intervention
8 novembre 2019
-
Bonjour tout le monde,

Alors, voilà, j'ai un souci qui, je croyais, était minime mais qui ne me fait pas avancer du tout.

Sur le site du zéro, il y a 2 tutoriels sur l'algorithme RSA (qui permet de générer des clés publiques et privées).

Je commence à lire ce tuto : http://www.siteduzero.com/tutoriel-3-2320-l-algorithme-rsa.html
et au moment de générer les clés problème.

Comme convenu je choisis p et q comme nombres premiers.
Pour bien comprendre et ne pas bêtement copier je choisis mes nombres premiers.
Avec p = 101 et q = 133.
Je lis que n = p x q soit n = 101 x 133 = 13433.
Et phi (n) = (p-1) x (q-1) soit phi (n) = 100 x 132 = 13200
Et e doit être strictement supérieur à p et q et le PGCD de phi (n) et e doit être égal à 1.
e = 137.
J'ai p = 101 ; q = 133 ; n = 13433 ; phi (n) = 13200 ; e = 137.

Pour coder on utilise e et n de cette façon :
ca^e % n = cc
avec ca : caractère en ASCII
% : modulo (le reste de la division euclidienne)
cc : caractère codé

Et là c'est le drame.
Alors que la calculatrice d'Ubuntu m'a parfaitement calculé des opérations simples voilà qu'elle peine avec les puissances et modulos de grands chiffres.

Je décide avec mon petit bagage en C de créer un programme pour calculer les puissances et modulo demandés.

Catastrophe, gcc (le compilateur que j'utilise) me jette littéralement à la gueule : "Tu m'emmerdes avec tes double, utilise des int."

Je m'exécute et ne mets que des int.
Problème, pas besoin d'être fin mathématicien pour savoir que 72^137 dépassera le nombre maximal qu'on peut avoir avec int (ou ses voisins proches, les unsigned int, long long int etc...)
(Oui, le message à coder est "Help !" et 72 est le code ASCII de "H")

Si une âme charitable veut bien m'aider à sortir de ce pétrin, je lui en serai reconnaissant.



<config>PC Portable Ubuntu 10.04 LTS, Mozilla Firefox 4>

7 réponses

Messages postés
16141
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
30 mars 2020
2 570
Je te conseilles plutôt ce tutoriel dont la deuxième partie t'apprends à utiliser GMP en C
1
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 76877 internautes nous ont dit merci ce mois-ci

Messages postés
509
Date d'inscription
jeudi 19 mai 2011
Statut
Membre
Dernière intervention
1 octobre 2014
7
La bibliothèque gmp est faite pour ca.
Pour savoir l'utiliser:
https://openclassrooms.com/fr/courses
Sheeps.
1
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 76877 internautes nous ont dit merci ce mois-ci

cap'tain sheeps
Messages postés
509
Date d'inscription
jeudi 19 mai 2011
Statut
Membre
Dernière intervention
1 octobre 2014
7
enfin si tu le fais en C++, après, normalement, pour calculer ce genre de nombre tu peux programmer un algorithme d'exponentiation rapide:
Par exemple pour 72^137, tu décompose 137 en puissance de 2, ce qui donne:
128+8+1
Ensuite vu que c'est de la criptographie, tu devra faire modulo un nombre et bah tu le fera au fur et à mesure de ton exponentiation rapide. Si tu fais mod 5 par exemple. (Je vais pas mon compliquer la vie avec de grands nombres ^^), ca donne:
72^1 % 5 = 72 % 5 = 2
72^2 % 5 = 2^2 % 5 = 4
72^4 % 5 = 4^2 % 5 = 1

Bon la je tombe sur 1, ca va me simplifier la vie, vu que 1^2 = 1 donc 72^8 =1 et 72^128 = 1 (en fait toutes les puissances de 2 d'après)

=> tu reprend ton nombres avec les nouvelles valeur:
Tu sais que 72^137 = 72^(128+8+1) = 72^128 * 72^8 * 72^1
Ce qui modulo 5 = 1 * 1 * 2 = 2

Voilà, bon la j'ai choisi des valeurs faciles pour pas m'emm****er mais si tu n'as pas compris dis-le moi et je ferrais avec un nombre plus grand.
cap'tain sheeps
Messages postés
509
Date d'inscription
jeudi 19 mai 2011
Statut
Membre
Dernière intervention
1 octobre 2014
7
Bon allez, je t'ai fais le début mais c'est bien parce que je suis au taff hein ... ^^
#include <stdio.h>

int main(int argc,char **argv)
{
    int nombre, exposant, modulo;// le nombre décomposé en 3
    int i,j; // les itérateurs nécessaires
    const int TAILLE = 100; //ca devrais suffire
    int tableau[TAILLE]; //tableau pour stocker la décomposition en puissance de 2

    printf("nombre? :");
    scanf("%d", &nombre);
    printf("\nexposant? :");
    scanf("%d", &exposant);
    printf("\nmodulo? :");
    scanf("%d", &modulo);

    i=1;
    while( i < modulo) //pour prendre la plus grande des puissances de 2
    {
        i = i*2;
    }
    if (i != modulo)
    i = i/2; // mais inférieure au nombre quand meme donc une itération en moins
    j = 0;
    while(modulo > 0) //décomposition en puissance de 2
    {
        if(modulo >= i)
        {
            tableau[j] = i;
            j++;
            modulo = modulo - i;
            i = i/2;
        }
        else
        {
            i = i/2;
        }
    }
    //bon là tu as ta décomposition dans le tableau et tableau[0] est le plus grand, ce qui sera ton marqueur de fin pour l'exponentiation rapide
    return 0;
}
cap'tain sheeps
Messages postés
509
Date d'inscription
jeudi 19 mai 2011
Statut
Membre
Dernière intervention
1 octobre 2014
7
Mouais, je me suis planté quelque part, je corrige ca...
tomsawyer1311
Messages postés
395
Date d'inscription
vendredi 1 mai 2009
Statut
Membre
Dernière intervention
8 novembre 2019
20
Ce n'était pas la peine de me commencer un programme, mais c'est gentil quand même merci. En fait, j'apprends ce langage assez complexe je trouve. Il y a certaines choses que je maîtrise assez (variables, conditions et boucles) d'autres où j'y travaille (les pointeurs surtout).
Là, c'est juste que je voulais tester l'algo RSA sur papier, or je pensais que mon ordi me remplacerait haut la main en ce qui concerne les calculs.
Mais, je vais lire ton code. Ca me fera progresser.
cap'tain sheeps
Messages postés
509
Date d'inscription
jeudi 19 mai 2011
Statut
Membre
Dernière intervention
1 octobre 2014
7
Mouais, j'ai fais ca parce que je m'ennuyais, après le code n'est pas vraiment utile. Pour tout te dire, ce que j'ai fais c'est seulement pour décomposer l'exposant en puissance de 2, ce qui est beaucoup moins long dans une application précise qu'en traitant avec des variables.
Le plus important, c'est le raisonnement mathématique de mon premier post, ne t'attardes pas sur ce morceau de code ;).
Messages postés
253
Date d'inscription
vendredi 23 février 2007
Statut
Membre
Dernière intervention
1 mai 2014
29
Salut,
utilise des long ( grand entrier )
Messages postés
395
Date d'inscription
vendredi 1 mai 2009
Statut
Membre
Dernière intervention
8 novembre 2019
20
Ok, j'essaie ça.
Je t'en dis plus.
Messages postés
395
Date d'inscription
vendredi 1 mai 2009
Statut
Membre
Dernière intervention
8 novembre 2019
20
Bon, ça fonctionne pas. En fait si mais, ça me mets le nombre long le plus élevé. Je vais réessayer avec des double ça devrait être possible.
Messages postés
395
Date d'inscription
vendredi 1 mai 2009
Statut
Membre
Dernière intervention
8 novembre 2019
20
Bon, alors je pensais avoir trouvé la solution mais non.

J'ai utilisé la fonction fmod() qui avait l'air de bien fonctionner.
J'ai fait un test avec : 3 ^ 45 % 13433.
D'après le programme : 3 ^ 45 = 2954312706550833610752
D'après la calculatrice d'Ubuntu : 3 ^ 45 = 2 954 312 706 550 833 698 643
Ensuite, 3 ^ 45 % 13433 donne :
dans le programme : 819
dans la calculatrice : 8112.
C'est pas très mathématiques tout ça. Je taquine bien entendu.
tomsawyer1311
Messages postés
395
Date d'inscription
vendredi 1 mai 2009
Statut
Membre
Dernière intervention
8 novembre 2019
20
J'ai testé le résultat donné par le programme de 3 ^ 45 soit 2954312706550833610752
Je l'ai copié dans la calculatrice et fait le modulo 13433.
Ca me donne bien : 819.

Je pense que "mon" programme est bon mais très mal optimisé. De toute façon ce n'est pas le but.
Bonjour
Pas besoin d'être fin mathématicien pour voir que 3 ^ 45 = 2954312706550833610752 est faux.
Une puissance entière de 3 se termine par 1,3,9 ou 7.
Suis le conseil de KX et utilise une bibliothèque faite pour manipuler les nombres avec un nombre arbitraire de chiffres significatifs.
tomsawyer1311
Messages postés
395
Date d'inscription
vendredi 1 mai 2009
Statut
Membre
Dernière intervention
8 novembre 2019
20
J'ai du mal à te suivre concernant les puissances de 3.
En ce qui concerne la lecture du tuto conseillé par KX j'y compte beaucoup évidemment.
Pour les puissances de 3 :

Remarque : pour avoir le chiffre des unités d'une multiplication, il suffit de multiplier les chiffres des unités des deux nombres :
1265877467 * 6385864633 finit comme 3*7, c'est à dire par 1. Il suffit de poser la multiplication comme pour la faire à la main, et c'est évident

commence par 3 puissance 0 ->1
tu multiplies par 3 ->3 finit par 3
tu multiplies par 3 -> 9 finit par 9
tu multiplies par 3-> 27 finit par 7
tu multiplies par 3 -> finira comme 3*7 = 21 -> par 1
tu multiplies par 3 -> finira comme 3*1 -> par 3
et ça continue 9,7,1,3,9,7...
tomsawyer1311
Messages postés
395
Date d'inscription
vendredi 1 mai 2009
Statut
Membre
Dernière intervention
8 novembre 2019
20
Merci beaucoup pour ton explication le père. J'avais testé sur la calculatrice mais comme tu l'écris c'est parfait.
Bon je vous laisse.
Pourvu que la nuit me porte conseil.

Ciao
Tom
Messages postés
395
Date d'inscription
vendredi 1 mai 2009
Statut
Membre
Dernière intervention
8 novembre 2019
20
Alors, grâce à cap'tain sheeps et KX surtout, j'ai résolu le problème, enfin GMP a résolu mon problème.

Je vais pouvoir continuer l'apprentissage de cet algorithme.

Merci beaucoup.

Ciao
Tom