What’s in a SSH RSA key pair?

What’s in a SSH RSA key pair?

You probably have your own closely guarded ssh key pair. Chances are good that it’s based on RSA, the default choice in ssh-keygen.

RSA is a very simple and quite brilliant algorithm, and this article will show what a SSH RSA key pair contains, and how you can use those values to play around with and encrypt values using nothing but a calculator.

RSA is based on primes, and the difficulty of factoring large numbers. This post is not meant as an intro to RSA, but here’s a quick reminder. I’ll use mostly the same symbols as Wikipedia: you generate two large primes, p and q. Let φ = (p-1)(q-1). Pick a number e coprime to φ, and let d ≡ e^-1 mod φ.

The public key is then (e, n), while your private key is (d, n). To encrypt a number/message m, let the ciphertext c ≡ m^e mod n. Then m ≡ c^d mod n.

This is very simple modular arithmetic, but when you generate a key pair with ssh-keygen, you instead get a set of opaque and scary looking files, id_rsa and id_rsa.pub. Here’s a bit from the private key id_rsa (no passphrase):


-----BEGIN RSA PRIVATE KEY-----
MIIBygIBAAJhANj3rl3FhzmOloVCXXesVPs1Wa++fIBX7BCZ5t4lmMh36KGzkQmn
jDJcm+O9nYhoPx6Bf+a9yz0HfzbfA5OpqQAyC/vRTVDgHhGXY6HFP/lyWQ8DRzCh
tsuP6eq9RYHnxwIBIwJhAKdf+4oqqiUWOZn//vXrV3/19LrGJYeU

...
-----END RSA PRIVATE KEY-----


How can we get our nice RSA parameters from this mess?

The easy way is with openssl: (I apologize in advance for all the data spam in the rest of the article).


vidar@vidarholen ~/.ssh $ openssl rsa -text -noout < id_rsa
Private-Key: (768 bit)
modulus:
00:d8:f7:ae:5d:c5:87:39:8e:96:85:42:5d:77:ac:
54:fb:35:59:af:be:7c:80:57:ec:10:99:e6:de:25:
...
publicExponent: 35 (0x23)
privateExponent:
00:a7:5f:fb:8a:2a:aa:25:16:39:99:ff:fe:f5:eb:
57:7f:f5:f4:ba:c6:25:87:94:48:64:93:fb:3d:a7:
...
prime1:
...
prime2:
...
exponent1:
...
exponent2:
...
coefficient:
...


Here, modulus is n, publicExponent is e, privateExponent is d, prime1 is p, prime2 is q, exponent1 is dP from the Wikipedia article, exponent2 is dQ and coefficient is qInv.

Only the first three are strictly required to perform encryption and decryption. The latter three are for optimization and the primes are for verification.

It’s interesting to note that even though the private key from RSA’s point of view is (d,n), the OpenSSH private key file includes e, p, q and the rest as well. This is how it can generate public keys given the private ones. Otherwise, finding e given (d,n) is just as hard as finding d given (e,n), except e is conventionally chosen to be small and easy to guess for efficiency purposes.

If we have one of these hex strings on one line, without colons, and in uppercase, then bc can work on them and optionally convert to decimal.


# If you don't want to do this yourself, see end for a script
vidar@vidarholen ~/.ssh $ { echo 'ibase=16'; cat | tr -d ':\n ' | tr a-f A-F; echo; } | bc

00:d8:f7:ae:5d:c5:87:39:8e:96:85:42:5d:77:ac:
54:fb:35:59:af:be:7c:80:57:ec:10:99:e6:de:25:
98:c8:77:e8:a1:b3:91:09:a7:8c:32:5c:9b:e3:bd:
....
Ctrl-d to end input
13158045936463264355006370413708684112837853704660293756254884673628\
63292...


We also need a power-modulo function, since b^e % m is unfeasibly slow if you go by way of b^e. Luckily, bc is programmable.


vidar@vidarholen ~/.ssh $ bc
bc 1.06.94
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.

# Our powermod function:
define pmod(b,e,m) { if(e == 0 ) return 1; if(e == 1) return b%m; rest=pmod(b^2%m,e/2,m); if((e%2) == 1) return (b*rest)%m else return rest; }



#Define some variables (this time unabbreviated)
n=13158045936463264355006370413708684112837853704660293756254884673628\
63292777770859554071108633728590995985653161363101078779505801640963\
48597350763180843221886116453606059623113097963206649790257715468881\
4303031148479239044926138311

e=35

d=10150492579557375359576342890575270601332058572166512326253768176799\
23111571423234513140569517447770196903218153051479115016036905320557\
80231250287900874055062921398102953416891810163858645414303785372309\
5688315939617076008144563059


# Encrypt the number 12345
c=pmod(12345, e, n)

# Show the encrypted number
c
15928992191730477535088375321366468550579140816267293144554503305092\
03492035891240033089011563910196180080894311697511846432462334632873\
53515625


#Decrypt the number
pmod(c, d, n)

12345


Yay, we’ve successfully encrypted and decrypted a value using real life RSA parameters!

What’s in the public key file, then?

ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAGEA2PeuXcWHOY6WhUJdd6xU+zVZr758gFfsEJnm3iWYyHfoobORCaeMMlyb472diGg/HoF/5r3LPQd/Nt8Dk6mpADIL+9FNUOAeEZdjocU/+XJZDwNHMKG2y4/p6r1FgefH [email protected]

This is a very simple file format, but I don’t know of any tools that will decode it. Simply base64-decode the middle string, and then read 4 bytes of length, followed by that many bytes of data. Repeat three times. You will then have key type, e and n, respectively.

Mine is 00 00 00 07, followed by 7 bytes “ssh-rsa”. Then 00 00 00 01, followed by one byte of 0x23 (35, our e). Finally, 00 00 00 61 followed by 0x61 = 97 bytes of our modulus n.

If you want to decode the private key by hand, base64-decode the middle bit. This gives you an ASN.1 encoded sequence of integers.

This is an annotated hex dump of parts of a base64-decoded private key

30 82 01 ca   - Sequence, 0x01CA bytes
    02 01: Integer, 1 byte
        00
    02 61:    - Integer, 0x61 bytes (n).
        00 d8 f7 ae 5d c5 87 39 8e 96 ... Same as from openssl!
    02 01:  - Integer, 1 byte, 0x23=35 (e)
        23
    02 61  - Integer, 0x61 bytes (d)
        00 a7 5f fb 8a 2a aa 25 16 39 ...
    ...

Here’s a bash script that will decode a private key and output variable definitions and functions for bc, so that you can play around with it without having to do the copy-paste work yourself. It decodes ASN.1, and only requires OpenSSL if the key has a passphrase.

When run, and its output pasted into bc, you will have the variables n, e, d, p, q and a few more, functions encrypt(m) and decrypt(c), plus a verify() that will return 1 if the key is valid. These functions are very simple and transparent.

Enjoy!