Suresh Kumar Pakalapati's Linux Administration: What’s in a SSH RSA key pair?

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):

...
-----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_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 d_P from the Wikipedia article, exponent2 is d_Q and coefficient is q_Inv.

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 root@suresh ~/.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.

root@suresh ~/.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 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

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

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

readLength() { 
    local bytes length n i 
    read bytes

    n=$((bytes&0x7F))
    if (( bytes & 0x80 ))
    then
        length=0
        for((i=0; i /dev/null # the sequence length
    unknown=$(readInt)
    n=$(readInt) #modulo
    e=$(readInt) #public exponent
    d=$(readInt) #private exponent
    p=$(readInt) #first prime
    q=$(readInt) #second prime
    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!