椭圆曲线数字签名算法(ECDSA)签名R S值

微博:比特币布道者

时间:2023年9月10日

一、ASN.1编码

参考:ASN1编码学习 – 编程之家 (jb51.cc)

为了解决高级语言中结构化数据在网络传输中的结构关系能送达目的地进行还原,出现了以下几种数据序列化的方法:ASN.1,XML,Json等。

ASN.1本身只定义了表示信息的抽象句法,但是没有限定其编码的方法,它与语言实现和物理标识无关。各种ASN.1编码规则提供了由ASN.1描述其抽象句法的数据的值的传送语法(具体表达)。标准的ASN.1编码规则有基本编码规则(BER,Basic Encoding Rules)、规范编码规则(CER,Canonical Encoding Rules)、唯一编码规则(DER,distinguished Encoding Rules)、压缩编码规则(PER,Packed Encoding Rules)和XML编码规则(XER,XML EncodingRules)。

CER和DER,是后来从BER派生两种编码规则,这两种规则是BER规范的特例,因此BER解码器能编解码这两种规范编码规则的传输语法,反之则不然。CER针对不定长格式,而DER针对定长格式。因此CER常用在需要传输大量的数据的情况下。

DER适合安全数据传输,特别是数字签名方面。在电子商务上面也有独特的优势,适合传输平均大小的数据。

二、ECDSA签名

参考:https://blog.csdn.net/aaron67/article/details/109006985

1、创建数字签名

用私钥 a 对消息 m 签名,得到的结果是两个整数 ( r , s ),计算过程如下。

  • 随机生成临时私钥 k,并计算其对应的公钥 K = k ⋅ G = ( x_K , y_K )
  • 计算 r = x_K   mod   n,若 r为 0,则回到第一步
  • 计算消息 m 的哈希 e = hash ( m ),并将 e 的二进制序列转成一个整数
  • 计算 s = k^(− 1)( e + ra )   mod   n,若 s 为 0,则回到第一步
  • 得到签名 ( r , s )

上面的n是点G的阶,n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE BAAEDCE6AF48A03BBFD25E8CD0364141

3、验签

用公钥 A 和消息 m 验证签名 ( r , s ),过程如下。

计算消息 m 的哈希 e = hash(m),并将 e 的二进制序列转成一个整数

计算整数 u_1 = s^(-1)e mod n

计算整数 u_2 = s^(-1) mod n

计算点 P = u_1 ⋅ G + u_2 ⋅ A = ( x_P , y_P )

当且仅当 r = x_P mod n 时,验签成功

注:对 ECDSA 签名 ( r , s ) ,在验证时如果使用 ( r , − s   mod   n ) ,则也能验签成功,这涉及到比特币的延展性攻击,文章后面会提到。

4、签名序列化(DER编码)

参考:libsecp256k1比特币密码算法开源库(十三) – 代码天地 (codetd.com)

参考:qomo/ECDSA (gitee.com)

序列化签名与序列化公钥一样,公钥分别序列化x和y坐标,这里要对数字签名的两个不同的数字r和s编码(数字签名由256比特的r值和256比特的s值连接在一起构成)。
但是注意这里的r和s不具备像公钥x和y那样的对应关系(公钥的x坐标值代入到椭圆曲线方程中就可以得到y),因而只有公钥才有所谓的压缩公钥和未压缩公钥,Signature不能被压缩。

这里签名序列化的标准是DER (Distinguished Encoding Rules 可分别编码规则)格式。DER格式被中本聪采用作为序列化签名的方法。最可能的原因是这个标准在2008年确立,并且得到OpenSSL库(比特币当时使用的库)的支持。与其创造一个新的标准,不如简单地采纳适应已有标准。

DER签名格式如下定义:

1.0×30:前缀,是通用的格式。
2.0×44或0x45:编码剩余签名的长度。
3.0×02,表示后面是一个整数。
4.0×20或0x21:整数r的长度, 如果r的第一个字节大于等于0x80,则在r前置0x00。
5.r:以大端序编码r。
6.0×02,表示后面是一个整数。
7.0×20或0x21:整数s的长度, 如果s的第一个字节大于等于0x80,则在r前置0x00。
8.s:以大端序编码s。

步骤4和步骤7规定了待序列化的r和s第一个字节大于0x80的情况,因为DER是一个通用的编码规则(也就是说DER不止给比特币数字签名用),ASN.1 规定整型 INTEGER 需要支持正整数、负整数和零。BER/DER 使用大端模式存储 INTEGER,并通过最高位来编码正负数(最高位0为正数,1为负数)。

这样的话,如果r或s的第一位(二进制转换后的第一位) 为1就意味着数字为负数,而ECDSA的签名数据中的数字都为正数,所以如果密钥参数值最高位为 1,则 BER/DER 编码会在参数前额外加 0x00 以表示正数,这也就是为什么有时候密钥参数前面会多出1字节 0x00 的原因。

3、解锁脚本序列化之后

r和s是一个256比特的整数。大端序最多需要32字节来表示,因为第一个字节可能大于等于0x80, 所以步骤4和6生成的r和s最多有33个字节(r和s本来最多32字节,如果在前面加一个0x00就是33字节了)。但如果r和s是一个相对小的数字,可能小于32个字节就能表示它。

3045022100884d142d86652a3f47ba4746ec719bbfbd040a570b1deccbb6498c75c4ae24cb02204b9f039ff08df09cbe9f6addac960298cad530a863ea8f53982c09db8f6e381301

包含以下9个元素:

● 0x30表示DER序列的开始
● 0x45 – 序列的长度(69字节)
● 0x02 – 一个整数值
● 0x21 – 整数的长度(33字节:如果最高位是1,需要加前缀0x00)
● R- 00884d142d86652a3f47ba4746ec719bbfbd040a570b1deccbb6498c75c4ae24cb
● 0x02 – 接下来是一个整数
● 0x20 – 整数的长度(32字节)
● S- 4b9f039ff08df09cbe9f6addac960298cad530a863ea8f53982c09db8f6e3813
● 后缀(0x01)指示使用的哈希的类型(SIGHASH_ALL)

签名字符串长度最大是73(0x49)个字节,常见的是71(0x47)、72(0x48)、73(0x49)个字节。

三、关于”Low S values in signatures”规则

广播交易时报错:

sendrawtransaction RPC error: {“code”:-26,”message”:”non-mandatory-script-verify-flag (Non-canonical signature: S value is unnecessarily high)”}

参考:https://www.cnblogs.com/sword03/p/9324000.html

在BIP中描述如下:

–BIP62–
“Low S values in signatures

The value S in signatures must be between 0x1 and 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0 (inclusive). If S is too high, simply replace it by S’ = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 – S.”

即规定S的最大值是(n – 1) / 2,S的取值只在“低半段”。

关于”Low S values in signatures”的必要性,有一段解释如下:

“Absent this rule, any person is able to take a Bitcoin transaction, flip s in any of its signatures, and push the transaction out again with a different TXID. Being able to do this only changes the hash of the transaction, and does not alter its validity in any way. Being able to mutate transactions breaks a number of potentially interesting transaction types in Bitcoin like payment channels, where chains of transactions will suddenly be invalidated by a parent being mutated and an alternate form included in a block.

By forcing valid transactions to always have low s this ability is removed, though a person with the private key for a transaction is still able to mutate their own transactions by resigning them with a new nonce.”

简言之,其目的是,防止延展性攻击——恶意第三方通过修改transaction(按照以往ecdsa规则,修改后依然合法)影响区块链网络运行,同时依然保障私钥所有者生成多样transaction的能力。

相关文章:

比特币布道者

比特币的坚定信仰者!

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注