0
0

ECDSA安全性证明

本文主要对2021年CCS的论文《Efficient Online-friendly Two-Party ECDSA Signature》这篇论文方案进行简述，并对椭圆曲线数字签名进行了安全性证明

文章目录

前言

由于双方ECDSA签名在加密货币中广泛部署，因此受到了广泛关注。根据是否需要消息，我们可以将双方签名分为两个不同的阶段，即离线和在线。理想情况下，在线阶段应该尽可能地轻量级。同时，离线阶段的成本应该保持与正常签名生成的成本相似。然而，现有的ECDSA双向协议并不是最优的:它们的在线阶段需要对密文进行解密，或者离线阶段需要至少执行两次乘法到加法的转换，这在总体复杂度上占主导地位。本文提出了一种在线友好的两方ECDSA，该ECDSA具有轻量级的在线阶段和单一的乘加函数的离线阶段。

它是由密钥的再共享和nonce的线性共享的新颖设计构成的。该方案显著改进了以往基于无关传输和同态加密的协议。

背景知识

椭圆曲线密码学
私钥为d，其中d是集合{1,2,…,n-1}中的一个元素，其中n是子群的阶
公钥是一个点H=dG，其中G是子群的一个基点
根据d和G求H很容易，根据H和G求解d很困难（根据离散对数难解问题）
ECDH
首先，有两个实体Alice和Bob
Alice持有私钥

     d
    
    
     A
    
   
  
  
   d_A
  
 
dA​和公钥

 
  
   
    
     H
    
    
     A
    
   
   
    =
   
   
    
     d
    
    
     A
    
   
   
    G
   
  
  
   H_A=d_AG
  
 
HA​=dA​G

Bob持有私钥

     d
    
    
     B
    
   
  
  
   d_B
  
 
dB​和公钥

 
  
   
    
     H
    
    
     B
    
   
   
    =
   
   
    
     d
    
    
     B
    
   
   
    G
   
  
  
   H_B=d_BG
  
 
HB​=dB​G

此时Alice和Bob通过非安全信道交换公钥

     H
    
    
     A
    
   
  
  
   H_A
  
 
HA​和

 
  
   
    
     H
    
    
     B
    
   
  
  
   H_B
  
 
HB​

#mermaid-svg-K85Jqi937E7XEfBV {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-K85Jqi937E7XEfBV .error-icon{fill:#552222;}#mermaid-svg-K85Jqi937E7XEfBV .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-K85Jqi937E7XEfBV .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-K85Jqi937E7XEfBV .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-K85Jqi937E7XEfBV .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-K85Jqi937E7XEfBV .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-K85Jqi937E7XEfBV .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-K85Jqi937E7XEfBV .marker{fill:#333333;stroke:#333333;}#mermaid-svg-K85Jqi937E7XEfBV .marker.cross{stroke:#333333;}#mermaid-svg-K85Jqi937E7XEfBV svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-K85Jqi937E7XEfBV .actor{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-K85Jqi937E7XEfBV text.actor>tspan{fill:black;stroke:none;}#mermaid-svg-K85Jqi937E7XEfBV .actor-line{stroke:grey;}#mermaid-svg-K85Jqi937E7XEfBV .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333;}#mermaid-svg-K85Jqi937E7XEfBV .messageLine1{stroke-width:1.5;stroke-dasharray:2,2;stroke:#333;}#mermaid-svg-K85Jqi937E7XEfBV #arrowhead path{fill:#333;stroke:#333;}#mermaid-svg-K85Jqi937E7XEfBV .sequenceNumber{fill:white;}#mermaid-svg-K85Jqi937E7XEfBV #sequencenumber{fill:#333;}#mermaid-svg-K85Jqi937E7XEfBV #crosshead path{fill:#333;stroke:#333;}#mermaid-svg-K85Jqi937E7XEfBV .messageText{fill:#333;stroke:#333;}#mermaid-svg-K85Jqi937E7XEfBV .labelBox{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-K85Jqi937E7XEfBV .labelText,#mermaid-svg-K85Jqi937E7XEfBV .labelText>tspan{fill:black;stroke:none;}#mermaid-svg-K85Jqi937E7XEfBV .loopText,#mermaid-svg-K85Jqi937E7XEfBV .loopText>tspan{fill:black;stroke:none;}#mermaid-svg-K85Jqi937E7XEfBV .loopLine{stroke-width:2px;stroke-dasharray:2,2;stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);}#mermaid-svg-K85Jqi937E7XEfBV .note{stroke:#aaaa33;fill:#fff5ad;}#mermaid-svg-K85Jqi937E7XEfBV .noteText,#mermaid-svg-K85Jqi937E7XEfBV .noteText>tspan{fill:black;stroke:none;}#mermaid-svg-K85Jqi937E7XEfBV .activation0{fill:#f4f4f4;stroke:#666;}#mermaid-svg-K85Jqi937E7XEfBV .activation1{fill:#f4f4f4;stroke:#666;}#mermaid-svg-K85Jqi937E7XEfBV .activation2{fill:#f4f4f4;stroke:#666;}#mermaid-svg-K85Jqi937E7XEfBV .actorPopupMenu{position:absolute;}#mermaid-svg-K85Jqi937E7XEfBV .actorPopupMenuPanel{position:absolute;fill:#ECECFF;box-shadow:0px 8px 16px 0px rgba(0,0,0,0.2);filter:drop-shadow(3px 5px 2px rgb(0 0 0 / 0.4));}#mermaid-svg-K85Jqi937E7XEfBV .actor-man line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-K85Jqi937E7XEfBV .actor-man circle,#mermaid-svg-K85Jqi937E7XEfBV line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;stroke-width:2px;}#mermaid-svg-K85Jqi937E7XEfBV :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}
Alice

  Bob

A的公钥HA

B的公钥HB

都计算出dadbG

 Alice

 Bob

用ECDSA进行签名

要传递的信息m的截断哈希值z,
Alice：
选取一个随机数k，k是{1,2，…,n-1}中的一个元素
然后计算出点P=kG,
计算r=

     x
    
    
     p
    
   
  
  
   x_p
  
 
xp​mod n;

然后计算s=

     k
    
    
     
      −
     
     
      1
     
    
   
   
    (
   
   
    z
   
   
    +
   
   
    r
   
   
    
     d
    
    
     A
    
   
   
    )
   
  
  
   k^{-1}(z+rd_A)
  
 
k−1(z+rdA​) mod n

把（r，s）发送给Bob
Bob：
计算u1=

     s
    
    
     
      −
     
     
      1
     
    
   
   
    r
   
  
  
   s^{-1}r
  
 
s−1r mod n

计算u2=

     s
    
    
     
      −
     
     
      1
     
    
   
   
    z
   
  
  
   s^{-1}z
  
 
s−1z mod n

计算P=

     u
    
    
     1
    
   
   
    G
   
  
  
   u_1G
  
 
u1​G+

 
  
   
    
     u
    
    
     2
    
   
  
  
   u_2
  
 
u2​

 
  
   
    
     H
    
    
     A
    
   
  
  
   H_A
  
 
HA​

验证r=

     x
    
    
     p
    
   
  
  
   x_p
  
 
xp​ mod n是否成立，若成立则Alice签名有效

MtA

根据k和x的分量计算k的逆和k的逆乘x代价很高。所以利用k和x的乘法份额和加法同态加密方案Paillier，由此产生的签名程序只涉及同态操作和解密操作，可以降低通信代价。本篇论文引入了MtA函数，将乘法转化为加法共享运算。
但是MtA函数的证明需要使用零知识证明的知识。
调用两次MTA根据k的加法分量计算

     k
    
    
     
      −
     
     
      1
     
    
   
  
  
   k^{-1}
  
 
k−1的分量，再调用**两次MTA**根据

 
  
   
    
     k
    
    
     
      −
     
     
      1
     
    
   
  
  
   k^{-1}
  
 
k−1的分量和x的分量计算

 
  
   
    
     k
    
    
     
      −
     
     
      1
     
    
   
   
    x
   
  
  
   k^{-1}x
  
 
k−1x的分量

离线和在线签名

MPC可以分为在线和离线阶段，其中
离线阶段：计算和用户输入无关的消息，（预计算），减少在线阶段的计算量，提高通信效率
在线阶段：计算和用户消息相关的部分
如果在线阶段是非交互式的，并且其成本与单一签名验证相同，阈值签名的在线阶段是最佳的。如果该方案的在线阶段是最优的，则被称为在线友好方案
有些方案采用乘法共享以及加法同构特性，在线阶段需要解密密文，在线阶段不是最优。以前的协议要么需要相对缓慢的在线计算，要么在离线阶段需要调用2到4次MtA，而在线阶段是最佳的；但是这样总体方案的代价不是最佳，所以我们的目标：尽可能最少次数调用MtA，而且获得最优的在线性能

本文简介

提出了一个在线友好的双方ECDSA，即2ECDSA，这样它的在线计算几乎是最优的，而且它的离线阶段只需要调用一次MtA。

具体贡献

1.在线阶段最优
在线阶段是非交互式的，并且只需要传输一个单独的元素，所以在线阶段最优；
离线阶段只需要调用一次MtA
提出了两种新的分享方案：
①k=k1(r1+k2)
②x=x1’k2+x2’
2.具体实例化
在Rust中提供了我们的两方2ECDSA协议的实现，并对Paillier加密、CL加密和遗忘传输中的MtA功能进行了实例化
3.门限秘密共享
提出的两方ECDSA可以和门限秘密共享进行结合，从而实现2-n的ECDSA方案。

技术概述

出发点：使用简单的乘法共享和加法共享来实现双方ECDSA

第一次尝试

使用x的秘密重分享
具体来说，离线阶段：引入k2前, 原始状态：x=x1+x2
引入k2后，现在状态：x=x1’k2+x2’(调用一次MTA)
在线阶段：P2计算S2，P1根据s2,k1,x1’计算s在线阶段计算
更具体，在离线阶段：
P1选择x1’,P1和P2 调用MTA，分别输入x1’和k2, 输出结果为tA+tB=x1’*k2;
这之后，P1持有tA和x1,x1’; P2持有tB,x2
然后进行交互，P1向P2发送cc=tA-x1; 然后P2计算x2’=-tB-cc+x2;
这样就完成了x的重分享
安全分析：在这种情况下，x1=x1’k2-tB-cc,P2只需设置K2=0就可以得知x1，此时是不安全的

第二次尝试

主要思想：增加一个x1的掩码r1,在P2选择k2之后，P1选择一个随机数r1，从而满足x=x1’(k2+r1)+x2’,这样就可以排除k2=0对x1泄露的可能性

方案中双方交互流程

之后再对论文具体方案进行补充

原始ECDSA方案安全性证明

下面主要对原始ECDSA方案的安全性进行规约证明。
首先，要证明一个加密或者签名算法的安全性，最常见的做法是将其规约到一个数学困难问题上，又因为数学问题是难解的，所以说这个加密或者签名方案就是难以攻破的，从而证明其安全性。
对于ECDSA椭圆曲线签名方案来说，它是基于ECDLP问题的，即
私钥为d，其中d是集合{1,2,…,n-1}中的一个元素，其中n是子群的阶
公钥是一个点H=dG，其中G是子群的一个基点
根据d和G求H很容易，根据H和G求解d很困难
签名算法持有公钥和私钥，但是私钥是保密的，公钥是公开的；
下面介绍攻击模型，该模型包括一个敌手 A和算法 B，他们之间进行交互式游戏。算法B接收一个随机的 ECDLP问题实例 Y = xG，他的目标是计算出 x 。算法 B把敌手 A作为子程序，算法 B扮演敌手 A的挑战者。如果最后A能根据伪造的消息和签名求出k，那么说明解决了ECDLP问题。

具体证明流程：
（1）设置阶段：算法B将一些系统公共参数发送给A，然后算法B维护一张

     L
    
    
     h
    
   
  
  
   L_h
  
 
Lh​列表（*存放一些（消息，哈希值）对*），并初始化该列表为空，

（2）查询阶段：（敌手A可以向算法B查询消息m对应的哈希值和签名）
①哈希查询：
敌手A可以向B发送消息m以查询其对应的哈希值，最初

     L
    
    
     h
    
   
  
  
   L_h
  
 
Lh​列表为空，此时B对

 
  
   
    
     L
    
    
     h
    
   
  
  
   L_h
  
 
Lh​列表进行查询，

 
  
   
    
     L
    
    
     h
    
   
  
  
   L_h
  
 
Lh​列表不存在（m,e）,所以此时算法B**随机选择一个e∈{0,1}
 
  
   
    
     
     
      n
     
    
   
   
    ^{n}
   
  
 n**,返回给敌手A，并将对应（m,e）存入

 
  
   
    
     L
    
    
     h
    
   
  
  
   L_h
  
 
Lh​列表中；

后续进行查询时也是相同逻辑，算法 B首先检查消息 m是否已经出现在列表 LH中。若已存在，算法 B直接将 e返回给敌手 A;否则，算法 B从 {0，1} n中任意选择 e，并将(m，e)存储进

     L
    
    
     h
    
   
  
  
   L_h
  
 
Lh​列表中，然后将 e返回给敌手 A

特别地，在

     q
    
    
     h
    
   
  
  
   q_h
  
 
qh​次查询中，不能全都返回给敌手A随机数，要*随机选择*一个消息记为

 
  
   
    
     m
    
    
     ∗
    
   
  
  
   m^{*}
  
 
m∗,对于该消息 算法B通过查询**随机预言机**返回给敌手A消息

 
  
   
    
     m
    
    
     ∗
    
   
  
  
   m^{*}
  
 
m∗**真正的哈希值**

 
  
   
    H
   
   
    (
   
   
    
     m
    
    
     ∗
    
   
   
    )
   
  
  
   H(m^{*})
  
 
H(m∗)

②签名查询：（在该阶段，敌手A可以向算法B查询一些消息的对应签名）
签名查询。敌手 A向算法 B提交消息 m ，算法 B任意选择随机数 k ∈ ［1，n － 1］，然后计算 Ｒ =kG = (x1，y1) ，提取 r = x1 mod n 。算法 B在

     L
    
    
     h
    
   
  
  
   L_h
  
 
Lh​列表中

搜索(m，e) ，若列表 L中不存在(m，e)（说明敌手A并没有进行过哈希查询，如果此时返回签名则会被A察觉到不是真实执行） ，则返回符号“⊥”，查询终止;
否则，算法 B计算 s =

     k
    
    
     
      −
     
     
      1
     
    
   
   
    (
   
   
    H
   
   
    (
   
   
    m
   
   
    )
   
   
    +
   
   
    x
   
   
    r
   
   
    )
   
  
  
   k^{-1}(H(m)+xr)
  
 
k−1(H(m)+xr)mod n;然后，将签名结果(r，s)返回给敌手 A

（3）伪造阶段：（在此阶段，敌手A有效地伪造出消息

     m
    
    
     ∗
    
   
  
  
   m^{*}
  
 
m∗对应的签名（

 
  
   
    
     r
    
    
     ∗
    
   
  
  
   r^{*}
  
 
r∗,

 
  
   
    
     s
    
    
     ∗
    
   
  
  
   s^{*}
  
 
s∗））

若算法 B在查询阶段没有终止退出，那么敌手 A将以至少为 ε的优势输出伪造消息
m* 和有效伪造签名(e* ，s* ) 。由于敌手 A执行哈希查询的次数大于 1/

     q
    
    
     H
    
   
  
  
   q_H
  
 
qH​ ，所以敌手 A至少以**ε’ ＞ ε /
 
  
   
    
     
      q
     
     
      H
     
    
   
   
    q_H
   
  
 qH​的优势**计算出 k = 

 
  
   
    (
   
   
    
     s
    
    
     ∗
    
   
   
    
     )
    
    
     
      −
     
     
      1
     
    
   
  
  
   (s^{*})^{-1}
  
 
(s∗)−1 ( H(m)+xr ) ，从而 ECDLP问题被解决.

又因为ECDLP是困难问题，暂时没有多项式时间算法可以以不可忽略的优势ε来解决ECDLP问题，所以不存在能够在 t时间内以不可忽略的优势 ε攻破改进方案的敌手。因此，方案是安全的。

标签： 密码学 安全 网络攻击模型
本文转载自: https://blog.csdn.net/m0_58355879/article/details/127970557
版权归原作者 白开水呀呀 所有， 如有侵权，请联系我们删除。
登录后发布评论

“ECDSA安全性证明”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

Docker 中使用环境变量的安全实践

[Linux]——常见指令（中）

【IntelliJ IDEA】IntelliJ IDEA中文语言包不起作用

vscode gitlens收费破解

是时候用开源降低AI落地门槛了

毕设开源 深度学习手写数字识别系统(源码+论文)

毕业设计 大数据电商用户行为分析及可视化(源码+论文)

文章导航