C++ fonction mathématique a^b mod c [Résolu/Fermé]

Signaler
Messages postés
70
Date d'inscription
lundi 3 décembre 2007
Statut
Membre
Dernière intervention
4 décembre 2009
-
Messages postés
70
Date d'inscription
lundi 3 décembre 2007
Statut
Membre
Dernière intervention
4 décembre 2009
-
Bonjour,

je suis en train d'implémenter l'algorithme RSA et j'utilise des clé réelles prisent directement dans des certificats.
Ces clé sont très très très grnade et faire un boucle pour calculer tout cela reviens à attendre la fin des temps avant de crypter un message. Les "nombres" sont si grand qu'on doit les coder sur des int* ou des byte* alors faire une boucle sur un pointeur de 1024 bytes c'est long...

Après de nombreuses recherches j'ai trouvé une fonction en JAVA : modpow qui à l'air de faire cela super rapidement mais je me demande si quelqu'un ne connaitrait pas l'équivalent en C++.

Cordialement Kzanadeus.

13 réponses

Messages postés
1
Date d'inscription
mardi 11 mars 2008
Statut
Membre
Dernière intervention
11 mars 2008
1
Merci kzanadeus. mais c'est bon j'ai trouvé, comme c'était juste un petit programme pour un TP je n'ai pas fait une implémentation générale mais juste une rapidement qui me permet d'exécuter l'exemple du prof. Pour ceux qui ont des commentaires sur le code c'est pas la peine, prenez ce qui vous intéresse dedans mais je ne cherche pas du tout à l'améliorer, mais on peut s'inspirer de la fonction mathématique pour faire une vraie et belle fonction.


En fait j'ai décomposé la mise à la puissance partant du principe que:

si b= b1* 1 000 000 +b0 alors

a^b mod c = (((a^b1 mod c) ^ 1 000 000) mod c ) * a^b0) mod c


Pour gérer les nombre de grande taille j'utilise la librairie GMP pour le C++ (disponible dans les dépots d'Ubuntu Gutsy 7.10). Si vous l'utilisez n'oubliez pas de l'indiquer à la compilation et d'inclure les entêtes utiles.



// en tête à inclure
#include <math.h>
#include <gmpxx.h>


// Calcul de "a ^ b mod c" avec des type mpz_class et c < 1 000 000
mpz_class powmod2(mpz_class a, mpz_class b, mpz_class c)
{
        mpz_class res(a);

	for(int i=0; i < (b-1); i++)
	{
		res *= a;
		res = res % c;
	}
	return res;
}

// Calcul de "a ^ b mod c" avec des type mpz_class et c > 1 000 000
// On découpe le c pour accélérer le calcul, on utilise la propriété suivante
// a^(tmp1*1000000+tmp2) = (a^tmp1)^1000000 * a^tmp2
mpz_class powmod(mpz_class a, mpz_class b, mpz_class c)
{
	mpz_class res(a), tmp1, tmp2;

	if( b > 1000000 )
	{
		tmp1 = b / 1000000;
		tmp2 = b - tmp1 * 1000000;
		res = powmod2(powmod2(a, tmp1, c), 1000000, c) * powmod2(a, tmp2, c);
	}
	else
		res = powmod2(a, b, c);

	return res%c;
}




Compilation:
user@machine$ g++ monprog.cpp -lgmpxx -o mon_exe
1
Merci

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

CCM 76687 internautes nous ont dit merci ce mois-ci

Messages postés
29443
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
26 novembre 2020
6 982
As-tu regardé du côté de libraries dédiées ?
https://packages.debian.org/lenny/libcrypto++-dev
https://www.cryptopp.com/

Bonne chance
Messages postés
70
Date d'inscription
lundi 3 décembre 2007
Statut
Membre
Dernière intervention
4 décembre 2009
4
Merci pour les liens je vais voir si dans le tas je trouve la fonction qui m'intéresse.

Cordialement Kzanadeus.
Messages postés
70
Date d'inscription
lundi 3 décembre 2007
Statut
Membre
Dernière intervention
4 décembre 2009
4
Finalement la fonction est en C et elle n'est implémentable qu'avec un bon nombre d'autres fonctions.

Je préfèrerais un code source que je peux modifier a souhait plutot qu'un gros package comme celui là...

Mais j'ai bien peur de ne pas trouver mon bonheur.

Si tu as d'autres pistes je suis preneur, sinon merci.

Cordialement Kzanadeus.
Messages postés
29443
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
26 novembre 2020
6 982
Désolée je n'en connais pas. A part fouiller sur google ou essayer d'extraire un code minimal de la librairie je ne sais pas trop quoi te dire.

Bonne chance
Messages postés
70
Date d'inscription
lundi 3 décembre 2007
Statut
Membre
Dernière intervention
4 décembre 2009
4
J'ai trouvée une implémentation en JAVA d'une classe qui fait tout cela alors j'essaie de la traduire en c++ et de manière à être utilisable facilement. (http://docjar.com/html/api/java/math/BigInteger.java.html)

Google c'est même pas la peine j'ai passé des journée entière à chercher.

Merci de ton aide.
Messages postés
29443
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
26 novembre 2020
6 982
J'imagine que du coup ton problème est résolu ?
Messages postés
70
Date d'inscription
lundi 3 décembre 2007
Statut
Membre
Dernière intervention
4 décembre 2009
4
On va dire que oui...
Messages postés
29443
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
26 novembre 2020
6 982
:-) Alors bon courage !
Messages postés
70
Date d'inscription
lundi 3 décembre 2007
Statut
Membre
Dernière intervention
4 décembre 2009
4
Merci beaucoup, si j'arrive à faire une implémentation correcte en c++ à partir de ces sources j'essaierais de les mettres à disposition.

Merci de ton aide.

Cordialement.
Messages postés
70
Date d'inscription
lundi 3 décembre 2007
Statut
Membre
Dernière intervention
4 décembre 2009
4
J'ai finit par y arriver... malheureusement mon patron n'est aps vraiment d'accord pour fournir les sources...

Cordialement.
Bonjour,

J'ai le même problème que tu avais. C'est la seule chose qui me manque pour terminer un devoir de Communication Sécurisée de mon cursus de Master Informatique. Pourrais-tu me mettre sur la piste ou désobéir à ton patron en message privé après tu n'as que ma parole que je la divulguerai pas mais c'est déjà pas mal non? Je continue de chercher...
Messages postés
70
Date d'inscription
lundi 3 décembre 2007
Statut
Membre
Dernière intervention
4 décembre 2009
4
Salut,

dis moi ou tu bloque car j'ai réussi à le finir.

Tu devrais regarder les algorithmes mathématiques de l'exponentiation binaire :
https://fr.wikipedia.org/wiki/Exponentiation_rapide

Dis moi si tu as besoin de plus d'aide.

Cordialement.

kzanadeus.
Messages postés
70
Date d'inscription
lundi 3 décembre 2007
Statut
Membre
Dernière intervention
4 décembre 2009
4
Tant mieu pour toi, si tu as réussi ;)

Dans mon cas je ne pouvais pas utilsier de librairie déjà existante c'est pour cela que j'ai tout fait tout seul.

Et comme je travail sur des nombres vraiment très gros il fallait que cela tourne le plus rapidement possible sans pour autant que cela ne tue toute la ressource mémoire.

Cordialement Kzanadeus.