/*
Algoritmo RSA con numeros primos basicos
Daniel Lerch Hostalot  
http://daniellerch.com/papers/html/algoritmo_rsa.html
How to use: ./rsa 19 3 7
*/
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 <plain number> <p prime> <q prime>\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 ("Numero plano: %ld\n", num_plain);
   printf ("Llave publica [e,n]: [%ld, %ld]\n",pubkey.e,pubkey.n);
   printf ("Llave privada [d,n]: [%ld, %ld]\n",privkey.d,pubkey.n);
   printf ("Numero cifrado: %ld\n", num_cipher);
   /* Desciframos */
   rsa_decipher (num_cipher, &num_plain, privkey);
   printf ("Numero descifrado: %ld\n", num_plain);
   printf ("\n");
   return 0;
}