If you are an advanced computer user you have probably used
ssh-keygen to generate an RSA key pair to access an online service. In this blog post we explain the principles behind the RSA encryption scheme, explaining
mathematics behind these keys and the assumptions that underpin it.
Before we get technical, note that there are more applications for RSA than just SSH authentication. For example, many websites use the RSA cryptosystem to prove to visitors that their content can be trusted (i.e. genuinely served by the company’s web servers as opposed to a dodgy man or woman in a van down the road or an meddling government).1 Moreover, modern browsers use the RSA cryptosystem to keep your credit card information secure when you shop online.
Background & terminology
To explain some of the mathematical properties of RSA keys we need to understand a number of mathematical concepts. If you are reasonably comfortable with mathematics you’re probably okay to skip this section.
Integer – With integers we mean whole numbers (e.g. , , , …). The integers in this blog post are all non-negative, unless stated otherwise.
Divides – We say an integer, , divides another integer, , if there is another integer, , such that . The important part here is that there is no remainder and , and are all whole numbers.
Greatest common divisor – For two integers, and , we say the greatest common divisor of and , denoted by , is the largest integer that divides both and .
Least common multiple – For two integers, and , we say the least common multiple of and , denoted by , is the smallest integer that is divisible by both and . By definition, both and divide .
Prime – We say an integer, , is a prime number when the only integers that divide are and itself.
Co-prime – We say two integers, and , are co-prime (also known as relatively prime) when . In other words, there is no integer greater than that divides both and .
Congruent – Finally, we say that two integers, and , are congruent modulo an integer , denoted by , if and only if there is a (possibly negative) integer, , such that . This implies the remainder of dividing by is equal to the remainder of dividing by .
Fermat’s little theorem – For any prime number, , and any integer not divisible by , the following congruence holds: . For this blog post we intend to just use this theorem as is, but you can find more information about it here.
Chinese remainder theorem – Let and be any integers and let and be two co-prime integers. If the congruences and both hold then the congruence holds also. Note that this theorem, as stated, is not really an accurate representation of the Chinese remainder theorem – it is more of a consequence. We point any unsatisfied readers to this article to find out more.
The mathematical properties of RSA integers
We start by looking at the integer fields contained within RSA key files and the mathematical properties that make them special. We list both the field names by which these numbers appear in RFC 3447 as well as commonly used mathematical symbols that are often used to represent them.2
|Field Name (RFC 3447)||Math Symbol||Description|
||A base for modular arithmetic.|
||A large prime number.|
||A large prime number.|
In this section, we are interested in the abstract mathematical properties of these integers.3 The integer values are different for every key pair but they always satisfy the following mathematical properties:
- The modulus, , is equal to .
- The public exponent, , is co-prime to .
- The private exponent, , is such that .4
These properties are met by construction. That is,
ssh-keygen makes sure these properties hold
for every RSA key pair that it generates. In this blog post we are not interested in how
ssh-keygen is able to achieve this –that is a whole other discussion– we are only
interested in what it means for us. To this end, we will derive further properties from the ones we have already.
To start with, using the definition of congruent (see here) we can expand property 3. The definition suggests that if then there must be an integer, , such that is equal to . This equality allows us to state the following property is guaranteed to hold for some integer :
We’ll need this equality for deriving our next property. The remaining properties are all quantified and hold for all integers, . The first one is this:
This property is non-trivial to demonstrate. First consider an such that divides . In this case, both the left-hand side and the right-hand side of the congruence are equivalent to meaning the congruence is trivially true. When does not divide things get more difficult. We will derive the congruence step-by-step:
If you are struggling to follow some of the steps – don’t worry. The main thing to remember is that holds. Property 5 can be restated to hold modulo to give us the next property:
The argument for property 6 is entirely symmetrical to that of property 5 as with substituted for – we won’t repeat it here.
Next comes the magical property we were really interested in. I’m going to call it the big cheese property, if you will, as it underpins the security of much of our current digital world:
This property uses the fact that both and are primes and hence are co-prime to each other. This, combined with the fact that both (property 5) and (property 6) we can apply the Chinese remainder theorem to get the ‘big cheese’ property:
That pretty much concludes the difficult part of this blog post. We will see why this property is so useful in the following section.
NOTE: As a small aside, you may have noticed we haven’t used property 2 in our derivations. As it turns out, property 2 is not useful in establishing the ‘big cheese’ property above but it is extremely relevant if you are in the business of generating RSA keys. As it turns out property 2 is a necessary and sufficient condition on public exponent that guarantees exactly one private exponent exists for which property 3 holds (see here).
How RSA is used in SSH authentication
It’s time to talk about the information contained the private key and public key.
Public key – The public key, , comprises the modulus, , and the public exponent, .
Private key – The private key, , comprises all the integer fields detailed above, i.e. the modulus, , the public exponent, , the private exponent, , and both prime numbers, and .
With SSH you install the public key, , on the SSH server. This tells the server to only allow access to the server to SSH clients with access to the matching private key, .
NOTE: As you can see, a private key is much like a physical key to your house. Really, anybody with access to your house key can get into your house. Similarly, an SSH server will let in anybody that can demonstrate they have access to the private key that matches the installed public key. In contast, a public key can be shared with others without compromising security.
To determine whether the client has access to the private key the SSH server will pose a the client a cryptographical challenge. This cryptographical challenge involves the encryption and decryption of an integer which we define next.
Encrypt and decrypt functions, and , are defined as follows:
Note that to implement the function you need access to the private exponent, , which is part of the private key, but not the public key. In contrast, anyone with access to either the private or public key can implement the function.
Cryptographical challenge – To determine whether an SSH client is allowed to access to the private key the SSH server poses the client with a challenge. If the client answers this challenge correctly, he is granted access and, conversely, is denied access if it’s wrong. The challenge is as follows:
“Using public key I have calculated the value of for some integer that I am not willing to share. The value of was . To demonstrate you have access to the private key that matches please tell me: what was ?”
For someone with access to the private key it is easy to answer this challenge. Simply compute and use the result as the answer. To see why this works please follow the derivation below:
It is clear from the result above that someone with access to the private key can easily answer the challenge and hence successfully authenticate with the SSH server.
However, what I think is really fascinating is this: even though the RSA cryptosystem has been around since 1976 and underpins much of the security of our digital infrastructure the jury is still out on whether someone without access to the private key and with malicious intent is able to do the same.
To the best of our knowledge nobody to date has demonstrated that it is either practical or intractible to answer the crypographical challenge without access to the private key.5
Why intractibility of integer factorisation is important
As explained in painstaking detail above, the RSA cryptosystem relies on the intractibility of figuring out the private exponent, , from the public key . As suggested, whether or not this is tractible or intractible is not known at this time. However, what we can show you is that if the integer factorisation of into it’s prime factors, and , was known to be tractible, then so is finding .
The easiest way of demonstrating by assuming we have got such a prime factorisation algorithm and all that remains is to calculate te private exponent, , given the public exponent, , the modulus, , and the modulus’ prime factors, and . We will make some code available below that does just that.
As it turns out, it really isn’t that hard. Computing a multiplicative inverse –which is what is to – can be done with the extended Euclid’s algorithm for calculating greatest common multiples. The extension also returns Bézout’s identity which, as it happens, is exactly what we need:
To confirm this works we’ve taken , , and from a previous blog post to try and see if the code computes the private exponent, , in a reasonable amount of time:
On my PC this code returns in about 13ms with the following value:
As you can confirm yourself, this is indeed the matching private exponent from the previous blog post. As a result we can conclude that the intractibility of calculating ’s prime factors indeed underpins the RSA cryptosystem’s security.
NOTE: Note that the implication only goes one way. It may well be possible to obtain the private component, , even if the integer factorisation of the modulus, , is found to be intractible. That is, there may be other ways of breaking RSA.
You can check this yourself. For example, if you head to, e.g., google.com and click on the little padlock symbol next to the address bar you can inspect the details of Google’s SSL certificate and confirm it was signed using the very same maths described in this blog post. ↩
It’s worth noting that the private key file has additional fields we are not discussing here, notably
coefficient. These fields exist to help make decryption computationally more efficient but have little bearing on what we are discussing in this post. ↩
For the types of keys commonly used in practiced and with reasonable resources. ↩