How is OID 2a 86 48 86 f7 0d parsed as 1.2.840.113549?

Question

I saw that an RSA key, created by OpenSSL, contains the following HEX string:

2a 86 48 86 f7 0d 01 01 01

that HEX string gets interpreted as Object ID:

1.2.840.113549.1.1.1

It is obvious 01 01 01 is 1.1.1, but how does 2a 86 48 86 f7 0d get interpreted (parsed) as 1.2.840.113549?

Answer 1

The question's bytestring 2a 86 48 86 f7 0d 01 01 01 is the Value field of an ASN.1 BER/DER TLV with type 6, which is the Object IDentifier for an RSA key (the Type and Length just before are coded as 06 09, and won't be further discussed).

In order to parse that Value bytestring, we first separate the bytes into blocks ending after each byte in which the high-order bit is clear (in other words: blocks end after a byte in range 00_h to 7f_h). Then we paste together the low-order 7 bits of the bytes (in big-endian/reading order); so that
_____2a|_____86_____48|_____86_____f7_____0d|_____01|_____01|_____01   becomes
0101010|00001101001000|000011011101110001101|0000001|0000001|0000001

We then interpret each block of bits as coding a non-negative integer in big-endian binary. The question's example now comes out as the six integers: 42 840 113549 1 1 1

There's a special case for the first integer: it was built as $z=40x+y$, with $x$ encoding the top-level authority that assigned $y$. Integer $x$ is always one of $0$ (for ccitt), $1$ (for iso) or $2$ (for joint-iso-ccitt), and if $x<2$ then $y<40$.
We thus replace the first integer $z$ by $x=\min(\lfloor z/40\rfloor,2)$ and $y=z-40x$.
Note: when $x=2$, $y$ can be arbitrarily large. Assigned $y$ include 40 (exercising the $\min$ rule), 48 (requiring coding $z$ over more than one byte), and 999 (with $y\ge2^8$), which might not be correctly handled by some existing software.

The question's example now comes out as the seven integers: 1 2 840 113549 1 1 1

One practice is to format these integers in decimal without a leading 0 digit (with the exception of the integer zero represented as 0), separated by dots, as in
1.2.840.113549.1.1.1
or sometimes enclosed in braces with separating spaces, as in
{1 2 840 113549 1 1 1}
or sometimes (as shown by the OID Repository)
{iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1) rsaEncryption(1)}
or in OID-IRI notation
/ISO/Member-Body/840/113549/1/1/1

The careful reader will notice that per the above conventions, different bytestrings can decode to the same OID; however the rule in crypto (for OIDs at least) is to stick to the unique DER encoding, such that (in the bitstring with the Value field of an OID) a byte 80_h can only follow a byte which high-order bit is set (otherwise the 80_h would encode leading zeroes of an integer, and must be suppressed).

---

Daniel Marschall's Study about OID encoding and size limitations was most useful in making the above (hopefully) correct; it also confirmed my intuition that OID decoding practices are chaotic. Microsoft has an explanation on OID format, which I found initially useful even though it turns out to be dangerously lacking.

The normative references for OID encoding are somewhere in IUT-T X.680 through X.695 Information Technology - Abstract Syntax Notation One (ASN.1) & ASN.1 encoding rules. They are also in its free ancestors IUT-T X.209:1988 Specification of Basic Encoding Rules for Abstract Syntax Notation One (ASN.1) in section 22 Encoding of an object identifier value, with definitions in IUT-T X.208:1988 Specification of Abstract Syntax Notation One (ASN.1) in section 28 Notation for the object identifier type and annexes B, C and D.