DER编码规则小记

X.690定义了ASN.1的编码格式，包括BER、CER、DER。另外 ASN.1的编码格式还有 XER、JER 等。

BER：Basic Encoding Rules
CER：Canonical Encoding Rules
DER：Distinguished Encoding Rules

DER是BER的子集，本文只关注DER。

规则

DER 指定了用于编码 ASN.1 数据结构的部分自描述和自定界协议。每个数据元素都将被编码为类型标识符、长度描述、实际数据元素。这些类型的编码通常称为类型type-长度length-值value (TLV) 编码。然而，在 DER 的术语中，它是标识符identifier-长度length-内容content。

Identifier：Type
Length：Length
Contents：Value

标识符Identifer

标识符占一个(Short form)或多个字节(Long form)。

der-identifier

标识符有四类（Class），本文关注Universal：

Universal：0，Native to ASN.1
Application：1
Context-specific：2
Private：3

值类型有两种（P/C）：

Primitive：Content直接是值
Constructed：Content包含多个其他编码值

ANS.1定义的一些type：

BOOLEAN：1
INTEGER：2
BIT STRING：3
OCTET STRING：4
NULL：5
OBJECT IDENTIFIER：6
OBJECT Descriptor：7
EXTERNAL：8
REAL：9
UTF8String：12
SEQUENCE，SEQUENCE OF：16
SET，SET OF：17
DATE：31
...

Type大于30时，标识符1个字节不够用，需要使用long form。

长度

DER不使用Indefinite，故只需要考虑Definite格式。它又分为short和long两种。

der-length

内容规则

对象标识符 OBJECT IDENTIFIER

OID 的前两个节点编码为单个字节。第一个节点乘以小数 40，结果将添加到第二个节点的值。
小于或等于 127 的节点值按一个字节进行编码。
大于或等于 128 的节点值按多个字节进行编码。最左侧字节的第 7 位设置为 1。每个字节的 0 到 6 位包含编码值。

BIT STRING

BIT STRING TLV 三元组的 “值” 字段包含一个前导字节，该字节指定内容最后一个字节中剩余未使用的位数。

位字符串数据类型的 der 编码

再上面的示例中， “长度L” 字段为“0x03”，因为后面跟着三个内容字节。“ 值V ”字段的前导字节设置为“0x04，因为最后一个内容字节中有四个未使用的位。每个未使用的位都由字母 x 表示。

注：图片来自：https://learn.microsoft.com/zh-cn/windows/win32/seccertenroll/about-bit-string

INTEGER

如果整数为正数，但高阶位设置为 1，则需要将0x00作为前导字符添加到内容中，以指示数字不是负数。

解码DER

python中好多支持der编解码的库，比如

https://pypi.org/project/asn1crypto/
https://pypi.org/project/asn1tools/
https://pypi.org/project/asn1/
https://pypi.org/project/pyasn1/
https://github.com/wiml/derlite

简单起见，我们按照DER的规则，自己写写，看能否解读RSA的公钥文件：

import struct
import base64
import re

def parse_der(data):
    #print(f'Parsing: {data.hex(" ")}, Length: {len(data)}\n')
    # parse tag and length
    tag = struct.unpack('B', data[0:1])[0]
    length = data[1]

    if length & 0x80:
        length_bytes = length & 0x7F
        length_value = struct.unpack(f'>{length_bytes}B', data[2:2+length_bytes])
        length = sum([byte << (8 * (length_bytes - i - 1)) for i, byte in enumerate(length_value)])
    else:
        length_bytes = 0
    contents = data[2+length_bytes : 2+length_bytes+length]
    total_length = length + 2 + length_bytes


    if tag == 0x01:  # Boolean
        return tag, total_length, bool(contents[0])
    elif tag == 0x02:  # Integer
        return tag, total_length, int.from_bytes(contents, 'big')
    elif tag == 0x03:  # BitString
        return tag, total_length, contents.hex(' ')
    elif tag == 0x04:  # OctetString
        return tag, total_length, contents.decode('utf-8')
    elif tag == 0x05:  # Null
        return tag, total_length, None
    elif tag == 0x06:  # ObjectIdentifier
        oid_bytes = struct.unpack(f'>{length}B', contents)
        first_byte = oid_bytes[0] // 40
        second_byte = oid_bytes[0] % 40
        oid = [str(first_byte), str(second_byte)]
        value = 0
        for byte in oid_bytes[1:]:
            value = value * 128 + (byte & 0x7F)
            if not byte & 0x80:
                oid.append(str(value))
                value = 0
        return tag, total_length, '.'.join(oid)
    elif tag == 0x30 or tag == 0x31:  # Sequence or Set
        # 0x30: tag 0x10 with P/C=1
        # 0x31: tag 0x11 with P/C=1
        parsed_data = []
        index = 0
        while index < len(contents)-1:
            sub_tag, sub_length, item = parse_der(contents[index:])
            parsed_data.append(item)
            index += sub_length

        return tag, total_length, parsed_data
    else:
        print(f'Unknown tag: {tag}')
        return tag, total_length, None

base64_data = b'''-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA2Wk4/RZTlV2Wp28mMlzG
EvCJtYUKlK1BD1bzGl4dS41dQuLjkmgV6QnLcOgpfJCF8CPuS4rVBCZ0jG0VuY6A
ZU+cBsY74LY+WDQt6GJCktgFmDoQ81onmA+SYS5yIhVJMo4KCbn88HXt201iWPJK
bla+EduA1CustJxDb+vkqylomceW0YZmBkyfFJ5v5VYqql7BD/Roa9tU/rYssE67
gnIfMRDyzWfATOKgPmERVEO4RPkwtH4NIHmTDN6NgZixrnRXuY+tc46JPvPI8mhM
Kq62A5wHVWmJkzayFH4cMPogIVAJocxh0Sct4jqIVA8FJOVoUzsUyZU/ct1fNU8p
bwIDAQAB
-----END PUBLIC KEY-----'''
# remove header and footer with regex
base64_data = re.sub(rb'----[A-Z ]+----', b'', base64_data)
der_data = base64.b64decode(base64_data)

parsed_data = parse_der(der_data)
print(parsed_data[2])

运行结果如下：

[['1.2.840.113549.1.1.1', None], '00 30 82 01 0a 02 82 01 01 00 d9 69 38 fd 16 53 95 5d 96 a7 6f 26 32 5c c6 12 f0 89 b5 85 0a 94 ad 41 0f 56 f3 1a 5e 1d 4b 8d 5d 42 e2 e3 92 68 15 e9 09 cb 70 e8 29 7c 90 85 f0 23 ee 4b 8a d5 04 26 74 8c 6d 15 b9 8e 80 65 4f 9c 06 c6 3b e0 b6 3e 58 34 2d e8 62 42 92 d8 05 98 3a 10 f3 5a 27 98 0f 92 61 2e 72 22 15 49 32 8e 0a 09 b9 fc f0 75 ed db 4d 62 58 f2 4a 6e 56 be 11 db 80 d4 2b ac b4 9c 43 6f eb e4 ab 29 68 99 c7 96 d1 86 66 06 4c 9f 14 9e 6f e5 56 2a aa 5e c1 0f f4 68 6b db 54 fe b6 2c b0 4e bb 82 72 1f 31 10 f2 cd 67 c0 4c e2 a0 3e 61 11 54 43 b8 44 f9 30 b4 7e 0d 20 79 93 0c de 8d 81 98 b1 ae 74 57 b9 8f ad 73 8e 89 3e f3 c8 f2 68 4c 2a ae b6 03 9c 07 55 69 89 93 36 b2 14 7e 1c 30 fa 20 21 50 09 a1 cc 61 d1 27 2d e2 3a 88 54 0f 05 24 e5 68 53 3b 14 c9 95 3f 72 dd 5f 35 4f 29 6f 02 03 01 00 01']

对比一下openssl的输出openssl rsa -pubin -in rsa_2048.pub -text：

Public-Key: (2048 bit)
Modulus:
    00:d9:69:38:fd:16:53:95:5d:96:a7:6f:26:32:5c:
    c6:12:f0:89:b5:85:0a:94:ad:41:0f:56:f3:1a:5e:
    1d:4b:8d:5d:42:e2:e3:92:68:15:e9:09:cb:70:e8:
    29:7c:90:85:f0:23:ee:4b:8a:d5:04:26:74:8c:6d:
    15:b9:8e:80:65:4f:9c:06:c6:3b:e0:b6:3e:58:34:
    2d:e8:62:42:92:d8:05:98:3a:10:f3:5a:27:98:0f:
    92:61:2e:72:22:15:49:32:8e:0a:09:b9:fc:f0:75:
    ed:db:4d:62:58:f2:4a:6e:56:be:11:db:80:d4:2b:
    ac:b4:9c:43:6f:eb:e4:ab:29:68:99:c7:96:d1:86:
    66:06:4c:9f:14:9e:6f:e5:56:2a:aa:5e:c1:0f:f4:
    68:6b:db:54:fe:b6:2c:b0:4e:bb:82:72:1f:31:10:
    f2:cd:67:c0:4c:e2:a0:3e:61:11:54:43:b8:44:f9:
    30:b4:7e:0d:20:79:93:0c:de:8d:81:98:b1:ae:74:
    57:b9:8f:ad:73:8e:89:3e:f3:c8:f2:68:4c:2a:ae:
    b6:03:9c:07:55:69:89:93:36:b2:14:7e:1c:30:fa:
    20:21:50:09:a1:cc:61:d1:27:2d:e2:3a:88:54:0f:
    05:24:e5:68:53:3b:14:c9:95:3f:72:dd:5f:35:4f:
    29:6f
Exponent: 65537 (0x10001)

仔细比较一下，可发现，Modulus和Exponent都包在 BIT STRING 输出里面了，但是是混在一块的。看来需要基于OID1.2.840.113549.1.1.1继续解读 BIT STRING 才行。

另注意，此处Modulus有前导字符0（因为下一个字符D9，最高位为1），也可以通过openssl rsa -modulus来查看具体的模值：

openssl rsa -pubin  -in rsa_2048.pub -modulus
Modulus=D96938FD1653955D96A76F26325CC612F089B5850A94AD410F56F31A5E1D4B8D5D42E2E3926815E909CB70E8297C9085F023EE4B8AD50426748C6D15B98E80654F9C06C63BE0B63E58342DE8624292D805983A10F35A27980F92612E72221549328E0A09B9FCF075EDDB4D6258F24A6E56BE11DB80D42BACB49C436FEBE4AB296899C796D18666064C9F149E6FE5562AAA5EC10FF4686BDB54FEB62CB04EBB82721F3110F2CD67C04CE2A03E61115443B844F930B47E0D2079930CDE8D8198B1AE7457B98FAD738E893EF3C8F2684C2AAEB6039C075569899336B2147E1C30FA20215009A1CC61D1272DE23A88540F0524E568533B14C9953F72DD5F354F296F

猜想对不对？可以用 Asn1Editor.WPF 工具对比确认一下：

asn1editor-rsa

可以看到它也在继续解读BIT STRING。

OK，临时修改一下上面的python代码（注意，此处跳过BitString的第一个字节00，它用于指定最后一个内容字节中存在的未使用位数）

    elif tag == 0x03:  # BitString
        print(parse_der(contents[1:])[2])
        return tag, total_length, contents.hex(' ')

可得到两个值：

[27445599381378035545670523148607236472225286815854892348596803754128427639970701679060637674408997570467049607589422583767959961753522984671350732011421502377280857000739029206485080166159886898664317181584241642378526386882345159670001146437538224818393591073459474805361047165591136893859645793002623819995930088355664715708614808951470601732409482672759339954069052827132163326960803603753820677019256485986991663132033163463784405045346025270316334503071062277674190893959720506018839850062431584678553749928642692097173492555975389032958879496564099492785722322726190859650291595641789787694809886825416252926319, 65537]

例子

RSA PKCS8/X.509 vs PKCS1

注意公钥头部 -----BEGIN PUBLIC KEY----- 与 -----BEGIN RSA PUBLIC KEY-----的不同。后者标出RSA字样，格式简单直接，存储RSA公钥；前者能存储各种算法的公钥，需要专门的OID标识。

对于公钥，这两个格式分别由X.509SubjectPublicKeyInfo 和 PKCS1RSAPublicKey规范
对于私钥，这两个格式分别由PKCS8 PrivateKeyInfo和 PKCS1 RSAPrivateKey规范

上面的例子中，我们解读的是RSA的公钥（X.509）。可以转换成PKCS1格式，再看看

转换可以通过openssl实现：

openssl rsa -pubin -in rsa_2048.pub -out rsa_2048_pkcs1.pub -RSAPublicKey_out

结果文件：

将这段内容直接贴进前面的python代码，输出结果如下（比前面简单直接）：

[27445599381378035545670523148607236472225286815854892348596803754128427639970701679060637674408997570467049607589422583767959961753522984671350732011421502377280857000739029206485080166159886898664317181584241642378526386882345159670001146437538224818393591073459474805361047165591136893859645793002623819995930088355664715708614808951470601732409482672759339954069052827132163326960803603753820677019256485986991663132033163463784405045346025270316334503071062277674190893959720506018839850062431584678553749928642692097173492555975389032958879496564099492785722322726190859650291595641789787694809886825416252926319, 65537]

PKCS1

https://www.rfc-editor.org/rfc/rfc3447#page-44

定义RSA公钥和私钥的格式，其中私钥：

      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
          otherPrimeInfos   OtherPrimeInfos OPTIONAL
      }

在ASN.1中，注释有两种形式，单行注释和多行注释。单行注释以 -- 开始，以行尾或者另一个--结束（以先遇到的为准）。多行注释以/*开始，以*/结束。多行注释允许多重嵌套，如果遇到多个/*，需要遇到同等的*/才结束注释。

公钥：

      RSAPublicKey ::= SEQUENCE {
          modulus           INTEGER,  -- n
          publicExponent    INTEGER   -- e
      }

PKCS8

https://datatracker.ietf.org/doc/html/rfc5208

定义私钥PrivateKeyInfo的格式

PrivateKeyInfo ::= SEQUENCE {
   version Version,
   privateKeyAlgorithm AlgorithmIdentifier {{PrivateKeyAlgorithms}},
   privateKey PrivateKey,
   attributes [0] Attributes OPTIONAL }

Version ::= INTEGER {v1(0)} (v1,...)

PrivateKey ::= OCTET STRING

Attributes ::= SET OF Attribute

以及EncryptedPrivateKeyInfo

EncryptedPrivateKeyInfo ::= SEQUENCE {
    encryptionAlgorithm AlgorithmIdentifier {{KeyEncryptionAlgorithms}},
    encryptedData EncryptedData
}

EncryptedData ::= OCTET STRING

但是公钥定义应该不再PKCS8里面。

SubjectPublicKeyInfo  ::=  SEQUENCE  {
     algorithm            AlgorithmIdentifier,
     subjectPublicKey     BIT STRING  }

AlgorithmIdentifier  ::=  SEQUENCE  {
     algorithm               OBJECT IDENTIFIER,
     parameters              ANY DEFINED BY algorithm OPTIONAL  }

对RSA来说， OID 是 1.2.840.113549.1.1.1, 其 RSAPublicKey 位于 subjectPublicKey 这个BIT STRING 中。

OpenSSL

OpenSSL 提供一个 asn1parse 的工具，用于解读 asn1文件。

输出内容说明：

d：嵌套深度(depth)
hl：头部长度(head length)
l：内容长度(length)
cons/prim：类型

解读 PUBLIC KEY 格式的公钥（X.509)：

openssl asn1parse -in rsa_2048.pub
d=0  hl=4 l= 290 cons: SEQUENCE
d=1  hl=2 l=  13 cons: SEQUENCE
d=2  hl=2 l=   9 prim: OBJECT            :rsaEncryption
d=2  hl=2 l=   0 prim: NULL
d=1  hl=4 l= 271 prim: BIT STRING

可以看到，默认和我们一样，key 在 BIT STRING 中，需要进一步解读。

解读 RSA PUBLIC KEY公钥（PKCS1）：

这个就比较直接：

openssl asn1parse -in rsa_2048_pkcs1.pub
d=0  hl=4 l= 266 cons: SEQUENCE
d=1  hl=4 l= 257 prim: INTEGER           :D96938FD1653955D96A76F26325CC612F089B5850A94AD410F56F31A5E1D4B8D5D42E2E3926815E909CB70E8297C9085F023EE4B8AD50426748C6D15B98E80654F9C06C63BE0B63E58342DE8624292D805983A10F35A27980F92612E72221549328E0A09B9FCF075EDDB4D6258F24A6E56BE11DB80D42BACB49C436FEBE4AB296899C796D18666064C9F149E6FE5562AAA5EC10FF4686BDB54FEB62CB04EBB82721F3110F2CD67C04CE2A03E61115443B844F930B47E0D2079930CDE8D8198B1AE7457B98FAD738E893EF3C8F2684C2AAEB6039C075569899336B2147E1C30FA20215009A1CC61D1272DE23A88540F0524E568533B14C9953F72DD5F354F296F
d=1  hl=2 l=   3 prim: INTEGER           :010001

参考

https://en.wikipedia.org/wiki/X.690#DER_encoding
https://learn.microsoft.com/zh-cn/windows/win32/seccertenroll/about-bit-string
https://www.oss.com/asn1/resources/asn1-made-simple/encoding-rules.html
https://www.alvestrand.no/objectid/1.2.840.113549.1.1.html
https://medium.com/asecuritysite-when-bob-met-alice/the-magic-of-cryptographic-identifiers-and-formats-oids-der-and-asn-1-efc4e75c94db
https://mbed-tls.readthedocs.io/en/latest/kb/cryptography/asn1-key-structures-in-der-and-pem/
https://stackoverflow.com/questions/18039401/how-can-i-transform-between-the-two-styles-of-public-key-format-one-begin-rsa

1+1=10

记记笔记，放松一下...