Hashingtoellipticcurve算法改进-创新互联

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算法改进-创新互联
当前链接:http://bzwzjz.com/article/ceehoe.html

其他资讯

Copyright © 2007-2020 广东宝晨空调科技有限公司 All Rights Reserved 粤ICP备2022107769号
友情链接: 网站制作公司 重庆网站制作 网站建设方案 成都网站建设 高端网站设计 高端定制网站设计 成都响应式网站建设 网站建设公司 成都网站建设 响应式网站设计 成都网站设计 成都网站制作 宜宾网站设计 成都网站制作 成都网站建设公司 专业网站建设 温江网站设计 重庆网站建设 企业网站设计 企业网站设计 定制网站设计 成都网站制作