1. 引言
前序博客有：
创新互联服务项目包括齐河网站建设、
齐河网站制作、齐河网页制作以及齐河网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，
齐河网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到齐河省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
- ECDSA VS Schnorr signature VS BLS signature 第3节“BLS签名”
私钥
p
k
pk
pk，对应的公钥为
P
=
p
k
×
G
P=pk\times G
P=pk×G。待签名消息
m
m
m。
BLS signature的签名流程为：
- 1）通过
H
(
m
)
H(m)
H(m)将消息
m
m
m映射为point on the curve，
G
m
=
H
(
m
)
G_m=H(m)
Gm=H(m)。
- 2）将私钥与
H
(
m
)
H(m)
H(m)相乘，
S
=
p
k
×
H
(
m
)
S=pk\times H(m)
S=pk×H(m)，
S
S
S即为相应的签名。
BLS signature is just one single point on the curve that takes only 33bytes in compressed serialization format。
具体如下图示意：
BLS的验签流程为：
- 1）通过
H
(
m
)
H(m)
H(m)将消息
m
m
m映射为point on the curve，
G
m
=
H
(
m
)
G_m=H(m)
Gm=H(m)。
- 2）验证
e
(
P
,
H
(
m
)
)
=
e
(
G
,
S
)
e(P,H(m))=e(G,S)
e(P,H(m))=e(G,S)成立即可。
具有pairing属性，以上验签等式恒成立：
e
(
P
,
H
(
m
)
)
=
e
(
p
k
×
G
,
H
(
m
)
)
=
e
(
G
,
p
k
×
H
(
m
)
)
=
e
(
G
,
S
)
e(P,H(m))=e(pk\times G,H(m))=e(G,pk\times H(m))=e(G,S)
e(P,H(m))=e(pk×G,H(m))=e(G,pk×H(m))=e(G,S)
具体如下图示意：
整个BLS signature非常简洁优美。
整个BLS签名算法中，有两个关键点是：
1）Hashing to the curve：
ECDSA和Schnorr 签名过程中，需要使用hash函数将消息
m
m
m映射为a number。
而BLS signature中需要调整hash算法，将消息
m
m
m hashes directly to the elliptic curve。
最简单的方式是，仍然将消息
m
m
m通过hash函数映射为a number，然后将该number作为elliptic curve 上point的x坐标。
Elliptic curves通常有
2
256
2^{256}
2256个points，采用SHA-256算法可以生成256-bit result。
但是对于
y
2
=
x
3
+
a
x
+
b
y^2=x^3+ax+b
y2=x3+ax+b形式的eclliptic curve，相同的x坐标，存在
(
x
,
y
)
和
(
x
,
−
y
)
(x,y)和(x,-y)
(x,y)和(x,−y)两个point均在curve上的情况。这就意味着借助SHA-256有约50%的概率能找到two points for some
x
x
x，有50%的概率找到point on the curve。
为了保证对任意的消息
m
m
m均能hashing to the curve，可以在消息
m
m
m后面追加数字，依次尝试直到能找到相应的curve point。如若
h
a
s
h
(
m
∣
∣
0
)
hash(m||0)
hash(m∣∣0)不能find a point，则依次试
h
a
s
h
(
m
∣
∣
1
)
,
h
a
s
h
(
m
∣
∣
2
)
hash(m||1),hash(m||2)
hash(m∣∣1),hash(m∣∣2)，直到找到point on the curve。【对于
(
x
,
y
)
和
(
x
,
−
y
)
(x,y)和(x,-y)
(x,y)和(x,−y)两个point，实际选择y坐标值更小的那个point。】（如上图所示）
2）curve pairing
BLS signautre要求能够将（相同或者不同）curve上的P和Q两个点映射a number：
e
(
P
,
Q
)
↦
n
e(P,Q)\mapsto n
e(P,Q)↦n
同时，应满足如下属性：（使得secret number
x
x
x unreveal。）
e
(
x
×
P
,
Q
)
=
e
(
P
,
x
×
Q
)
e(x\times P,Q)=e(P,x\times Q)
e(x×P,Q)=e(P,x×Q)
更通用的表达为应具有如下属性：
e
(
a
×
P
,
b
×
Q
)
=
e
(
P
,
a
b
×
Q
)
=
e
(
a
b
×
P
,
Q
)
=
e
(
P
,
Q
)
(
a
b
)
e(a\times P,b\times Q)=e(P,ab\times Q)=e(ab\times P,Q)=e(P,Q)^{(ab)}
e(a×P,b×Q)=e(P,ab×Q)=e(ab×P,Q)=e(P,Q)(ab)
Hashing to curve函数
H
H
H需为：
- indifferentiable from a random oracle
- 且为constant-time的
令
F
q
\mathbb{F}_q
Fq为某有限域，
E
b
:
y
2
=
x
3
+
b
E_b: y^2=x^3+b
Eb:y2=x3+b为某ordinary椭圆曲线（即，non-supersingular椭圆曲线），其
j
j
j-invariant为0，同时满足
b
∈
F
q
\sqrt{b}\in\mathbb{F}_q
b
∈Fq以及
q
≢
1
(
m
o
d
27
)
q\not\equiv 1(\mod 27)
q≡1(mod27)。
当前最快的constant-time indifferentiable hashing to
E
b
(
F
q
)
E_b(\mathbb{F}_q)
Eb(Fq)算法需要：
- 基于
F
q
\mathbb{F}_q
Fq的2次exponentiation运算【以BLS12-377为例，其基于highly 2-adic有限域，相应的indifferentiable Wahby-Boneh hash函数需要应用2次 slow Tonelli-Shanks algorithm算法来提取基域的2个平方根。】
在Dmitrii Koshelev 2021年论文 Indifferentiable hashing to ordinary elliptic
F
q
\mathbb{F}_q
Fq-curves of
j
=
0
j = 0
j=0 with the cost of one exponentiation in
F
q
\mathbb{F}_q
Fq 论文中，所实现的constant-time indifferentiable hashing to
E
b
(
F
q
)
E_b(\mathbb{F}_q)
Eb(Fq)算法：
- 仅需要1次exponentiation运算。【仍以BLS12-377为例，仅需要提取1次立方根，可 以有限域内的1次exponentiation运算来表示。】
开源实现见：
- https://github.com/dishport/Indifferentiable-hashing-to-ordinary-elliptic-curves-of-j-0-with-the-cost-of-one-exponentiation（Sage脚本）
- https://github.com/zhenfeizhang/indifferentiable-hashing（Rust，但非constant-time实现）
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享标题：Hashingtoellipticcurve算法改进-创新互联
URL标题：
http://cdkjz.cn/article/ceehoe.html
