Commentaires sur une source : CODAGE RSA SUR 1024 BITS

jourgun Messages postés 19 Date d'inscription vendredi 21 février 2003 Statut Membre Dernière intervention 27 août 2007
14 mars 2005 à 01:18

oui, mais le hard révèle une réalité mathématique ( et universelle) du problème : il est plus dur de diviser que de multiplier.

contax Messages postés 20 Date d'inscription lundi 17 janvier 2005 Statut Membre Dernière intervention 13 mars 2005
13 mars 2005 à 14:08

deux commentaires plus haut que celui-ci : je parle algorithme pas hardware.

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
13 mars 2005 à 14:04

"Division et multiplication c'est kif kif"
faut ouvrir un manuel Intel !!! le rapport est 2.5 en benef pour la multiplication.

contax Messages postés 20 Date d'inscription lundi 17 janvier 2005 Statut Membre Dernière intervention 13 mars 2005
13 mars 2005 à 14:02

Ce que je veux dire c'est qu'il exite un Karatsuba pour la division, une FFT pour la division, tout comme pour la multiplication.

coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 44
13 mars 2005 à 13:50

tout dépends de ta multiplication... la division, ça a toujours été très lent, la multiplication t'as la transformée de fournier qui aide...

jourgun Messages postés 19 Date d'inscription vendredi 21 février 2003 Statut Membre Dernière intervention 27 août 2007
13 mars 2005 à 13:06

Ben non.. j'ai fait les mesures ( avec RDTSC) et j'ai bien vu que on passe beaucoup plus de temps pour faire les division que pour faire des multiplications

contax Messages postés 20 Date d'inscription lundi 17 janvier 2005 Statut Membre Dernière intervention 13 mars 2005
13 mars 2005 à 12:30

Division et multiplication c'est kif kif bourricot. Mais si c'est 'chiant', alors là y'a rien à faire. J'comprend.

jourgun Messages postés 19 Date d'inscription vendredi 21 février 2003 Statut Membre Dernière intervention 27 août 2007
13 mars 2005 à 11:17

Je ne connaissait pas Karatsuba. J'ai été sur internet et j'ai vu que c'était très interessant... mais surtout très chaint a programmer de manière efficace ( si on veut que sesoit efficace, il faut que se soit itératif et pas récursif). De plus, les processeur modernes effectuent la multiplication en très peu de temps ( 2 à 3 fois plus long q'une addition, selon la facon dont elle est programmée). Donc cet algo est très efficace sur les processeurs anciens mais je pense pas que le gain de temps sera éorme sur un atlon 64 puisque en fait, d'après ce que j'ai compris, on augmente le nombre d'additions a faire. De plus, contrairement à ce que l'on pourrait croire, la majeure partie du temps est passé à faire la division et a faire les copies des objets.
Donc je ne réécrirait pas mes fonctions operator* pour toutes ces raisons

contax Messages postés 20 Date d'inscription lundi 17 janvier 2005 Statut Membre Dernière intervention 13 mars 2005
13 mars 2005 à 09:27

Ok, j'ai été peut être un peu trop agressif ... Je vais reprendre les choses zenement, et expliquer clairement comment j'interprète la phrase ci-dessus, et pourquoi je fus agressif envers son auteur, après deux ou trois choses :
- Arnaud : c'est d'algorithmie dont je parle. Ici c'est la rubrique crypto. on utilise des modules de 1024 bits, (parce que jourgun en a fait le choix, mais on utilise aussi bien du 2048, 4096 bits ...) autant dire que la recherche d'efficacité ici est une motivation incontournable pour les calculs (parce qu'on ne fait QUE des maths, beaucoup de multiplications très couteuse). Or cette efficacité est théorique et se rencontre dans les bouquins de math et d'algo, et en parcourant le code source de bibliothèques de renom. Rien à voir avec une notion de 'confiance', je parle d'apprentissage et de culture informatique. comme si tu voulais développer ton propre player, tu ne va pas réinventer la roue, même si tu veux tout développer par toi-même, tu vas repiquer les idées (voir directement le code) de ceux qui excellent en la matière, ce sera efficace et ça t'apprendra beaucoup...
"Bien d'accord, se passer tant qu'on peut de libs additionnelles garantit qu'on reste le patron de son code."
D'abord cette remarque est écrite par quelqu'un qui m'a exposé sa vision du logiciel libre. Elle prend tout son sens à la lumière de cette opinion, et c'est ainsi eclairé que je m'énervasse. En effet, utiliser des librairies ésotériques dont le code source est jalousement tenu secret n'est pas vraiment alléchant, je suis d'accord. En revanche, nous, nous vivons dans un monde libre et pouvons consulter ce que de grands mathématiciens produissent lorsqu'ils s'interesssent à la prog : ne nous privons pas de le faire. Quand à rester 'patron' de son code, c'est un état d'esprit directement issu de la vision du monde précitée. En fait cette remarque était gratuite et n'a, à mon avis, que très peut de rapport avec jourgun qui code son RSA ... C'est la gratuité de cette remarque lourde de sous-entendus qui m'insupporte et le 'tant qu'on peux' n'arrange rien, le vrai troll était là, embusqué ...

J'avoue que je ne suis pas un fin cryptanalyse du mélage C++/asm mais il me semble que pour ta multiplication tu ne fais que multiplier à la queueleuleu les mots qui composent ton entier en propageant la (grosse) retenue. La multiplication étant centrale dans ce que tu fais, elle mérite d'être particulièrement optimisée. D'autant plus que tu as optimisé ton exponentiation avec l'algo binaire rapide, c'est dommage de perdre dans la multiplication le temps gagné. Utilise Karatsuba (en assembleur, puisque ça ne te rebute pas).

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
12 mars 2005 à 22:23

J'avais pourtant bien mis "tant qu'on peut", mais bon, inutile de continuer sur ce genre de troll.

Arnaud16022 Messages postés 1329 Date d'inscription vendredi 15 août 2003 Statut Membre Dernière intervention 16 juin 2010 2
12 mars 2005 à 22:16

????
Rien a voire avec la confiance que l'on met dans une lib que l'on utilise, contax
dans ce cas la, je ne fais plus confiance ni a opengl, ni a fmod, si a quoi que ce soit.
Je suis entierement d'accord avec ce que dit .. euhh je sé plus qui c'était, qqch que tu fais toi-meme, tu sais ce que ca fait, c'est approprié a tes besoins, en + t'es content d'avoir fait ca toi meme; ca ne t'empeche pas de te simplifier la tache en utilisant des trucs tout faits - qu'on serait incapables de reprogrammer, j'insiste la dessus. par exemple, j'utilise en ce moment le loader md2 de Digiben, je ne l'aime pâs, il me saoule, je le garde temporairement pour me consavrer a autre chose, mais je le referai un jour; par contre, fmod, je le garde, je ne pourrai jamais le refaire moi-meme.
++
Arnaud

contax Messages postés 20 Date d'inscription lundi 17 janvier 2005 Statut Membre Dernière intervention 13 mars 2005
12 mars 2005 à 20:09

" ... Bien d'accord, se passer tant qu'on peut de libs additionnelles garantit qu'on reste le patron de son code. ..."
C'est vraiment *** comme remarque.
tu ferai mieux de rester dans ta rubrique à vanter les mérites de windows. Je suis en ce moment les cours de math d'Henry Cohen l'inventeur (au sens propre) de la bibliothèque de calcul formel PARI devenu PARI/GP depuis qu'un looser (ironie liée à un message du forum où Brunews crache sur le libre) le maintient sous licence GPL. Je parle donc d'expérience
1) quand quelqu'un de ce gabarit à passé 20 ans de sa vie à developper une bibliothèque de grands nombres on l'utilise les yeux fermés (à moins d'avoir le niveau pour l'améliorer)
2) Du point de vue genie logiciel cette remarque (" ... se passer tant qu'on peut de libs additionnelles ...") est complètement anti-productive et limite idiote.
Ca n'a rien à voir avec ton code jourgun, ne le prend pas pour toi, j'aime coder je sais ce que c'est, c'est juste cette ****** de remarque qui m'énerve.

coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 44
5 mars 2005 à 18:23

RSA en théorie n'a rien de vraiment compliqué... c'est l'aplication à des nombres énormes en limitant le plus possible les pertes de vitesse qui est un vrai chalenge... et le test de miller rabin, sans compter les générateurs de nombres aléatoires qui doivent êtres les plus aléatoires... enfin, voila, c'est simple dans la théorie... complexe dans la pratique (d'ou la longueur du code, mais si tu veux te limiter à 23 bits, c'est vachement plus simple...)

Arnaud16022 Messages postés 1329 Date d'inscription vendredi 15 août 2003 Statut Membre Dernière intervention 16 juin 2010 2
5 mars 2005 à 15:33

ouah... bn ca confirme mon opinion, le rsa C pas pour moi :)

merci a Brunews pour les urls

jourgun Messages postés 19 Date d'inscription vendredi 21 février 2003 Statut Membre Dernière intervention 27 août 2007
4 mars 2005 à 23:29

Pour mon code, je suis franchement désolé des mauvaises habitudes que j'ai prises ( peu de commentaires.....) pourtant je trouve que j'en ai mis plus que d'hab. Le truc dur a comprendre en fait, c'est qu'il y a un peu d'asm en AT&T et pour les non-initiés.. c'est dur.

Pour la génération de mes nombres premiers : je dit que je suis sur qu'il s'agisse bien de nombres premiers mais je ne suis pas sur qu'ils soient suffisment aléatoires ( j'ai choisi un générateur à congruence linéaire.. assez prévisible)

Pour le 0 et le 1 je ne suis pas d'accord : il suffit d'ouvrir n'importe quel fichiers avec un éditeur hexadécimal pour voir que l'octet 0 est beaucoup plus utilisé que les autres, et il est tres probable de voir des séquences de 128 octets 0 de suite ( pour t'en convaincre, ouvre un simple .exe). Et ensuite, si tu crypte en 1024bits, tu ne pe pas avoir des blocs de 1024bits car sinon certain ne pouraient pas se crypter car supèrieurs à n. Donc en fait, une des solution ( une des plus simple = une des plus mavaises) et de prendre des blocs de 127octets ( ou moins) et de remplir le reste par des noombres aléatoires. C'est une solution assez mauvaise car elle réduit le nombre d'octets par blocs a trouver par le méchant ( et oui.. il y a le gentil et le méchant..) et donc c'est peut être plsu facile a trouver... bien que je n'en soit pas sur. Mais de toutes facon, RSA n'est jamais utilisé pour décrypter des messages directement

coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 44
4 mars 2005 à 21:55

"MAIS : le RSA seul est très vulnérable : il ne faut pas lui mettre en entrée des nombres particuliers (genre 1 ou 0, qui ne se cryptent pas et il y a d'autres cas particulers qui le rendent vulnérable)
Deuxieme MAIS : la génération de nombres premiers aléatoires de mon programme et très mauvaise. D'où une deuxième vulnérabilité."

j'ai du mal comprendre....

tu génère tes nombres premiers avec miller rabin... c'est pas encore sufisant ???

et sinon, en rsa on ne passe jamais de 0 ni de 1 car on mets le texte en bloc... t'as une probabilitée très faible d'obtennir un 0 : explication :
tu crypte en 1024 bits : donc tes blocs font 1024 bits (pour n le plus proche possible de la limite...)
donc, tu mets 128 octets dans un bloc... si en 128 octets tu arrives à tous les avoir à 0 c'est que t'as vraiment pas de chance... idem si ils sont tous à 0 sauf le dèrnier qui est à 1...

tu as une chance par bloc sur 2^1024 si je ne me trompes pas.... ça fait quand même peu de chances... surtout que tu metras que 120 blocs dans un mail environ...

j'ai pas comris ton code.... je ne suis pas assez familiarisé avec l'OO pour cela... et je n'ai pas assez de temps... mais promis, j'essairais de comprendre... Donc merci pour cette source.

Arnaud16022 Messages postés 1329 Date d'inscription vendredi 15 août 2003 Statut Membre Dernière intervention 16 juin 2010 2
4 mars 2005 à 19:50

j'y vais de ce pas, merci bien
:)

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
4 mars 2005 à 17:32

Arnaud16022 > Regarde ces explications (sommaires) sur l'intérêt du 64 bits données par mon pote Gilles Vollant:

http://www.winimage.com/misc/pcexpert_page2.pdf
http://www.winimage.com/misc/pcexpert_page28.pdf

Arnaud16022 Messages postés 1329 Date d'inscription vendredi 15 août 2003 Statut Membre Dernière intervention 16 juin 2010 2
4 mars 2005 à 17:16

Ok merci bcp pr ces explications :)
mais maintenant: rares sont les progs qui ont besoin de nombres aussi grands, déja 4 milliards C énorme.
je vois tout a fait l'intéret pour la recherche/ les grandes entreprises/les autres/..., mais en quoi un processeur 64bits va faire tourner GTA plus vite?

jourgun Messages postés 19 Date d'inscription vendredi 21 février 2003 Statut Membre Dernière intervention 27 août 2007
3 mars 2005 à 21:42

En ce qui concerne le 64 bits, je vais essayer d'être plus clair : avec un processeur 32bits, on est capable de faire nativement des opérations avec des nombres infèrieurs à 2^32(enviroon 4 miliards). Avec un processeur 64bits, on travaille avec des nombres de 64bits donc inférieurs à 2^64.

Pour RSA, on travaille avec des tres grands nombres (512, 1024 ou 2048 bits). Pour effectuer ces opérations, on décompose en nombres de 64 bits (ou 32bits). Pour simplifier, je prend un exemple : la multiplication de deux entiers de 128bits pour donner un entier de 256bits dans une plateforme 64bits
- on décompose chaque nombre de 128bits en nombres de 64bits comme ceci : n=a+b*2^64
- on fait la multiplication : n1 * n2= (a1+b1*2^64)*(a2+b2*2^64)=a1*a2 + (b1*a1 + b2*a2)*2^64 + b1*b2*2^128. Les multplications par 2^64 ou 2^128 sont très simples a faire et les autres sont des multiplications de deux nombres de 64bits ( faisables nativement par le processeur)
Ceci permet donc de faire 4 multiplications. Sur une plateforme 32bits, il faut décomposer chaque nombre en 4 nombres de 32bits et donc faire 16 multiplications.

Pour une multiplication, 64bits permet de faire 4 fois moins de multiplications. Pour l'addition et la soustraction, 2 fois moins. Et pour la division, 6 fois moins environ. On voit donc bien l'interet du 64bits...

Je ne sais pas exactement combien de temps j'aurais perdu à faire du 32 bits mais il y a au moins a mon avis un facteur 3 ou 4.

Pour rendre compatible ce code, il faut retaper tous ce qui est écrit en assembleur et bidouiller un peu pour la division. Perso, ca ne m'enchante pas du tout..

jourgun Messages postés 19 Date d'inscription vendredi 21 février 2003 Statut Membre Dernière intervention 27 août 2007
3 mars 2005 à 21:20

En ce qui concerne le cryptage, oui je suis sur qu'il crypte réellement car ceci n'est pas très complexe en fait.
MAIS : le RSA seul est très vulnérable : il ne faut pas lui mettre en entrée des nombres particuliers (genre 1 ou 0, qui ne se cryptent pas et il y a d'autres cas particulers qui le rendent vulnérable)
Deuxieme MAIS : la génération de nombres premiers aléatoires de mon programme et très mauvaise. D'où une deuxième vulnérabilité.
L'autre défaut de RSA est qu'il ne peut pas crypter des nombres > au modulo ( la partie commune aux deux clés). Donc RSA ne peut pas crypter tous les blocs de 1024bits. Du coup, quand on crypte avec RSA 1024, on crypte avec des blocs de 512bits max et on les transforme en blocs de 1024bits avec des fonctions redondantes.
De plus, RSA est très lent donc on l'utilise rarement seul : on l'utilise en fait pour crypter une clée symetrique permettant de décrypter le reste du message. Ceci permet aussi de choisir soi-même le bloc à crypter ( puisqu'il s'agit d'une clée choisie plus ou moins au hasard) et donc d'éviter les vulnérabilités dont j'ai parlé plus haut.

Arnaud16022 Messages postés 1329 Date d'inscription vendredi 15 août 2003 Statut Membre Dernière intervention 16 juin 2010 2
3 mars 2005 à 20:56

l'année derniere j'ai fait un TPE sur les codes secrets (bon pas exactement mais ...) et j'étais tombé sur un site tout ce qu'il y a de plus sérieux qui affirmait que 100 personnes max dans le monde sont capables de programmer un prog comme ca qui crypte réellement. Je n'ai jamais compris grand chose au systeme RSA, je ne peux donc pas juger, mais qu'est-ce qui te fait affirmer que ton prog est 100% sur ? (dans les limites du RSA bien sur)
Merci beaucoup de ta réponse, ca m'intéresse.
Autre question: en quoi le 64 bits est il un tel avantage? c'est + rapide de combien? y-a-t-il un moyen de rendre ces codes compatibles avec des machines traditionnelles, vu que si des applications sont dvpées en 64 bits, elles ne fonctionneront pas sur mon PC?
merci encore :)

++
ad

jourgun Messages postés 19 Date d'inscription vendredi 21 février 2003 Statut Membre Dernière intervention 27 août 2007
3 mars 2005 à 20:36

Voila j'ai modifié mon code mon palier à ce ki a été dit dans le message précédent et j'ai inliné quelques fonctions pour optimiser..

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
3 mars 2005 à 16:42

Bien d'accord, se passer tant qu'on peut de libs additionnelles garantit qu'on reste le patron de son code.

Pourquoi dans DecaleAdd() utilises-tu les registres > à r11 ? Tu forces le compilo à des PUSHs et POPs de ces registres, ça nuit gravement aux performances. Mieux vaudrait utiliser rax,rcx et rdx, non ?

jourgun Messages postés 19 Date d'inscription vendredi 21 février 2003 Statut Membre Dernière intervention 27 août 2007
3 mars 2005 à 15:31

oui je connais GMP.. mais le but était d'utiliser le moins de librairies possibles ( je trouve ca plus amusant)

cs_myrion Messages postés 21 Date d'inscription mercredi 2 février 2005 Statut Membre Dernière intervention 7 décembre 2005
3 mars 2005 à 14:49

et GMP par exemple pour générer tes nombres? C'est super optimisé, très rapide et bourré de fonctions pour manipuler de grands nombres (aucune limite supérieure... en théorie!)

jourgun Messages postés 19 Date d'inscription vendredi 21 février 2003 Statut Membre Dernière intervention 27 août 2007
3 mars 2005 à 14:15

euh.. non en fait ça me permet de tricher un peu et de faire un code plus performant que les autres ( et en plus c'est orienté objet.. donc ça me ralentit encore plus) : grâce au 64 bits, chaque opération est décomposé en moins d'opérations élémentaires et ca va plus vite..
Mais il faut pas tomber dans le piège du " oula mais il est super bien ce code : super rapide et tout" car en fait je bénéfitie du 64bits.

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
3 mars 2005 à 13:41

Je crois que tu es le 1er à déposer un code 64 bits.
Faut fêter ça, CHAMPAGNE...

CODAGE RSA SUR 1024 BITS

Votre réponse

Discussions similaires