本帖最后由 迅雷链大学 于 2019-6-7 00:34 编辑
目录
1. 数字签名与验证
2. 数字签名算法模型
2.1. RSA签名与验证
2.1.1. 密钥生成算法
2.1.2. 签名算法
2.1.3. 验签算法
2.2. DSA算法
2.2.1. 密钥生成算法
2.2.2. 签名算法
2.2.3. 验签算法
2.3. ECDSA算法
2.3.1. 密钥生成算法
2.3.2. 签名算法
2.3.3. 验签算法
3. 数字签名算法的应用
3.1. 多重签名
3.2. 群签名
3.2.1. 群签名的安全性
3.2.2. 群签名的一般流程
3.3. 环签名
3.3.1. 环签名生成
3.3.2. 环签名验证
3.3.3. 群签名与环签名对比
1. 数字签名与验证
上节我们介绍到,在采用传统的Diffie-Hellman密钥协商算法的过程中,由于缺乏对消息发送方的验证,因此存在攻击者在中间篡改协商密钥的风险。这样的风险可以通过使用数字签名与验证来解决。
数字签名的作用主要是用来保证信息传输的完整性,对发送者的身份进行认证,并防止发送者对消息进行抵赖。具体来说,数字签名技术是将摘要信息用发送者的私钥加密,与原文一起传送给接收者。接收者只有用发送者的公钥才能解密被加密的摘要信息,然后用哈希函数对收到的原文产生一个摘要信息,与解密的摘要信息对比。如果相同,则说明收到的信息是完整的,在传输过程中没有被修改,否则说明信息被修改过,因此数字签名能够验证信息的完整性。
数字签名与验证基于公钥密码体制,公钥密码体制中包含一对公私钥。私钥作为签名密钥,公钥作为验证密钥。签名验证算法通常包含三个具体的算法函数,即密钥生成算法(KeyGen)、签名算法(Sign)和验证算法(Verify)。
密钥生成算法:(PK,SK)←KeyGen(λ)
密钥生成算法以安全常数λ作为输入,输出一个公钥PK和一个私钥SK。
签名算法:σ←Sign(SK,M)
签名算法以私钥SK和待签名的消息M作为输入,输出签名σ。
验证算法:b←Verify(PK,σ,M)
验证算法以公钥PK,签名σ和消息M作为输入,输出一比特的值b。b=1则签名验证通过,b=0则签名验证不通过。
消息签名示意图
2. 数字签名算法模型
数字签名算法模型中,最常用的模型包括RSA模型和DSA模型。对于数字签名,以至于推广到其所属的公钥密码体制,背后的安全理论基础在于利用了数学问题的难解性。RSA模型基于了大素数分解问题的数学难解性,而DSA模型基于离散对数问题的数学难解性。
2.1. RSA签名与验证
RSA签名与验证模型基于大素数分解问题的数学难解性,其算法流程是RSA签名算法的逆运算。具体的算法流程如下:
2.1.1. 密钥生成算法
· 生成公私钥对,公钥(e,n),私钥(d,n)
2.1.2. 签名算法
· 签名者计算待签名消息M的哈希,生成h(M)
· 签名者使用私钥(d,n)对h(M)签名,s=h(M)^d mod n
· 签名者将签名s,连同消息M一起发送给验签者
2.1.3. 验签算法
· 验签者接收到消息和附带的签名(s,M)
· 验签者计算消息的哈希h(M)
· 验签者使用签名者的公钥(n,e)对s进行验证,h(M)'=s^e mod n
· 比较h(M)和h(M)’是否相等,相等则证明签名是针对消息M的合法签名。
2.2. DSA算法
DSA算法模型基于离散对数问题的数学难解性。具体的算法流程如下:
2.2.1. 密钥生成算法
· 寻找质数参数p和q,满足g^q=1 mod p,其中g是有限域的生成元。
· 签名者随机选择私钥x,满足0<x<q
· 签名者计算公钥y=g^x mod p
2.2.2. 签名算法
· 签名者计算待签名消息M的哈希,生成h(M)
· 签名者选择随机数k,满足1<k<q
· 签名者计算r=(g^k mod p)mod q,若r=0则重新选择k进行后续操作
· 签名者计算s=k^(-1) (h(M)+xr)mod q,若s=0则重新选择k进行后续操作
· 签名者将签名(r,s),连同消息M一起发送给验签者
2.2.3. 验签算法
· 验签者接收到签名(r,s)和消息M
· 判断r和s的值是否满足0<r,s<q,如果不是则判定签名无效
· 计算w=s^(-1) mod q
· 计算u_1=h(M)∙w mod q
· 计算u_2=r∙w mod q
· 计算v=(g^(u_1 ) y^(u_2 ) mod p) mod q
· 比较r和v是否相等,相等则证明签名是针对消息M的合法签名。
2.3. ECDSA算法
ECDSA算法模型是ECC椭圆曲线算法和DSA算法的结合,是基于椭圆曲线域上离散对数问题的数学难解性。具体的算法流程如下:
2.3.1. 密钥生成算法
· 取椭圆曲线的基点G,椭圆曲线的阶为n,随机选择私钥d_A,满足0<d_A<n
· 公钥Q_A=d_A ×G
2.3.2. 签名算法
· 签名者计算待签名消息M的哈希,生成h(M)
· 签名者选择随机数k,满足1<k<n
· 计算k与基点G的乘积(x_1,y_1 )=k×G
· 计算r=x_1 mod n,如果r=0,则重新选择随机数k进行后续操作
· 计算s=k^(-1) (h(M)+rd_A ) mod n,如果s=0,则重新选择随机数k进行后续操作
· 签名者将签名(r,s),连同消息M一起发送给验签者
2.3.3. 验签算法
· 验签者收到消息和签名后,首先检验签名者的公钥Q_A是否是合法的椭圆曲线上的点,且不等于无穷远点。若验证失败则判定签名无效
· 判断r和s的值是否满足0<r,s<n,如果不是则判定签名无效
· 计算w=s^(-1) mod n
· 计算u_1=h(M)∙w mod q
· 计算u_2=r∙w mod q
· 计算(x_1,y_1 )=u_1×G+u_2×Q_A,如果(x_1,y_1 )等于无穷远点,则判定签名无效
· 判断r≡x_1 mod n是否满足,若满足则证明签名是针对消息M的合法签名。
3. 数字签名算法的应用
介绍完最基础的签名验证算法定义以及常用模型,我们就可以知道如何使用数字签名来保护消息的完整性了。但是,数字签名的功能还不局限于此,应用密码学家在数字签名的基础上,设计出了更多基于数字签名的应用,丰富了数字签名的应用场景并解决了更多现实的问题。
3.1. 多重签名
m-of-n多重签名
多重签名技术(Multi-Signature)就是多个用户同时对一个数字资产进行签名。可以简单的理解为,一个账户多个人拥有签名权和支付权。多重签名可以应用在单人多设备维护密钥或者多人共同维护密钥的场景中
如果一个地址只能由一个私钥签名和支付,表现形式就是1/1;而多重签名的表现形式是m/n,也就是说一共n个私钥可以给一个账户签名,而当m个地址签名时,就可以支付一笔交易。所以,m一定是小于等于n的。
3.2. 群签名
群签名是一种保护签名者隐私的签名技术。签名者在签名之前,首先组建一个签名群,由群管理员进行管理和签名证书的分发。随后,签名者在进行签名并发送给接收者之后,接收者只能得知签名来自群组中的一员,但无法具体定位到实际的签名人。
3.2.1. 群签名的安全性
完整性:有效的签名能够被正确验证
不可伪造性:只有群成员才能产生有效的群签名。其他任何人包括群管理员也不能伪造一个合法的签名。
匿名性:给定一个群签名后,对除了唯一的群管理员以外的任何人来说,确定签名者的身份是不可行的,至少在计算上是困难的。
可跟踪性:群管理员在发生纠纷的情况下可以打开一个签名来确定出签名者的身份,而且任何人都不能阻止一个合法签名的打开。
不关联性:在不打开签名的情况下,确定两个不同的签名是否为同一个群成员所签的是不可行的,至少在计算上是困难的。
没有框架:即使其他小组成员相互串通,也不能为不在组里的成员进行签名
不可伪造的跟踪验证:撤销管理员不能错误地指责签名者创建他没有创建的签名。
抵抗联合攻击:即使一些群成员串通在一起也不能产生一个合法的不能被跟踪的群签名。
3.2.2. 群签名的一般流程
1) 初始化
群管理者建立群资源,生成对应的群公钥(Group Public Key)和群私钥(Group Private Key)群公钥对整个系统中的所有用户公开,比如群成员、验证者等。
2) 成员加入
在用户加入群的时候,群管理者颁发群证书(Group Certificate)给群成员。
3) 签名
群成员利用获得的群证书签署文件,生成群签名。
4) 验证
同时验证者利用群公钥仅可以验证所得群签名的正确性,但不能确定群中的正式签署者。
5) 打开
群管理者利用群私钥可以对群用户生成的群签名进行追踪,并暴露签署者身份。为了保护签名者的隐私,这一步骤通常流程是不操作的。
流程如下图所示:
群签名流程示意图
3.3. 环签名
与群签名类似,环签名(Ring Signature)也是一种用于隐藏签名者身份信息的签名技术。签名的验证者只知道签名发起者是来自“环中”签名者中的一个,但不能确定具体来自哪一个。在环签名中只有环成员,没有管理者,不需要环成员之间的合作,签名者利用自己的私钥和集合中其他成员的公钥就能独立的进行签名,不需要其他人的帮助,集合中的其他成员可能不知道自己被包含在了其中。
环签名过程如下:
1) 密钥生成。为环中每个成员产生一个密钥对(公钥PKi,私钥SKi)
2) 签名。签名者用自己的私钥和任意n个环成员的公钥为消息m生成签名a
3) 签名验证。签名者根据环签名和消息m,验证签名是否是环中成员所签。如果有效就接收,如果无效就丢弃。
环签名流程示意图
环签名的核心在于利用了Trapdoor函数的特殊性质。Trapdoor函数指单向计算比较容易,但反向计算非常困难的函数。例如非对称密码算法中的RSA、ECC算法都可以被用作Trapdoor函数。私钥所有者利用Trapdoor函数生成签名的过程非常简单,但攻击者如果没有私钥,则很难伪造出具备环签名性质的合法签名。
具体的环签名使用流程如下。
3.3.1. 环签名生成
(假设我们是环中的第3个成员)
· 令k=hash(M), k是未来作为E_k对应的对称密钥
· 选取一个随机数v
· 选取n-1个随机数{x_1,x_2,x_4,…,x_n},并用过Trapdoor函数y_i=g_i (x_i )正向计算得到相应的{y_1,y_2,y_4,…,y_n}
· 令C_(k,v) (y_1,y_2,y_4,…,y_n )=v,计算得到满足等式成立的y_3,其中,C_(k,v)被称作Combining函数,计算过程如下:
环签名生成示意图
也就是说,初始随机数v和随后的所有的签名者的加密信息叠加异或操作。
· 将y_3看做利用公钥P_3加密得出的结果,那么利用私钥可以通过Trapdoor函数的逆向函数计算出y_3对应的x_3
· 最后,关于消息M的环签名是一个2n+1元组(P_1,P_2,P_3,…,P_n,v,x_1,x_2,x_3,…,x_n),其中P_1,P_2,P_3,…,P_n是环成员的公钥。外界在不知道私钥的情况下无法从这个签名中得知此签名是来自第3个成员签发的。
3.3.2. 环签名验证
· 通过公钥{P_1,P_2,P_3,…,P_n}利用正向Trapdoor函数计算出{x_1,x_2,x_3,…,x_n}对应的值{y_1,y_2,y_3,…,y_n}
· 计算E_k对应的对称密钥k=hash(M)
· 验证等式C_(k,v) (y_1,y_2,y_4,…,y_n )=v是否成立
3.3.3. 群签名与环签名对比
1) 匿名性:都是一种个体代表群体签名的体制,验证者能验证签名为群体中某个成员所签,但并不能知道为哪个成员,以达到签名者匿名的作用。
2) 可追踪性:群签名中,群管理员的存在保证了签名的可追踪性。群管理员可以撤销签名,揭露真正的签名者。环签名本身无法揭示签名者,除非签名者本身想暴露或者在签名中添加额外的信息。提出了一个可验证的环签名方案,方案中真实签名者希望验证者知道自己的身份,此时真实签名者可以通过透露自己掌握的秘密信息来证实自己的身份。
3) 管理系统:群签名由群管理员管理,环签名不需要管理,签名者只有选择一个可能的签名者集合,获得其公钥,然后公布这个集合即可,所有成员平等。
群签名和环签名都是用来保护签名发送者隐私的技术,在区块链中,除了保护发送者的隐私,还有其他的一些数据隐私也需要保护。这就将需要更多的密码学技术了,包括同态加密、零知识证明等。具体的技术将在下一节进行详细介绍。
|
|