Looking to my previous posts I've noticed that I haven't described the methods how certificate extensions are encoded. Cryptography in overall relies on encoded data. For example, digital certificate is a byte array that contains encoded certificate fields. All certificate content is encoded using Abstract Syntax Notation 1 Distinguished Encoding Rules (simply ASN.1 DER). If certificate is stored in Base64 string format, system just converts Base64 content to a byte array. There are several encoding rules for each data type. For example, object identifiers (OIDs) has their own encoding rules, DateTime — their own encoding rules and so on.

In this post I would like to demonstrate encoding rules for Object Identifier data type. Object Identifiers are used to encode Enhanced Key Usage, Application Policies, Certificate Policies and other certificate extensions. The following format is used:

• Tag value
• String length
• Data type
• Actual data string length
• Encoded data string

In the following example we will encode simple OID (1.3.6.1.5.5.7.3.1) using ASN.1 DER. Mostly 'Tag value' is set to 0x30 (48) that identifies 'constructed type'. The next byte represents string length. Data type for OID is 0x6 (6). The next byte represents encoded OID string length end the rest bytes is encoded data string (actual data). At first we will look to OID string encoding. The first encoded string byte represents first two OID octets. This is because the first OID string is limited to the following values: 0, 1 and 2. Second octet is limited to the value range 0-39 (in decimal). Therefore it is possible to encode first two octets by using one byte as follows:

0x00 = 0.0
0x01 = 0.1
0x27 = 0.39
0x28 = 1.0
0x29 = 1.1
0x4f = 1.39
0x50 = 2.0
0x51 = 2.1
and so on.

Therefore first byte of actual data will be 0x2b that represents first two OID string octets (1.3). Here is another mathematical trick to determine first byte value: 40 * 1st OID octet + 2nd OID octet. For example, we have an OID that starts with 2.8.x.x.x. To calculate the first encoded byte we multiply 40 by 2 (as the first OID octet) and plus 8 (as the second OID octet) and we get 88 in decimal or 0x58 in hex.

Since OID is numerical value only, each next octet is encoded by octet actual values (6.1.5.5.7.3.1) with the base 128:

0x06, 0x01, 0x05, 0x05, 0x07, 0x03 and 0x01. Now we can calculate the length of the actual encoded data string — 0x08. And the length of the same string with the data type octet — 0x0a (0x8 + 0x2). So we can construct the following encoded string: 30 0a 06 08 2b 06 01 05 07 03 01 (all values in hex).

Since each subsequent octet has a base 128, the highest value of the byte can be 0x7f or 127 in decimal. What if OID octet is higher than 127? For example, 130. In that case current byte is set to 0x81 (0x80 is reserved for initial base) that will represent the value = 128 and the next byte will represent the remaining value (130 – 128 = 2) — 0x81 0x02. So the octets that are higher than 127 are encoded in two or more bytes — transitional byte (or bytes) and remaining value byte. If you increment transitional byte minor value by 1, the actual value is incremented by 128. Since minor byte value may have value range 0x0 — 0xf (16 values) the highest actual octet value can be 128 * 16 = 2048. when you increment byte minor value by one, the base will increment by 128. For example the OID octet value is 311, the encoded byte will be 0x82 0x37. Let's see how these values are got. 311 is greater than 127 and the difference between 311 and 128 is greater than 128, so current byte will become as transitional byte — 0x82 and base 256. The difference between 311 and 256 is less than 128 (55) so we set the transitional byte to 0x82 and the next byte will represent the difference between 311 and 256 (55 or 0x37 in hex). There is a simple formula: Actual value / 128 = Increment (rounding to lesser integer). In our case this is 311 / 128 = 2,43. Round the result to the lesser integer and we get 2. Increment 0x80 by 2 will result 0x82. In example of OID octet = 500 we will calculate as follows: 500 / 128 = 3,90. Round the result to the lesser integer will result 3. Therefore the transitional byte minor value will be 3 (0x83). Subtract actual value (500) from base (128 * 3 = 384) and we get 116. The next byte will represent this difference — 0x74 and the encoded bytes of this octet will be: 0x83 0x74.

We can increment transitional byte minor value up to 0xf (0x8f) with the base = 1920 (0xf * 128) and the highest OID octet value for this base is 2047. What if an OID value is greater than 2048? In that case we increment transitional byte major value and set byte minor value to 0. For example an octet has the value = 2050. We increment transitional byte major value by one and get 90. The base now is 2048. 2050 (octet value) – 2048 (base) will result 2. This result must be encoded and placed after transitional byte — 0x90 0x02. Incrementing transitional byte major value will increment base by 2048. For example if transitional byte is 0xa0, the base will be 3968. If the transitional byte is 0xa1 will increment base by 128 and results the new base = 4096.

Using this explanation we can produce resultant simple calculation formula. The calculation process will consist of the following steps:

1. Divide octet value by 2048 and round result value to the lesser integer. If lesser integer is 0, continue with the next step. If lesser integer is greater than 0, set the transitional byte major value to: 8 + lesser integer.
2. If transitional byte major value is greater than 0 set the base as 2048 * lesser integer. Otherwise set the base as 0.
3. Subtract base from octet value and divide by 128. Round the result to the lesser integer. If lesser integer is 0, remove transitional byte. The value must be encoded by using single byte.
4. If lesser integer is greater than 0, set the transitional byte minor value as lesser integer as: 128 * lesser integer.
5. Set the transitional byte hex value as: 2048 * lesser integer produced at the step 1 (major value) and 128 * lesser integer produced at the step 3.
6. Subtract actual octet value from resulting base and encode the difference by using single byte.

Let's see several examples:

• Octet value is 5000.

Divide 5000 by 2048 = 2,44. Round the result to the lesser integer = 2. Set transitional byte major value to 0x8 + 0x2 = 0xa and set the base as 2048 * 2 = 4096. Subtract the base from from actual octet value: 5000 – 4096 = 904. Divide 904 by 128 = 7,06. Round this to the lesser integer = 7. Set transitional byte minor value to 0x7 and the base as: 4096 + 7 * 128 = 4992. The complete transitional byte is 0xa7. Subtract the base from octet value: 5000 – 4992 = 8. Encode this value as a single byte = 0x8. As a result, the encoded value of the OID octet = 5000 will be: 0xa7 0x08.

• Octet value = 10 000

Divide 10000 by 2048 = 4,88. Round the result to the lesser integer = 4. Set transitional byte major value to 0x8 + 0x4 = 0xC and set the base as 2048 * 4 = 8192. Subtract the base from actual octet value: 10000 – 8192 = 1808. Divide 1808 by 128 = 14,12. Round the result to the lesser integer = 14. Set transitional byte minor value to 0xe (14 in decimal) and set the base 8192 + 14 * 128 = 9984. The complete transitional byte is 0x4e. Subtract the base from the actual octet value: 10000 – 9984 = 16. Encode this value as a single byte = 0x10 (16 in decimal). As a result the encoded value of the OID octet = 10 000 will be: 0xCE 0x10.

• Octet value is 1500

Divide 1500 by 2048 = 0,73. Round the result to the lesser integer = 0. Set the transitional byte major value to 0x8 + 0x0 = 0x8 and set the base as 2048 * 0 = 0. Subtract the base from actual octet value: 1500 – 0 = 1500. Divide 1500 by 128 = 11,71. Round the result to the lesser integer = 11. Set transitional byte minor value to 0xB and set the base 0 + 11 * 128 = 1408. The complete transitional byte is 0x8B. Subtract the base from the actual octet value: 1500 – 1408 = 92. Encode this value as a single byte = 0x5C (92 in decimal). As a result encoded value of the OID = 1500 will be: 0x8B 0x5C.

Using these rules we can encode OID octets with the value up to 16383 (0xff 0x7f). What if the octet value is greater than 16383? In that case additional transitional byte is required. Additional transitional byte minor value increment the base by 16384 and transitional byte major value will increment the base by 262144. The following example will show the calculation process for the octet values greater than 16383:

• Octet value is 100 000

Divide 100 000 by 262144 = 0,38. Round the result to the lesser integer = 0. Set the first transitional byte major value to 0x8 + 0 = 0x8 and set the base as 262144 * 0 = 0. Subtract the base from the actual octet value: 100 000 – 0 = 100 000. Divide 100000 by 16384 = 6,1. Round this value to the lesser integer = 6. Set the first transitional byte minor value to 0x6 and set the base 0 + 6 * 16384 = 98304. The first transitional byte is 0x86. Subtract the base from the actual octet value: 100 000 – 983384 = 1696. Continue with the second transitional byte. Divide 1696 by 2048 = 0,82. Round the result to the lesser integer = 0. Set the second transitional byte major value to 0x8 + 0x0 = 0x8 and set the base to 98304 + 0x0 = 98304. Subtract the base from the actual octet value: 100 000 – 98304 = 1696. Divide 1696 by 128 = 13,25. Round the result to the lesser integer = 13. Set the second transitional byte minor value to 0xd and set the base to 0 + 13 * 128 = 1664. The complete second transitional byte is 0x8D. Subtract the base from the remainder: 1696 – 1664 = 32. Encode this value as a single byte = 0x20 (32 in decimal). As a result encoded value of this OID will be: 0x86 0x8D 0x20.

Usually you don't need to manually convert OIDs to the encoded values. There are .NET class: X509EnhancedKeyUsageExtension and IX509ExtensionEnhancedKeyUsage COM interface that will do this task.