The key generation of the RSA crypto system

The principles of the RSA crypto system have been explained, but now we need to implement the generation of the public and private key.  The core is to find two large prime numbers p and q, and a public key e, that satisfies the property that it is relative prime to Phi(p.q).

We have in fact all fundamental tools to put this in place.  Nevertheless, we will implement three auxiliary functions to make life easier.  The first one is to generate a big random number.  Now, we did here something that is a bad idea in general, we used the simple C-library random number generator, which is a very bad idea to use, because it is not a cryptographically secure pseudo-random number generator, but the code here is simply for illustrative purposes.  In a true cryptographic application, this random number generator is the true generator of entropy, and should be carefully designed ; ideally, one would use a true random number generator.  Entrop-x can help with that.

Concerning the code, we would like to remind: Code examples

 void randomgen(number* myran)
/* generate a random number in the modular ring */
  {
  number rawran;
  number q;
  int i;

  for (i = 0 ; i < nofdigits ; i++)
    {
      rawran.digit[i] = rand() % basis ; 
    }
  dividenum(&rawran,&modulo,&q,myran);
  } // end randomgen

As said before, this is a simplistic random number generator, which has no cryptographic quality, but is good enough for our illustrative purposes.

The second auxiliary function is a simple conversion from a machine integer into a "large number" integer:

 
void makebig(int small, number* big)
/* convert a machine integer into a big number */
  {
  int i;
  int r;
  int q;
  for (i = 0 ; i < nofdigits ; i++)
    {
    big->digit[i] = 0;
    }
  i = 0;
  q = small;
  do
    {
    r = q % basis;
    q = q / basis;
    big->digit[i] = r;
    i++;
    }
  while (q > 0); 
  } // end makebig

The third auxilliary function finds the first prime number greater than a given number:

void findnextprimerabin(number* x, number* y, int k)
/* using Miller-Rabin's primality test, finds the first prime that follows x */
  {
  number nextone;
  number nextnextone;
  number one;
  number q;
  int r;
  int i;
  for (i = 0 ; i < nofdigits ; i++)
    {
    one.digit[i] = 0;
    }
  one.digit[0] = 1;
  divide2(x,&q,&r);
  if (r == 1)
    {
    // x is uneven, OK
    sumnum(x,&one,&nextone);
    }
  else
    {
    // x is even, we need to add one
    sumnum(x,&one,&nextnextone);
    sumnum(&nextnextone,&one,&nextone);
    }
  do
    {
    sumnum(&nextone,&one,&nextnextone);
    sumnum(&nextnextone,&one,&nextone);
    }
  while (isprimerabin(&nextnextone,k) == 0);
  difnum(&nextone,&one,y);
  } // end findnextprimerabin
 

With these three auxiliary functions, we can finally turn to the generator function of an RSA key pair:

 
void rsakeygen(int nbits, number* p1, number* p2, number* n, number* pkey, number* skey)
  {
  number oldmodulo;
  number zero;
  number one;
  number two;
  number allbits;
  number nbitsbig;
  number ran1;
  number ranlim;
  number dummy;
  number dummy2;
  number p1m1;
  number p2m1;
  number phin;
  number gcd;
  int i;

  /* we first test that the number of bits of the keys is less than half the available number of bits in our integers */
  if (nbits > basisbits * (nofdigits - 1) / 2 ) 
    {
    printf("rsakeygen error: nbits too large. \n");
    }

  /* we put the current modulus away and set the modulus to the maximum */
  for (i = 0 ; i < nofdigits ; i++)
    {
    oldmodulo.digit[i] = modulo.digit[i];
    modulo.digit[i] = basis - 1;
    zero.digit[i] = 0;
    one.digit[i] = 0;
    two.digit[i] = 0;
    }
  one.digit[0] = 1;
  two.digit[0] = 2;
  /* we calculate the highest possible number in agreement with our number of bits */
  makebig(nbits,&nbitsbig);
  power(&two,&nbitsbig,&allbits);
  /* we find the first prime p1 */
  do
    {
    randomgen(&ran1);
    dividenum(&ran1,&allbits,&dummy,&ranlim);
    findnextprimerabin(&ranlim,p1,20);
    }
  while (isbigger(p1,&allbits) != -1);
  /* we find the second prime p2 */
  do
    {
    randomgen(&ran1);
    dividenum(&ran1,&allbits,&dummy,&ranlim);
    findnextprimerabin(&ranlim,p2,20);
    }
  while (isbigger(p2,&allbits) != -1);
  timesnum(p1,p2,n);
  difnum(p1,&one,&p1m1);
  difnum(p2,&one,&p2m1);
  timesnum(&p1m1,&p2m1,&phin);
  /* we now find a number e (called pkey) such that gcd(e,phin) = 1 */
  do
    {
    randomgen(&ran1);
    dividenum(&ran1,&phin,&dummy,pkey);
    exteuclid(pkey, &phin, &gcd, &dummy, &dummy2);
    }
  while (isbigger(&gcd,&one) != 0);
  /* finally, we calculate the private key which is the inverse of pkey in the ring modulo phin */
  /* we write phin in the modulus */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = phin.digit[i];
    }
  inversenum(pkey,skey);
  /* we put the original modulo parameter back */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = oldmodulo.digit[i];
    }  
  } // end rsakeygen

We specify the number of bits on which we want to generate prime numbers ; the actual keys will hence be about twice that number of bits.  For instance, if we specify 80 bits, then we will get two random prime numbers of about 80 bits, and n, e and d will then be about 160 bits.  As such, we have to test that our number system can support twice the number of specified bits, otherwise our key generation will not be possible in that number system with that amount of bits.

We put the modulus of the number system to its maximum, and we generate a biggest number that has the specified amount of bits.  Generating a random number and taking the rest by this biggest number will give us a random number that needs less than that specified amount of bits.  From that random number onwards, we will now find the first prime number that is bigger.   Of course, it is possible that the search for a prime number gets us "over the maximum", and would need more bits ; so we have to test in the end whether the prime number we found, is still smaller than the maximum allowed ; if not, we have to find another one until we find one that is small enough.  This will give us the first prime number p of our key system.   Doing this again for the second prime number q, gives us finally the necessary pair of random prime numbers p and q (which are called p1 and p2 in the code).

We can now calculate n = p.q and Phi(n) = (p-1).(q-1).

Next, we have to find a public key e (which is called pkey in the code), which is relative prime to Phi(n).  We do this by finding a random number, and taking the rest of its division by Phi(n): that rest is of course smaller than Phi(n).  We test whether it is relative prime to Phi(n): if it isn't, we try another random number until we find one that is relative prime.

We now have to generate the private key, which is nothing else but the multiplicative inverse of e in the modular ring with modulus Phi(n).  In order for this to work, we have to set the global modulus to Phi(n), and then we simply have to invoke the multiplicative inverse function on e.  This gives us d (which is called skey in the code).

Of course, the "true" private key in the RSA system are the two primes p and q, together with the number e.  But we can actually forget about p and q once we have calculated n and d.  Once this generation is done, the public key is (e,n), and the private key is (d,n).  Note that once we've forgotten the true private key (p,q,e), we cannot restore the public key any more from the private key.  In fact, the pair (e,n) and the pair (d,n) are "symmetrical" in the sense that we can take (e,n) as the public key, and (d,n) as the private one (as intended), but we could just as well interchange this, and consider (d,n) the public key, and (e,n) the private one.  Once these pairs have been generated, we can actually forget p and q.

We would like to stress, again, that our implementation of the RSA key generation is cryptographically correct, except for the source of entropy.  Don't use the C-library random number generator to generate cryptographic keys.

The encryption and decryption

Although the RSA crypto system is an asymmetric cryptographic system and was in fact historically the first largely adopted one (it is the system that brought asymmetric cryptography to the world), its structure is entirely symmetric.  The only difference between "public" and "private" is the choice to call one key (e,n) the "public" key, and the other one of the pair, (d,n), the "private" one.  However, the algorithm to encrypt, or to decrypt, is identical.  It simply depends what key you feed it.  The message length that is encrypted is given by n, so it is essentially the key length.  There is some fluctuation in the message length, because of the random nature of the two prime numbers, and hence the random nature of n.  As the message has to be an element of the modular ring with modulus n, it has to "fit in".  For instance, if the two prime numbers p and q are "1024 bits", it essentially means that n will be not much smaller than 22048, but it will of course be smaller.  Taking a message of, say, 2000 bits will essentially always work (one has to have that n is bigger than 22000 which only doesn't happen in one out of 248 keys).

 
void rsacrypt(number* cleartext,number* pkey, number* n, number* cyphertext)
/* this procedure uses an existing public key to do RSA encryption */
/* it is also the procedure to decrypt: one puts the private key in, and the cypher text */
  {
  number oldmodulo;
  int i;

  /* we put the current modulus away and set the modulus to n */
  for (i = 0 ; i < nofdigits ; i++)
    {
    oldmodulo.digit[i] = modulo.digit[i];
    modulo.digit[i] = n->digit[i];
    }
  power(cleartext,pkey,cyphertext);
    /* we put the original modulo parameter back */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = oldmodulo.digit[i];
    }  
  }

The code speaks for itself: we put n as the modulus, and the act of encryption or decryption is simply the exponentiation.  The names of the variables in the code are for the "encryption" case, but it is sufficient to interchange "cleartext" and "cyphertext", and replace pkey by skey.

RSA digital signature

The symmetrical behaviour of encryption and decryption, and the interchangeability of the public and private key, render the RSA system particularly suited for digital signatures.  Indeed, in mode "encryption", the public key (e,n) is used to encrypt, and only the private key (d,n) can decrypt.  But we saw that the roles of (e,n) and (d,n) can be interchanged.  As such, something that is encrypted by (d,n) can be decrypted by (e,n).  Well, that's nothing else but the RSA digital signature: only the owner of the private key, (d,n) can encrypt (sign) a message, in such a way that it is decrypted by (e,n), which everybody can verify as (e,n) is public.  If the decryption by (e,n) succeeds, that means that it has been encrypted by (d,n), and hence, by the only holder of that private key.  As such, it is a signature by that entity.  The signature could not be produced with anything else but that private key.

Final comments

RSA has been the first well-known asymmetric cryptographic system, and it is still robust.  The only problem with the RSA system is that there are quite efficient techniques to look for prime factors, and one has to go to rather large keys.  1024 bits is a minimum (prime numbers of 512 bits), and actually if one needs good protection, it is advised to go to 2048 bits or higher.  As such, it is quite a computing-intensive system, and one often prefers now elliptic curve systems over RSA for matters of computational efficiency.

However, the RSA system is important in the following sense: it is conceptually extremely simple, and as demonstrated here, once the principles are understood, it is not difficult to implement it.   As such, it becomes essentially impossible for any legal system to "outlaw" efficiently secure cryptography.  One can re-write an RSA system "from scratch" in no time.  No conventions need to be implemented.  Two big numbers, (e and n), are all that is needed to communicate a public key.  No software needs to be distributed.  The code here on entrop-x is sufficient to communicate securely for instance.    The simplicity of the RSA system makes that asymmetric cryptography is now "out of the bottle" for ever.  Its security can be increased indefinitely by increasing the bit size.  This will of course increase a lot the computational burden, but, as its principles are extremely simple, just any computing device of sufficient power can do it.

However, as pointed out, the RSA crypto system is computationally intensive, and needs very large keys.   This is why other systems start having more success in practice.