How does ASN.1 encode an object identifier?

OID encoding for dummies :) :

• each OID component is encoded to one or more bytes (octets)
• OID encoding is just a concatenation of these OID component encodings
• first two components are encoded in a special way (see below)
• if OID component binary value has less than 7 bits, the encoding is just a single octet, holding the component value (note, most significant bit, leftmost, will always be 0)
• otherwise, if it has 8 and more bits, the value is "spread" into multiple octets - split the binary representation into 7 bit chunks (from right), left-pad the first one with zeroes if needed, and form octets from these septets by adding most significant (left) bit 1, except from the last chunk, which will have bit 0 there.
• first two components (X.Y) are encoded like it is a single component with a value 40*X + Y

This is a rewording of ITU-T recommendation X.690, chapter 8.19

Yes, the OID is encoded in the binary data. The OID 1.3.6.1.5.5.7.48.1 you mention becomes 2b 06 01 05 05 07 30 01 (the first two numbers are encoded in a single byte, all remaining numbers are encoded in a single bytes as well because they're all smaller than 128).

A nice description of OID encoding is found here.

But the best way to analyze your ASN.1 data is to paste in into an online decoder, e.g. http://lapo.it/asn1js/.

If all your digits are less than or equal to 127 then you are very lucky because they can be represented with a single octet each. The tricky part is when you have larger numbers which are common, such as 1.2.840.113549.1.1.5 (sha1WithRsaEncryption). These examples focus on decoding, but encoding is just the opposite.

1. First two 'digits' are represented with a single byte

You can decode by reading the first byte into an integer

var firstByteNumber = 42;
var firstDigit = firstByteNumber / 40;
var secondDigit = firstByteNumber % 40;

Produces the values

1.2

2. Subsequent bytes are represented using Variable Length Quantity, also called base 128.

VLQ has two forms,

Short Form - If the octet starts with 0, then it is simply represented using the remaining 7 bits.

Long Form - If the octet starts with a 1 (most significant bit), combine the next 7 bits of that octet plus the 7 bits of each subsequent octet until you come across an octet with a 0 as the most significant bit (this marks the last octet).

The value 840 would be represented with the following two bytes,

10000110
01001000

Combine to 00001101001000 and read as int.

---

Great resource for BER encoding, http://luca.ntop.org/Teaching/Appunti/asn1.html

The first octet has value 40 * value1 + value2. (This is unambiguous, since value1 is limited to values 0, 1, and 2; value2 is limited to the range 0 to 39 when value1 is 0 or 1; and, according to X.208, n is always at least 2.)

The following octets, if any, encode value3, ..., valuen. Each value is encoded base 128, most significant digit first, with as few digits as possible, and the most significant bit of each octet except the last in the value's encoding set to "1." Example: The first octet of the BER encoding of RSA Data Security, Inc.'s object identifier is 40 * 1 + 2 = 42 = 2a16. The encoding of 840 = 6 * 128 + 4816 is 86 48 and the encoding of 113549 = 6 * 1282 + 7716 * 128 + d16 is 86 f7 0d. This leads to the following BER encoding:

06 06 2a 86 48 86 f7 0d

---

Finally, here is a OID decoder I just wrote in Perl.

sub getOid {
    my $bytes = shift;

    #first 2 nodes are 'special';
    use integer;
    my $firstByte = shift @$bytes;
    my $number = unpack "C", $firstByte;
    my $nodeFirst = $number / 40;
    my $nodeSecond = $number % 40;

    my @oidDigits = ($nodeFirst, $nodeSecond);

    while (@$bytes) {
        my $num = convertFromVLQ($bytes);
        push @oidDigits, $num;
    }

    return join '.', @oidDigits;
}

sub convertFromVLQ {
    my $bytes = shift;

    my $firstByte = shift @$bytes;
    my $bitString = unpack "B*", $firstByte;

    my $firstBit = substr $bitString, 0, 1;
    my $remainingBits = substr $bitString, 1, 7;

    my $remainingByte = pack "B*", '0' . $remainingBits;
    my $remainingInt = unpack "C", $remainingByte;

    if ($firstBit eq '0') {
        return $remainingInt;
    }
    else {
        my $bitBuilder = $remainingBits;

        my $nextFirstBit = "1";
        while ($nextFirstBit eq "1") {
            my $nextByte = shift @$bytes;
            my $nextBits = unpack "B*", $nextByte;

            $nextFirstBit = substr $nextBits, 0, 1;
            my $nextSevenBits = substr $nextBits, 1, 7;

            $bitBuilder .= $nextSevenBits;
        }

        my $MAX_BITS = 32;
        my $missingBits = $MAX_BITS - (length $bitBuilder);
        my $padding = 0 x $missingBits;
        $bitBuilder = $padding . $bitBuilder;

        my $finalByte = pack "B*", $bitBuilder;
        my $finalNumber = unpack "N", $finalByte;
        return $finalNumber;
    }

}