RSA CRYPTO EN C POUR GCC LINUX
coucou747
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
-
16 avril 2004 à 13:59
coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 - 19 juil. 2004 à 20:20
coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 - 19 juil. 2004 à 20:20
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/22003-rsa-crypto-en-c-pour-gcc-linux
https://codes-sources.commentcamarche.net/source/22003-rsa-crypto-en-c-pour-gcc-linux
19 juil. 2004 à 20:20
13 juil. 2004 à 14:45
On avait notament parlé d'une librairie permettant de crypter en rsa avec des nombres énormes, on avait parlé des algorythmes de cryptographie, asymétriques et symétriques, ect...
J'ai toujours mon problème en C pur, j'arive pas a faire la surchage d'opérateurs, et la division, je ne vois toujours pas
23 avril 2004 à 22:32
23 avril 2004 à 20:13
23 avril 2004 à 12:43
21 avril 2004 à 14:17
Cette operation est beaucoup plus couteuse en temps de calcul que (rand() %10). Et oui celle que tu conseille travaille sur des flottants, ce qui est _long_. En plus il faut 1 multipliacation, 1 division et 1 addition... Au niveau rapidite c est une horreur (je vais faire un petit programme pour comparer).
Sinon pour avoir des nombres aleatoires "solides", voir /dev/urandom sous Linux et presque tous les autres Unix...
21 avril 2004 à 12:55
bref a mediter jai bien dit... ceci dit c'est la bonne methode a utiliser, mais pour etre vraiment sur d'avoir un tirage aleatoire, il faut utiliser des algorithmes de generation de nombres pseudo-aleatoires plus compliqués que rand(), qui est il faut le dire quand meme, "assez" previsible. J n'ai pas d'exemple a donner sous la main, mais en cherchant sur le net nul doute que vous trouverez votre bonheur.
20 avril 2004 à 17:59
20 avril 2004 à 12:50
a noter que ceci est une horreur et n'est pas une bonne facon de faire : l'operation % est d'une part une opertation couteuse en temps de calcul. Et il me semble aussi qu'elle agit sur les bits de poids faible pas aussi imprevisibles que les bits de poids fort.
A faire donc : (exemple)
Si vous désirez engendrer un entier aléatoire entre 1 et 10, vous devez toujours procéder en utilisant les bits de poids forts, comme dans :
j=1+(int) (10.0*rand()/(RAND_MAX+1.0));
et jamais ainsi :
j=1+(rand() % 10);
(extrait du manuel man sous linux)
a méditer donc.
Pour l histoire des tres grand nombres il existe des algorithmes efficaces (lancer lami google pour lui demander) de multiplication de grands entiers, et de tests de primalité.
18 avril 2004 à 20:30
18 avril 2004 à 20:29
Sinon je connais une routine pour generer des nombres pseudo-aleatoires, quand je la retrouve je la poste!!!
18 avril 2004 à 19:53
18 avril 2004 à 01:31
unsigned long int n = ...;
unsigned long int hasard = 0;
for(int i = 0; i + RAND_MAX < n; i+=RAND_MAX)
hasard += rand()%RAND_MAX;
hasard += rand() % (n % RAND_MAX);
comme ça on s'en sort.
18 avril 2004 à 00:10
int i=0;
int nombre[100000]
nombre[0]=9999
while (i<100000){
i++
nombre[100000]=un nombre aléatoire entr 0 et 9 compris
}
et de cette façon, nombre[0] est le nombre de chiffre du nombre, nombre[1] le chiffre des unitées, nombre[2] le chiffre des dizaines...
17 avril 2004 à 23:49
int i=0;
int nombre[100000]
nombre[0]=9999
while (i<100000){
i++
nombre[100000]=un nombre aléatoire entr 0 et 9 compris
}
et de cette façon, nombre[0] est le nombre de chiffre du nombre, nombre[1] le chiffre des unitées, nombre[2] le chiffre des dizaines...
17 avril 2004 à 22:02
"par contre rand() te donne un nombre entre 0 et RAND_MAX donc si tu veux un nombre entre 0 et n il faut faire (rand() % n). Voila!!"
Y a un problème avec ça, c'est qu'en général RAND_MAX vaut 32767, et donc tu ne peux pas générer de nombre au hasard au delà de cette limite, et en RSA on traîte des grands nombres. Multiplier le résultat par une constante n'est évidemment pas une solution, puisqu'on obiendrait alors une plage de valeurs discrète, et donc un hasard trompé. Comment on fait si on a besoin d'un nombre au hasard entre 0 et n, avec n un réel positif non limité? je sais bien qu'il n'y a pas de hasard en informatique, mais il y a sûrement une routine qui le simule.
17 avril 2004 à 17:47
17 avril 2004 à 14:58
17 avril 2004 à 14:12
rsa utilise une version presque identique, qui dit que si un entier n = p1.p2 (p1 et p2 etant premiers), et bien tout entier e < n (ou bien e non multiple de n...) vérfie la propriété : n est un diviseur de e^((p1-1)(p2-1))-1
il s'agit 'presque' de la généralisation d'euler du théoreme de fermat, sauf ke e et n n'ont pas besoin d'etre premiers entre eux.
17 avril 2004 à 14:04
17 avril 2004 à 13:27
Enfin, tu feras sans alors, mais je vois pas comment tu peux t'en tirer... si j'en crois les différents textes à ce sujet sur internet, c'est le moyen le plus efficace.
17 avril 2004 à 13:22
17 avril 2004 à 13:14
17 avril 2004 à 12:16
le return, je penses pouvir régler le problème avec ta solution, merci.
pour le nombre premier, je ne connais pas la formule ou l'algorythme de test (sauf celui du programme qui est beaucoupzs trop long)... Je suis allé sur plein de sites, mais ils n'expliquent rien...
17 avril 2004 à 11:57
Pour obtenir un nombre aleatoire, et si la meilleure solution c etait rand(). Mais attention il faut initialiser le generateur aleatoire avec srand().
Le plus courant est de faire :
#include <time.h> // pour time()
/* ... */
srand(time(NULL));
par contre rand() te donne un nombre entre 0 et RAND_MAX donc si tu veux un nombre entre 0 et n il faut faire (rand() % n). Voila!!
Non tu ne peux pas faire ce que tu dis pour %, * et /. Parce que si tu dois prendre le modulo d un nombre tres grand, ton programme va etre incroyablement lent (il ne pourra sans doute meme pas finir en 10 ans de calcul sur le meilleur P4...). Pareil pour *. Imagine que tui dois calculer le produit de 2 nombres de 100 chiffres...bon courage avec ta methode...
Non il faut tout reprendre comme au primaire pour * et /, et pour % je ne sais pas :-(
Et puis meme si tu programme ces fonctions il te faudra d autres algorithmes comme l exponentiation modulaire rapide, pour calculer rapidement (a^b) % n,...
Je ne comprend paas tres bien tn probleme de return... return marche sur un tableau!! il renvoie un pointeur sur celui-ci, mais si ton tableau est local a la fonction, c est la que tu vas faire un SEGFAULT...
17 avril 2004 à 11:47
ma calculatrice, c'est une ti83+ silver éditoin... 1mo5 de mémoire...
et ta calto n'est surement pas plus performante que la ti92+... je sais qu'il y en a d'autres, mais à 2* plus cher...
Pour ma librairie, c'est facile, que ce soit /*-+ ou encore %
pour le %, il suffit de faire - jusqu'a ce que le nombre soit plus petit...
idem pour le / mais en comptant combien de fois on peut faire -
pour * c'est un peu plus compliqué, car les nombres ne doivent pas prendre plus d'un octet, sinon, je vais faire une erreur de mémoire (ségmentation fault)... je dois donc aussi faire une fonction qui si le chiffre est + grand que la base, alors on baisse le nombre de la base pour ajouter 1 au nombre suivant...
ce qui me pose problème, c'est a la sortie de toutes ces fonctions, comment main pourra t'elle recevoir l'argument... Le return fonctionnerais pour un nombre, mais pas pour autant...
17 avril 2004 à 11:31
Deja regarde bien ta calculatrice, ca doit etre un TI-83+, a moins que TI ai sorti un produit secret sans me le dire...
La TI-89 c est la meillleure calculatrice de TI, avec le calcul formel et le support des nombres jusqu a plusieurs centaines de chiffres (450! ca passe dessus!!!). Donc ce n est pas un programme, mais deja inclu dans la calculatrice.
gcc pour windows, j ai jamais essaye... je me souviens simplement avoir porte un programme sous Dev-C++ pour mo TPE l an dernier.
Pour utiliser des grands nombres, ils y a plusieurs voies :
- celle de la facilite : utiliser NTL qui est un librairies qui fait ca tte seule comme une grande et qui est en C++.
- la vraie voie, qui est de tout faire soit-meme, c est a dire ecrire une classe (ou un ensemble de fonctions) qui permettent de faire des operations sur des grands entiers. La methode est celle que tu as decrite : stocker dans un tableau, et faire les operations comme au primaire (pour +, - et x ca passe, mais beaucoup moins bien pour /...).
Apres pour creer un nombre premier enorme, on n est pas sur qu il soit premier, mais presque sur!!! En fait on genere un nombre tres grand aleatoirement et on teste si il a des chances d etre premier (algorithme de Miller-Rabin, qui donne la probabilite qu un nombre soit premier tres vite par rapport a un vrai test), et on recommence jusuq a ce que le nombre passe le test....
Pour que le nombre soit aleatoire, il suffit de remplir chque case memoire (chaque chiffre) avec un nombre aleatoire!
17 avril 2004 à 11:20
Bref, j'y comprends rien...
J'avais trouvé gcc pour windows, mais le problème c'est que pour l'installer, il faut modifier autoexec.bat, et que sous xp, il est présent, mais on ne s'en sert pas...
Le réseau, je n'y ai pas encre touché, les graphismes non plus, je pensais à sdl pour les graphismes, mais voile, c'est compliqué...
Simple question a part : Comment votre ti89 a pu supporter un nombre de 70 bits ?!?! j'ai une ti93+se et elle refuse les nombres de plus de 10 chiffres si on ne veut pas les passer en float, et en float, ils perdent leur précision... Je serais curieux de voir le programme...
Vous parliez de routine au début, pour pouvoir utiliser des nombres de + de 48 bits, comment la feriez vous ? moi je pensais à le stoquer dans un tableau, un [0] le nombre de chiffre, en [1] le chiffre des unitées, en [2] des dizaines, et ainsi de suite... Le problème, c'est que je ne sais pas comment on peut modifier une variable au retour de fonction, et un tableau ne passe pas en teturn...
Autre problème, pour crée des clées, comment créer un nombre premier énorme ?
Autre problème Coment faire que ce nombre soit aléatoire ?
C'est pour ces quelques raisons que j'ai décidé de limiter à 48 bits...
17 avril 2004 à 11:05
Comme compilateur tu peux essayer celui de microsoft, mais il va pleurer a cause de plein de choses...
En fait utilise plutot Dev-C++, qui est un portage de gcc sur windows (a ce que j ai compris) et qui possede un IDE pas mal.
Par contre pour tes sources reseau, il va falloir reecrire ca avec l API winsock, mais les differences sont mineures. La ou c est plus relou c est avec getopt() qui existe pas sous windows!!!
17 avril 2004 à 11:01
quand on veut se faire se déplacer une image... DSL mon site n'est plus en ligne, on me l'a supprimé de dyndns.org car je le remettait a jours trop souvent...
Franchement, le linux c'est super, mais j'aimerais savoir quel compilateur c est gratuit et fonctionne parfaitement sous xp, car pour mes potes, le linux c'est compliqué, et ils ne s'y metterons jamais (j'ai 15 ans, je suis en seconde, je programmais avant en qbasic quand j'étais en sixième, je suis passé au html, puis au javascipt, ensuite au tibasic puis au c, je suis entrain d'essayer le php...) Bref, je suis plus motivé que mes potes, ils ne pensent qu'a jouer, mais j'aimerais quand même leur passer mes programmes...
17 avril 2004 à 10:50
En plus RSA n offre AUCUNE securite en dessous d un certain seuil, et tu es malheureusement en dessous de celui-ci (a titre d exemple ma TI-89 factorise en quelques secondes un nombre de 70 bits...).
Sinon pour Linux je suis tout a fait d accord!! Konqueror est pas mal, mais il ne vaut pas Mozilla.
16 avril 2004 à 20:34
Et merci pour ton code. J'pense aussi que 48 bits suffisent.
On ne va pas crypter des docs du FBI et MI6 etc. qui sont si secrets que qqun se ferait la peine de faire du brute force pendant des heures et des heures ...
[LinuX RuleS]
16 avril 2004 à 19:11
J'utilise konqueror comme naviguateur...
16 avril 2004 à 18:20
J ai pas encore regarde ton code, mais il me parait bien leger pour du RSA complet. Ce que je veux dire par la c est que RSA pour que ca marche il faut utiliser des nombres de plusieurs centaines de chiffres, donc programmer une gestion specifique...
16 avril 2004 à 18:15
16 avril 2004 à 17:11
Sous linux, les retours à la lignes sont fait en un seul caractère alors que sous windows, il en faut 2, donc on ne peut pas lire ceci facilement.
Wordpad fait la convertion, mais je n'ai pas wordpad, je suis dsl pour deux qui ont la flème de copier coller dans un wordpad, mais je ne vois pas comment ils auraient fait de toute façon pour le compiler autrement.
16 avril 2004 à 17:02
16 avril 2004 à 13:59