# Exploring RSA Encryption in OpenSSL

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.

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.

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.

Tools and Technologies for Scale and Reliability

by Linux Journal Editor Bill Childers

Sponsored by IBM

Scheduling Crontabs With an Enterprise Scheduler

On Demand

Moderated by *Linux Journal* Contributor Mike Diehl

Sponsored by Skybot

## Trending Topics

When Official Debian Support Ends, Who Will Save You? | May 01, 2015 |

May 2015 Issue of Linux Journal: Cool Projects | May 01, 2015 |

May 2015 Video Preview | May 01, 2015 |

Ubuntu Ditches Upstart | Apr 30, 2015 |

Video On Demand: 8 Signs You're Beyond Cron | Apr 29, 2015 |

Picking Out the Nouns | Apr 27, 2015 |

- When Official Debian Support Ends, Who Will Save You?
- Ubuntu Ditches Upstart
- Video On Demand: 8 Signs You're Beyond Cron
- May 2015 Issue of Linux Journal: Cool Projects
- Picking Out the Nouns
- "No Reboot" Kernel Patching - And Why You Should Care
- DevOps: Better Than the Sum of Its Parts
- Return of the Mac
- JavaScript All the Way Down
- Drupageddon: SQL Injection, Database Abstraction and Hundreds of Thousands of Web Sites

## Comments

## Re: Exploring RSA Encryption in OpenSSL

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

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...

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

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

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

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).