SSH is a great tool but it can also be pretty complex. Therefore it is often misunderstood, misused or underutilized. In this short series of two articles we’ll go into what SSH is, how exactly it works and how we can use it most effectively and securely, avoiding common pitfalls. Warning, there will be math, but based on simple concepts from school and really useful later on.
Many developers use SSH daily, for tasks like remote administration, deployment, tunneling, firewalls. An essential part of all these are SSH keys, which allow passwordless logins. But for most of us, these are opaque binary blobs of cryptographic material, which we’re told to store securely and don’t hand out left and right. Let’s look inside, to see what are they made of.
Generating a key
Most commonly done by invoking sshkeygen t rsa
, and often the only thing we use this program for. It can do much more, in fact it is a rich tool for key file management, something outside of the scope of this article. Let’s look at how the key, in the algorithmic sense only, is constructed:
 Choose two^{1} large primes: \(p, q \in \mathbb{P}\).

Calculate modulus \(n = p \cdot q\).
Its length (position of leftmost 1 bit) is commonly referred to as key size. If we want to generate a modulus of 2048 bits, then both primes should be 1024 bits long, or about 300 decimal digits.

Calculate totient: \(\phi(n) = (p  1)(q  1)\).
Euler’s totient \(\phi(n)\) is the count of numbers less than or equal to $n$, which have no common divisors with it: \(gcd(a, n) = 1\).
By definition then, for a prime \(p\) it is equal to \(p1\). For a prime power \(\phi(p^k) = p^{k1}(p1)\), because there are exactly \((k1)\) multiples of \(p\) that are less then \(p^k\), and these do have a common divisor with it (which is \(p\)). And finally, totient is a multiplicative function \(\phi(m\cdot n) = \phi(m) \cdot \phi(n)\) when its arguments are prime, giving us the formula above.
In actual RSA implementations, Carmichael’s totient is used instead: \(\lambda(p \cdot q) = {\rm lcm}(\lambda(p), \lambda(q)) = {\rm lcm}(p  1, q  1)\) when both are prime. Both totients can be used, but Carmichael’s has additional useful properties, which we’ll discuss further on. \({\rm lcm}(p, q)\) is the least common multiple of given two numbers. \(\lambda(n)\) always divides \(\phi(n)\).

Pick a public exponent \(\mathbf{e} = 65537\)
Any number that is coprime to \(\lambda(n)\) can be used, and if it happens that 65537 is not coprime, then another one must be chosen. The smallest number that could be used here is 3.
It is more efficient to choose numbers with small Hamming weights (number of ones in their binary representation), as the fast exponentiation methods used in encryption benefit from that. This is why 65537 is commonly chosen, as it’s equal to \(2^{16}+1\), so has two one bits set.

Find its multiplicative inverse: a number \(\mathbf{d}\) such that \(e \cdot d = 1 \bmod \phi(n)\)
For example, if our primes were \(p = 11, q = 13\), and we used Euler’s totient, then \(n=143\) and \(\phi(n)=10 \cdot 12 = 120\). We cannot use \(e=3\), as \(3 \vert 120\), and the next smallest number we can use is \(e=7\). Then its inverse is \(103\), because \(7 \cdot 103 = 721 = 7 \cdot 120 + 1 \equiv 1 \bmod 120\).
Under Carmichael’s totient, we have \(\lambda(n) = {\rm lcm}(\lambda(10), \lambda(12)) = \ldots = 60\), which does divide \(\phi(n)\) as expected. Then for \(e=7\) again, the inverse (modulo \(\lambda(n)\)) is \(43\). Note that \(103\) is also an inverse, and is congruent to the other inverse modulo \(\lambda(n)\) which is not an accident. Carmichael’s totient tends to produce smaller exponents, which improves encryption performance.
This is the private exponent.
As you can see, the numbers are chosen very deliberately. This is so that the pair of \(e\) and \(d\) have an important property: that for any \(m\),
\((m^e)^d \bmod n = m \bmod n\).
That equation is the core of RSA encryption. Doctrina offers a very readable proof of why that works.
By the way, if you ever need a long prime number, openssl
can generate one for you:
openssl prime generate bits 1024
Distributing keys
 Pack together \((e, n)\) and ship it freely, this is your public key.
 Keep \((d, n)\) secret, this is your private key.
For performance, other derived values are often stored with the private key. Performant implementations don’t use simple module exponentiation, but rather an optimized method based on the Chinese Remainder Theorem, which uses some values computed from \(p, q\) and \(d\).
Exposing the public key does not harm your security: an attacker that knows your \((e, n)\) pair would have to spend lots of computing resources to factorize \(n\) into \(p \cdot q\) to find the totient, and then your decryption key. By keeping \(n\) large (thousands of bits in length), the scheme can be tuned to resist newer and faster computers, simply by making it impractically expensive to compute. On the other hand, the encryption and decryption operations are comparatively very cheap!
And all that is inside key files?
Let’s generate one and look inside, again with openssl tools that you most likely already have. However, we need to choose a key format they can read, and the default SSH2 internal format isn’t one. Let’s use PEM:
And look inside the private key:
Look at the public exponent  it is 65537, as described. prime1
and prime2
are \(p\) and \(q\) respectively, and the other three entries are precomputed values for the Chinese Remainder Theorem exponentiation algorithm.
Another look at this file can be obtained with asn1parse
. ASN.1 is the data stream format these are stored in, then base64encoded and wrapped in terminator markers as specified by PEM.
Note that field numbers are not shown, as they are not encoded in this form, but only specified by the format (PKCS#1 RSA Private Key)). Choosing one of the other two formats produces a SSHstyle private key file, because both RFC4716 and PKCS#8 specify a public key format. But asn1parse
complains:
This key is not ASN.1 encoded. But it still resembles one, because it uses both base64 and PEM delimiter lines. Let’s strip them and look inside:
grep v
returns lines that don’t match the pattern, and since the pattern starts with dashes like an option, we needed to terminate option parsing with 
before it. The rest is fairly obvious. The format contains:
 a nullterminated format id prefix
opensshkeyv1
 at
0F
, a 32 bit length int, and at13
content for the cipher name,none
 length and content for KDF^{2} name, offsets
17
and1B
, againnone
 length for KDF data, which is zero, followed by zero bytes of KDF data at
1F
 32 bit number of keys at
23
, fixed to one key per file, so1
 at
27
a 32 bit length of the public part:00000197
, which is 407 decimal  the public key:
 length and bytes of key type,
sshrsa
at2b
and2f
 length and bytes of public exponent at
36
and3a
. Unsurprisingly, the exponent bytes are010001
, which is exactly 65537.  length and bytes of the modulus, starting at
3d
. The modulus is 385 (hex0181
) bytes long, and starts with00a975
. This is not the same modulus as in previous examples, as the key was generated anew.
 length and bytes of key type,
 following, but not visible in this truncated example, is the actual private key
The public key structure is modeled after RFC4253, and the private part uses a similar scheme, with some padding added.
Prying the lid open
Let’s write a short program to read everything. We’ll use the excellent bindata gem for brevity.
Run this with:
$ grep v  '' example_key  base64 d  ruby parsekey.rb
AJ O’Neal did some sleuthing on this topic, and offers some insight as well as links to relevant sourcecode in Portable SSH (which is not OpenSSH, but is very compatible).
Twoinone
So the private key file actually contains both the public and private keys, with modulus and public exponent stored twice. Even if you lose your public key file, it is easy to regenerate it from that private key:
And the public key
OpenSSH accepts three public key formats: PKCS#8, RFC4716 and its internal oneliner. Starting with the last one:
$ sshkeygen y f example_key
sshrsa AAAAB3NzaC1yc2EAAAADAQABAAABgQCpd[...] user@host
The last field is a comment, the first is obviously key type, but what’s the middle part? Looks like Base64 again.
$ sshkeygen y f example_key  cut d' ' f2  base64 d  hexdump C
00000000 00 00 00 07 73 73 68 2d 72 73 61 00 00 00 03 01 ....sshrsa.....
00000010 00 01 00 00 01 81 00 a9 75 c5 14 dd 81 5f 81 19 ........u...._..
00000020 3d 48 4f 87 8c fc 5b 05 90 05 bd 05 82 93 f4 0a =HO...[.........
00000030 05 ca 5b f4 d6 cb 36 48 9a cc 43 33 b2 ec 59 b3 ..[...6H..C3..Y.
Well, we’ve seen that before  it’s the public key part described previously (where it was placed at offset 2b
). There’s key type, public exponent 010001
, and the modulus starting with 00a975
. And the whole body has length 407
, or hex 197
, which was also the length of public key part before.
PKCS#8 is processably by openssl
tools again:
$ sshkeygen e m PKCS8 f example_key  openssl rsa pubin noout text
RSA PublicKey: (3072 bit)
Modulus:
00:a9:75:c5:14:dd:81:5f:81:19:3d:48:4f:87:8c:
[snip]
Exponent: 65537 (0x10001)
$ sshkeygen e m PKCS8 f example_key  grep v  ''  base64 d  openssl asn1parse inform DER
0:d=0 hl=4 l= 418 cons: SEQUENCE
4:d=1 hl=2 l= 13 cons: SEQUENCE
6:d=2 hl=2 l= 9 prim: OBJECT :rsaEncryption
17:d=2 hl=2 l= 0 prim: NULL
19:d=1 hl=4 l= 399 prim: BIT STRING
# Inspecting the BIT STRING above by using strparse with an offset
$ sshkeygen e m PKCS8 f example_key  grep v  ''  base64 d  openssl asn1parse inform der strparse 19
0:d=0 hl=4 l= 394 cons: SEQUENCE
4:d=1 hl=4 l= 385 prim: INTEGER :A975C514DD815F81193D484F878CFC5B059005BD058293F40A05CA5BF4D6CB36489ACC[snip]
393:d=1 hl=2 l= 3 prim: INTEGER :010001
Which by this point we recognize as the modulus and public exponent. Finally, RFC4716 has a slightly different format:
$ sshkeygen e m RFC4716 f example_key  head
 BEGIN SSH2 PUBLIC KEY 
Comment: "3072bit RSA, converted by user@host from OpenSSH"
AAAAB3NzaC1yc2EAAAADAQABAAABgQCpdcUU3YFfgRk9SE+HjPxbBZAFvQWCk/QKBcpb9N
But the insides are still Base64, so let’s open them:
# Using grep E to have a richer pattern stripping both delimiters and the comment
$ sshkeygen e m RFC4716 f example_key  grep Ev  'Comment'  base64 d  hexdump C
00000000 00 00 00 07 73 73 68 2d 72 73 61 00 00 00 03 01 ....sshrsa.....
00000010 00 01 00 00 01 81 00 a9 75 c5 14 dd 81 5f 81 19 ........u...._..
00000020 3d 48 4f 87 8c fc 5b 05 90 05 bd 05 82 93 f4 0a =HO...[.........
00000030 05 ca 5b f4 d6 cb 36 48 9a cc 43 33 b2 ec 59 b3 ..[...6H..C3..Y.
We’ve already seen this exact thing twice  it’s the RFC4253style key. Same thing, different wrapper.
Not only RSA
However, OpenSSH can use keys in other formats  most notably, Elliptic Curve Cryptography (ECC keys), either ECDSA or ED25519. We’ll not delve into the algorithm this time, as it requires more complex mathematics. Key files for the latter use a basically identical structure, save for a different parameter set, as they don’t use moduli and exponents. ECDSA keys in PEM format can be inspected with openssl
:
$ sshkeygen f example_ec t ecdsa m PEM
$ openssl pkey text noout < example_ec
PrivateKey: (256 bit)
priv:
4d:4d:e3:44:78:48:fb:9f:01:26:21:fa:12:21:6a:
55:1c:59:ff:e1:bd:d4:7a:63:e5:9a:c1:46:e5:04:
79:b1
pub:
04:ff:f1:f4:5c:41:66:53:9d:ee:cd:08:3a:0a:72:
72:95:30:88:f3:81:d6:8f:47:21:72:21:9d:60:c2:
3e:e8:4c:1f:af:88:fe:c1:c4:21:7a:93:2d:7c:6c:
d5:45:21:3f:8b:39:2c:50:6e:a5:b7:e6:eb:04:59:
1a:37:b6:e5:fb
ASN1 OID: prime256v1
NIST CURVE: P256
To be continued
Now that we know (almost) everything about SSH keys, it’s time to put them into good use. We will go into that in second article, starting with key handling and security concerns worth knowing.