El algoritmo RSA y la factorización de números grandes

---

typedef unsigned long num;

typedef struct t_rsa_pubkey t_rsa_pubkey;
struct t_rsa_pubkey {

   num e;
   num n;
};

typedef struct t_rsa_privkey t_rsa_privkey;
struct t_rsa_privkey {


   num d;
   num n;
};


/* Verifica si el parametro es un numero primo */
int is_prime (num pr) {

   num i;

   if (pr==1) return 1;

   for (i=3; i<pr; i+=2)
      if ((pr%i != 0) && (i*i <= pr)) break;

   if (i*i > pr) return 1;
   else return 0;
}


/* (a^b) mod n */
static num modexp (num a, num b, num n) {

   num y;

   y = 1;
   while (b!=0) {

      if (b & 1) y = (y * a) % n;

      a = (a * a) % n;
      b = b >> 1;
   }

   return y;
}

/* Cifra plaintext */
void rsa_cipher (num plaintext, num *ciphertext, t_rsa_pubkey pubkey) {

   *ciphertext = modexp (plaintext, pubkey.e, pubkey.n);
}

/* Descifra ciphertext */
void rsa_decipher (num ciphertext, num *plaintext, t_rsa_privkey privkey) {

   *plaintext = modexp (ciphertext, privkey.d, privkey.n);
}

/* Genera un clave publica y una privada a partir de p y q. */
void rsa_genkeys (num p, num q, t_rsa_pubkey *pubkey, t_rsa_privkey *privkey) {

   num n, fi, i, e, d;

   /* Calculamos n */
   n = p * q;

   /* Calculamos fi */
   fi = (p-1) * (q-1);

   /* Calculamos e */
   for (i=1; i<fi; i++)  if (is_prime(i)) { if (fi%i!=0) { e=i; break; } }

   /* Calculamos d */
   for (i=1; i<fi; i++)  if ( ((i*fi)+1)%e == 0) { d=((i*fi)+1)/e; break; }

   pubkey->e = e;
   pubkey->n = n;

   privkey->d = d;
   privkey->n = n;
}


int main (int argc, char **argv)
{
   num num_plain;
   num num_cipher;
   t_rsa_pubkey pubkey;
   t_rsa_privkey privkey;
   num p, q;

   if (argc != 4) {

      printf ("Uso: %s  
 \n\n", argv[0]);
      return 0;
   }

   num_plain = atoll (argv[1]);
   p = atoll (argv[2]);
   q = atoll (argv[3]);


   /* Generamos las claves a partir de p y q */
   rsa_genkeys (p, q, &pubkey, &privkey);

   /* Ciframos */
   rsa_cipher (num_plain, &num_cipher, pubkey);

   printf ("Plain number: %ld\n", num_plain);
   printf ("Cipher number: %ld\n", num_cipher);

   /* Desciframos */
   rsa_decipher (num_cipher, &num_plain, privkey);
   printf ("Plain number: %ld\n", num_plain);

   printf ("\n");
   return 0;
}

#include <stdio.h>
#include <openssl/rsa.h>
#include <openssl/engine.h>



int main()
{


   RSA *keypair;
   char *cleartext = "Hola caracola";
   char *ciphertext;
   char *cleartext2;

   keypair = RSA_new();


   /* Generamos un par de claves de 1024 bits */
   keypair = RSA_generate_key (1024, 17, NULL, NULL);


   ciphertext = malloc(RSA_size(keypair));
   
   RSA_public_encrypt (strlen(cleartext)+1, cleartext, ciphertext, keypair, 
                       RSA_PKCS1_PADDING);


   cleartext2 = malloc(RSA_size(keypair));

   RSA_private_decrypt (RSA_size(keypair), ciphertext, cleartext2, keypair, 
                        RSA_PKCS1_PADDING);


   printf("%s\n", cleartext2);

   RSA_free(keypair);

   
   return 0;
}

#include 

int main (int argc, char **argv) {

   mpz_t x1;
   mpz_t x2;
   mpz_t k;
   mpz_t l;
   mpz_t n;
   mpz_t g;
   mpz_t tmp;

   if (argc!=2) {

      printf ("%s \n", argv[0]);
      return 0;
   }

   mpz_init (x1);
   mpz_init (x2);
   mpz_init (k);
   mpz_init (l);
   mpz_init (n);
   mpz_init (g);
   mpz_init (tmp);
 
   /* Inicializamos valores */
   mpz_set_ui  (x1, 5);  
   mpz_set_ui  (x2, 2);  
   mpz_set_ui  (k, 1);  
   mpz_set_ui  (l, 1);  
   mpz_set_str (n, argv[1], 10);  

   /* Si n es primo, salir */
   if (mpz_probab_prime_p (n, 5)) {

      gmp_printf ("primo: %Zd\n", n);
      return 0;
   }

   while (1) {

      /* MCD (x1-x2, n) */
      mpz_sub (tmp, x2, x1);
      mpz_gcd (g, tmp, n);

      /* si g=1 */
      if (mpz_cmp_ui (g, 1)==0) {

         mpz_sub_ui (k, k, 1);
         
         if (mpz_cmp_ui (k, 0)==0) {   
      
            mpz_set (x2, x1);
            mpz_mul_ui (l, l, 2);
            mpz_set (k, l);     
         }
            
         /* x=x^2+1 */
         mpz_mul (x1, x1, x1);
         mpz_add_ui (x1, x1, 1);
         mpz_mod (x1, x1, n);
         
      }
      else {

         gmp_printf ("factor: %Zd \n", g);

         /* Si g=n, error!! */
         if (mpz_cmp (g, n)==0) { gmp_printf ("Error!!\n"); return 0; }

         /* n=n/g */
         mpz_cdiv_q (n, n, g);

         /* x1=x1 mod n */
         mpz_mod (x1, x1, n);

         /* x2=x2 mod n */
         mpz_mod (x2, x2, n);

         /* Si n es primo, salir */
         if (mpz_probab_prime_p (n, 5)) {

            gmp_printf ("primo: %Zd \n", n);
            return 0;
         }
      }
   
   }

   mpz_clear (x1);
   mpz_clear (x2);
   mpz_clear (k);
   mpz_clear (l);
   mpz_clear (n);
   mpz_clear (g);
   mpz_clear (tmp);

   return 0;
}