WARNING: The following post features mathematics performed either by professionals or under the supervision of professionals. Accordingly, CyberCrud and its producer must insist that no one attempt to answer or solve any equation or theorem proven in this post.
Most of us are probably somewhat familiar with public-key cryptosystems. In fact, it’s pretty hard not to brush shoulders with them once in a while these days. You probably use things like SSH, GnuPG, and OpenSSL all the time. The level of securiy these tools provide is incredible and it’s partly due to a clever system called RSA. It’s well into it’s third decade and still going strong.
Yet you can’t truly appreciate something like RSA until you actually understand just how your super secret messages are being shattered into unrecognizable pieces and then reconstructed perfectly once again. Fortunately, you don’t need a Ph.D in some obscure branch of ancient Egyptian algebra to understand it either; the mathematics involved aren’t too far-fetched. If you’ve ever taken a class in discrete mathematics, you’ll feel right at home here.
A Little History
Before getting into anything messy, it’s important to understand the basics of how congruence relations apply to cryptology. So let’s go back in time to around 50 BC and take a look at the Caesar cipher. Everyone into the TARDIS! <insert annoying whooshing sound>
As you can probably guess from the name, the Caesar cipher was popularized by Julius Caesar during the Gallic Wars. Caesar kept his messages secret by replacing each letter in the original message with the letter that is three positions further down in the alphabet. That is, the letter A becomes D, the letter B becomes E, C becomes F, and so on.
Expressed mathematically, each letter is first replaced by an integer between 0 and 25, determined by is position in the alphabet. A is replaced by 0, B is replaced by 1, C by 2, and so on until Z becomes 25. The encryption process can be represented using the function which assigns to a non-negative integer
, where
, the integer
in the set
with:
Consider the example of encrypting the message “THE CAKE IS A LIE”.
Begin by replacing each letter in the message with its corresponding position in the alphabet (beginning at 0). You get:
19 7 4 2 0 10 4 8 18 0 11 8 4
Replacing each of these numbers by
gives:
22 10 7 5 3 13 7 11 21 3 14 11 7
And finally, translating this back to letters produces the ciphertext: “WKH FDNH LV D OLH”.
Simple enough, right? Now to recover the original message, the inverse of , denoted
, is used. The function
sends an integer
from
to:
That is, to find the original message, each letter is shifted back by three letters in the alphabet.
However, the magnitude of the shift in the Caesar cipher does not necessarily have to be restricted to just three. The previous equations can be expressed more generally if we shift each letter by .
Though at this point, it’s more appropriate to refer to this cipher as a shift cipher instead.
It’s pretty obvious that Caesar’s method and shift ciphers in general only offer a laughable amount of security. Each letter changes its identity yet retains its position, making it vulnerable to cryptanalysis using simple frequency analysis.
Public-Key Cryptography
These methods are very basic examples of private-key cryptosystems (sometimes called symmetric-key algorithms). The same cryptographic keys are used for both encryption and decryption. To encrypt a message with our shift ciphers, we shifted right by and to decrypt it we shifted left by
. This is one of its greatest weaknesses since both parties are required to have access to a secret key but without means to securely exchange the key.
In walks the public-key cryptosystem to save the day. In such a system, knowing how to send someone an encrypted message will not help you decrypt other messages sent to that person. Each party has a publicly known encryption key while only the decryption keys are kept secret. That’s why the encryption key is sometimes referred to as the “public key” and the decryption key as the “private key.” Only the intended receiver of a given message can decrypt it since the encryption key simply does not allow someone to derive the decryption key (technically, it is sometimes possible but more on that later.) It basically says “You know what? Fine. You want this key so bad? Take the damn thing. See if I care. In fact, send me anything you like with it. But good luck trying to eavesdrop on anything else I might send.”
Introducing the RSA Cryptosystem
Perhaps the most widely used application of public-key cryptography is RSA which popped its head up during 1977 at MIT. It’s name comes from the researchers involved in its publication: Ron Rivest, Adi Shamir, and Leonard Adleman. I would’ve named it something cool like Really Super Algorithm, though. Their initial research is available here which I strongly suggest reading. (It’s also funny to see them use phrases back then like “the era of ‘electronic mail’ may soon be upon us.”)
What makes RSA so neat is that it doesn’t actually propose anything new. It’s unlike private-key systems whose strength lies in the complexity of some discrete algorithm continuously applied to a bit stream. All they did was utilize existing mathematics that have been sitting around for centuries.
As a public-key cryptosystem, RSA relies not on one key, as in our shift cipher example, but on two: a public key and a private key. The public key is made freely available, while the private key is kept a secret. Should you wish to communicate with someone, you simply send them your public key, allowing them to encrypt any messages sent to you so that only you can decipher them. Conversely, you will also need their public key in order to reply back.
Encryption Phase
So what exactly does an encryption key consist of? How is it that you can be so confident in giving away the key without fear of decryption by an adversary? That seems like magic.
It’s not magic. It’s math! RSA keys are based on modular exponentiation modulo the product of two large primes. That can be a scary phrase but, for now, know that the encryption key consists of two integers and
– expressed as
– where
is the exponent and
is the modulus used in the encryption function.
The modulus is simply the product of two large primes,
and
. Expressed
. These primes can be chosen at random using probabilistic primality tests. When you hear people talk about their 1024-bit keys or 2048-bit keys, they are actually referring to the bit length of
.
To compute the exponent , first we must find the number of positive integers less than
that are relatively prime to
. This is called Euler’s fotient function. For prime numbers
:
.
Because the totient function is multiplicative, in our case:
.
Then is chosen as a random value between the range
. That is,
and
.
Now that you’ve got an encryption key, the actual encryption phase can begin. Encryption begins by translating the message into a sequence of integers, just like we did with the Caesar cipher. The resulting integers are then grouped together to form even larger integers where each group represents a block of letters. The process continues by transforming the integer (the original message) into an integer
(the ciphertext) using the following function:
However, it’s impractical to first compute and then find it’s remainder when divided by
. Remember, we’re dealing with huge integers here. That’s why an algorithm for fast modular exponentiation is used instead. Unfortunately, a full discussion of modular exponentiation would make this post a lot longer than it needs to be. I won’t leave you hanging though. Just so that you’re able to actually perform some of these examples, see the following Ruby code for an implementation of the Right-to-Left Binary method.
# Computes b^e mod m using Right-to-Left Binary method. def mod_exp(b, e, m) x = 1 while e > 0 x = (x * b) % m if e.odd? e = e >> 1 b = (b * b) % m end return x end
Let’s try an example ourselves. Keep in mind that we’ll be using much smaller values for and
for practical reasons.
For my Portal fans out there, let’s use the same message “THE CAKE IS A LIE” when ,
, and
.
Note that and
are relatively prime. That is:
Begin by translating each letter into their respective two-digit integer representation and grouping them into blocks of four. However, unlike with the shift cipher, the alphabet begins at 1, not 0. This is because 0 is used to represent a space. Therefore, 00 = space, 01 = A, 02 = B, … 26 = Z. The result would be:
2008 0500 0301 1105 0009 1900 0100 1209 0500
Notice how the last block has been padded with 00. Then we apply the previous formula using the given variables.
All that’s left is to substitute for each block of integers. Using the method for modular exponentiation, we get:
Finally, we’re left with our encrypted message:
1230 2330 0129 2348 1864 1317 0197 1108 2330
Give it a shot yourself. Using the above mod_exp()
function, fire up Ruby and run:
p = 43; q = 59; e = 13; n = p * q [2008, 500, 301, 1105, 9, 1900, 100, 1209, 500].each {|m| printf "%04d ", mod_exp(m, e, n) }
Decryption Phase
To recover the original message, the decryption key is used. As with the encryption key, the decryption key also consists of two integers: the same modulus and the integer
, an inverse of
modulo
. Such an inverse exists since
and
are relatively prime. To demonstrate this, recall the theorem which states that the integers
and
are congruent modulo
if and only if there is an integer
such that
. This means that if
, then there is an integer
such that
. Therefore:
Assuming that (which holds true except in rare cases), we can use Fermat’s Little Theorem to show that
and
. Further simplifying:
and
Finally, because and
are relatively prime, that ol’ crazy Chinese Remainder Theorem lets us conclude that:
Let’s test it out and try decrypting our ciphertext. We know that and
. To find the decryption key
we need to find the inverse of
modulo
.
We use 937 as our decryption key, . To decrypt a ciphertext block
, we compute:
Then it’s just a process of using modular exponentiation like last time.
Doesn’t this look familiar?
2008 0500 0301 1105 0009 1900 0100 1209 0500
It’s our original message, “THE CAKE IS A LIE”. It’s numerical representation, anyway.
Security Implications
The security of the RSA cryptosystem is based on what’s called the RSA Problem; that is, the process of performing a private key operation (decryption) when given only a public key. Given the public key pair , this involves finding the e-th root modulo a composite
in order to recover a value
such that
.
This approach involves factoring the modulus in order to recover the prime factors
and
. An attacker could then compute
and then proceed to derive the private key exponent
. However, the problem isn’t so cut and dry. Remember that we’re dealing with very large integers. If
and
were each 500 digits, the
would be 1,000 digits. No polynomial-time method exists that can factor prime integers of this magnitude in a reasonable amount of time on a modern computer.
So that’s it? Big numbers? That’s it’s secret power? Hasn’t anybody considered that computers may be able to easily factor these numbers some day?
Yes. It is true that cracking RSA encryption is not impossible. It’s just infeasible. As of now, the largest factored key was 768-bits. But even that was on a huge state-of-the-art distributed system comprised of hundreds of machines and took almost two years. Those types of setups aren’t exactly common. Considering that the default key size used by ssh-keygen
is 2048, you can be safe in the knowledge that your precious SSH boxes will remain secure for more than a lifetime. Even the overly paranoid can use a 4096-bit key which most believe won’t be factored until D.B. Cooper is found.
Moving Forward
Hopefully, you now have a better understanding of how RSA is implemented. It’s a fascinating subject that really makes you appreciate the works of mathematicians of centuries old that made it all possible. Don’t stop there though. RSA is just one contender in the public-key boxing ring. The Diffie–Hellman algorithm is another method which came slightly before RSA. There’s also the ElGamal signature scheme. Dive in and enjoy!