Codage rsa sur 1024 bits

Commenter

Contenu du snippet

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 / Exemple : 


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

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (jourgun)