Programming .NET Security : Asymmetric Encryption Explained (part 2) - Creating the Encrypted Data

2. Asymmetric Algorithm Security

Asymmetric algorithms use much longer keys than symmetric algorithms. In our examples, we selected small values to demonstrate the key generation protocol, but the numeric values used in practice contain many hundreds of digits.

Measure asymmetric key lengths in bits. The way to determine the number of bits differs between algorithms. The RSA algorithm specifies that the key length is the smallest number of bits needed to represent the value of the key modulus, n, using binary. Round up the number of bits to a factor of eight so that you can express the key using bytes; for example, consider a modulus represented by 509 bits to be a 512-bit key. Common lengths for keys are 512 and 1024-bits, but a 1024-bit asymmetric key does not provide 16 times more resistance to attack than a 64-bit symmetric key. Table 1 lists the equivalent asymmetric and symmetric key lengths accepted as providing equivalent resistance to brute force attacks (where Eve obtains the value of the private/secret key by testing all of the possible key values).

Most asymmetric algorithms rely on some form mathematical task that is difficult or time-consuming to perform. Cryptographers consider the RSA algorithm secure because it is hard to find the factors of a large number; given our example value for n (713), it would take some time to establish that the factors are the values you selected for p (23) and q (31). The longer the value of n, the longer it takes to determine the factors; bear in mind that the example value of n has only five digits, whereas the numbers that you would use for a secure key pair will be significantly longer.

Table 1. Asymmetric and symmetric key lengths providing equivalent resistance to brute force attacks

Symmetric key length	Asymmetric key length
64 bits	512 bits
80 bits	768 bits
112 bits	1792 bits
128 bits	2304 bits

Therefore, the essence of security for RSA is that given only the public key e and n, it takes a lot of computation to discover the private key d. Once you know the factors p and q, it is relatively easy to calculate d and decrypt ciphertext. Bob makes it difficult for Eve to decrypt his messages by keeping secret the values of d, pq. and

The main risk with asymmetric algorithms is that someone may discover a technique to solve the mathematical problems quickly, undermining the security of the algorithm. New techniques to factor large numbers might make it a simple process to decrypt messages or to deduce the value of the private key from the public key, and this would render the RSA algorithm (and any others that rely on the same mathematical problem) insecure.

3. Creating the Encrypted Data

We have already explained how the encryption and decryption functions are at the heart of an asymmetric algorithm. The protocol for encrypting data using an asymmetric algorithm is as follows:

1. Break the plaintext into small blocks of data.

2. Encrypt each small plaintext block by using the public key and the encryption function.

3. Concatenate the encrypted blocks to form the ciphertext.

The length of the public key determines the size of the block to which we break the plaintext. Each algorithm specifies a rule for working out how many bytes of data should be in each block, and for the RSA protocol, we subtract 1 from the key length (in bits) and divide the result by 8. The integral part of the result (the part of the number to the left of the decimal point) tells you how many bytes of data should be in each block of plaintext passed that is to the encryption function. You can work out how many bytes should be in a plaintext block for a 1024-bit key, as follows:

The integral value of the result is 127, meaning that when using the RSA algorithm with a 1024-bit public key we should break the plaintext into blocks of 127 bytes. The small key that you generated to demonstrate the key generation protocol is 16 bits long (713 is 1011001001 in binary and the bit length is therefore rounded up to be 16 bits) and with a 16-bit key, we must use 1-byte blocks (the integral part of (10 - 1)/8 = 1.875 is 1).

Encrypt each data block by interpreting it as an integer value and compute a ciphertext block using the RSA encryption function shown below (m is the integer value of the plaintext block and c is the ciphertext block):

c = m^e mod n

Figure 4 demonstrates how this process works for a 24-bit key, meaning that you process 2 bytes of plaintext at a time; the figure shows how the encryption function is applied to encrypt the string ".NET" into the ciphertext "35 7B AE 05 F1 6F."

Figure 4. Using the RSA encryption function to encrypt the string .NET using a 24-bit public key

For reference, we created our 24-bit key using 1901 for p and 1999 for q. We chose e to be 19, giving a secret key value, d, of 2805887. Notice that the output of the cipher function is the same length as the key modulus, making the ciphertext larger than the plaintext.

Decrypting data is the reverse of the encryption protocol:

1. Break the ciphertext into small blocks of data that are the same length as the public key modulus.

2. Decrypt each small ciphertext block by using the private key and the decryption function.

3. Concatenate the decrypted blocks to form the restored plaintext.

The decryption function is as follows (c is the value of the ciphertext block and m is the plaintext block):

m = c^d mod n

Notice that the decryption function uses the secret key (d) and the modulus from the public key (n). Figure 5 demonstrates how this process works for our 24-bit key, meaning that we process 3 bytes of ciphertext at a time; the figure shows how we decrypt the ciphertext that we created in Figure 4.

Figure 5. Using the RSA decryption function

3.1. Asymmetric data padding

Asymmetric encryption algorithms rely on padding to protect against specific kinds of attack, in much the same way that symmetric algorithms rely on cipher feedback. Padding schemes also ensure that the encryption function does not have to process partial blocks of data.

Asymmetric padding schemes are a series of instructions that specify how to prepare data before encryption, and usually mix the plaintext with other data to create a ciphertext that is much larger than the original message. The .NET Framework supports two padding schemes for the RSA algorithm: Optimal Asymmetric Encryption Padding (OAEP) and PKCS #1 v1.5. OAEP is a newer scheme that provides protection from attacks to which the PKCS #1 v1.5 scheme is susceptible. You should always use OAEP, unless you need to exchange encrypted data with a legacy application that expects PKCS #1 v1.5 padding.

We do not discuss the details of either padding scheme in this book; it is important only that you understand that padding is used in conjunction with the asymmetric algorithm to further protect confidential data.