BER编码

RSA与ECDSA的签名都采用了BER编码。
BER(Basic Encoding Rule)，BER的数据都是TLV格式的。

每种TAG的定义如下：

Tag 定义
0x01 BOOL
0x02 INT，整型
0x04 OCTSTR，字符串类型
0x05 NULL，空类型
0x06 OBJID，对象标识ObjectID（在这里就是对应的HASH算法的OID编码）
0x0A ENUM
0x30 SEQ，Sequence组合类型
0x31 SETOF
0x40 IPADDR
0x41 COUNTER
0x42 GAUGE
0x43 TIMETICKS
0x44 OPAQUE

RSA签名

RSA私钥签名时要基于某个HASH算法，比如MD5或者SHA1等。

RSA签名过程：先对明文做HASH计算，然后对HASH后的数据进行BER编码，再用私钥直接对编码后的数据加密。

RSA验签过程：先用公钥解密，解析TLV数据从中得到HASH算法的OID和HASH值，根据OID选择相应的HASH算法对明文进行计算，最后比对HASH值。

例子：
公钥模：
89 54 E6 61 C1 52 DB ED 07 57 50 04 AD B3 D2 A7 A9 8F E8 D8 20 5B 01 B2 E5 E4 7A 7B EE 80 E3 C0 13 11 D2 F9 AD C3 CC 5F 1D 96 AC B2 AB BE 9C 14 9E 76 31 06 B2 E6 FA 01 52 A7 2E 53 C2 1D 3B 7B 9B 68 05 D2 5E 35 31 98 0E 02 93 E0 D9 0C 38 2D 3D EE 10 E6 87 53 79 DF B2 1E 12 D9 9E EF 89 6D 01 59 0D 13 94 DB 05 B7 09 34 D3 5B AB ED 7C FE 0E BE 87 EE E8 DD 01 39 3A CA 3A A7 17 B8 AA E3

公钥指数：
01 00 01

私钥指数：
01 FE B1 BA 09 CC E2 54 F7 1E 55 93 3B D2 B8 E4 A6 99 E8 8F FB 28 57 45 FA 00 EF A6 8D 38 62 16 90 30 5A 18 36 65 F9 BA 07 FC 00 56 38 18 74 BB F7 F1 4F 95 01 54 49 9D 6B 4D F2 66 55 13 87 A1 A6 95 74 72 6A D8 3A EA 34 A8 F8 40 5F 27 11 30 4F 96 3A 2E 7B E6 B6 47 3C 3B 4D 24 E8 FA 51 19 59 FB 52 E0 9B D2 24 B3 B5 8A 36 BF 34 20 E9 2A AB 5D 55 9B 60 01 D5 04 81 E8 E7 EC B2 5F 81 41

私钥P：
BF 36 08 66 63 74 6A 79 D0 77 64 21 73 6D 1A B9 13 BB 35 13 BE A6 73 84 C8 7D 83 67 BE C2 F5 0C 3A 7F 5F EF 6E 73 E2 BC 31 D2 0C 78 06 D7 38 85 7E F5 06 40 62 A6 1D 53 CC 97 34 30 58 EE E2 05

私钥Q：
B7 DD 46 99 58 B2 52 4B 87 FB E1 F1 09 44 AB 9A AD D1 93 90 9C 40 E0 2F 36 63 F4 7F 49 CB 36 E3 2C DA 85 5C 6E CE 41 AC CB 09 6C 27 B6 44 2B D8 26 5F D5 63 DF 2A C8 60 57 3B 23 13 2B 5F 65 C7

私钥DP：
A6 EF C4 9B A7 9E DE CA E5 2F 27 33 71 33 C3 0D EC 65 18 2C D9 D9 36 A7 A9 E6 B2 CF E3 A3 10 10 12 0E 5C B2 8C 2B 0E BC 21 7E F2 35 E4 3B 08 74 BC 67 AD 82 8E DD DA 62 EC 0E E2 98 87 3C 60 05

私钥DQ：
B6 A0 8B A7 75 7A 6A 53 AB D6 7D 2E 35 CE 87 C5 34 31 9F 29 5C 8A F4 22 F1 1B 87 97 87 6C DA 2F FC 35 71 91 C6 5E 08 CD E1 3E 92 B7 3F 4B A7 61 23 7C BD 30 5E 52 D8 85 19 20 1C 4E C6 1E 13 B1

私钥InvQ：
B4 12 D6 05 1C 2C 2B 6F B5 73 99 F3 B7 A7 08 6F A3 E8 2D 6F 33 A6 AE E5 BE 7B 89 86 7F 48 3B DD BC 4A 07 BF A4 A1 BB 96 BD 0E 46 F1 43 FA FB DE A0 1B AB 38 7D 49 59 45 EE 8C F9 3D 89 CF EB AC

明文：
11 22 33 44 55

签名数据：
56 E1 5E 29 84 D6 BC FB 87 7F 55 93 B4 E1 F3 75 2C 64 A5 BC 04 3A D7 0A DB 84 AD 8B 9C 4D D8 E6 8A 56 85 7B 2C 5E 50 E5 81 EB DC 40 D8 9A 29 64 54 19 5B F0 2B 77 D3 DB CF A2 17 BF 33 3F 19 19 B0 FF 36 53 D3 C2 36 1D 90 43 27 2C 0F 54 34 54 F7 E8 D2 09 75 E4 F1 A0 8B F5 38 EA 66 D6 53 14 E4 C5 B6 5A C7 74 52 6E 0A 16 C6 9B B7 81 0B 06 61 8A E7 41 BB 97 E6 EE 3E 6A 1C 7A E6 32 18 60

用公钥对上面的数据解密后得到：
30 20 30 0C 06 08 2A 86 48 86 F7 0D 02 05 05 00 04 10 28 3D 4F EA 5D DE D5 9C F8 37 D3 04 73 28 F5 AF

解析其TLV格式：
30 20 30 0C 06 08 2A 86 48 86 F7 0D 02 05 05 00 04 10 28 3D 4F EA 5D DE D5 9C F8 37 D3 04 73 28 F5 AF
第一级：
tag: 30(Sequence组合类型) 长度：20
内容：
30 0C 06 08 2A 86 48 86 F7 0D 02 05 05 00 04 10 28 3D 4F EA 5D DE D5 9C F8 37 D3 04 73 28 F5 AF

第二级：
tag: 30(Sequence组合类型) 长度：0C
内容：
06 08 2A 86 48 86 F7 0D 02 05 05 00

tag: 04(字符串类型) 长度：10
内容：
28 3D 4F EA 5D DE D5 9C F8 37 D3 04 73 28 F5 AF
正好就是明文数据11 22 33 44 55的MD5值。

第三级：
tag: 06(对象标识ObjectID) 长度：08
内容：
2A 86 48 86 F7 0D 02 05

tag: 05(空类型) 长度：00
内容：无

RSA每次基于不同的HASH算法对不同的数据进行签名时，构造的这一段BER数据的基本格式是固定不变的，只是HASH算法的OID和哈希值会变。

HASH算法的OID的编码

每个算法的OID都是固定的一串十进制数据，是国际权威组织定的。
比如MD5的OID 是 1.2.840.113549.2.5 ，
表示为”iso(1) member-body (2) US (840) rsadsi(113549) digestAlgorithm (2) md5 (5)”, 所以当解码程序看到这个OID时,就知道是MD5散列。

对OID的编码规则如下：
前两部分如果定义为x.y, 那么它们将合成一个字40*x + y, 其余部分单独作为一个字节进行编码。
每个字首先被分割为最少数量的没有头零数字的7位数字。

这些数字以big-endian格式进行组织,并且一个接一个地组合成字节。
除了编码的最后一个字节外,其他所有字节的最高位(位8)都为1。

以MD5举例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1.将1.2.840.113549.2.5转换成字数组 {42, 840, 113549, 2, 5}（因为前两部分定义为1.2，那么合成一个字40x1+2=42）

2.将每个字分割为带有最高位的7位数字。
42=42，只有一个7位数字,那么最高为0，结果为{0x2A}

840= 6*128^1+72，除最后一个字节外,其他字节的BIT8都置1，结果为{0x86,0x48}

113549=6*128^2+119*128^1+13，除最后一个字节外,其他字节的BIT8都置1，结果为{0x86,0xF7,0x0D}

2=2, 只有一个7位数字,那么最高为0，结果为{0x02}

5=5, 只有一个7位数字,那么最高为0，结果为{0x05}

最终结果为{{0x2A},{0x86,0x48},{0x86,0xF7,0x0D},{0x02},{0x05}}

3.加上TAG和LEN，得到OID编码为 0x06 08 2A 86 48 86 F7 0D 02 05

常见的HASH算法在用于RSA签名时的BER数据编码格式：

hash算法 十进制数据 BER数据编码
MD2 1.2.840.113549.2.2 30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 02 05 00 04 10
MD4 1.2.840.113549.2.4 30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 04 05 00 04 10
MD5 1.2.840.113549.2.5 30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 05 05 00 04 10
SHA1 1.3.14.3.2.26 30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14
SHA224 2.16.840.1.101.3.4.2.4 30 2D 30 0d 06 09 60 86 48 01 65 03 04 02 04 05 00 04 1C
SHA256 2.16.840.1.101.3.4.2.1 30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20
SHA384 2.16.840.1.101.3.4.2.2 30 41 30 0d 06 09 60 86 48 01 65 03 04 02 02 05 00 04 30
SHA512 2.16.840.1.101.3.4.2.3 30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40
SM3 1.2.156.197.1.504 30 30 30 0c 06 08 2a 81 1C 81 45 01 83 78 05 00 04 20

ECDSA签名

ECDSA签名和验签过程在上一篇文章中介绍过：
ECDSA非对称加密算法

ECDSA的签名是( r, s)两个数值，签名中直接以BER编码方式存储这两个值。
例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
signature:
['0x30', '0x65', '0x2', '0x30', '0x33', '0xdf', '0xb5', '0xb2', '0x8a', '0x8a', '0xd5', '0x49', '0x21', '0xe4', '0x50', '0xc0', '0xf6', '0x8a', '0x38', '0x58', '0xdb', '0xd8', '0x92', '0x7', '0x80', '0x41', '0x8b', '0xcc', '0xe8', '0xbb', '0xa9', '0x16', '0xf8', '0xf', '0xd', '0x32', '0x35', '0xa1', '0xdf', '0x24', '0xcd', '0xc8', '0x49', '0x86', '0x76', '0xad', '0xe1', '0x22', '0xe', '0xfa', '0xfb', '0x2', '0x2', '0x31', '0x0', '0xc9', '0x4b', '0xbb', '0xa1', '0xbe', '0xc', '0x2d', '0xc9', '0xfe', '0xfc', '0x6f', '0x60', '0xf3', '0x64', '0xe5', '0x7a', '0x2c', '0x50', '0x4f', '0x1f', '0xb0', '0xc8', '0x6d', '0x76', '0xbd', '0x37', '0x3b', '0x4f', '0xfb', '0x97', '0x27', '0x19', '0xe2', '0x4c', '0xf5', '0xee', '0xb2', '0x21', '0x91', '0x79', '0x69', '0x51', '0xd1', '0x45', '0x4f', '0x6f', '0xac', '0x28']

分析：
message_sign message:
SEQ
len: 101
content:
0x2,0x30,0x33,0xdf,0xb5,0xb2,0x8a,0x8a,0xd5,0x49,0x21,0xe4,0x50,0xc0,0xf6,0x8a,0x38,0x58,0xdb,0xd8,0x92,0x7,0x80,0x41,0x8b,0xcc,0xe8,0xbb,0xa9,0x16,0xf8,0xf,0xd,0x32,0x35,0xa1,0xdf,0x24,0xcd,0xc8,0x49,0x86,0x76,0xad,0xe1,0x22,0xe,0xfa,0xfb,0x2,0x2,0x31,0x0,0xc9,0x4b,0xbb,0xa1,0xbe,0xc,0x2d,0xc9,0xfe,0xfc,0x6f,0x60,0xf3,0x64,0xe5,0x7a,0x2c,0x50,0x4f,0x1f,0xb0,0xc8,0x6d,0x76,0xbd,0x37,0x3b,0x4f,0xfb,0x97,0x27,0x19,0xe2,0x4c,0xf5,0xee,0xb2,0x21,0x91,0x79,0x69,0x51,0xd1,0x45,0x4f,0x6f,0xac,0x28

INT
len: 48
content:
0x33,0xdf,0xb5,0xb2,0x8a,0x8a,0xd5,0x49,0x21,0xe4,0x50,0xc0,0xf6,0x8a,0x38,0x58,0xdb,0xd8,0x92,0x7,0x80,0x41,0x8b,0xcc,0xe8,0xbb,0xa9,0x16,0xf8,0xf,0xd,0x32,0x35,0xa1,0xdf,0x24,0xcd,0xc8,0x49,0x86,0x76,0xad,0xe1,0x22,0xe,0xfa,0xfb,0x2
int val:
7984118745046642712070940994226527427165301776521416471029518628654486337875805051425722475318955077043620618631938

INT
len: 49
content:
0x0,0xc9,0x4b,0xbb,0xa1,0xbe,0xc,0x2d,0xc9,0xfe,0xfc,0x6f,0x60,0xf3,0x64,0xe5,0x7a,0x2c,0x50,0x4f,0x1f,0xb0,0xc8,0x6d,0x76,0xbd,0x37,0x3b,0x4f,0xfb,0x97,0x27,0x19,0xe2,0x4c,0xf5,0xee,0xb2,0x21,0x91,0x79,0x69,0x51,0xd1,0x45,0x4f,0x6f,0xac,0x28
int val:
30982264106513726684219845244978923429128158159747238210412885484291235505874905425357164893263783009371945614421032

python 部分代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
解析signature到print输出:

    def print_sign_message(self,signature):
        ber_tag = BER_TAG().BER_Tag
        bytes_index = 0
        while bytes_index < len(signature):
            if signature[bytes_index] in ber_tag: 
                tag_index = signature[bytes_index]
                print(ber_tag[tag_index])
                bytes_index = bytes_index + 1
                tag_len = int(signature[bytes_index])
                print("len: " + str(tag_len))
                bytes_index = bytes_index + 1 
                print("content:")
                print(','.join([hex(i) for i in signature[bytes_index:bytes_index+tag_len]]))
                if tag_index == 0x02: # INT
                    print("int val:")
                    print(int.from_bytes(signature[bytes_index:bytes_index+tag_len], byteorder='big', signed=False))
                self.print_sign_message(signature[bytes_index:bytes_index+tag_len])
                bytes_index = bytes_index + tag_len
            else:
                break

解析signature输出[r,s]:

    def __decode_signature(self,signature):
        ber_tag = BER_TAG().BER_Tag
        bytes_index = 0
        while bytes_index < len(signature):
            if signature[bytes_index] in ber_tag: 
                tag_index = signature[bytes_index]
                #print(ber_tag[tag_index])
                bytes_index = bytes_index + 1
                tag_len = int(signature[bytes_index])
                #print("len: " + str(tag_len))
                bytes_index = bytes_index + 1 
                #print("content:")
                #print(','.join([hex(i) for i in signature[bytes_index:bytes_index+tag_len]]))
                if tag_index == 0x02: # INT
                    self.__sign_r_s.append(signature[bytes_index:bytes_index+tag_len])
                    #print("int val:")
                    #print(int.from_bytes(signature[bytes_index:bytes_index+tag_len], byteorder='big', signed=False))
                self.__decode_signature(signature[bytes_index:bytes_index+tag_len])
                bytes_index = bytes_index + tag_len
            else:
                break

    def decode_signature(self,signature):
        self.__sign_r_s = []
        self.__decode_signature(signature)
        return self.__sign_r_s

将[r,s]合并为signature:

    def encode_to_signature(self,r_bytes,s_bytes):
        if r_bytes[0] & 0x80:
            int_r = 0x02.to_bytes(1, byteorder= 'big') + \
            (len(r_bytes) + 1).to_bytes(1, byteorder= 'big') + \
            0x00.to_bytes(1, byteorder= 'big') + r_bytes
        else:
            int_r = 0x02.to_bytes(1, byteorder= 'big') + \
            len(r_bytes).to_bytes(1, byteorder= 'big') + r_bytes
        if s_bytes[0] & 0x80:
            int_s = 0x02.to_bytes(1, byteorder= 'big') + \
            (len(s_bytes) + 1).to_bytes(1, byteorder= 'big') + \
            0x00.to_bytes(1, byteorder= 'big') + s_bytes
        else:
            int_s = 0x02.to_bytes(1, byteorder= 'big') + \
            len(s_bytes).to_bytes(1, byteorder= 'big') + s_bytes 
        int_r_s = int_r + int_s
        return 0x30.to_bytes(1, byteorder= 'big') + len(int_r_s).to_bytes(1, byteorder= 'big') + int_r_s   

BER_TAG定义：

# -*- coding: UTF-8 -*-

__author__ = 'Mr.Bluyee'

class BER_TAG(object):

    """docstring for BER_TAG"""

    BER_Tag = {
        0x01 : "BOOL",  # BOOL
        0x02 : "INT",  # 整型
        0x04 : "OCTSTR",  # 字符串类型
        0x05 : "NULL",  # 空类型
        0x06 : "OBJID",  # 对象标识ObjectID（在这里就是对应的HASH算法的OID编码）
        0x0A : "ENUM",  # ENUM
        0x30 : "SEQ",  # Sequence组合类型
        0x31 : "SETOF",
        0x40 : "IPADDR",
        0x41 : "COUNTER",
        0x42 : "GAUGE",
        0x43 : "TIMETICKS",
        0x44 : "OPAQUE"
    }

    def __init__(self):
        super(BER_TAG, self).__init__()

附：
int数值的长度应等于对应的密钥参数的长度，
但在有些情况下，bytes最前面总会多一个0的原因：

密钥的长int型数据都是以big endian转为bytes。
有些值转为bytes，在bytes第一个字节，最高位上为1。
在有些默认处理signed的机器上，为了避免机器处理为负数，则又在前面添加了一个0，这样转换出来的数的最高位就不是1。当然，如果强制把该值处理为unsigned型，就没有这个问题。

部分内容整理自：
RSA签名验签学习笔记