## Saturday, September 17, 2011

### 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++fIBX7BCZ5t4lmMh36KGzkQmnjDJcm+O9nYhoPx6Bf+a9yz0HfzbfA5OpqQAyC/vRTVDgHhGXY6HFP/lyWQ8DRzChtsuP6eq9RYHnxwIBIwJhAKdf+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).

`root@suresh ~/.ssh \$ openssl rsa -text -noout < id_rsaPrivate-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 scriptroot@suresh ~/.ssh \$ { echo 'ibase=16'; cat | tr -d ':\n ' | tr a-f A-F; echo; } | bc00: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 input13158045936463264355006370413708684112837853704660293756254884673628\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.
`root@suresh ~/.ssh \$ bcbc 1.06.94Copyright 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\4303031148479239044926138311e=35d=10150492579557375359576342890575270601332058572166512326253768176799\23111571423234513140569517447770196903218153051479115016036905320557\80231250287900874055062921398102953416891810163858645414303785372309\5688315939617076008144563059# Encrypt the number 12345c=pmod(12345, e, n)# Show the encrypted numberc15928992191730477535088375321366468550579140816267293144554503305092\03492035891240033089011563910196180080894311697511846432462334632873\53515625`
`#Decrypt the numberpmod(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 suresh@suresh.spam`
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 0×23 (35, our e). Finally, 00 00 00 61 followed by 0×61 = 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
#!/bin/bash
```
set -e

die() {
echo "\$@" >&2
exit 1
}

if [[ -z \$1 ]]
then
die "Usage: \$0 private_rsa_key"
fi

sshkey=\$(< \$1)
if [[ \$sshkey != "-----BEGIN RSA PRIVATE KEY-----"* ]]
then
die "This does not appear to be an RSA private key"
fi

if [[ \$sshkey == *ENCRYPTED* ]]
then
echo "Key is encrypted, using openssl to decrypt"
sshkey=\$(openssl rsa <<< "\$sshkey")
fi

base64key=\$(sed '1d; \$d;' <<< "\$sshkey") #the base64 data
decdump=\$(base64 -d <<< "\$base64key" | od -t u1 | sed -e 's/^[^ ]*//')
decbytes=\$(echo \$decdump | tr ' ' '\n') #decimal bytes, one on each line

#    echo "read type \$byte" >&2
(( (byte & 0x1F) != 2 )) && \
die "\$byte doesn't encode an integer :O"

#    echo "read length \$length" >&2
exp="0"
for((i=0; i&2
exp="(\$exp)*256+\$b"
done
bc <<< "\$exp" | tr -d '\n\\ '
}

local bytes length n i

n=\$((bytes&0x7F))
if (( bytes & 0x80 ))
then
length=0
for((i=0; i /dev/null # the sequence length
exp1=\$(readInt) # d mod p-1
exp2=\$(readInt) # d mod q-1
c=\$(readInt) || c=0 # p^1 mod q

length=\$(bc -l <<< "scale=20; v=l(\$n)/l(2); scale=1; v/1")
echo "# Key is \$length bits long"
echo "# Input for bc:"
echo "n=\$n"
echo "p=\$p"
echo "q=\$q"
echo "e=\$e"
echo "d=\$d"
echo "c=\$c"
echo "exp1=\$exp1"
echo "exp2=\$exp2"
echo "scale=0"
echo "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;  }"
echo "define encrypt(message) { return pmod(message, e, n); }"
echo "define decrypt(message) { return pmod(message, d, n); }"
echo "define verify() { return n == p*q && (d*e)%((p-1)*(q-1)) == 1 && exp1 == d % (p-1) && exp2 == d % (q-1) && (c*q)%p == 1; }"
echo "# End bc"
) <<< "\$decbytes"  ```

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!