Secure Key Exchange over an Insecure Medium with Public Key Cryptography - Implementing SSL/TLS Using Cryptography and PKI - page 120

and multiplication routines and call those from exponentiation routine. This
would actually negate the need for the division at each step of the exponentiation.
There are actually many additional speed-ups possible; real implementations,
of course, enable all of these. However, this code is performant enough.

Encrypting a Plaintext Message

So, now that you have a working RSA encrypt and decrypt algorithm, you're still
missing two important pieces of the puzzle. The fi rst is how keys are generated
and distributed. The topic of key distribution actually takes up all of Chapter 5.
The second topic is how to convert a plaintext message into a number m to be
passed into rsa_compute . Each rsa_compute operation returns a result mod n .
This means that you can't encrypt blocks larger than n without losing informa-
tion, so you need to chop the input up into blocks of length n or less. On the fl ip
side, if you want to encrypt a very small amount of data, or the non-aligned
end of a long block of data, you need to pad it to complicate brute-force attacks.
Just like the previous chapter's symmetric algorithms, RSA works on blocks
of data. Each block includes a header and some padding (of at least 11 bytes), so
the resulting input blocks are modulus_length -11

bytes minimum. The header is
pretty simple: It's a 0 byte, followed by a padding identifi er of 0, 1, or 2. I examine
the meaning of the different padding bytes later. For RSA encryption, always
use padding identifi er 2, which indicates that the following bytes, up to the fi rst
0 byte, are padding and should be discarded. Everything following the fi rst 0
byte, up to the length of the modulus n in bytes, is data.

NOTE Unlike the symmetric algorithms of the previous chapter, RSA pads at
the beginning of its block.

To implement this in code, follow these steps:

1. Defi ne an rsa_key type that holds the modulus and exponent of a key, as
shown in Listing 3-20. Notice that it doesn't matter whether it's a public
or a private key. Each includes a modulus and an exponent; the only dif-
ference is which exponent.

Listing 3-20: “rsa.h” rsa_key structure

typedef struct
{
huge *modulus;
huge *exponent;
}
rsa_key;

2. Defi ne an rsa_encrypt routine that takes in the data to be encrypted along
with the public key. Notice also that the output is a pointer to a pointer.