GnuPG 1.4 RSA: Where's the Padding?

Question

In an effort to better understand RSA I've been fooling around with the source code for GunPG 1.4, specifically the RSA implementation in the rsa.c file. As the title says, I can't figure out where the padding is happening.

So typically in RSA, padding is done right before the encryption and is taken off during the decryption. Encryption first starts around line 409 where we see

int 
rsa_encrypt( int algo, MPI *resarr, MPI data, MPI *pkey )
{
RSA_public_key pk;

if( algo != 1 && algo != 2 )
return G10ERR_PUBKEY_ALGO;

pk.n = pkey[0];
pk.e = pkey[1];
resarr[0] = mpi_alloc( mpi_get_nlimbs( pk.n ) );
public( resarr[0], data, &pk );
return 0;
}

That seems easy, it's giving data to "public" function higher up on line 220. Public is responsible for calculating the important (c = m^e mod n) process. That all looks like:

static void
public(MPI output, MPI input, RSA_public_key *pkey )
{
    if( output == input ) { /* powm doesn't like output and input the same */
    MPI x = mpi_alloc( mpi_get_nlimbs(input)*2 );
    mpi_powm( x, input, pkey->e, pkey->n );
    mpi_set(output, x);
    mpi_free(x);
}
else
mpi_powm( output, input, pkey->e, pkey->n );
}

Wait a second...now it looks like public is passing the job of that calculation off to mpi_powm() located in the mpi-pow.c file. I'll spare you the details but that function gets really long.

Somewhere in all of this some sort of PKCS#1 padding and unpadding (or something similar) is happening but I can't figure out where for the life of me. Can anyone help me see where the padding happens?

Answer 1

In an effort to better understand RSA I've been fooling around with the source code for GnuPG 1.4, specifically the RSA implementation in the rsa.c file.

Since you’re looking at the older (< 2.0) stuff anyway, and since it’s only for learning purposes, I would rather advise you to check out “ye olde rsaref.c from gnupg.org” where the padding is implemented in a pretty obvious way.

… some sort of PKCS#1…

To be exact, GnuPG uses PKCS #1 v1.5 (specified in RFC 4880).

Can anyone help me see where the padding happens?

Hmmm, let’s see if I can wrap that up somewhat logically. GnuGP pads according to PKCS #1 v1.5, so it just adds random pad to satisfy length requirements.

If you take a look at the cipher/pubkey.c file (which includes the rsa.h file in its head), you’ll notice a pubkey_table_s struct which defines a list of elements that define the key. For padding reasons, random bytes are appended to that list (better: after that struct). It’s done that way because those random bytes can easily be stripped by looking for the end of the list. Keeping a long story short, that’s where random.c probably starts to make a bit more sense to you. Now, all that stuff (and a whole lot more) is compiled into a lib called libcipher… which in itself is compiled to be used by functions that add the padding and handle the RSA stuff the way you expected it. In the end, the compiled executables use the functions libcipher provides to take care of the padding – depending on the individual need for padding.

So what you currently expect to find in 1 or 2, maybe 3 files is actually spread out across more than half a dozen files… which I regard not to be the best base for your learning efforts. As said, for reference purposes, I’ld go for the old rsaref.c they once started out with.

Not sure if this actually provides all the details you wanted to get, but it should give you a first good heads-up… hope it helps.

Answer 2

GPG 1.4 doesn't use any padding at all. It encrypts the raw session key.