Scott Hanselman

Decoding an SSH Key from PEM to BASE64 to HEX to ASN.1 to prime decimal numbers

August 24, 2018 Comment on this post [6] Posted in Musings | Open Source
Sponsored By

I'm reading a new chapter of The Imposter's Handbook: Season 2 that Rob and I are working on. He's digging into the internals of what's exactly in your SSH Key.

Decoding a certificate

I generated a key with no password:

ssh-keygen -t rsa -C

Inside the generated file is this text, that we've all seen before but few have cracked open.


The private key is an ASN.1 (Abstract Syntax Notation One) encoded data structure. It's a funky format but it's basically a packed format with the ability for nested trees that can hold booleans, integers, etc.

However, ASN.1 is just the binary packed "payload." It's not the "container." For example, there are envelopes and there are letters inside them. The envelope is the PEM (Privacy Enhanced Mail) format. Such things start with ----- BEGIN SOMETHING ----- and end with ----- END SOMETHING ------. If you're familiar with BASE64, your spidey sense may tell you that this is a BASE64 encoded file. Not everything that's BASE64 turns into a friendly ASCII string. This turns into a bunch of bytes you can view in HEX.

We can first decode the PEM file into HEX. Yes, I know there's lots of ways to do this stuff at the command line, but I like showing and teaching using some of the many encoding/decoding websites and utilities there are out there. I also love using for these things as you can build a visual pipeline.


This ASN.1 JavaScript decoder can take the HEX and parse it for you. Or you can that ASN.1 packed format at the *nix command line and see that there's nine big integers inside (I trimmed them for this blog).

openssl asn1parse -in notreal
0:d=0 hl=4 l=1188 cons: SEQUENCE
4:d=1 hl=2 l= 1 prim: INTEGER :00
7:d=1 hl=4 l= 257 prim: INTEGER :B5DF00B3CE6C3948E3923575DAE8CC2199A1C9E81791C9866935A4DF5F6F401DFE7292215
268:d=1 hl=2 l= 3 prim: INTEGER :010001
273:d=1 hl=4 l= 257 prim: INTEGER :8195EB82324A9A667CFFE867991AD697FA4774FD920DA671C6F51A0CAE8B2E3C30D8A1967
534:d=1 hl=3 l= 129 prim: INTEGER :E22B40AC22007370E309E68A29C64EEF085B6937D8B808F74D2862EDEDCBC8CB18BEAAD48
666:d=1 hl=3 l= 129 prim: INTEGER :CDDC00D77FD6E9E7EE83AD95F1805076FAE3690D817C47ED4FA05B7872B5631C6174DEAA7
798:d=1 hl=3 l= 128 prim: INTEGER :747EECEFFD0F9866D43B3C497C5D0E3967679659D2C270B3D9456D37BADDD5CE6F2F7ED4B
929:d=1 hl=3 l= 128 prim: INTEGER :742961DC388A184144E8CEE9DE75AE72050E8FF80C0A0A38520745B648DC2BCA170030A97
1060:d=1 hl=3 l= 129 prim: INTEGER :997742BA4458617495BE121EFF68893C9BC0A1A38226E6F14E16B9FDF5EE072981790499E

Per the spec the format is this:

   An RSA private key shall have ASN.1 type RSAPrivateKey:

RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER -- (inverse of q) mod p }

I found the description for how RSA works in this blog post very helpful as it uses small numbers as examples. The variable names here like p, q, and n are agreed upon and standard.

The fields of type RSAPrivateKey have the following meanings:
o version is the version number, for compatibility
with future revisions of this document. It shall
be 0 for this version of the document.
o modulus is the modulus n.
o publicExponent is the public exponent e.
o privateExponent is the private exponent d.
o prime1 is the prime factor p of n.
o prime2 is the prime factor q of n.
o exponent1 is d mod (p-1).
o exponent2 is d mod (q-1).
o coefficient is the Chinese Remainder Theorem
coefficient q-1 mod p.

Let's look at that first number q, the prime factor p of n. It's super long in Hexadecimal.


That hexadecimal number converted to decimal is this long ass number. It's 308 digits long!


It's hard work to prove this number is prime but there's a great Integer Factorization Calculator that actually uses WebAssembly and your own local CPU to check such things. Expect to way a long time, sometimes until the heat death of the universe. ;)

Rob and I are finding it really cool to dig just below the surface of common things we look at all the time. I have often opened a key file in a text file but never drawn a straight and complete line through decoding, unpacking, decoding, all the way to a math mathematical formula. I feel I'm filling up some major gaps in my knowledge!

Sponsor: Preview the latest JetBrains Rider with its built-in spell checking, initial Blazor support, partial C# 7.3 support, enhanced debugger, C# Interactive, and a redesigned Solution Explorer.

About Scott

Scott Hanselman is a former professor, former Chief Architect in finance, now speaker, consultant, father, diabetic, and Microsoft employee. He is a failed stand-up comic, a cornrower, and a book author.

facebook twitter subscribe
About   Newsletter
Hosting By
Hosted in an Azure App Service
August 26, 2018 13:03
Given that "[it's] hard work to prove this number is prime", there's an obvious question: how did OpenSSH (or OpenSSL) generate this prime in the first place?

I did some quick research and it turns out that OpenSSL, for example, simply generates a large random number and then uses some probabilistic tests for primality (e.g. Miller-Rabin). This means that your number is probably prime (more tests gets you arbitrarily close to 100% certain), but it's not guaranteed.

In practice, this apparently doesn't matter.
August 27, 2018 2:43
That Cryptii is a really cool and useful tool! I've found another tool, with a similar flow of building a pipeline of instructions called "CyberChef" by the GCHQ - Government Communications Headquarters - basically the British NSA from my understanding of their FAQ.

It's open sourced on GitHub, runs in just about any modern browser, portable, works offline (I keep a copy sync'd in my Dropbox), and really is, as they state, a "Cyber Swiss Army Knife".

I was reminded of it since this post is about crypto, and I was using Cyberchef recently to work through the CryptoPals Crypto Challenges, which may be a good link as an "exercise left to the reader" type of reference for this chapter of the book?

I have no affiliation with any of these groups/sites/governments/etc., just trying to share the knowledge available out there!
August 27, 2018 5:00
> In practice, this apparently doesn't matter.

If I remember correctly, it doesn't matter as long as the message encrypted with the key is relatively prime to the two primes chosen, p and q (i.e. they don't have a common factor other than 1). Being prime just means that all messages round trip, but not being prime means that there are some messages that do not.
August 27, 2018 19:47
Well shoot, now I'm all curious about the next level down, particularly the bit @jswolf19 mentioned about the keys being "relatively" prime. That suggests it's possible some messages don't make the round trip and can't be decrypted. (And that's on top of the ongoing wonderment about how one key from a pair can be used to encrypt a message but not to decrypt it afterward.)

Dang it Scott! I've fallen for your devious scheme!
August 28, 2018 16:45

Expect to way a long time, sometimes until the sun death of the universe. ;)

When you say "sun death of the universe", did you mean "heat death of the universe"? Because as far as I can recall, the universe doesn't have a sun.
September 04, 2018 9:56
This is rather interesting. I'd like to point out one thing, though: using the various online tools is not without peril, as there is absolutely no way to know who is behind them. People may become accustomed to using them, and sloppily see how their real password encrypts, and hey ho - you've just given that password to someone. It's not a big leap to connect that to an email address and go try out all popular online services.

Just remember to be mindful of these things. I know (hope) it doesn't affect most people reading your articles, but still...

Comments are closed.

Disclaimer: The opinions expressed herein are my own personal opinions and do not represent my employer's view in any way.