一文读懂基于身份的数字签名算法

导语：本课堂用通俗易懂的系列内容为大家呈现区块链与密码学领域相关知识。这里有知识也有故事，从感兴趣到有乐趣，全民课堂等你来学。

这个系列中的课程内容首先从比特币着手进行入门介绍，再延伸至区块链的相关技术原理与发展趋势，然后深入浅出地依次介绍在区块链中应用的各类密码学技术。欢迎大家订阅本公众号，持续进行学习。

【本课堂内容全部选编自PlatON首席密码学家、武汉大学国家网络安全学院教授、博士生导师何德彪教授的《区块链与密码学》授课讲义、教材及互联网，版权归属其原作者所有，如有侵权请立即与我们联系，我们将及时处理。】

6.6

基于身份的数字签名算法

PKI是指由数字证书、证书颁发机构 (CA) 和证书注册机构(RA)组成的一套系统：

数字证书公钥和私钥

加密算法和摘要算法

证书链

受信任的根证书颁发机构——中级根证书颁发机构——用户证书

证书管理：申请、颁发、吊销、重新颁发、续期等

数字证书主要用途是绑定用户的身份和公钥，可以用于公钥加密、密钥写上、数字签名等领域。

证书的可靠性问题

从证书可靠性角度来评估中国互联网的安全性，中国互联网面临着三大安全风险：

：大部分重要系统没有部署SSL证书

例如：邮件系统、移动APP中的手机银行、移动社交软件

：部分重要系统都部署外国CA签发的SSL证书，如：银行网银证书、电子商务系统

例如：网上银行、证券交易所等

：一些重要系统部署了不安全的SSL证书

例如：12306购票系统、高校的VPN系统和各种需要登录的系统都在使用自签证书

证书的管理问题

CA体系从根证书开始，逐级签发各级证书，从而形成树状信任体系。

弊端：

难以构造复杂的身份标志体系

难以同步数字证书的撤销与数字签名的「作废」

数字证书的管理难度以及风险随系统规模的增大而增加

数字证书和私钥都需要载体，使用起来不方便

证书查找与证书验证的开销

层次化证书结构示意图

1984年，以色列密码学家Adi Shamir提出了基于身份的密码系统(Identity-based Cryptography, IBC)的概念，并设计了一个采用RSA算法的基于身份的数字签名算法。

密码学科普之Adi Shamir

Adi Shamir，以色列密码学家。他与罗纳德·李维斯特和伦纳德·阿德曼共同发明了RSA加密算法，他是差分密码分析的发明者之一，以及在密码学和计算机科学等领域做出许多杰出贡献而知名。RSA被广泛使用在计算机安全应用上，包括https。

2002年，他与罗纳德·李维斯特和伦纳德·阿德曼一起因在公钥密码学RSA加密算法取得的杰出贡献而获得。

在2001年，D.Boneh和M.Franklin，R.Sakai，K.Ohgishi和M.Kasahara利用椭圆曲线上的双线性对设计了基于身份的加密算法。

同年，C.Cocks利用平方剩余难题设计了基于身份的加密算法。D.Boneh和M.Franklin提出的IBC (BF-IBC)的安全性可以证明并且有较好的效率，引起了极大的反响。

算法构成

一个基于身份的数字签名算法由以下4个子算法构成：

初始化

输入：安全参数k

输出：系统参数params和主密钥master-key

用户私钥生成

输入：系统参数params、主密钥master-key和用户身份ID∈*

输出：用户私钥dID

签名

输入：系统参数params，消息M和签名者的私钥dID

输出：签名σ

验证

输入：系统参数params，签名σ，签名者公钥(身份)ID∈*, 消息M

输出：「Accept」或者「Reject」

Shamir提出了一个采用RSA算法的基于身份的数字签名算法：

初始化

选取两个大素数p，q，计算它们的乘积n；

选取与Φ(n)互素的整数e，计算主私钥d满足e×d=1 mod Φ(n)

选取一个单向函数h

输出系统参数：n, e, h；保存主密钥: n和d

用户私钥生成

给定用户的ID，PKG计算用户的私钥gID=h(ID)d mod n

签名

用户利用私钥gID执行如下步骤，签署消息m:

选取随机整数r，计算t=r e mod n；

计算s=gID×"r"h(t, m) mod n；

输出签名σ =

验证

验证者收到σ = ，消息m和签名者的公钥(身份ID), 验证下式是否成立

s e = h(ID) × "t "h(t, m) mod n

如果成立则输出「Accept」，否则输出「Reject」

效率

签名和验证都需要模幂(Modular Exponentiations)，模乘(Modular Multiplication) 和哈希运算(Hash Operation)

安全性

分解因子问题困难Integer Factorization Problem (IFP)