Exploring RSA Encryption in OpenSSL

Using OpenSSL to explore some of the details of how RSA encryption works.
RSA Key Generation

Generating the numbers N, E and D requires the generation of primes and relative primes. To generate N, you need to find two large primes and multiply them together. We can define N as a math equation:

      N = P * Q

where P and Q are both random, prime numbers. The encryption key E and decryption key D both must be relative prime to (P-1)*(Q-1). This means they must satisfy the equation:

      (E * D) mod (P-1)*(Q-1) = 1

If two numbers are relative primes, it means their prime factorizations share nothing in common. For instance, 9 and 40 are relative primes to each other because they have no common factors:

          9 = 3 * 3
          40 = 2 * 2 * 2 * 5

Generating a random prime number for an RSA key is nothing more than a guess-and-check process. The files openssl/bn/bn_prime.* implement a quick sieve testing approach to choosing primes. The quick sieve approach asks the question "Is this number prime?" but only receives the answers:

  • No

  • Maybe

OpenSSL generates random numbers and then runs a test-prime function multiple times to weed out any false positives. If the test fails, the random number is discarded and the process begins anew. There are no guarantees that the generated number really is prime, but math gurus have shown that a number can be shown prime with 99.9% probability by using this test.

The encryption key E usually is chosen to be a constant, prime number for a protocol (such as SSL). Therefore, only the number N needs to be sent across the Internet. Common choices are the numbers 3 or 65537. Finding the decryption key D is a little more difficult because you need to find the modulo inverse. This involves calculating the greatest common divisor by using Euclid's algorithm as detailed in Knuth's book (see Resources). If you look in the file openssl/crypto/rsa/rsa_gen.c, you can get an idea of how it works in OpenSSL.

Basic Math for Big Numbers

A secure RSA implementation requires rather large numbers. Most secure protocol standards recommend key sizes of 1,024-bit numbers, which 32-bit processors, such as the Pentium III or PowerPC, cannot handle natively. To get around this barrier, OpenSSL implements a new data type called a BIGNUM. The BIGNUM data struct is implemented in file openssl/crypto/bn/bn.h and is defined in Listing 1.

Listing 1. BIGNUM Data Struct

The generic computer can handle 1,024-bit numbers only if they are stored as arrays of smaller 32-bit numbers. The variable d in the BIGNUM structure stores a pointer to a dynamically allocated array. The length of the array is stored in dmax so that routines for handling BIGNUM variables can avoid buffer overrun errors.

Basic arithmetic on BIGNUMs is as simple as elementary math class, but with an added twist. Let us look at simple addition of two numbers:

          1 1    <== carry
          1 4 7
        + 2 6 3
        -------
          4 1 0

Humans break addition of multidigit numbers into smaller pieces by adding together single digits at a time, from right to left. Computers can add large numbers in the same manner. If we separate each digit into a separate array element, we can implement elementary addition like this:

#define BASE 10
void add(int *a, int *b, int *c, int top) {
  int i, carry;
  for (i=carry=0; i < top; i++) {
    c[i] = a[i] + b[i] + carry;
    if (c[i] >= BASE) {
      carry = 1;
      c[i] -= BASE;
    } else {
      carry = 0;
    }
  }
}

The variable top represents the number of digits to add. By using this technique to break up numbers, we can define a number that is thousands of digits in size if we so desired. It is not memory efficient to define BASE as ten, so why not use base sixteen or even base four billion? The answer is we can use any base that we like up to the maximum value of a 32-bit integer:

void add(unsigned int *a, unsigned int *b,
         unsigned int *c, int top) {
  int i, carry;
  for (i=carry=0; i < top; i++) {
    c[i] = a[i] + b[i] + carry;
    /* is there an overflow? */
    if ((c[i] < a[i]) || (c[i] < b[i])) {
      carry = 1; /* yes overflow, so carry */
    } else {
      carry = 0; /* no overflow, no carry */
    }
  }
}

Because the largest number that a 32-bit integer can store is 232-1, anything larger wraps around with an overflow error. We can use this "error" to our advantage, because it has the same effect as subtracting the base. This is the principle that OpenSSL uses to implement arithmetic on the BIGNUM structure.

If you look in openssl/crypto/bn/bn_add.c and in openssl/crypto/bn/bn_asm.c, you can find hyper-optimized addition and subtraction functions. These functions use fancy pointer techniques to reference array elements in the BIGNUM variables, but the principles are the same. Some other details they keep track of include:

  • negative numbers, necessary with subtraction

  • different values for the top variable

  • buffer overrun errors

  • microprocessor independence

All the error checks and minor optimizations that address these issues may make BN_add() and BN_sub() daunting at first, but they simply are fancy C code wrappers for the old tried and true method.

Multiplication also generalizes quite well with the BIGNUM data structure. When a 32-bit unsigned integer is used to represent a single digit, we can use the classic elementary school algorithm. For example:

             2 4 3
           * 4 1 5
           -------
           1 2 1 5     <== 243 * 5
           2 4 3       <== 243 * 1
         9 7 2         <== 243 * 4
       -----------
       1 0 0 8 4 5

If we allow for 232 total digits instead of the usual ten, we can implement multiplication in terms of the addition function discussed previously.

void mul(unsigned int *a, unsigned int *b,
         unsigned int *c, int top) {
  unsigned long long prod; /* 64-bit num in GNU C */
  unsigned int i,j, hi32, lo32, carry;
  unsigned int acc[top]; /* array of size top */
  /* initialize c[] to all zeros */
  for (j=0; j < top; j++) {
    /* initialize acc[] to all zeros */
    for (i=carry=0; i < top; i++) {
      prod = a[i] * b[j];
      lo32 = prod & 0x00000000FFFFFFFFULL;
      hi32 = prod & 0xFFFFFFFFr0000000ULL;
      acc[i] = lo32+carry;
      carry = hi32;
    }
    add(acc,c+i,c+i,top);
  }
}

Notice that we need 64 bits when multiplying two 32-bit numbers. To handle a 64-bit quantity properly, we need to split it into two 32-bit quantities. The number a is multiplied by a digit in b, and the result is added to the total. To optimize multiplication, OpenSSL uses a trick called Karatsuba's recursive algorithm. It reduces the time complexity from O(n2) to O(n1.5) by using a divide-and-conquer approach.

Division is a beast similar to multiplication, but one that requires a little extra thought. Whereas converting addition to subtraction simply requires a sign change, division has to account for the remainder, or modulo. Although OpenSSL implements division in openssl/crypto/bn/bn_div.c, it is not needed directly in RSA because RSA uses Montgomery multiplication instead (more to come).

OpenSSL implements exponentiation based on a multiplication-modulo algorithm. Directly raising a 1,024-bit number to a 1,024-bit number power requires about 10300 Gigabytes of memory. So, how does the computer compute the RSA operation ME mod N? The trick lies in distributing the mod operation within the multiplications. For example:

                 436 mod 13 =
       (432 mod 13) * (44 mod 13)

By distributing the mod operation, it is unnecessary to ever store more than 1,024 extra bits on an intermediate operation.

Another subtlety to exponentiation makes it possible to compute the operation in a short amount of time. Let us take a look at openssl/crypto/bn/bn_exp.c:

for (i=1; i<bits; i++)
        {
        if (!BN_sqr(v,v,ctx)) goto err;
        if (BN_is_bit_set(p,i))
                {
                if (!BN_mul(rr,rr,v,ctx)) goto err;
                }
        }

This function computes vp and then stores the result in rr. Because a number is represented in binary, it is possible to represent an exponentiation as a product of powers of two. Take a look at this breakdown:

        432 = 416 * 416 <==
        416 = 48 * 48
        48 = 44 * 44
        44 = 42 * 42    <==
        436 = 432 * 44

If we examine the excerpt from BN_exp() above, we see that v is squared at every step. Then, if a bit is set in p, it is multiplied into the total. The number 36 is 00100010 in binary, so exponentiation is nothing more than a shift-test- multiply operation.

To exponentiate BIGNUM variables, each step requires a multiplication operation and a modulo operation. Rather than go through the basic algorithms, it is possible to combine the multiplication and modulo into a single step called modular multiplication (aka Montgomery multiplication). OpenSSL uses this method to accelerate the modular exponentiation of a BIGNUM variable. The file openssl/crypto/bn/bn_mont.c has an implementation that requires some time to comprehend fully. If you have further interest, reviews this paper.

Converting a text string to a BIGNUM variable and back is the last piece necessary to implement the RSA_public_encrypt() and RSA_private_decrypt() functions. Both are defined in openssl/crypto/rsa/rsa_lib.c. If you are interested to see how to include RSA in your own programs, take a look at openssl/crypto/rsa/rsa_test.c. This example illustrates how to do everything with the OpenSSL RSA package you may ever need.

______________________

Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Re: Exploring RSA Encryption in OpenSSL

Anonymous's picture

A little confused at an equation like C = 63 mod 25 = 16. I tried every key with N=25 and M=6, and got it to work. But, when M= any other number, trying to decrypt it fails. Should N be changed?

Re: Exploring RSA Encryption in OpenSSL

Anonymous's picture

M has to be the same as M in the first equation, here, check this out

C = M^E mod N
M = C^D mod N

in the second equation, M is equal to whatever M is in the first equation, so if it is 6, then it would look like this

C = 6^E mod N
6 = C^D mod N

Some Exceptions...

Anonymous's picture

This algo fails for M = 3,5,7 etc.....considering E=3 and N=25 and D=17. Please guide what to do..

Re: Exploring RSA Encryption in OpenSSL

Anonymous's picture

Very good article. I am doing a course in Cryptography and I wanted to have a real-world example of what's been taught. I can very easily understand this and also the other comments.

thanks guys.

Re: A better reference

Anonymous's picture

Practical Cryptography by Schneier and Ferguson is a better
book to read than Applied Cryptography for an accessible
explaination of RSA encryption. If you naively employ
RSA you probably aren't going to get it right. Practical
Cryptography explains about a lot of the things you need
to worry about when using RSA.

Re: Exploring RSA Encryption in OpenSSL

Anonymous's picture

Okay, this was a pretty good explanation as to how RSA works and how to code for it, but it oversimplifies a couple of real-world things.

1. First off, asymmetric systems like RSA are rarely used to pass "user data" like a credit card number. Rather, RSA is used to exchange symmetric keys for algorithms such as DES or AES, since symmetric algorithms are significantly faster to compute.

2. There are several sins of omission in the example of exchanging public keys: "Because nobody else knows that D=17, it is impossible for anybody except the bookstore to decrypt messages. Hence, you can contact anybody on the Internet and feel safe that your sensitive info is secure from theft."

This example completely ignores the man-in-the-middle attack that exists if an adversary is able to substitute HIS public key for one or the other party (Alice or Bob). This is why SSH asks you to kindly verify the public key of the other side before accepting it (which most people do blindly, anyway).

Webinar
One Click, Universal Protection: Implementing Centralized Security Policies on Linux Systems

As Linux continues to play an ever increasing role in corporate data centers and institutions, ensuring the integrity and protection of these systems must be a priority. With 60% of the world's websites and an increasing share of organization's mission-critical workloads running on Linux, failing to stop malware and other advanced threats on Linux can increasingly impact an organization's reputation and bottom line.

Learn More

Sponsored by Bit9

Webinar
Linux Backup and Recovery Webinar

Most companies incorporate backup procedures for critical data, which can be restored quickly if a loss occurs. However, fewer companies are prepared for catastrophic system failures, in which they lose all data, the entire operating system, applications, settings, patches and more, reducing their system(s) to “bare metal.” After all, before data can be restored to a system, there must be a system to restore it to.

In this one hour webinar, learn how to enhance your existing backup strategies for better disaster recovery preparedness using Storix System Backup Administrator (SBAdmin), a highly flexible bare-metal recovery solution for UNIX and Linux systems.

Learn More

Sponsored by Storix