# Exploring RSA Encryption in OpenSSL

When sending your credit card number through a public medium, such as the Internet, your financial credibility may be compromised if the number is not first encrypted. It is impossible to tell who may be listening in on your connection as you shop for new CDs or books. The RSA encryption method often is used to hide your credit card number from would-be thiefs on the Internet, because it uses a public key to hide your information and a private key to reveal it. This article banishes the mystery surrounding RSA encryption and explains how a realistic implementation of RSA works in the OpenSSL library. The only files you need to concern yourself with appear in the openssl/crypto/bn and openssl/crypto/rsa subdirectories. Feel free to download and take a look at the code to get a feel for it before continuing.

The best way to understand asymmetric encryption is to think of a box that has two kinds of keys: one key locks it and the other unlocks it. Anybody who has a copy of the locking key (aka public key) can put a secret in the box. Because only you have the unlocking key (aka private key), nobody else can reveal a secret that someone else locked in the box. This is different from symmetric key encryption, in which the same key is used for locking and unlocking.

Here is an example of encryption using the same key. First, we choose a number and call it the key. We want to encrypt a credit card number, so we subtract each number of the credit card from the key. For instance, take the number 1424 3135 2435 1556 and choose the number 12. We could encrypt it like so:

12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 -1 -4 -2 -4 -3 -1 -3 -5 -2 -4 -3 -5 -1 -5 -5 -6 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 11 8 10 8 9 11 9 7 10 8 9 7 11 7 7 6

The bottom list of numbers then would be the encrypted credit card number. To decrypt the credit card number, we need only to subtract each number from the key once again:

12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 11 8 10 8 9 11 9 7 10 8 9 7 11 7 7 6 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 1 4 2 4 3 1 3 5 2 4 3 5 1 5 5 6

Modern encryption algorithms such as AES and Triple DES are much more complicated--not to mention more secure--than this technique, but the example shows how the same key is used for both encryption and decryption. Before two parties can use this system, they both need to know the key 12. The algebra equations that symbolize this algorithm are:

C = K - M M = K - C

where M is the number to encrypt, K is the key (12 in the above example) and C is the encrypted cipher-text number. If two parties can agree on a key before beginning communications, then symmetric encryption is enough. This prearrangement, however, is not always feasible.

Say you log on to a bookstore for the first time and decide to buy something with a credit card. How do you know which key to use? Either you or the on-line bookstore has to choose the key (K), but it cannot be sent over the Internet because snoopers may see it. This is where RSA comes in handy. The equations for encrypting and decrypting are only a little more complicated than they are for the subtraction technique:

C = ME mod N M = CD mod N

If you are not used to seeing mod, it means to take the remainder if the number is divided by N. In the first equation, we raise M to the power E and divide the result by N, then store the remainder in C.

Again, M is the number to encrypt and C is the cipher- text number. There are two keys: E is for encryption, while D is for decryption. The best way to think of N is its the box in which the secret is hidden. As an example, say we wish to encrypt the number 6. We choose an encryption key of E=3, a decryption key of D=17 and a box of N=25. You want to send the message M=6 to the bookstore, so the encryption happens like this:

C = 63 mod 25 = 16

When you log in to the on-line bookstore, the seller sends you key E=3 and box N=25 so you can encrypt your credit card number. However, decryption is impossible without knowing that D=17:

M = 1617 mod 25 = 6

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 technique is so simple that encoding and decoding for 32-bit numbers can be implemented in a single line of C code. The real complications arise when you ask such questions as "How do I generate an RSA key pair?" or "How large do the numbers need to be for security?". The answers to these questions complicate RSA implementations a hundred times over. The rest of this article illustrates how these obstacles are tackled in the OpenSSL library. You can download the latest version from www.openssl.org. Click on the tab labeled Source to download the latest version (0.9.7b at the time of this writing).

## Trending Topics

## Webinar

### Practical Task Scheduling Deployment

July 20, 2016 12:00 pm CDT

One of the best things about the UNIX environment (aside from being stable and efficient) is the vast array of software tools available to help you do your job. Traditionally, a UNIX tool does only one thing, but does that one thing very well. For example, grep is very easy to use and can search vast amounts of data quickly. The find tool can find a particular file or files based on all kinds of criteria. It's pretty easy to string these tools together to build even more powerful tools, such as a tool that finds all of the .log files in the /home directory and searches each one for a particular entry. This erector-set mentality allows UNIX system administrators to seem to always have the right tool for the job.

Cron traditionally has been considered another such a tool for job scheduling, but is it enough? This webinar considers that very question. The first part builds on a previous Geek Guide, Beyond Cron, and briefly describes how to know when it might be time to consider upgrading your job scheduling infrastructure. The second part presents an actual planning and implementation framework.

Join *Linux Journal*'s Mike Diehl and Pat Cameron of Help Systems.

Free to *Linux Journal* readers.

SUSE LLC's SUSE Manager | Jul 21, 2016 |

My +1 Sword of Productivity | Jul 20, 2016 |

Non-Linux FOSS: Caffeine! | Jul 19, 2016 |

Murat Yener and Onur Dundar's Expert Android Studio (Wrox) | Jul 18, 2016 |

Rogue Wave Software's Zend Server | Jul 14, 2016 |

Webinar: Practical Task Scheduling Deployment | Jul 14, 2016 |

- SUSE LLC's SUSE Manager
- Google's SwiftShader Released
- Murat Yener and Onur Dundar's Expert Android Studio (Wrox)
- My +1 Sword of Productivity
- Managing Linux Using Puppet
- Non-Linux FOSS: Caffeine!
- SuperTuxKart 0.9.2 Released
- Parsing an RSS News Feed with a Bash Script
- Interview with Patrick Volkerding
- Doing for User Space What We Did for Kernel Space

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