CodeS-SourceS est hébergé par Frontier.fr

Ce site au démarrage

begin process at 2012 05 27 14:37:57

Accueil Codes Tutoriels Forum Livres Emploi Services Connexion

Trouver un code source :

dans

[ Dernières recherches ]

Accueil >

CODAGE RSA SUR 1024 BITS

Information sur la source

Note :

5,25 / 10

Catégorie :Sécurité & Cryptage Classé sous :rsa, cryptographie, miller rabin, assembleur Niveau :Expert Date de création :03/03/2005 Date de mise à jour :05/05/2009 00:01:46 Vu :10 956

Auteur : jourgun

Ecrire un message privé

Commentaire sur cette source (28)

Ajouter un commentaire et/ou une note

Description

Cliquez pour voir la capture en taille normale

Génère un couple de clés privée/publique puis génère un message clair au hasard, le crypte puis le décrypte, en utilisant l'algorithme RSA. Utilise 3 classes gérant des nombres de 512, 1024 ou 2048 bits ( pour simplifier le code, on pourrait en faire qu'une mais je crain que le code devienne plus lent). Ne marche que sur une machine 64bits.

Source

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
class Nb512;
class Nb1024;
unsigned long long NbHasard;
void InitHasard(){ NbHasard=time(NULL); }
class Nb2048{
public:
union {
unsigned D[64];
unsigned long long Q[32];
struct {
unsigned long long Lo;
unsigned long long Hi;
} O[16];
} Nb __attribute__ ((aligned(16)));
bool carry;
bool ChercheQuotient;
void DecaleAdd (const Nb1024 &terme, unsigned char decal); //Permet d'ajouter à un nombre de 1024 bits un nombre de 512 bits, en le décalant d'un nombre entier de qword
Nb1024 operator% (const Nb1024 &Mod)const;
Nb2048 operator+ (const Nb2048 &Terme)const;
Nb2048 operator- (const Nb2048 &Terme)const;
Nb2048& operator= (unsigned long long Nb);
Nb2048& operator= (const Nb1024 &Nb);
bool operator== (const Nb2048 &Nb)const;
Nb2048() : ChercheQuotient(false){};
};
class Nb1024{
public:
union {
unsigned char B[128];
unsigned D[32];
unsigned long long Q[16];
struct {
unsigned long long Lo;
unsigned long long Hi;
} O[8];
} Nb __attribute__ ((aligned(16)));
bool carry;
Nb2048* Quotient;
bool ChercheQuotient;
void DecaleAdd (const Nb512 &terme, unsigned char decal); //Permet d'ajouter à un nombre de 1024 bits un nombre de 512 bits, en le décalant d'un nombre entier de qword
Nb1024& operator= (unsigned long long Nb);
Nb1024& operator= (const Nb512 &Nb);
Nb1024& operator= (const Nb1024 &Nb);
Nb1024& operator= (const Nb2048 &Nb);
Nb512 operator% (const Nb512 &Mod)const;
Nb1024 operator+ (const Nb1024 &Terme)const;
Nb1024 operator- (const Nb1024 &Terme)const;
Nb2048 operator* (unsigned long long fact)const;
Nb2048 operator* (const Nb1024 &fact)const;
bool operator== (const Nb1024 &Nb)const;
Nb1024 Nb1024::Puissance (const Nb1024 &Exp, const Nb1024 &Mod)const;
Nb1024() : ChercheQuotient(false),Quotient(NULL){}
Nb1024(const Nb1024& c){
for(int i=0; i<16; i++) Nb.Q[i]=c.Nb.Q[i];
carry=c.carry;
ChercheQuotient=c.ChercheQuotient;
if(c.Quotient!=NULL){
Quotient=new Nb2048;
*Quotient=*c.Quotient;
} else Quotient=NULL;
}
~Nb1024(){if(Quotient!=NULL) delete Quotient;}
Nb1024 Inverse(const Nb1024 &Mod)const;
};
class Nb512{
public:
union {
unsigned char B[64];
unsigned D[16];
unsigned long long Q[8];
struct {
unsigned long long Lo;
unsigned long long Hi;
} O[4];
} Nb __attribute__ ((aligned(16)));
bool carry;
Nb1024* Quotient;
Nb512 operator+ (const Nb512 &Terme)const;
Nb512 operator- (const Nb512 &Terme)const;
Nb512& operator= (unsigned long long Nb);
Nb512& operator= (const Nb512 &Nb);
Nb512& operator= (const Nb1024 &Nb);
Nb1024 operator* (const Nb512 &Fact)const; //Il est plus rapide de mettre les plus petits nombres en premier opérande avec cet opérateur( si possible)
Nb1024 operator* (unsigned long long fact)const;
bool operator== (const Nb512 &Nb)const;
Nb512 Puissance (const Nb512 &Exp, const Nb512 &Mod)const;
void Hasard (); //Crée un nombre aléatoire non-sécurisé ( pour les tests et le test de Miller-Rabin)
bool MillerRabin(unsigned int Boucles)const;
void Premier();
Nb512():Quotient(NULL){}
Nb512(const Nb512& c){
for(int i=0; i<8; i++) Nb.Q[i]=c.Nb.Q[i];
carry=c.carry;
if(c.Quotient!=NULL){
Quotient=new Nb1024;
*Quotient=*c.Quotient;
}else Quotient=NULL;
}
~Nb512(){if(Quotient!=NULL) delete Quotient;}
};
inline void Nb1024::DecaleAdd(const Nb512 &terme, unsigned char decal){
asm ("add %8, %0\n\t"
"adc %9, %1\n\t"
"adc %10,%2\n\t"
"adc %11,%3\n\t"
"adc %12,%4\n\t"
"adc %13,%5\n\t"
"adc %14,%6\n\t"
"adc %15,%7\n\t"
/*FIXME : mettre la derniere retenue dans la variable carry*/
"jnc 1f\n\t"
"lea %7,%%R8\n\t"
"0:\n\t" //gestion de la retenue : si elle persiste, on la fait remonter tout le nombre (pas de gestion de dépassement de la fin du nombre -> peut provoquer des bugs)
"jnc 1f\n\t"
"add $8,%%R8\n\t"
"add $1,(%%R8)\n\t"
"jmp 0b\n\t"
"1:\n\t"
:
"=m" (Nb.Q[decal+0]), "=m" (Nb.Q[decal+1]), "=m" (Nb.Q[decal+2]), "=m" (Nb.Q[decal+3]),
"=m" (Nb.Q[decal+4]), "=m" (Nb.Q[decal+5]), "=m" (Nb.Q[decal+6]), "=m" (Nb.Q[decal+7])
:
"r" (terme.Nb.Q[0]), "r" (terme.Nb.Q[1]), "r" (terme.Nb.Q[2]), "r" (terme.Nb.Q[3]),
"r" (terme.Nb.Q[4]), "r" (terme.Nb.Q[5]), "r" (terme.Nb.Q[6]), "r" (terme.Nb.Q[7])
);
}
inline void Nb2048::DecaleAdd(const Nb1024 &terme, unsigned char decal){
bool c;
asm ("add %9, %0\n\t"
"adc %10,%1\n\t"
"adc %11,%2\n\t"
"adc %12,%3\n\t"
"adc %13,%4\n\t"
"adc %14,%5\n\t"
"adc %15,%6\n\t"
"adc %16,%7\n\t"
"setc %8\n\t"
:
"=m" (Nb.Q[decal+0]), "=m" (Nb.Q[decal+1]), "=m" (Nb.Q[decal+2]), "=m" (Nb.Q[decal+3]),
"=m" (Nb.Q[decal+4]), "=m" (Nb.Q[decal+5]), "=m" (Nb.Q[decal+6]), "=m" (Nb.Q[decal+7]),
"=g" (c)
:
"r" (terme.Nb.Q[0]), "r" (terme.Nb.Q[1]), "r" (terme.Nb.Q[2]), "r" (terme.Nb.Q[3]),
"r" (terme.Nb.Q[4]), "r" (terme.Nb.Q[5]), "r" (terme.Nb.Q[6]), "r" (terme.Nb.Q[7])
);
asm ("test $1,%8\n\t"
"clc\n\t"
"jz 1f\n\t"
"stc\n\t"
"1:\n\t"
"adc %9, %0\n\t"
"adc %10,%1\n\t"
"adc %11,%2\n\t"
"adc %12,%3\n\t"
"adc %13,%4\n\t"
"adc %14,%5\n\t"
"adc %15,%6\n\t"
"adc %16,%7\n\t"
/*FIXME : mettre la derniere retenue dans la variable carry*/
"jnc 1f\n\t"
"lea %7,%%R8\n\t"
"0:\n\t" //gestion de la retenue : si elle persiste, on la fait remonter tout le nombre (pas de gestion de dépassement de la fin du nombre -> peut provoquer des bugs)
"jnc 1f\n\t"
"add $8,%%R8\n\t"
"add $1,(%%R8)\n\t"
"jmp 0b\n\t"
"1:\n\t"
:
"=m" (Nb.Q[decal+8]), "=m" (Nb.Q[decal+9]), "=m" (Nb.Q[decal+10]),"=m" (Nb.Q[decal+11]),
"=m" (Nb.Q[decal+12]),"=m" (Nb.Q[decal+13]),"=m" (Nb.Q[decal+14]),"=m" (Nb.Q[decal+15])
:
"g" (c),
"r" (terme.Nb.Q[8]), "r" (terme.Nb.Q[9]), "r" (terme.Nb.Q[10]),"r" (terme.Nb.Q[11]),
"r" (terme.Nb.Q[12]),"r" (terme.Nb.Q[13]),"r" (terme.Nb.Q[14]),"r" (terme.Nb.Q[15])
);
}
inline Nb512& Nb512::operator= (unsigned long long Nb){
memset(&this->Nb,0,sizeof(this->Nb));
this->Nb.Q[0]=Nb;
return *this;
}
inline Nb1024& Nb1024::operator= (unsigned long long Nb){
memset(&this->Nb,0,sizeof(this->Nb));
this->Nb.Q[0]=Nb;
return *this;
}
inline Nb2048& Nb2048::operator= (unsigned long long Nb){
memset(&this->Nb,0,sizeof(this->Nb));
this->Nb.Q[0]=Nb;
return *this;
}
inline Nb512& Nb512::operator= (const Nb1024 &Nb){
memcpy(&this->Nb,&Nb.Nb,sizeof(this->Nb));
return *this;
}
inline Nb1024& Nb1024::operator= (const Nb2048 &Nb){
memcpy(&this->Nb,&Nb.Nb,sizeof(this->Nb));
return *this;
}
inline Nb2048& Nb2048::operator= (const Nb1024 &Nb){
memcpy(&this->Nb, &Nb.Nb, sizeof(Nb.Nb));
memset((char*)&this->Nb + sizeof(Nb.Nb), 0, sizeof(this->Nb)-sizeof(Nb.Nb));
return *this;
}
inline Nb1024& Nb1024::operator= (const Nb512 &Nb){
memcpy(&this->Nb, &Nb.Nb, sizeof(Nb.Nb));
memset((char*)&this->Nb + sizeof(Nb.Nb), 0, sizeof(this->Nb)-sizeof(Nb.Nb));
return *this;
}
inline Nb1024& Nb1024::operator= (const Nb1024 &Nb){
memcpy(this, &Nb,sizeof(Nb));
if(Nb.Quotient!=NULL){
Quotient=new Nb2048;
*Quotient=*Nb.Quotient;
} else Quotient=NULL;
return *this;
}
inline Nb512& Nb512::operator= (const Nb512 &Nb){
memcpy(this, &Nb,sizeof(Nb));
if(Nb.Quotient!=NULL){
Quotient=new Nb1024;
*Quotient=*Nb.Quotient;
} else Quotient=NULL;
return *this;
}
inline Nb512 Nb512::operator+ (const Nb512 &Terme)const{
Nb512 Res;
asm ("add %17, %9\n\t"
"adc %18, %10\n\t"
"adc %19, %11\n\t"
"adc %20, %12\n\t"
"adc %21, %13\n\t"
"adc %22, %14\n\t"
"adc %23, %15\n\t"
"adc %24, %16\n\t"
"mov %9, %0\n\t"
"mov %10,%1\n\t"
"mov %11,%2\n\t"
"mov %12,%3\n\t"
"mov %13,%4\n\t"
"mov %14,%5\n\t"
"mov %15,%6\n\t"
"mov %16,%7\n\t"
"setc %8\n\t"
:
"=m" (Res.Nb.Q[0]), "=m" (Res.Nb.Q[1]), "=m" (Res.Nb.Q[2]), "=m" (Res.Nb.Q[3]),
"=m" (Res.Nb.Q[4]), "=m" (Res.Nb.Q[5]), "=m" (Res.Nb.Q[6]), "=m" (Res.Nb.Q[7]),
"=g" (Res.carry)
:
"r" (Terme.Nb.Q[0]), "r" (Terme.Nb.Q[1]), "r" (Terme.Nb.Q[2]), "r" (Terme.Nb.Q[3]),
"r" (Terme.Nb.Q[4]), "r" (Terme.Nb.Q[5]), "r" (Terme.Nb.Q[6]), "r" (Terme.Nb.Q[7]),
"g" (Nb.Q[0]), "g" (Nb.Q[1]), "g" (Nb.Q[2]), "g" (Nb.Q[3]),
"g" (Nb.Q[4]), "g" (Nb.Q[5]), "g" (Nb.Q[6]), "g" (Nb.Q[7])
);
return Res;
}
inline Nb1024 Nb1024::operator+ (const Nb1024 &Terme)const{
Nb1024 Res;
asm ("add %17, %9\n\t"
"adc %18, %10\n\t"
"adc %19, %11\n\t"
"adc %20, %12\n\t"
"adc %21, %13\n\t"
"adc %22, %14\n\t"
"adc %23, %15\n\t"
"adc %24, %16\n\t"
"mov %9, %0\n\t"
"mov %10,%1\n\t"
"mov %11,%2\n\t"
"mov %12,%3\n\t"
"mov %13,%4\n\t"
"mov %14,%5\n\t"
"mov %15,%6\n\t"
"mov %16,%7\n\t"
"setc %8\n\t"
:
"=m" (Res.Nb.Q[0]), "=m" (Res.Nb.Q[1]), "=m" (Res.Nb.Q[2]), "=m" (Res.Nb.Q[3]),
"=m" (Res.Nb.Q[4]), "=m" (Res.Nb.Q[5]), "=m" (Res.Nb.Q[6]), "=m" (Res.Nb.Q[7]),
"=g" (Res.carry)
:
"r" (Terme.Nb.Q[0]), "r" (Terme.Nb.Q[1]), "r" (Terme.Nb.Q[2]), "r" (Terme.Nb.Q[3]),
"r" (Terme.Nb.Q[4]), "r" (Terme.Nb.Q[5]), "r" (Terme.Nb.Q[6]), "r" (Terme.Nb.Q[7]),
"g" (Nb.Q[0]), "g" (Nb.Q[1]), "g" (Nb.Q[2]), "g" (Nb.Q[3]),
"g" (Nb.Q[4]), "g" (Nb.Q[5]), "g" (Nb.Q[6]), "g" (Nb.Q[7])
);
asm ("testl $1,%8\n\t"
"clc\n\t"
"jz 1f\n\t"
"stc\n\t"
"1:\n\t"
"adc %17, %9\n\t"
"adc %18, %10\n\t"
"adc %19, %11\n\t"
"adc %20, %12\n\t"
"adc %21, %13\n\t"
"adc %22, %14\n\t"
"adc %23, %15\n\t"
"adc %24, %16\n\t"
"mov %9, %0\n\t"
"mov %10,%1\n\t"
"mov %11,%2\n\t"
"mov %12,%3\n\t"
"mov %13,%4\n\t"
"mov %14,%5\n\t"
"mov %15,%6\n\t"
"mov %16,%7\n\t"
"setc %8\n\t"
:
"=m" (Res.Nb.Q[8]), "=m" (Res.Nb.Q[9]), "=m" (Res.Nb.Q[10]),"=m" (Res.Nb.Q[11]),
"=m" (Res.Nb.Q[12]),"=m" (Res.Nb.Q[13]),"=m" (Res.Nb.Q[14]),"=m" (Res.Nb.Q[15]),
"+g" (Res.carry)
:
"r" (Terme.Nb.Q[8]), "r" (Terme.Nb.Q[9]), "r" (Terme.Nb.Q[10]),"r" (Terme.Nb.Q[11]),
"r" (Terme.Nb.Q[12]),"r" (Terme.Nb.Q[13]),"r" (Terme.Nb.Q[14]),"r" (Terme.Nb.Q[15]),
"g" (Nb.Q[8]), "g" (Nb.Q[9]), "g" (Nb.Q[10]), "g" (Nb.Q[11]),
"g" (Nb.Q[12]),"g" (Nb.Q[13]),"g" (Nb.Q[14]), "g" (Nb.Q[15])
);
return Res;
}
inline Nb512 Nb512::operator- (const Nb512 &Terme)const{
Nb512 Res;
asm ("sub %17, %9\n\t"
"sbb %18, %10\n\t"
"sbb %19, %11\n\t"
"sbb %20, %12\n\t"
"sbb %21, %13\n\t"
"sbb %22, %14\n\t"
"sbb %23, %15\n\t"
"sbb %24, %16\n\t"
"mov %9, %0\n\t"
"mov %10,%1\n\t"
"mov %11,%2\n\t"
"mov %12,%3\n\t"
"mov %13,%4\n\t"
"mov %14,%5\n\t"
"mov %15,%6\n\t"
"mov %16,%7\n\t"
"setc %8\n\t"
:
"=m" (Res.Nb.Q[0]), "=m" (Res.Nb.Q[1]), "=m" (Res.Nb.Q[2]), "=m" (Res.Nb.Q[3]),
"=m" (Res.Nb.Q[4]), "=m" (Res.Nb.Q[5]), "=m" (Res.Nb.Q[6]), "=m" (Res.Nb.Q[7]),
"=g" (Res.carry)
:
"r" (Nb.Q[0]), "r" (Nb.Q[1]), "r" (Nb.Q[2]), "r" (Nb.Q[3]),
"r" (Nb.Q[4]), "r" (Nb.Q[5]), "r" (Nb.Q[6]), "r" (Nb.Q[7]),
"g" (Terme.Nb.Q[0]), "g" (Terme.Nb.Q[1]), "g" (Terme.Nb.Q[2]), "g" (Terme.Nb.Q[3]),
"g" (Terme.Nb.Q[4]), "g" (Terme.Nb.Q[5]), "g" (Terme.Nb.Q[6]), "g" (Terme.Nb.Q[7])
);
return Res;
}
inline Nb1024 Nb1024::operator- (const Nb1024 &Terme)const{
Nb1024 Res;
asm ("sub %17, %9\n\t"
"sbb %18, %10\n\t"
"sbb %19, %11\n\t"
"sbb %20, %12\n\t"
"sbb %21, %13\n\t"
"sbb %22, %14\n\t"
"sbb %23, %15\n\t"
"sbb %24, %16\n\t"
"mov %9, %0\n\t"
"mov %10,%1\n\t"
"mov %11,%2\n\t"
"mov %12,%3\n\t"
"mov %13,%4\n\t"
"mov %14,%5\n\t"
"mov %15,%6\n\t"
"mov %16,%7\n\t"
"setc %8\n\t"
:
"=m" (Res.Nb.Q[0]), "=m" (Res.Nb.Q[1]), "=m" (Res.Nb.Q[2]), "=m" (Res.Nb.Q[3]),
"=m" (Res.Nb.Q[4]), "=m" (Res.Nb.Q[5]), "=m" (Res.Nb.Q[6]), "=m" (Res.Nb.Q[7]),
"=g" (Res.carry)
:
"r" (Nb.Q[0]), "r" (Nb.Q[1]), "r" (Nb.Q[2]), "r" (Nb.Q[3]),
"r" (Nb.Q[4]), "r" (Nb.Q[5]), "r" (Nb.Q[6]), "r" (Nb.Q[7]),
"g" (Terme.Nb.Q[0]), "g" (Terme.Nb.Q[1]), "g" (Terme.Nb.Q[2]), "g" (Terme.Nb.Q[3]),
"g" (Terme.Nb.Q[4]), "g" (Terme.Nb.Q[5]), "g" (Terme.Nb.Q[6]), "g" (Terme.Nb.Q[7])
);
asm ("testl $1,%8\n\t"
"clc\n\t"
"jz 1f\n\t"
"stc\n\t"
"1:\n\t"
"sbb %17, %9\n\t"
"sbb %18, %10\n\t"
"sbb %19, %11\n\t"
"sbb %20, %12\n\t"
"sbb %21, %13\n\t"
"sbb %22, %14\n\t"
"sbb %23, %15\n\t"
"sbb %24, %16\n\t"
"mov %9, %0\n\t"
"mov %10,%1\n\t"
"mov %11,%2\n\t"
"mov %12,%3\n\t"
"mov %13,%4\n\t"
"mov %14,%5\n\t"
"mov %15,%6\n\t"
"mov %16,%7\n\t"
"setc %8\n\t"
:
"=m" (Res.Nb.Q[8]), "=m" (Res.Nb.Q[9]), "=m" (Res.Nb.Q[10]),"=m" (Res.Nb.Q[11]),
"=m" (Res.Nb.Q[12]),"=m" (Res.Nb.Q[13]),"=m" (Res.Nb.Q[14]),"=m" (Res.Nb.Q[15]),
"+g" (Res.carry)
:
"r" (Nb.Q[8]), "r" (Nb.Q[9]), "r" (Nb.Q[10]), "r" (Nb.Q[11]),
"r" (Nb.Q[12]),"r" (Nb.Q[13]),"r" (Nb.Q[14]), "r" (Nb.Q[15]),
"g" (Terme.Nb.Q[8]), "g" (Terme.Nb.Q[9]), "g" (Terme.Nb.Q[10]),"g" (Terme.Nb.Q[11]),
"g" (Terme.Nb.Q[12]),"g" (Terme.Nb.Q[13]),"g" (Terme.Nb.Q[14]),"g" (Terme.Nb.Q[15])
);
return Res;
}
inline Nb2048 Nb2048::operator- (const Nb2048 &Terme)const{
Nb2048 Res;
Res.carry=false;
for(int i=0; i<32; i+=8)
asm ("test $1,%8\n\t"
"clc\n\t"
"jz 1f\n\t"
"stc\n\t"
"1:\n\t"
"sbb %17, %9\n\t"
"sbb %18, %10\n\t"
"sbb %19, %11\n\t"
"sbb %20, %12\n\t"
"sbb %21, %13\n\t"
"sbb %22, %14\n\t"
"sbb %23, %15\n\t"
"sbb %24, %16\n\t"
"mov %9, %0\n\t"
"mov %10,%1\n\t"
"mov %11,%2\n\t"
"mov %12,%3\n\t"
"mov %13,%4\n\t"
"mov %14,%5\n\t"
"mov %15,%6\n\t"
"mov %16,%7\n\t"
"setc %8\n\t"
:
"=m" (Res.Nb.Q[i+0]), "=m" (Res.Nb.Q[i+1]), "=m" (Res.Nb.Q[i+2]), "=m" (Res.Nb.Q[i+3]),
"=m" (Res.Nb.Q[i+4]), "=m" (Res.Nb.Q[i+5]), "=m" (Res.Nb.Q[i+6]), "=m" (Res.Nb.Q[i+7]),
"+g" (Res.carry)
:
"r" (Nb.Q[i+0]), "r" (Nb.Q[i+1]), "r" (Nb.Q[i+2]), "r" (Nb.Q[i+3]),
"r" (Nb.Q[i+4]), "r" (Nb.Q[i+5]), "r" (Nb.Q[i+6]), "r" (Nb.Q[i+7]),
"g" (Terme.Nb.Q[i+0]), "g" (Terme.Nb.Q[i+1]), "g" (Terme.Nb.Q[i+2]), "g" (Terme.Nb.Q[i+3]),
"g" (Terme.Nb.Q[i+4]), "g" (Terme.Nb.Q[i+5]), "g" (Terme.Nb.Q[i+6]), "g" (Terme.Nb.Q[i+7])
);
return Res;
}
Nb1024 Nb512::operator* (const Nb512 &fact)const{
Nb512 TamponPair[8];
Nb512 TamponImpair[8];
bool Zero[8];
for(int i=0; i<8; i++){
if(Nb.Q[i]==0){
Zero[i]=true;
continue;
}
Zero[i]=false;
register unsigned long long ChiffreThis asm("%rcx")=Nb.Q[i];
for(int j=0; j<8; j+=2){
asm("mul %3"
:"=a" (TamponPair[i].Nb.Q[j & 0xE]), "=d" (TamponPair[i].Nb.Q[(j & 0xE)+1])
:"a" (fact.Nb.Q[j]), "r" (ChiffreThis)
);
asm("mul %3"
:"=a" (TamponImpair[i].Nb.Q[j & 0xE]), "=d" (TamponImpair[i].Nb.Q[(j & 0xE)+1])
:"a" (fact.Nb.Q[j+1]), "r" (ChiffreThis)
);
}
}
Nb1024 Retour;
Retour=0;
for(int i=0; i<8; i++) {
if(Zero[i]==false){
Retour.DecaleAdd(TamponPair[i],i);
Retour.DecaleAdd(TamponImpair[i],i+1);
}
}
return Retour;
}
Nb2048 Nb1024::operator* (const Nb1024 &fact)const{
Nb1024 TamponPair[16];
Nb1024 TamponImpair[16];
bool Zero[16];
for(int i=0; i<16; i++){
if(Nb.Q[i]==0){
Zero[i]=true;
continue;
}
Zero[i]=false;
register unsigned long long ChiffreThis asm("%rcx")=Nb.Q[i];
for(int j=0; j<16; j+=2){
asm("mul %3"
:"=a" (TamponPair[i].Nb.Q[j & 0xE]), "=d" (TamponPair[i].Nb.Q[(j & 0xE)+1])
:"a" (fact.Nb.Q[j]), "r" (ChiffreThis)
);
asm("mul %3"
:"=a" (TamponImpair[i].Nb.Q[j & 0xE]), "=d" (TamponImpair[i].Nb.Q[(j & 0xE)+1])
:"a" (fact.Nb.Q[j+1]), "r" (ChiffreThis)
);
}
}
Nb2048 Retour;
Retour=0;
for(int i=0; i<16; i++) {
if(Zero[i]==false){
Retour.DecaleAdd(TamponPair[i],i);
Retour.DecaleAdd(TamponImpair[i],i+1);
}
}
return Retour;
}
inline Nb1024 Nb512::operator* (unsigned long long fact)const{
Nb512 Tampon;
Nb1024 Res;
if(fact==0) return Res=0;
Res=0;
for(int i=0; i<8; i+=2){
asm("mul %3"
:"=a" (Res.Nb.Q[i & 0xE]), "=d" (Res.Nb.Q[(i & 0xE)+1])
:"a" (Nb.Q[i]), "r" (fact)
);
asm("mul %3"
:"=a" (Tampon.Nb.Q[i & 0xE]), "=d" (Tampon.Nb.Q[(i & 0xE)+1])
:"a" (Nb.Q[i+1]), "r" (fact)
);
}
Res.DecaleAdd(Tampon,1);
return Res;
}
inline Nb2048 Nb1024::operator* (unsigned long long fact)const{
Nb1024 Tampon;
Nb2048 Res;
if(fact==0) return Res=0;
Res=0;
for(int i=0; i<16; i+=2){
asm("mul %3"
:"=a" (Res.Nb.Q[i & 0xE]), "=d" (Res.Nb.Q[(i & 0xE)+1])
:"a" (Nb.Q[i]), "r" (fact)
);
asm("mul %3"
:"=a" (Tampon.Nb.Q[i & 0xE]), "=d" (Tampon.Nb.Q[(i & 0xE)+1])
:"a" (Nb.Q[i+1]), "r" (fact)
);
}
Res.DecaleAdd(Tampon,1);
return Res;
}
//Un chiffre = un DWORD
Nb512 Nb1024::operator% (const Nb512 &Mod)const{
Nb512 Res;
if(ChercheQuotient) {
if(Res.Quotient!=NULL) delete Res.Quotient;
Res.Quotient=new Nb1024;
*Res.Quotient=0;
}
//ChiffreBase : contient l'index du chiffre dans Dividende que l'on va utiliser pour faire la premiere approche de Quotient
signed char IndexThis, ChiffreBase;
for(IndexThis=31; this->Nb.D[IndexThis]==0; IndexThis--) if (IndexThis==0) return Res=0;
for(ChiffreBase=15; Mod.Nb.D[ChiffreBase]==0; ChiffreBase--) if(ChiffreBase==0) exit(-1); //division par 0
if(IndexThis<ChiffreBase) return Res=*this;
Nb1024 Dividende; //Dividende partiel traité à une itération de la boucle
Dividende=0;
for(int i=ChiffreBase-1; i>=0; i--, IndexThis--) Dividende.Nb.D[i]=this->Nb.D[IndexThis];
for(; IndexThis>=0; IndexThis--){
// TODO : A faire en Asm (SSE ou non, selon le mieux)
for(int i=15; i>=0; i--) Dividende.Nb.D[i+1]=Dividende.Nb.D[i];
Dividende.Nb.D[0]=this->Nb.D[IndexThis];
unsigned long long Quotient, RestePart;
asm ("divq %4" //Premiere estimation de Quotient
:"=a" (Quotient), "=d" (RestePart)
:"a" ( Dividende.Nb.D[ChiffreBase] + ((unsigned long long)Dividende.Nb.D[ChiffreBase+1]<<32)), "d" (0), "g" ( (unsigned long long)Mod.Nb.D[ChiffreBase])
);
bool QuotientOK=false;
if(Quotient > 0xFFFFFFFF) {
Quotient=0xFFFFFFFF;
//RestePart = Dividende.Nb.D[ChiffreBase+1]:Dividende.Nb.D[ChiffreBase] - 0xFFFFFFFF * Md.Nb.D[ChiffreBase]
RestePart= Dividende.Nb.D[ChiffreBase] + ((unsigned long long)Dividende.Nb.D[ChiffreBase+1]<<32) - ((unsigned long long)Mod.Nb.D[ChiffreBase]<<32) + Mod.Nb.D[ChiffreBase]<<32;
if(RestePart & 0xFFFFFFFF00000000) QuotientOK=true;
}
//Ensuite, le but est de rajouter des chiffres et de calculer l'erreur que l'on commet : on multiplie l'estimation du quotient déjà faite par les chiffres
//de Mod déja pris en compte puis on soustrait les chiffres de dividende déjà pris en compte. Si le résultat est négatif ou nul, pas de problème,
//Quotient n'est pas trop grand (il ne peut pas être trop petit). Dans ce cas, l'opposé du résultat correspond au reste de la division. S'il est positif,
//on le divise par les chiffres de Mod déjà pris en compte : on obtient un nombre qu'il faut soustraire à Quotient. Sans optimisation, cette méthode est
//impossible : on se retrouve a faire des divisions avec un dénominateur énorme et tout un tas de multiplications...
//Pour simplifier, on se rend compte que ce nombre est calculable a partir du reste de la division précédente (calculé lors de la derniere estimation de
//Quotient: on supprime donc beaucoup de multiplications inutiles. De plus, seules la premiere itération de cette boucle est utiles : les autres ne pourront
//Faire descendre Quotient que de 1 : on remplace donc toutes ces itérations par une comparaison entre Quotient*Mod et Diviseur, qui nous dira s'il faut
//décrémenter Quotient ou non.
//Petite vérification.. histoire de pas faire des opérations pour rien
if(Quotient == 0) continue;
if(ChiffreBase == 0) QuotientOK=true;
if(!QuotientOK){
unsigned long long Tmp=Quotient*Mod.Nb.D[ChiffreBase-1];
if(Tmp > ((unsigned long long)RestePart<<32) + Dividende.Nb.D[ChiffreBase-1])
//Le nombre dont on parle dans le § de commentaires plus haut est positif : on réajuste Quotient
//Diviseion en arrondissant par au dessus : d'où le 1 + et le -1
Quotient-=1 + (Tmp - ((unsigned long long)RestePart<<32) - Dividende.Nb.D[ChiffreBase-1] - 1) / ( ((unsigned long long)Mod.Nb.D[ChiffreBase]<<32) + Mod.Nb.D[ChiffreBase-1] );
}
Dividende=Dividende-Mod*Quotient;
if(Dividende.carry) {
Dividende.DecaleAdd(Mod,0);
Quotient--;
}
if(ChercheQuotient)
Res.Quotient->Nb.D[IndexThis]=Quotient;
}
return Res=Dividende;
}
Nb1024 Nb2048::operator% (const Nb1024 &Mod)const{
Nb1024 Res;
if(ChercheQuotient) {
if(Res.Quotient!=NULL) delete Res.Quotient;
Res.Quotient=new Nb2048;
*Res.Quotient=0;
}
//ChiffreBase : contient l'index du chiffre dans Dividende que l'on va utiliser pour faire la premiere approche de Quotient
signed char IndexThis, ChiffreBase;
for(IndexThis=63; this->Nb.D[IndexThis]==0; IndexThis--) if (IndexThis==0) return Res=0;
for(ChiffreBase=31; Mod.Nb.D[ChiffreBase]==0; ChiffreBase--) if(ChiffreBase==0) exit(-1); //division par 0
if(IndexThis<ChiffreBase) return Res=*this;
Nb2048 Dividende; //Dividende partiel traité à une itération de la boucle
Dividende=0;
for(int i=ChiffreBase-1; i>=0; i--, IndexThis--) Dividende.Nb.D[i]=this->Nb.D[IndexThis];
for(; IndexThis>=0; IndexThis--){
// TODO : A faire en Asm (SSE ou non, selon le mieux)
for(int i=31; i>=0; i--) Dividende.Nb.D[i+1]=Dividende.Nb.D[i];
Dividende.Nb.D[0]=this->Nb.D[IndexThis];
unsigned long long Quotient, RestePart;
asm ("divq %4" //Premiere estimation de Quotient
:"=a" (Quotient), "=d" (RestePart)
:"a" ( Dividende.Nb.D[ChiffreBase] + ((unsigned long long)Dividende.Nb.D[ChiffreBase+1]<<32)), "d" (0), "g" ( (unsigned long long)Mod.Nb.D[ChiffreBase])
);
bool QuotientOK=false;
if(Quotient > 0xFFFFFFFF) {
Quotient=0xFFFFFFFF;
//RestePart = Dividende.Nb.D[ChiffreBase+1]:Dividende.Nb.D[ChiffreBase] - 0xFFFFFFFF * Md.Nb.D[ChiffreBase]
RestePart= Dividende.Nb.D[ChiffreBase] + ((unsigned long long)Dividende.Nb.D[ChiffreBase+1]<<32) - ((unsigned long long)Mod.Nb.D[ChiffreBase]<<32) + Mod.Nb.D[ChiffreBase]<<32;
if(RestePart & 0xFFFFFFFF00000000) QuotientOK=true;
}
//Ensuite, le but est de rajouter des chiffres et de calculer l'erreur que l'on commet : on multiplie l'estimation du quotient déjà faite par les chiffres
//de Mod déja pris en compte puis on soustrait les chiffres de dividende déjà pris en compte. Si le résultat est négatif ou nul, pas de problème,
//Quotient n'est pas trop grand (il ne peut pas être trop petit). Dans ce cas, l'opposé du résultat correspond au reste de la division. S'il est positif,
//on le divise par les chiffres de Mod déjà pris en compte : on obtient un nombre qu'il faut soustraire à Quotient. Sans optimisation, cette méthode est
//impossible : on se retrouve a faire des divisions avec un dénominateur énorme et tout un tas de multiplications...
//Pour simplifier, on se rend compte que ce nombre est calculable a partir du reste de la division précédente (calculé lors de la derniere estimation de
//Quotient: on supprime donc beaucoup de multiplications inutiles. De plus, seules la premiere itération de cette boucle est utiles : les autres ne pourront
//Faire descendre Quotient que de 1 : on remplace donc toutes ces itérations par une comparaison entre Quotient*Mod et Diviseur, qui nous dira s'il faut
//décrémenter Quotient ou non.
//Petite vérification.. histoire de pas faire des opérations pour rien
if(Quotient == 0) continue;
if(ChiffreBase == 0) QuotientOK=true;
if(!QuotientOK){
unsigned long long Tmp=Quotient*Mod.Nb.D[ChiffreBase-1];
if(Tmp > ((unsigned long long)RestePart<<32) + Dividende.Nb.D[ChiffreBase-1])
//Le nombre dont on parle dans le § de commentaires plus haut est positif : on réajuste Quotient
//Diviseion en arrondissant par au dessus : d'où le 1 + et le -1
Quotient-=1 + (Tmp - ((unsigned long long)RestePart<<32) - Dividende.Nb.D[ChiffreBase-1] - 1) / ( ((unsigned long long)Mod.Nb.D[ChiffreBase]<<32) + Mod.Nb.D[ChiffreBase-1] );
}
//On fait la grande multiplcation et soustraction
Dividende=Dividende-Mod*Quotient;
if(Dividende.carry) {
Dividende.DecaleAdd(Mod,0);
Quotient--;
}
if(ChercheQuotient)
Res.Quotient->Nb.D[IndexThis]=Quotient;
}
return Res=Dividende;
}
inline bool Nb512::operator== (const Nb512 &Nb)const{
return !memcmp(&this->Nb,&Nb.Nb,sizeof(Nb.Nb));
}
inline bool Nb1024::operator== (const Nb1024 &Nb)const{
return !memcmp(&this->Nb,&Nb.Nb,sizeof(Nb.Nb));
}
inline bool Nb2048::operator== (const Nb2048 &Nb)const{
return !memcmp(&this->Nb,&Nb.Nb,sizeof(Nb.Nb));
}
Nb512 Nb512::Puissance (const Nb512 &Exp, const Nb512 &Mod)const{
Nb512 Res;
Res=1;
//TODO ne pas faire les premiers octets vides
for(int i=63; i>=0; i--)
for(int j=128; j>0; j>>=1){
Res=Res*Res % Mod;
if(Exp.Nb.B[i] & j){
Res=Res* *this % Mod;
}
}
return Res;
}
Nb1024 Nb1024::Puissance (const Nb1024 &Exp, const Nb1024 &Mod)const{
Nb1024 Res;
Res=1;
//TODO ne pas faire les premiers octets vides
for(int i=127; i>=0; i--)
for(int j=128; j>0; j>>=1){
Res=Res*Res % Mod;
if(Exp.Nb.B[i] & j){
Res=Res* *this % Mod;
}
}
return Res;
}
void Nb512::Hasard (){
for(int i=0; i<8; i++){
NbHasard*=6364136223846793005; //Générateur de Haynes
NbHasard++;
this->Nb.Q[i]=NbHasard;
}
while ((Nb.Q[7] & ((unsigned long long)1<<63)) == 0){ //Pour avoir un VRAI nombre de 512 bits
NbHasard*=6364136223846793005; //Générateur de Haynes
NbHasard++;
this->Nb.Q[7]=NbHasard;
}
}
//http://cryptosec.lautre.net/article.php3?id_article=12
bool Nb512::MillerRabin(unsigned int Boucles)const{
unsigned int b;
Nb512 thism1,un;
un=1; thism1=*this -un;
//calcul de b
for(b=0;b<512; b+=64)
if(thism1.Nb.Q[b>>6]!=0) break;
if(b==512) return false; // *this==1
for(; b<512; b++)
if( (thism1.Nb.Q[b>>6] & ( 1 << (b&63)) )!=0) break;
//calcul de r
Nb512 r; int i;
for(i=0; i<7 - (b>>6); i++)
r.Nb.Q[i]=(thism1.Nb.Q[i + (b>>6) + 1]<<(64-(b&63))) | (thism1.Nb.Q[i + (b>>6)]>>(b&63));
r.Nb.Q[i]=thism1.Nb.Q[i + (b>>6)]>>(b&63);
for(i++; i<8; i++) r.Nb.Q[i]=0;
for(i=0; i<Boucles; i++){
Nb512 a;
a.Hasard();
//On s'assure que a<this* en mettant a 0 1 octet de plus dans a que dans this
for(int j=63; j>=0; j--){
a.Nb.B[i]=0;
if(this->Nb.B[i] != 0) break;
}
//y est représenté ici par a :
a=a.Puissance(r,*this);
if(a==un) continue;
for( int j=0; j<b; j++){
if(a==un) return false;
if(a==thism1) break;
a=a*a % *this;
}
if(!(a==thism1)) return false;
}
return true;
}
void Nb512::Premier(){
do{
Hasard(); /*FIXME : utiliser un meilleur générateur aléatoire*/
Nb.B[0]|=1;
} while (!MillerRabin(5));
}
//trouve le nombre a tel que this*a = PGCD(this;Mod) modulo Mod
//En fait, ici on l'appele avec this et Mod premiers entres eux.. donc PGCD=1 donc a*this = 1 modulo Mod donc a est bine l'inverse de this modulo Mod
//On utilise pour ceci l'algoritme d'euclide étendu
Nb1024 Nb1024::Inverse(const Nb1024 &Mod)const{
Nb1024 Tmp1024;
struct sListeQuotients{
struct sListeQuotients* q;
Nb1024 t;
} *ListeQuotients=new struct sListeQuotients,*TmpListeQuotients;
//On commence par appliquer l'algoritme d'euclide et on retient tous les quotients
Nb1024 Nb2,Zero;
Nb2048 Nb1;
ListeQuotients->q=NULL;
Zero=0;
Nb1=Mod;
Nb2=*this;
do{
Nb1.ChercheQuotient=true;
Tmp1024=Nb1 % Nb2;
ListeQuotients->t=*Tmp1024.Quotient;
Nb1=Nb2;
Nb2=Tmp1024;
TmpListeQuotients=new struct sListeQuotients;
TmpListeQuotients->q=ListeQuotients;
ListeQuotients=TmpListeQuotients;
}while(!(Nb2==Zero));
//On enlève deux éléments de la liste : le premier car il est vide et le deuxième car on se fiche du dernier quotient obtenu
TmpListeQuotients=ListeQuotients;
ListeQuotients=ListeQuotients->q;
delete TmpListeQuotients;
TmpListeQuotients=ListeQuotients;
ListeQuotients=ListeQuotients->q;
delete TmpListeQuotients;
//Et on le remonte pour finalement trouver les deux coefficients de Bezout, dont l'un est le nombre cherché
//On calcule la suite : U(n-2)=U(n)-q(n-2)*U(n-1) où q(n) est le n-ième quotient calculé plus haut
//Pour simplifier, on fait tous ces calculs modulo Mod. Si on se retrouve avec un U(n-2) négatif, on lui ajoute Mod
Nb1024 Unm1,Un;
Unm1=1;
Un=0;
while(ListeQuotients!=NULL){
Tmp1024=Un- ((ListeQuotients->t * Unm1) % Mod);
if(Tmp1024.carry) Tmp1024=Tmp1024+Mod;
Un=Unm1;
Unm1=Tmp1024;
TmpListeQuotients=ListeQuotients;
ListeQuotients=ListeQuotients->q;
delete TmpListeQuotients;
}
return Unm1;
}
int main(){
Nb512 p,q,un,clair512;
un=1;
Nb1024 n,e,d,phi,clair,chiffre,dechiffre;
Nb2048 Verif;
InitHasard();
p.Premier();
q.Premier();
n=p*q;
printf("\n\nModulo commun aux deux clées :\n");
for(int i=31; i>=0; i--) printf("%.8X ",n.Nb.D[i]);
phi=(p-un)*(q-un);
e=0x10001;
printf("\n\nExposant public e:(Par défaut, 0x10001)");
//for(int i=31; i>=0; i--) printf("%.8X ",e.Nb.D[i]);
d=e.Inverse(phi);
printf("\n\nExposant privé d :\n");
for(int i=31; i>=0; i--) printf("%.8X ",d.Nb.D[i]);
printf("\n\nPour vérification, d*e mod phi(n)=(p-1)*(q-1): (doit être 1)\n");
Verif=d*e;
Verif=Verif % phi;
for(int i=31; i>=0; i--) printf("%.8X ",Verif.Nb.D[i]);
printf("\n\n\nTest: Bloc de départ (non chiffré) :\n");
clair512.Hasard();
clair=clair512;
clair512.Hasard();
clair.DecaleAdd(clair512,8);
clair.Nb.B[127]&=0xf;
for(int i=31; i>=0; i--) printf("%.8X ",clair.Nb.D[i]);
printf("\n\nTest: Bloc chiffré :\n");
chiffre=clair.Puissance(e,n);
for(int i=31; i>=0; i--) printf("%.8X ",chiffre.Nb.D[i]);
printf("\n\nTest: Bloc déchiffré :\n");
dechiffre=chiffre.Puissance(d,n);
for(int i=31; i>=0; i--) printf("%.8X ",dechiffre.Nb.D[i]);
printf("\n");
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

class Nb512;
class Nb1024;

unsigned long long NbHasard;
void InitHasard(){ NbHasard=time(NULL); }

class Nb2048{
  public:
  union {
    unsigned D[64];
    unsigned long long Q[32];
    struct {
      unsigned long long Lo;
      unsigned long long Hi;
    } O[16];
  } Nb __attribute__ ((aligned(16)));
  bool carry;
  bool ChercheQuotient;
  void DecaleAdd (const Nb1024 &terme, unsigned char decal); //Permet d'ajouter à un nombre de 1024 bits un nombre de 512 bits, en le décalant d'un nombre entier de qword
  Nb1024 operator% (const Nb1024 &Mod)const;
  Nb2048 operator+ (const Nb2048 &Terme)const;
  Nb2048 operator- (const Nb2048 &Terme)const;
  Nb2048& operator= (unsigned long long Nb);
  Nb2048& operator= (const Nb1024 &Nb);
  bool operator== (const Nb2048 &Nb)const;
  Nb2048() : ChercheQuotient(false){};
};

class Nb1024{
  public:
  union {
    unsigned char B[128];
    unsigned D[32];
    unsigned long long Q[16];
    struct {
      unsigned long long Lo;
      unsigned long long Hi;
    } O[8];
  } Nb __attribute__ ((aligned(16)));
  bool carry;
  Nb2048* Quotient;
  bool ChercheQuotient;
  void DecaleAdd (const Nb512 &terme, unsigned char decal); //Permet d'ajouter à un nombre de 1024 bits un nombre de 512 bits, en le décalant d'un nombre entier de qword
  Nb1024& operator= (unsigned long long Nb);
  Nb1024& operator= (const Nb512 &Nb);
  Nb1024& operator= (const Nb1024 &Nb);
  Nb1024& operator= (const Nb2048 &Nb);
  Nb512 operator% (const Nb512 &Mod)const;
  Nb1024 operator+ (const Nb1024 &Terme)const;
  Nb1024 operator- (const Nb1024 &Terme)const;
  Nb2048 operator* (unsigned long long fact)const;
  Nb2048 operator* (const Nb1024 &fact)const;
  bool operator== (const Nb1024 &Nb)const;
  Nb1024 Nb1024::Puissance (const Nb1024 &Exp, const Nb1024 &Mod)const;
  Nb1024() : ChercheQuotient(false),Quotient(NULL){}
  Nb1024(const Nb1024& c){ 
    for(int i=0; i<16; i++) Nb.Q[i]=c.Nb.Q[i];
    carry=c.carry;
    ChercheQuotient=c.ChercheQuotient;
    if(c.Quotient!=NULL){
      Quotient=new Nb2048;
      *Quotient=*c.Quotient;
    } else Quotient=NULL;
  }
  ~Nb1024(){if(Quotient!=NULL) delete Quotient;}
  Nb1024 Inverse(const Nb1024 &Mod)const;
};

class Nb512{
    public:
  union {
    unsigned char B[64];
    unsigned D[16];
    unsigned long long Q[8];
    struct {
      unsigned long long Lo;
      unsigned long long Hi;
    } O[4];
  } Nb __attribute__ ((aligned(16)));
  bool carry;
  Nb1024* Quotient;
  Nb512 operator+ (const Nb512 &Terme)const;
  Nb512 operator- (const Nb512 &Terme)const;
  Nb512& operator= (unsigned long long Nb);
  Nb512& operator= (const Nb512 &Nb);
  Nb512& operator= (const Nb1024 &Nb);
  Nb1024 operator* (const Nb512 &Fact)const; //Il est plus rapide de mettre les plus petits nombres en premier opérande avec cet opérateur( si possible)
  Nb1024 operator* (unsigned long long fact)const;
  bool operator== (const Nb512 &Nb)const;
  Nb512 Puissance (const Nb512 &Exp, const Nb512 &Mod)const;
  void Hasard (); //Crée un nombre aléatoire non-sécurisé ( pour les tests et le test de Miller-Rabin)
  bool MillerRabin(unsigned int Boucles)const;
  void Premier();
  Nb512():Quotient(NULL){}
  Nb512(const Nb512& c){ 
    for(int i=0; i<8; i++) Nb.Q[i]=c.Nb.Q[i];
    carry=c.carry;
    if(c.Quotient!=NULL){
      Quotient=new Nb1024;
      *Quotient=*c.Quotient;
    }else Quotient=NULL;
  }
  ~Nb512(){if(Quotient!=NULL) delete Quotient;}
}; 

inline void Nb1024::DecaleAdd(const Nb512 &terme, unsigned char decal){
  asm ("add %8, %0\n\t"
       "adc %9, %1\n\t"
       "adc %10,%2\n\t"
       "adc %11,%3\n\t"
       "adc %12,%4\n\t"
       "adc %13,%5\n\t"
       "adc %14,%6\n\t"
       "adc %15,%7\n\t"
       
       /*FIXME : mettre la derniere retenue dans la variable carry*/
       "jnc 1f\n\t"
       "lea %7,%%R8\n\t"
       "0:\n\t" //gestion de la retenue : si elle persiste, on la fait remonter tout le nombre (pas de gestion de dépassement de la fin du nombre -> peut provoquer des bugs)
       "jnc 1f\n\t"
       "add $8,%%R8\n\t"
       "add $1,(%%R8)\n\t"
       "jmp 0b\n\t"
       "1:\n\t"
     : 
       "=m" (Nb.Q[decal+0]), "=m" (Nb.Q[decal+1]), "=m" (Nb.Q[decal+2]), "=m" (Nb.Q[decal+3]),
       "=m" (Nb.Q[decal+4]), "=m" (Nb.Q[decal+5]), "=m" (Nb.Q[decal+6]), "=m" (Nb.Q[decal+7])
     : 
       "r" (terme.Nb.Q[0]), "r" (terme.Nb.Q[1]), "r" (terme.Nb.Q[2]), "r" (terme.Nb.Q[3]), 
       "r" (terme.Nb.Q[4]), "r" (terme.Nb.Q[5]), "r" (terme.Nb.Q[6]), "r" (terme.Nb.Q[7])
     );
}

inline void Nb2048::DecaleAdd(const Nb1024 &terme, unsigned char decal){
  bool c;
  asm ("add %9, %0\n\t"
       "adc %10,%1\n\t"
       "adc %11,%2\n\t"
       "adc %12,%3\n\t"
       "adc %13,%4\n\t"
       "adc %14,%5\n\t"
       "adc %15,%6\n\t"
       "adc %16,%7\n\t"
       
       "setc %8\n\t"
     : 
       "=m" (Nb.Q[decal+0]), "=m" (Nb.Q[decal+1]), "=m" (Nb.Q[decal+2]), "=m" (Nb.Q[decal+3]),
       "=m" (Nb.Q[decal+4]), "=m" (Nb.Q[decal+5]), "=m" (Nb.Q[decal+6]), "=m" (Nb.Q[decal+7]),
       
       "=g" (c)
     : 
       "r" (terme.Nb.Q[0]), "r" (terme.Nb.Q[1]), "r" (terme.Nb.Q[2]), "r" (terme.Nb.Q[3]), 
       "r" (terme.Nb.Q[4]), "r" (terme.Nb.Q[5]), "r" (terme.Nb.Q[6]), "r" (terme.Nb.Q[7])
     );
  asm ("test $1,%8\n\t"
       "clc\n\t"
       "jz 1f\n\t"
       "stc\n\t"
       "1:\n\t"
       
       "adc %9, %0\n\t"
       "adc %10,%1\n\t"
       "adc %11,%2\n\t"
       "adc %12,%3\n\t"
       "adc %13,%4\n\t"
       "adc %14,%5\n\t"
       "adc %15,%6\n\t"
       "adc %16,%7\n\t"
       
       /*FIXME : mettre la derniere retenue dans la variable carry*/
       "jnc 1f\n\t"
       "lea %7,%%R8\n\t"
       "0:\n\t" //gestion de la retenue : si elle persiste, on la fait remonter tout le nombre (pas de gestion de dépassement de la fin du nombre -> peut provoquer des bugs)
       "jnc 1f\n\t"
       "add $8,%%R8\n\t"
       "add $1,(%%R8)\n\t"
       "jmp 0b\n\t"
       "1:\n\t"
     : 
       "=m" (Nb.Q[decal+8]), "=m" (Nb.Q[decal+9]), "=m" (Nb.Q[decal+10]),"=m" (Nb.Q[decal+11]),
       "=m" (Nb.Q[decal+12]),"=m" (Nb.Q[decal+13]),"=m" (Nb.Q[decal+14]),"=m" (Nb.Q[decal+15])       
     : 
       "g" (c),
     
       "r" (terme.Nb.Q[8]), "r" (terme.Nb.Q[9]), "r" (terme.Nb.Q[10]),"r" (terme.Nb.Q[11]), 
       "r" (terme.Nb.Q[12]),"r" (terme.Nb.Q[13]),"r" (terme.Nb.Q[14]),"r" (terme.Nb.Q[15])
     );
}

inline Nb512& Nb512::operator= (unsigned long long Nb){
  memset(&this->Nb,0,sizeof(this->Nb));
  this->Nb.Q[0]=Nb;
  return *this;
}

inline Nb1024& Nb1024::operator= (unsigned long long Nb){
  memset(&this->Nb,0,sizeof(this->Nb));
  this->Nb.Q[0]=Nb;
  return *this;
}

inline Nb2048& Nb2048::operator= (unsigned long long Nb){
  memset(&this->Nb,0,sizeof(this->Nb));
  this->Nb.Q[0]=Nb;
  return *this;
}

inline Nb512& Nb512::operator= (const Nb1024 &Nb){
  memcpy(&this->Nb,&Nb.Nb,sizeof(this->Nb));
  return *this;
}

inline Nb1024& Nb1024::operator= (const Nb2048 &Nb){
  memcpy(&this->Nb,&Nb.Nb,sizeof(this->Nb));
  return *this;
}

inline Nb2048& Nb2048::operator= (const Nb1024 &Nb){
  memcpy(&this->Nb, &Nb.Nb, sizeof(Nb.Nb));
  memset((char*)&this->Nb + sizeof(Nb.Nb), 0, sizeof(this->Nb)-sizeof(Nb.Nb));
  return *this;
}

inline Nb1024& Nb1024::operator= (const Nb512 &Nb){
  memcpy(&this->Nb, &Nb.Nb, sizeof(Nb.Nb));
  memset((char*)&this->Nb + sizeof(Nb.Nb), 0, sizeof(this->Nb)-sizeof(Nb.Nb));
  return *this;
}

inline Nb1024& Nb1024::operator= (const Nb1024 &Nb){
  memcpy(this, &Nb,sizeof(Nb));
  if(Nb.Quotient!=NULL){
    Quotient=new Nb2048;
    *Quotient=*Nb.Quotient;
  } else Quotient=NULL;
  return *this;
}

inline Nb512& Nb512::operator= (const Nb512 &Nb){
  memcpy(this, &Nb,sizeof(Nb));
  if(Nb.Quotient!=NULL){
    Quotient=new Nb1024;
    *Quotient=*Nb.Quotient;
  } else Quotient=NULL;
  return *this;
}

inline Nb512 Nb512::operator+ (const Nb512 &Terme)const{
  Nb512 Res;
  asm ("add %17, %9\n\t"
       "adc %18, %10\n\t"
       "adc %19, %11\n\t"
       "adc %20, %12\n\t"
       "adc %21, %13\n\t"
       "adc %22, %14\n\t"
       "adc %23, %15\n\t"
       "adc %24, %16\n\t"
       
       "mov %9, %0\n\t"
       "mov %10,%1\n\t"
       "mov %11,%2\n\t"
       "mov %12,%3\n\t"
       "mov %13,%4\n\t"
       "mov %14,%5\n\t"
       "mov %15,%6\n\t"
       "mov %16,%7\n\t"
       
       "setc %8\n\t"
     : 
       "=m" (Res.Nb.Q[0]), "=m" (Res.Nb.Q[1]), "=m" (Res.Nb.Q[2]), "=m" (Res.Nb.Q[3]), 
       "=m" (Res.Nb.Q[4]), "=m" (Res.Nb.Q[5]), "=m" (Res.Nb.Q[6]), "=m" (Res.Nb.Q[7]),
       
       "=g" (Res.carry)
     :
       "r" (Terme.Nb.Q[0]), "r" (Terme.Nb.Q[1]), "r" (Terme.Nb.Q[2]), "r" (Terme.Nb.Q[3]),
       "r" (Terme.Nb.Q[4]), "r" (Terme.Nb.Q[5]), "r" (Terme.Nb.Q[6]), "r" (Terme.Nb.Q[7]),
       
       "g" (Nb.Q[0]), "g" (Nb.Q[1]), "g" (Nb.Q[2]), "g" (Nb.Q[3]),
       "g" (Nb.Q[4]), "g" (Nb.Q[5]), "g" (Nb.Q[6]), "g" (Nb.Q[7])
     );
  return Res;
}

inline Nb1024 Nb1024::operator+ (const Nb1024 &Terme)const{
  Nb1024 Res;
  asm ("add %17, %9\n\t"
       "adc %18, %10\n\t"
       "adc %19, %11\n\t"
       "adc %20, %12\n\t"
       "adc %21, %13\n\t"
       "adc %22, %14\n\t"
       "adc %23, %15\n\t"
       "adc %24, %16\n\t"
       
       "mov %9, %0\n\t"
       "mov %10,%1\n\t"
       "mov %11,%2\n\t"
       "mov %12,%3\n\t"
       "mov %13,%4\n\t"
       "mov %14,%5\n\t"
       "mov %15,%6\n\t"
       "mov %16,%7\n\t"
       
       "setc %8\n\t"
     : 
       "=m" (Res.Nb.Q[0]), "=m" (Res.Nb.Q[1]), "=m" (Res.Nb.Q[2]), "=m" (Res.Nb.Q[3]), 
       "=m" (Res.Nb.Q[4]), "=m" (Res.Nb.Q[5]), "=m" (Res.Nb.Q[6]), "=m" (Res.Nb.Q[7]),
       
       "=g" (Res.carry)
     :
       "r" (Terme.Nb.Q[0]), "r" (Terme.Nb.Q[1]), "r" (Terme.Nb.Q[2]), "r" (Terme.Nb.Q[3]),
       "r" (Terme.Nb.Q[4]), "r" (Terme.Nb.Q[5]), "r" (Terme.Nb.Q[6]), "r" (Terme.Nb.Q[7]),
       
       "g" (Nb.Q[0]), "g" (Nb.Q[1]), "g" (Nb.Q[2]), "g" (Nb.Q[3]),
       "g" (Nb.Q[4]), "g" (Nb.Q[5]), "g" (Nb.Q[6]), "g" (Nb.Q[7])
     );
  asm ("testl $1,%8\n\t"
       "clc\n\t"
       "jz 1f\n\t"
       "stc\n\t"
       "1:\n\t"
       
       "adc %17, %9\n\t"
       "adc %18, %10\n\t"
       "adc %19, %11\n\t"
       "adc %20, %12\n\t"
       "adc %21, %13\n\t"
       "adc %22, %14\n\t"
       "adc %23, %15\n\t"
       "adc %24, %16\n\t"
       
       "mov %9, %0\n\t"
       "mov %10,%1\n\t"
       "mov %11,%2\n\t"
       "mov %12,%3\n\t"
       "mov %13,%4\n\t"
       "mov %14,%5\n\t"
       "mov %15,%6\n\t"
       "mov %16,%7\n\t"
       
       "setc %8\n\t"
     : 
       "=m" (Res.Nb.Q[8]), "=m" (Res.Nb.Q[9]), "=m" (Res.Nb.Q[10]),"=m" (Res.Nb.Q[11]), 
       "=m" (Res.Nb.Q[12]),"=m" (Res.Nb.Q[13]),"=m" (Res.Nb.Q[14]),"=m" (Res.Nb.Q[15]),
       
       "+g" (Res.carry)
     :
       "r" (Terme.Nb.Q[8]), "r" (Terme.Nb.Q[9]), "r" (Terme.Nb.Q[10]),"r" (Terme.Nb.Q[11]),
       "r" (Terme.Nb.Q[12]),"r" (Terme.Nb.Q[13]),"r" (Terme.Nb.Q[14]),"r" (Terme.Nb.Q[15]),
       
       "g" (Nb.Q[8]), "g" (Nb.Q[9]), "g" (Nb.Q[10]), "g" (Nb.Q[11]),
       "g" (Nb.Q[12]),"g" (Nb.Q[13]),"g" (Nb.Q[14]), "g" (Nb.Q[15])
     );
  return Res;
}

inline Nb512 Nb512::operator- (const Nb512 &Terme)const{
  Nb512 Res;
  asm ("sub %17, %9\n\t"
       "sbb %18, %10\n\t"
       "sbb %19, %11\n\t"
       "sbb %20, %12\n\t"
       "sbb %21, %13\n\t"
       "sbb %22, %14\n\t"
       "sbb %23, %15\n\t"
       "sbb %24, %16\n\t"
       
       "mov %9, %0\n\t"
       "mov %10,%1\n\t"
       "mov %11,%2\n\t"
       "mov %12,%3\n\t"
       "mov %13,%4\n\t"
       "mov %14,%5\n\t"
       "mov %15,%6\n\t"
       "mov %16,%7\n\t"
       
       "setc %8\n\t"
     : 
       "=m" (Res.Nb.Q[0]), "=m" (Res.Nb.Q[1]), "=m" (Res.Nb.Q[2]), "=m" (Res.Nb.Q[3]), 
       "=m" (Res.Nb.Q[4]), "=m" (Res.Nb.Q[5]), "=m" (Res.Nb.Q[6]), "=m" (Res.Nb.Q[7]),
       
       "=g" (Res.carry)
     :
       "r" (Nb.Q[0]), "r" (Nb.Q[1]), "r" (Nb.Q[2]), "r" (Nb.Q[3]),
       "r" (Nb.Q[4]), "r" (Nb.Q[5]), "r" (Nb.Q[6]), "r" (Nb.Q[7]),
       
       "g" (Terme.Nb.Q[0]), "g" (Terme.Nb.Q[1]), "g" (Terme.Nb.Q[2]), "g" (Terme.Nb.Q[3]),
       "g" (Terme.Nb.Q[4]), "g" (Terme.Nb.Q[5]), "g" (Terme.Nb.Q[6]), "g" (Terme.Nb.Q[7])
     );
  return Res;
}

inline Nb1024 Nb1024::operator- (const Nb1024 &Terme)const{
  Nb1024 Res;
  asm ("sub %17, %9\n\t"
       "sbb %18, %10\n\t"
       "sbb %19, %11\n\t"
       "sbb %20, %12\n\t"
       "sbb %21, %13\n\t"
       "sbb %22, %14\n\t"
       "sbb %23, %15\n\t"
       "sbb %24, %16\n\t"
       
       "mov %9, %0\n\t"
       "mov %10,%1\n\t"
       "mov %11,%2\n\t"
       "mov %12,%3\n\t"
       "mov %13,%4\n\t"
       "mov %14,%5\n\t"
       "mov %15,%6\n\t"
       "mov %16,%7\n\t"
       
       "setc %8\n\t"
     : 
       "=m" (Res.Nb.Q[0]), "=m" (Res.Nb.Q[1]), "=m" (Res.Nb.Q[2]), "=m" (Res.Nb.Q[3]), 
       "=m" (Res.Nb.Q[4]), "=m" (Res.Nb.Q[5]), "=m" (Res.Nb.Q[6]), "=m" (Res.Nb.Q[7]),
       
       "=g" (Res.carry)
     :
       "r" (Nb.Q[0]), "r" (Nb.Q[1]), "r" (Nb.Q[2]), "r" (Nb.Q[3]),
       "r" (Nb.Q[4]), "r" (Nb.Q[5]), "r" (Nb.Q[6]), "r" (Nb.Q[7]),
       
       "g" (Terme.Nb.Q[0]), "g" (Terme.Nb.Q[1]), "g" (Terme.Nb.Q[2]), "g" (Terme.Nb.Q[3]),
       "g" (Terme.Nb.Q[4]), "g" (Terme.Nb.Q[5]), "g" (Terme.Nb.Q[6]), "g" (Terme.Nb.Q[7])
     );
  asm ("testl $1,%8\n\t"
       "clc\n\t"
       "jz 1f\n\t"
       "stc\n\t"
       "1:\n\t"
       
       "sbb %17, %9\n\t"
       "sbb %18, %10\n\t"
       "sbb %19, %11\n\t"
       "sbb %20, %12\n\t"
       "sbb %21, %13\n\t"
       "sbb %22, %14\n\t"
       "sbb %23, %15\n\t"
       "sbb %24, %16\n\t"
       
       "mov %9, %0\n\t"
       "mov %10,%1\n\t"
       "mov %11,%2\n\t"
       "mov %12,%3\n\t"
       "mov %13,%4\n\t"
       "mov %14,%5\n\t"
       "mov %15,%6\n\t"
       "mov %16,%7\n\t"
       
       "setc %8\n\t"
     : 
       "=m" (Res.Nb.Q[8]), "=m" (Res.Nb.Q[9]), "=m" (Res.Nb.Q[10]),"=m" (Res.Nb.Q[11]), 
       "=m" (Res.Nb.Q[12]),"=m" (Res.Nb.Q[13]),"=m" (Res.Nb.Q[14]),"=m" (Res.Nb.Q[15]),
       
       "+g" (Res.carry)
     :
       "r" (Nb.Q[8]), "r" (Nb.Q[9]), "r" (Nb.Q[10]), "r" (Nb.Q[11]),
       "r" (Nb.Q[12]),"r" (Nb.Q[13]),"r" (Nb.Q[14]), "r" (Nb.Q[15]),
       
       "g" (Terme.Nb.Q[8]), "g" (Terme.Nb.Q[9]), "g" (Terme.Nb.Q[10]),"g" (Terme.Nb.Q[11]),
       "g" (Terme.Nb.Q[12]),"g" (Terme.Nb.Q[13]),"g" (Terme.Nb.Q[14]),"g" (Terme.Nb.Q[15])
     );
  return Res;
}

inline Nb2048 Nb2048::operator- (const Nb2048 &Terme)const{
  Nb2048 Res;
  Res.carry=false;
  for(int i=0; i<32; i+=8)
    asm ("test $1,%8\n\t"
         "clc\n\t"
         "jz 1f\n\t"
         "stc\n\t"
         "1:\n\t"
       
         "sbb %17, %9\n\t"
         "sbb %18, %10\n\t"
         "sbb %19, %11\n\t"
         "sbb %20, %12\n\t"
         "sbb %21, %13\n\t"
         "sbb %22, %14\n\t"
         "sbb %23, %15\n\t"
         "sbb %24, %16\n\t"
       
         "mov %9, %0\n\t"
         "mov %10,%1\n\t"
         "mov %11,%2\n\t"
         "mov %12,%3\n\t"
         "mov %13,%4\n\t"
         "mov %14,%5\n\t"
         "mov %15,%6\n\t"
         "mov %16,%7\n\t"
       
         "setc %8\n\t"
      : 
         "=m" (Res.Nb.Q[i+0]), "=m" (Res.Nb.Q[i+1]), "=m" (Res.Nb.Q[i+2]), "=m" (Res.Nb.Q[i+3]), 
         "=m" (Res.Nb.Q[i+4]), "=m" (Res.Nb.Q[i+5]), "=m" (Res.Nb.Q[i+6]), "=m" (Res.Nb.Q[i+7]),
       
         "+g" (Res.carry)
       :
         "r" (Nb.Q[i+0]), "r" (Nb.Q[i+1]), "r" (Nb.Q[i+2]), "r" (Nb.Q[i+3]),
         "r" (Nb.Q[i+4]), "r" (Nb.Q[i+5]), "r" (Nb.Q[i+6]), "r" (Nb.Q[i+7]),
     
         "g" (Terme.Nb.Q[i+0]), "g" (Terme.Nb.Q[i+1]), "g" (Terme.Nb.Q[i+2]), "g" (Terme.Nb.Q[i+3]),
         "g" (Terme.Nb.Q[i+4]), "g" (Terme.Nb.Q[i+5]), "g" (Terme.Nb.Q[i+6]), "g" (Terme.Nb.Q[i+7])
       );
  return Res;
}

Nb1024 Nb512::operator* (const Nb512 &fact)const{
  Nb512 TamponPair[8];
  Nb512 TamponImpair[8];
  bool Zero[8];
  for(int i=0; i<8; i++){
    if(Nb.Q[i]==0){
      Zero[i]=true;
      continue;
    }
    Zero[i]=false;
    
    register unsigned long long ChiffreThis asm("%rcx")=Nb.Q[i];
    for(int j=0; j<8; j+=2){
      asm("mul %3"
          :"=a" (TamponPair[i].Nb.Q[j & 0xE]),   "=d" (TamponPair[i].Nb.Q[(j & 0xE)+1])
          :"a" (fact.Nb.Q[j]), "r" (ChiffreThis)
         );
      asm("mul %3"
          :"=a" (TamponImpair[i].Nb.Q[j & 0xE]),   "=d" (TamponImpair[i].Nb.Q[(j & 0xE)+1])
          :"a" (fact.Nb.Q[j+1]), "r" (ChiffreThis)
         );
    }
  }
  
  Nb1024 Retour;
  Retour=0;
  for(int i=0; i<8; i++) {
    if(Zero[i]==false){
      Retour.DecaleAdd(TamponPair[i],i);
      Retour.DecaleAdd(TamponImpair[i],i+1);
    }
  }
  
  return Retour;
}

Nb2048 Nb1024::operator* (const Nb1024 &fact)const{
  Nb1024 TamponPair[16];
  Nb1024 TamponImpair[16];
  bool Zero[16];
  for(int i=0; i<16; i++){
    if(Nb.Q[i]==0){
      Zero[i]=true;
      continue;
    }
    Zero[i]=false;
    
    register unsigned long long ChiffreThis asm("%rcx")=Nb.Q[i];
    for(int j=0; j<16; j+=2){
      asm("mul %3"
          :"=a" (TamponPair[i].Nb.Q[j & 0xE]),   "=d" (TamponPair[i].Nb.Q[(j & 0xE)+1])
          :"a" (fact.Nb.Q[j]), "r" (ChiffreThis)
         );
      asm("mul %3"
          :"=a" (TamponImpair[i].Nb.Q[j & 0xE]),   "=d" (TamponImpair[i].Nb.Q[(j & 0xE)+1])
          :"a" (fact.Nb.Q[j+1]), "r" (ChiffreThis)
         );
    }
  }
  
  Nb2048 Retour;
  Retour=0;
  for(int i=0; i<16; i++) {
    if(Zero[i]==false){
      Retour.DecaleAdd(TamponPair[i],i);
      Retour.DecaleAdd(TamponImpair[i],i+1);
    }
  }
  
  return Retour;
}

inline Nb1024 Nb512::operator* (unsigned long long fact)const{
  Nb512 Tampon;
  
  Nb1024 Res;
  if(fact==0) return Res=0;
    
  Res=0;
  
  for(int i=0; i<8; i+=2){
    asm("mul %3"
        :"=a" (Res.Nb.Q[i & 0xE]),   "=d" (Res.Nb.Q[(i & 0xE)+1])
        :"a" (Nb.Q[i]), "r" (fact)
       );
    asm("mul %3"
        :"=a" (Tampon.Nb.Q[i & 0xE]),   "=d" (Tampon.Nb.Q[(i & 0xE)+1])
        :"a" (Nb.Q[i+1]), "r" (fact)
       );
  }
    
  Res.DecaleAdd(Tampon,1);
  
  return Res;
}

inline Nb2048 Nb1024::operator* (unsigned long long fact)const{
  Nb1024 Tampon;
  
  Nb2048 Res;
  if(fact==0) return Res=0;
    
  Res=0;
  
  for(int i=0; i<16; i+=2){
    asm("mul %3"
        :"=a" (Res.Nb.Q[i & 0xE]),   "=d" (Res.Nb.Q[(i & 0xE)+1])
        :"a" (Nb.Q[i]), "r" (fact)
       );
    asm("mul %3"
        :"=a" (Tampon.Nb.Q[i & 0xE]),   "=d" (Tampon.Nb.Q[(i & 0xE)+1])
        :"a" (Nb.Q[i+1]), "r" (fact)
       );
  }
    
  Res.DecaleAdd(Tampon,1);
  
  return Res;
}

//Un chiffre = un DWORD
Nb512 Nb1024::operator% (const Nb512 &Mod)const{
  Nb512 Res;  
  
  if(ChercheQuotient) {
    if(Res.Quotient!=NULL) delete Res.Quotient;
    Res.Quotient=new Nb1024;
    *Res.Quotient=0;
  }
  
  //ChiffreBase : contient l'index du chiffre dans Dividende que l'on va utiliser pour faire la premiere approche de Quotient
  signed char IndexThis, ChiffreBase;
  for(IndexThis=31; this->Nb.D[IndexThis]==0; IndexThis--) if (IndexThis==0) return Res=0;
  for(ChiffreBase=15; Mod.Nb.D[ChiffreBase]==0; ChiffreBase--) if(ChiffreBase==0) exit(-1); //division par 0
  if(IndexThis<ChiffreBase) return Res=*this;
  
  Nb1024 Dividende; //Dividende partiel traité à une itération de la boucle
  Dividende=0;
  for(int i=ChiffreBase-1; i>=0; i--, IndexThis--) Dividende.Nb.D[i]=this->Nb.D[IndexThis];  
  
  for(; IndexThis>=0; IndexThis--){    
    // TODO : A faire en Asm (SSE ou non, selon le mieux)
    for(int i=15; i>=0; i--) Dividende.Nb.D[i+1]=Dividende.Nb.D[i];
    Dividende.Nb.D[0]=this->Nb.D[IndexThis];
        
    unsigned long long Quotient, RestePart;
    asm ("divq %4"  //Premiere estimation de Quotient
       :"=a" (Quotient), "=d" (RestePart)
       :"a" ( Dividende.Nb.D[ChiffreBase] + ((unsigned long long)Dividende.Nb.D[ChiffreBase+1]<<32)), "d" (0), "g" ( (unsigned long long)Mod.Nb.D[ChiffreBase])
       );
    bool QuotientOK=false;
    if(Quotient > 0xFFFFFFFF) {
      Quotient=0xFFFFFFFF; 
      //RestePart = Dividende.Nb.D[ChiffreBase+1]:Dividende.Nb.D[ChiffreBase] - 0xFFFFFFFF * Md.Nb.D[ChiffreBase]
      RestePart= Dividende.Nb.D[ChiffreBase] + ((unsigned long long)Dividende.Nb.D[ChiffreBase+1]<<32) - ((unsigned long long)Mod.Nb.D[ChiffreBase]<<32) + Mod.Nb.D[ChiffreBase]<<32;
      if(RestePart & 0xFFFFFFFF00000000) QuotientOK=true;
    }
    //Ensuite, le but est de rajouter des chiffres et de calculer l'erreur que l'on commet : on multiplie l'estimation du quotient déjà faite par les chiffres 
    //de Mod déja pris en compte puis on soustrait les chiffres de dividende déjà pris en compte. Si le résultat est négatif ou nul, pas de problème, 
    //Quotient n'est pas trop grand (il ne peut pas être trop petit). Dans ce cas, l'opposé du résultat correspond au reste de la division. S'il est positif,
    //on le divise par les chiffres de Mod déjà pris en compte : on obtient un nombre qu'il faut soustraire à Quotient. Sans optimisation, cette méthode est 
    //impossible : on se retrouve a faire des divisions avec un dénominateur énorme et tout un tas de multiplications...
    //Pour simplifier, on se rend compte que ce nombre est calculable a partir du reste de la division précédente (calculé lors de la derniere estimation de 
    //Quotient: on supprime donc beaucoup de multiplications inutiles. De plus, seules la premiere itération de cette boucle est utiles : les autres ne pourront 
    //Faire descendre Quotient que de 1 : on remplace donc toutes ces itérations par une comparaison entre Quotient*Mod et Diviseur, qui nous dira s'il faut 
    //décrémenter Quotient ou non.
      
    //Petite vérification.. histoire de pas faire des opérations pour rien
    if(Quotient == 0) continue;
     
    if(ChiffreBase == 0) QuotientOK=true;
    
    if(!QuotientOK){
      unsigned long long Tmp=Quotient*Mod.Nb.D[ChiffreBase-1];
      if(Tmp > ((unsigned long long)RestePart<<32) + Dividende.Nb.D[ChiffreBase-1])
        //Le nombre dont on parle dans le § de commentaires plus haut est positif : on réajuste Quotient
        //Diviseion en arrondissant par au dessus : d'où le  1 + et le -1
        Quotient-=1 + (Tmp - ((unsigned long long)RestePart<<32) - Dividende.Nb.D[ChiffreBase-1] - 1) / ( ((unsigned long long)Mod.Nb.D[ChiffreBase]<<32) + Mod.Nb.D[ChiffreBase-1] );
    }
      
    Dividende=Dividende-Mod*Quotient;
    if(Dividende.carry) {
      Dividende.DecaleAdd(Mod,0);
      Quotient--;
    }
    if(ChercheQuotient) 
      Res.Quotient->Nb.D[IndexThis]=Quotient;
  }
  
  return Res=Dividende;
}

Nb1024 Nb2048::operator% (const Nb1024 &Mod)const{
  Nb1024 Res;  
  
  if(ChercheQuotient) {
    if(Res.Quotient!=NULL) delete Res.Quotient;
    Res.Quotient=new Nb2048;
    *Res.Quotient=0;
  }
  
  //ChiffreBase : contient l'index du chiffre dans Dividende que l'on va utiliser pour faire la premiere approche de Quotient
  signed char IndexThis, ChiffreBase;
  for(IndexThis=63; this->Nb.D[IndexThis]==0; IndexThis--) if (IndexThis==0) return Res=0;
  for(ChiffreBase=31; Mod.Nb.D[ChiffreBase]==0; ChiffreBase--) if(ChiffreBase==0) exit(-1); //division par 0
  if(IndexThis<ChiffreBase) return Res=*this;
  
  Nb2048 Dividende; //Dividende partiel traité à une itération de la boucle
  Dividende=0;
  for(int i=ChiffreBase-1; i>=0; i--, IndexThis--) Dividende.Nb.D[i]=this->Nb.D[IndexThis];
  
  for(; IndexThis>=0; IndexThis--){    
    // TODO : A faire en Asm (SSE ou non, selon le mieux)
    for(int i=31; i>=0; i--) Dividende.Nb.D[i+1]=Dividende.Nb.D[i];
    Dividende.Nb.D[0]=this->Nb.D[IndexThis];
        
    unsigned long long Quotient, RestePart;
    asm ("divq %4"  //Premiere estimation de Quotient
       :"=a" (Quotient), "=d" (RestePart)
       :"a" ( Dividende.Nb.D[ChiffreBase] + ((unsigned long long)Dividende.Nb.D[ChiffreBase+1]<<32)), "d" (0), "g" ( (unsigned long long)Mod.Nb.D[ChiffreBase])
       );
    bool QuotientOK=false;
    if(Quotient > 0xFFFFFFFF) {
      Quotient=0xFFFFFFFF; 
      //RestePart = Dividende.Nb.D[ChiffreBase+1]:Dividende.Nb.D[ChiffreBase] - 0xFFFFFFFF * Md.Nb.D[ChiffreBase]
      RestePart= Dividende.Nb.D[ChiffreBase] + ((unsigned long long)Dividende.Nb.D[ChiffreBase+1]<<32) - ((unsigned long long)Mod.Nb.D[ChiffreBase]<<32) + Mod.Nb.D[ChiffreBase]<<32;
      if(RestePart & 0xFFFFFFFF00000000) QuotientOK=true;
    }
    //Ensuite, le but est de rajouter des chiffres et de calculer l'erreur que l'on commet : on multiplie l'estimation du quotient déjà faite par les chiffres 
    //de Mod déja pris en compte puis on soustrait les chiffres de dividende déjà pris en compte. Si le résultat est négatif ou nul, pas de problème, 
    //Quotient n'est pas trop grand (il ne peut pas être trop petit). Dans ce cas, l'opposé du résultat correspond au reste de la division. S'il est positif,
    //on le divise par les chiffres de Mod déjà pris en compte : on obtient un nombre qu'il faut soustraire à Quotient. Sans optimisation, cette méthode est 
    //impossible : on se retrouve a faire des divisions avec un dénominateur énorme et tout un tas de multiplications...
    //Pour simplifier, on se rend compte que ce nombre est calculable a partir du reste de la division précédente (calculé lors de la derniere estimation de 
    //Quotient: on supprime donc beaucoup de multiplications inutiles. De plus, seules la premiere itération de cette boucle est utiles : les autres ne pourront 
    //Faire descendre Quotient que de 1 : on remplace donc toutes ces itérations par une comparaison entre Quotient*Mod et Diviseur, qui nous dira s'il faut 
    //décrémenter Quotient ou non.
      
    //Petite vérification.. histoire de pas faire des opérations pour rien
    if(Quotient == 0) continue;
     
    if(ChiffreBase == 0) QuotientOK=true;
    
    if(!QuotientOK){
      unsigned long long Tmp=Quotient*Mod.Nb.D[ChiffreBase-1];
      if(Tmp > ((unsigned long long)RestePart<<32) + Dividende.Nb.D[ChiffreBase-1])
        //Le nombre dont on parle dans le § de commentaires plus haut est positif : on réajuste Quotient
        //Diviseion en arrondissant par au dessus : d'où le  1 + et le -1
        Quotient-=1 + (Tmp - ((unsigned long long)RestePart<<32) - Dividende.Nb.D[ChiffreBase-1] - 1) / ( ((unsigned long long)Mod.Nb.D[ChiffreBase]<<32) + Mod.Nb.D[ChiffreBase-1] );
    }
      
    //On fait la grande multiplcation et soustraction
    Dividende=Dividende-Mod*Quotient;
    if(Dividende.carry) {
      Dividende.DecaleAdd(Mod,0);
      Quotient--;
    }
    if(ChercheQuotient) 
      Res.Quotient->Nb.D[IndexThis]=Quotient;
  }
  
  return Res=Dividende;
}

inline bool Nb512::operator== (const Nb512 &Nb)const{
  return !memcmp(&this->Nb,&Nb.Nb,sizeof(Nb.Nb));
}

inline bool Nb1024::operator== (const Nb1024 &Nb)const{
  return !memcmp(&this->Nb,&Nb.Nb,sizeof(Nb.Nb));
}

inline bool Nb2048::operator== (const Nb2048 &Nb)const{
  return !memcmp(&this->Nb,&Nb.Nb,sizeof(Nb.Nb));
}

Nb512 Nb512::Puissance (const Nb512 &Exp, const Nb512 &Mod)const{
  Nb512 Res;
  Res=1;
  //TODO ne pas faire les premiers octets vides
  for(int i=63; i>=0; i--)
    for(int j=128; j>0; j>>=1){
      Res=Res*Res % Mod;
      if(Exp.Nb.B[i] & j){
        Res=Res* *this % Mod;
      }    
    }
  return Res;
}

Nb1024 Nb1024::Puissance (const Nb1024 &Exp, const Nb1024 &Mod)const{
  Nb1024 Res;
  Res=1;
  //TODO ne pas faire les premiers octets vides
  for(int i=127; i>=0; i--)
    for(int j=128; j>0; j>>=1){
      Res=Res*Res % Mod;
      if(Exp.Nb.B[i] & j){
        Res=Res* *this % Mod;
      }    
    }
  return Res;
}

void Nb512::Hasard (){
  for(int i=0; i<8; i++){
    NbHasard*=6364136223846793005; //Générateur de Haynes
    NbHasard++;
    
    this->Nb.Q[i]=NbHasard;
  }
  while ((Nb.Q[7] & ((unsigned long long)1<<63)) == 0){ //Pour avoir un VRAI nombre de 512 bits
    NbHasard*=6364136223846793005; //Générateur de Haynes
    NbHasard++;
    
    this->Nb.Q[7]=NbHasard;
  }
}

//http://cryptosec.lautre.net/article.php3?id_article=12
bool Nb512::MillerRabin(unsigned int Boucles)const{  
  unsigned int b;
  Nb512 thism1,un;
  un=1; thism1=*this -un;
  
  //calcul de b
  for(b=0;b<512; b+=64)
    if(thism1.Nb.Q[b>>6]!=0) break;
  
  if(b==512) return false; // *this==1
  
  for(; b<512; b++)
    if( (thism1.Nb.Q[b>>6] & ( 1 << (b&63)) )!=0) break;
  
  //calcul de r
  Nb512 r; int i;
  for(i=0; i<7 - (b>>6); i++)
    r.Nb.Q[i]=(thism1.Nb.Q[i + (b>>6) + 1]<<(64-(b&63))) | (thism1.Nb.Q[i + (b>>6)]>>(b&63));
  r.Nb.Q[i]=thism1.Nb.Q[i + (b>>6)]>>(b&63);
  for(i++; i<8; i++) r.Nb.Q[i]=0;
  
    
  for(i=0; i<Boucles; i++){
    Nb512 a;
    a.Hasard();
    //On s'assure que a<this* en mettant a 0 1 octet de plus dans a que dans this
    for(int j=63; j>=0; j--){
      a.Nb.B[i]=0;
      if(this->Nb.B[i] != 0) break;
    }
    
    //y est représenté ici par a :
    a=a.Puissance(r,*this);
    if(a==un) continue;
    for( int j=0; j<b; j++){
      if(a==un) return false;
      if(a==thism1) break;
      a=a*a % *this;
    }
    if(!(a==thism1)) return false;
  }
  return true;
}

void Nb512::Premier(){
  do{
    Hasard(); /*FIXME : utiliser un meilleur générateur aléatoire*/
    Nb.B[0]|=1;
  } while (!MillerRabin(5));
}

//trouve le nombre a tel que this*a = PGCD(this;Mod) modulo Mod
//En fait, ici on l'appele avec this et Mod premiers entres eux.. donc PGCD=1 donc a*this = 1 modulo Mod donc a est bine l'inverse de this modulo Mod
//On utilise pour ceci l'algoritme d'euclide étendu
Nb1024 Nb1024::Inverse(const Nb1024 &Mod)const{
  Nb1024 Tmp1024;

  struct sListeQuotients{
     struct sListeQuotients* q;
     Nb1024 t;
  } *ListeQuotients=new struct sListeQuotients,*TmpListeQuotients;
  
  
  //On commence par appliquer l'algoritme d'euclide et on retient tous les quotients
  Nb1024 Nb2,Zero;
  Nb2048 Nb1;
  ListeQuotients->q=NULL;
  Zero=0;
  Nb1=Mod;
  Nb2=*this;
  do{
    Nb1.ChercheQuotient=true;
    Tmp1024=Nb1 % Nb2;
    ListeQuotients->t=*Tmp1024.Quotient;
    Nb1=Nb2;
    Nb2=Tmp1024;
    TmpListeQuotients=new struct sListeQuotients;
    TmpListeQuotients->q=ListeQuotients;
    ListeQuotients=TmpListeQuotients;
  }while(!(Nb2==Zero));
  
  //On enlève deux éléments de la liste : le premier car il est vide et le deuxième car on se fiche du dernier quotient obtenu
  TmpListeQuotients=ListeQuotients;
  ListeQuotients=ListeQuotients->q;
  delete TmpListeQuotients;
  TmpListeQuotients=ListeQuotients;
  ListeQuotients=ListeQuotients->q;
  delete TmpListeQuotients;
  
  //Et on le remonte pour finalement trouver les deux coefficients de Bezout, dont l'un est le nombre cherché
  //On calcule la suite : U(n-2)=U(n)-q(n-2)*U(n-1) où q(n) est le n-ième quotient calculé plus haut
  //Pour simplifier, on fait tous ces calculs modulo Mod. Si on se retrouve avec un U(n-2) négatif, on lui ajoute Mod
  Nb1024 Unm1,Un;
  Unm1=1;
  Un=0;
  while(ListeQuotients!=NULL){
    Tmp1024=Un- ((ListeQuotients->t * Unm1) % Mod);
    if(Tmp1024.carry) Tmp1024=Tmp1024+Mod;
    
    Un=Unm1;
    Unm1=Tmp1024;
    
    TmpListeQuotients=ListeQuotients;
    ListeQuotients=ListeQuotients->q;
    delete TmpListeQuotients;
  }
  return Unm1;
}

int main(){
  Nb512 p,q,un,clair512;
  un=1;
  Nb1024 n,e,d,phi,clair,chiffre,dechiffre;
  Nb2048 Verif;
  InitHasard();
  
  p.Premier();  
  q.Premier();
  
  n=p*q;
  printf("\n\nModulo commun aux deux clées :\n");
  for(int i=31; i>=0; i--) printf("%.8X ",n.Nb.D[i]);
  
  phi=(p-un)*(q-un);
  
  e=0x10001;
  printf("\n\nExposant public e:(Par défaut, 0x10001)");
  //for(int i=31; i>=0; i--) printf("%.8X ",e.Nb.D[i]);
  
  d=e.Inverse(phi);
  printf("\n\nExposant privé d :\n");
  for(int i=31; i>=0; i--) printf("%.8X ",d.Nb.D[i]);
  
  printf("\n\nPour vérification, d*e mod phi(n)=(p-1)*(q-1): (doit être 1)\n");
  Verif=d*e;
  Verif=Verif % phi;
  for(int i=31; i>=0; i--) printf("%.8X ",Verif.Nb.D[i]);
  
  printf("\n\n\nTest: Bloc de départ (non chiffré) :\n");
  clair512.Hasard();
  clair=clair512;
  clair512.Hasard();
  clair.DecaleAdd(clair512,8);
  clair.Nb.B[127]&=0xf;
  for(int i=31; i>=0; i--) printf("%.8X ",clair.Nb.D[i]);
  
  printf("\n\nTest: Bloc chiffré :\n");
  chiffre=clair.Puissance(e,n);
  for(int i=31; i>=0; i--) printf("%.8X ",chiffre.Nb.D[i]);
  
  printf("\n\nTest: Bloc déchiffré :\n");
  dechiffre=chiffre.Puissance(d,n);
  for(int i=31; i>=0; i--) printf("%.8X ",dechiffre.Nb.D[i]);
  
  printf("\n");
}

Conclusion

Se compile avec gcc ( soit la version Unix 64 bits, soit une version sous windows, toujours 64bits).
Un petit bug à la compilation, du à gcc : il faut compiler avec l'option -O (sinon il refuse de compiler).
Pas de bugs connus, mais quelques précisions : le message à coder ne doit pas être supèrieur ou égal à n.

Historique

03 mars 2005 20:34:31 :
29 novembre 2005 17:11:48 :: Ajout de mots-cles
05 mai 2009 00:01:46 :: corrections de typos.

Sources du même auteur

DESSINATEUR DE FRACTALES

Toutes les sources de jourgun

Sources de la même categorie

PROJET DE CRYPTOGRAPHIE: RSA À JEU REDUIT D'INSTRUCTION par samatarahmed

CRYPTOSYSTÈME ELGAMAL LIBRAIRIE GMP par louelh95

NOUVEL ALGORITHME D'ENCRYPTION-DÉSENCRYPTION DYNAMIQUE (INFA... par vletktol

A2DCRYPT - CRYPTAGE 2048 BITS par darkor

CRYPTEUR-DÉCRYPTEUR-IP par antho974

Toutes les sources de la catégorie Sécurité & Cryptage

Sources en rapport avec celle ci

SECURE REMOTE SHELL [WIN32] par ganjarasta

PROJET DE CRYPTOGRAPHIE: RSA À JEU REDUIT D'INSTRUCTION par samatarahmed

CRYPTOSYSTÈME ELGAMAL LIBRAIRIE GMP par louelh95

NOUVEL ALGORITHME D'ENCRYPTION-DÉSENCRYPTION DYNAMIQUE (INFA... par vletktol

[C++] & SFML CRYPTOGRAPHIE par pop70

Commentaires et avis

Commentaire de BruNews le 03/03/2005 13:41:56 administrateur CS

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

Commentaire de jourgun le 03/03/2005 14:15:37

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.

Commentaire de myrion le 03/03/2005 14:49:50

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!)

Commentaire de jourgun le 03/03/2005 15:31:50

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

Commentaire de BruNews le 03/03/2005 16:42:29 administrateur CS

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 ?

Commentaire de jourgun le 03/03/2005 20:36:50

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..

Commentaire de Arnaud16022 le 03/03/2005 20:56:54

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

Commentaire de jourgun le 03/03/2005 21:20:40

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.

Commentaire de jourgun le 03/03/2005 21:42:56

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..

Commentaire de Arnaud16022 le 04/03/2005 17:16:34

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?

Commentaire de BruNews le 04/03/2005 17:32:53 administrateur CS

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

Commentaire de Arnaud16022 le 04/03/2005 19:50:45

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

Commentaire de coucou747 le 04/03/2005 21:55:32 administrateur CS

"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.

Commentaire de jourgun le 04/03/2005 23:29:21

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

Commentaire de Arnaud16022 le 05/03/2005 15:33:46

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

merci a Brunews pour les urls

Commentaire de coucou747 le 05/03/2005 18:23:45 administrateur CS

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...)

Commentaire de contax le 12/03/2005 20:09:23

" ... 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.

Commentaire de Arnaud16022 le 12/03/2005 22:16:29

????
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

Commentaire de BruNews le 12/03/2005 22:23:28 administrateur CS

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

Commentaire de contax le 13/03/2005 09:27:44

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).

Commentaire de jourgun le 13/03/2005 11:17:24

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

Commentaire de contax le 13/03/2005 12:30:19

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

Commentaire de jourgun le 13/03/2005 13:06:37

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

Commentaire de coucou747 le 13/03/2005 13:50:32 administrateur CS

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...

Commentaire de contax le 13/03/2005 14:02:54

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.

Commentaire de BruNews le 13/03/2005 14:04:27 administrateur CS

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

Commentaire de contax le 13/03/2005 14:08:43

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

Commentaire de jourgun le 14/03/2005 01:18:28

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.

Ajouter un commentaire

Discussions en rapport avec ce code source dans le forum

cryptage RSA [ par moicmoi ] Bon je me doute que je vais passer pour un boulet mais j'aurai besoin avant jeudi d'un code source du cryptage RSA en LANGAGE C. Mais un code tout si Cryptage RSA [ par ritchie00 ] Salut,Qqun saurait où je peux trouver une API C++ de chiffrement/dechiffrement RSA, qui marcherait avec des certificats et des tailles de clés paramét Debugage assembleur [ par crocejf2000 ] Salut,Qq'un pourrai il peut etre m'aider, j'ai une méchante érreur et jmy connais pas trop en assembleur, Borland c++ 5 me renvoi ceci : Il s'arrete a mettre de l'assembleur en ligne sous Visual C++ [ par alain34270 ] alainBonjour,Voilà. J'ai un problème avec mon disque dur. je voudrais lire les secteurs physiques de mon disque dur, si possible à partir de visual C+ récupérer code assembleur [ par none77 ] Bonjour,j'aimerai savoir si lorsque je programme en C il m'est possible de récupérer le code assembleur automatiquement.Je demande ca car je dois util Macro assembleur pour microcontroleur [ par Tyozhebes ] Bonjour à tous ! Je suis actuellement sur la programmation d'un 68HC11 et, pour des raisons de mémoire (seulement 2ko), il me faut le programmer en [Asm][Devc++] [ par Gonath ] Bon voilà, je programme sur devc++ depuis peu. Je voudrais y insérer des codes en assembleur vu que je connais l'assembleur. Mais le prob, c qu'il n'a Le cryptage par MD5 de RSA [ par LSRS ] Salut tout le monde...J'ai un très grand problème avec l'algorithme de hachage MD5 qui réprésente le squelette de mon stage d'été... Je n'arrive pas à interruprion assembleur [ par seito ] SVP est ce que quelqu'un sait comment éxecuter les interuptions assembleurs dans Visual Cmerci Pb avec l'assembleur dev-cpp [ par 6co ] Voici une source vue sur cppfrance et corrigée pour l'assembleur de Dev-Cpp#include <iostream>#include <stdlib.h>#include <conio.c>#

Nos sponsors

Derniers Blogs

IMAGINE CUP 2012, MAKE A SIGN EN FINALE par junarnoalg

KINECT 1.5 IS OUT ! par Vko

LES ACTUALITéS DE LA SEMAINE SUR C2I.FR (14 MAI - 20 MAI) par richardc

REACTIVE EXTENSIONS : CONSOMMER DES SERVICES AVEC RX PARTIE 3, LES PIèGES à éVITER par Groc

SHAREPOINT BLOG SITE, PROBLèME D'ARCHIVES par junarnoalg

Forum

MATRICE TEMPLATE par hjr2610

SUPERVISION DE LA BATTERIE par romanticgirl

RE : OPENCV ET INTERFACE GRAPHIQUE VISUAL STUDIO par buno

RE : SAC A DOS par hadjkaddour

OPENCV ET INTERFACE GRAPHIQUE VISUAL STUDIO par ssaif

Côté IT

Offres d'emploi

Formations Video

Appels d'offres

Realisation d-une version 2 d-un site e-commerce existant sous prestashop-REPUBLICATION
Budget : 5 000€
Recherche Infogerance Serveur Debian Linux
Budget : 1 800€
Creation d-un site vitrine avec MagentO
Budget : 2 000€

Logiciels

sDEVIS-FACTURES vlPRO (8.1.0.3)
SDEVIS-FACTURES VLPRO (8.1.0.3)

sDEVIS-FACTURES vlPRO a été mis au point pour les particuliers, créateurs, entrepreneurs, artisa...

Cliquez pour télécharger sDEVIS-FACTURES vlPRO
974 Application Server (12.2.4.6)
974 APPLICATION SERVER (12.2.4.6)

Développez de puissantes applications dans un environnement de 'cloud computing', clusterisé, séc...

Cliquez pour télécharger 974 Application Server
vPicture (1.4.2.1)
VPICTURE (1.4.2.1)

Avec vPicture, hébergez vos images facilement et rapidement. vPicture est un utilitaire simple, ...

Cliquez pour télécharger vPicture
Easy-Planning (2.2.1.6)
EASY-PLANNING (2.2.1.6)

Easy-Planning permet de créer des plannings sous la représentation de diagrammes et est adapté au...

Cliquez pour télécharger Easy-Planning
COM-BACKUP (2.0)
COM-BACKUP (2.0)

COM-BACKUP est un logiciel de sauvegarde qui permet de planifier les sauvegardes de vos dossiers ...

Cliquez pour télécharger COM-BACKUP