基于编码的数字签名技术综述

来源:用户上传      作者:

　　摘要：为抵抗量子算法的攻击，编码密码技术成为了近期密码学领域的热点研究内容之一。将编码密码技术与数字签名技术有效的联系起来成为了当代密码学及信息安全领域研究的重要课题之一。本文首先对编码理论及相关基础知识做了一定的介绍，其次介绍了几种高级数字签名;最后分析了经典的CFS签名算法。
　　关键词：编码;数字签名;CFS签名
　　中图分类号：TP311 文献标识码：A 文章编号：1007-9416（2020）09-0186-04
　　0 引言
　　数字签名是信息安全技术中的重要组成部分，可应用于日常生活及商业、政治、军事等重大领域。1976年，Diffie和Hellman首次在“密码学新方向”一文中提出数字签名的概念，概念描述为签名人保存其私钥用于产生签名，公布其公钥用于验证签名。目前，存在RSA公钥数字签名、ECC椭圆曲线数字签名、ElGamal数字签名等很多种不同的数字签名，但是，随着数字签名技术的不断发展，盲签名、群签名等不同形式的高级数字签名相继出现，这些高级数字签名不仅拥有数字签名的基本性质，还具有其特殊性。虽然这些不同种类的数字签名算法都得到了广泛的应用，但是由于其多是基于数学困难问题构建的，无法有效的抵制量子攻击算法。因此，基于编码问题研究环签名、群签名等应用于特殊领域的数字签名技术具有非常重要的意义。
　　1990年西安电子科技大学的王新梅教授[1]首先尝试将编码问题用于数字签名技术。随后Courtois等学者于2001年利用线性分组码的译码困难问题构造了CFS（Courtois finasz sendrier）[1]数字签名算法，其签名是利用Hash函数对消息进行重复计算，直到输出可译码的校验子为止，该签名体制的安全性能够规约到McEliece问题，是真正严格意义上比较安全的基于编码的数字签名算法。2007年，Dallot[2]对CFS算法进行修正并给出安全性证明。2009年，Finiasz[3]等学者对CFS算法做了进一步的安全性分析，并给出新的安全参数。
　　此外，学者们也致力于基于编码问题研究各种不同应用领域的数字签名。2007年，郑东教授基于CFS签名算法提出了一种基于编码的环签名方案[4];同年，Cayrel等学者[5]首次利用编码问题实现了基于身份的数字签名方案。Overbeck于2009年基于QC码[6]首次提出了基于编码的盲签名方案，但由于其签名长度较长，实用性不高;同年Leonard等[7]学者提出了可证明安全性的基于编码的门限环签名，这是首次给出的可证明安全性的基于编码的数字签名方案。2013年，李泽慧等学者基于Niederreiter公钥体制[8]和McEliece公钥体制[9]提出了两种基于编码的盲签名方案。
　　本文首先介绍了基于编码的数字签名技术的相关基础知识，并对数字签名做了简单的概述，然后介绍了经典了CFS方案。
　　1 基础知识
　　1.1 编码基础
　　定义1：线性分组码（Linear block codes）有限域F2上的一个（n，k）线性分组码C是n维线性空间的一个k维子空间，C中的向量称为码字，n称为码长，k称为码的维数。
　　定义2：生成矩阵（generating matrix）与校验矩阵（parity check matrix）（n，k）线性分组码C的生成矩阵是一个k×n阶的矩阵G，其中G的行向量构成了C的一组基。校验矩阵是一个（n-k）×n阶的矩阵H，其中校验矩阵H的任意行向量与生成矩阵G的任意行向量正交，即HGT=0。
　　定义3：SD问题（Syndrome Decoding）给定有限域F2上的r×n矩阵H，字及整数，是否存在字满足且重量小于。
　　1.2 数字签名基础
　　数字签名（Data Signature），是一种可以为消息的接收者确认消息发送者的身份，并且可以验证消息完整性的算法方案，同时，签名及消息的真实性可由第三方验证。一个数字签名算法的基本结构如图1所示。
　　一个数字签名算法一般由签名人和验证者两个参与实体构成，通常包括3个算法，密钥生成算法、签名算法和验证算法：
　　（1）密钥生成：密钥生成算法是一个概率多项式时间算法，简记为keygen（k），系统输入安全参数k，输出签名人的公钥pk、私钥sk，其中，公钥pk公开，私钥sk交由签名人保密;
　　（2）签名：签名算法是一个概率多项式时间交互协议，简记为sign（sk，M），签名人用私钥sk对消息M进行签名，得到消息的签名σ;
　　（3）验证：验证者利用公钥pk验证消息的签名σ，简记为verify（pk，σ），输出“1”（表示签名有效）、“0”（表示签名无效）。
　　一个基本的数字签名算法，应满足以下几点：1）验证者应能验证消息内容及消息来源的真实性，并且可以验证签名人的身份;2）除签名人之外的任何人均不可伪造出消息的合法签名，签名人也不可否认其签名;3）当签名人和验证者对签名的真实性发生争执时，可在第三方（仲裁者）处对签名的真伪进行验证。
　　2 高级数字签名
　　数字签名技术在身份认证、匿名性及不可否认性等信息安全领域，特别是在电子商务、电子政务等需要计算机网络安全的领域都有着非常重要的作用，是信息安全的核心技术之一。随着电子商务、电子政务的不斷发展，出现了很多基于不同领域的高级数字签名，下面对其进行简要的介绍：
　　（1）盲签名（blind signature）：1982年，Chaum首次提出盲签名的概念。消息拥有者通过签名人获得消息的签名，而签名人只能证明自己对消息签过名，却无法得到消息的任何具体内容，也无法追踪消息与执行签名过程间的相互关系。如在电子交易中，货币的使用人实现电子交易，却不希望银行知道自己账户的信息以及变化详情，这就可以用到盲签名。 　　（2）群签名（group signature）：群签名的概念是Chaum和Heyst于1991年首次提出的。在一个群签名体制中，群体中的任一成员都可以代表整个群体以匿名的方式对消息进行签名，验证者只能确定签名是由群体中的某一成员产生的，但不知道具体是哪一个成员，即匿名性。当存在争议时，群管理员可通过打开签名查出签名人的实际身份，使签名人不可否认自己的签名，即可追踪性。另外，在不打开群签名的条件下，任何人不能确定两个群签名是否为同一群成员生成。
　　（3）环签名（ring signature）：环签名的概念是在群签名的基础上提出的，于2001年由Rivest等人在亚洲密码学年会上提出。在环签名体制中，签名人随意选取n-1人，连同自己一起构成一个n人的环，然后用自己的私钥和其他n-1人的公钥一起对消息进行环签名操作。由于环签名是环中成员自发进行的，体制中无法追踪签名人的身份，具有不可撤销的匿名性。
　　（4）基于身份的数字签名（IBS，Identity Based Signature）：1984年，Shamir提出了一种基于身份的密码思想，利用用户公开的身份信息计算或者由公开的身份信息通过公开的算法计算用户的公钥，由密钥生成器生成用户的私钥，并由用户自己保密，交互双方通过对方的身份信息加密或签名验证。
　　（5）民主群签名（democratic group signature）：民主群签名是一种特殊的群签名，由Manulis于2006年提出，民主群签名即群中的任意成员都可代表群体产生群签名，并且群体中的任意成员都可从群签名中恢复出该签名的群成员身份。
　　（6）具有消息恢复的签名：Nyberg和Rueppel于1994年提出了基于消息恢复签名方案，该签名可根据签名结果恢复被签名的消息。
　　（7）多重签名：Itakura等学者于1983年提出了一种特殊的数字签名，即多重签名，即多人参与对文件的签名，并分别对其进行签名。
　　除了以上数字签名外，还有不可否认签名、指定确认人签名等其他形式的数字签名，这些不同类型的数字签名也得到了学者的广泛关注。
　　3 基于编码的数字签名
　　目前基于编码的数字签名方案在一般数字签名、环签名等领域取得了一定的成果，如Courtois等学者提出的CFS签名方案，郑东教授提出的基于编码的环签名方案等。本节主要介绍经典的CFS签名算法，其安全性可以归结为一般译码问题和Goppa码与随机线性码的不可区分问题等NP困难问题。算法的具体过程如下所示。
　　3.1 初始化Setup
　　在有限域F2上选取一个m次既约多项式g（x），由多项式g（x）生成一个（n，k，t）既约Goppa码，其中n=2m为码长，k=n-mt为码的维数，t为码的纠错能力。码的（n-k）×n阶校验矩阵记为H0，对应的译码算法记为γ。随机选择的（n-k）×（n-k）阶非奇异矩阵U，n×n阶置换矩阵P，计算H=UH0P，H可看做（n，k，t）线性分组码C的（n-k）×n阶校验矩阵。公开公钥H，私钥U、P、H0、γ由签名人保密。
　　3.2 签名Sing
　　（1）签名人选择一个公开的哈希函数h，并对消息M进行哈希运算得到n-k长的序列s：s=h（M）;
　　（2）用哈希函数h计算n-k长的序列si：si=h（s|i），其中i=0，1，2…;
　　（3）签名人使用秘密的译码算法γ对si尝试译码，将最小的使si可译码的i记为i0，并将译出的字记作z，满足：HzT=si0，ω（z）=t;
　　（4）令i1i2…it为z中取值为1的位置标号，计算z的标号Iz：
　　（5）公开消息-签名对（M，σ）=（M，[Iz|i0]）。
　　3.3 验证Verify
　　（1）验证者收到（M，σ），根据消息M的哈希值h（M）和签名σ中的i0计算n-k长的序列s1：s1=h（[h（M）|i0]）;
　　（2）根据签名σ中的标号Iz恢复出z，将z左乘公钥H计算其校验子s2：s2=HzT;
　　（3）若s1=s2，则签名有效，否则签名无效。
　　由于签名时的平均译码尝试次数约为t！次，而一个快速有界译码算法在几分钟内即可完成约一百万次译码，则t的取值应不超过10（10！=3628800）[10]。因此，在Canteaut-Chabaud攻击下，可接受的安全强度为280次CPU运算，当t=10、n=215時，译码开销为287.4;当t=9、n=216时，译码开销为283.7，能够达到可接受的安全强度。
　　4 结语
　　基于编码的数字签名是目前可以抵抗量子算法攻击的一类数字签名，由于其安全性较高，受到了国内外研究学者们的重视。到目前为止，基于编码的数字签名的研究在不断发展，但是仍然不够成熟，具有很大的研究与应用的空间。本文即对基于编码的数字签名技术做了一个简单的综述介绍。
　　参考文献
　　[1] Xinmei W.Digital signature scheme based on error-correcting codes[J].Electronics Letters，1990，26（13）：898-899.
　　[2] Courtois，Matthieu Finiasz，Nicolas Sendrier.How to Achieve a McEliece-Based Digital Signature Scheme[C].Advances in Cryptology - ASIACRYPT 2001，International Conference on the Theory and Application of Cryptology and Information Security， Gold Coast，Australia，December 9-13，2001，Proceedings，2001. 　　[3] Dallot L.Towards a Concrete Security Proof of Courtois， Finiasz and Sendrier Signature Scheme[M].Research in Cryptology.Springer-Verlag，2008.
　　[4] Matthieu Finiasz，Nicolas Sendrier.Security Bounds for the Design of Code-Based Cryptosystems [C].Advances in Cryptology - ASIACRYPT 2009，International Conference on the Theory and Application of Cryptology and Information Security，Tokyo，Japan， December 6-10，2009.Proceedings，2009.
　　[5] Zheng D，Li X，Chen K.Code-based Ring Signature Scheme[J].Chinese Journal of Electronics，2007，16（3）：154-157.
　　[6] Cayrel P L，Otmani A，Vergnaud D.On Kabatianskii-Krouk-Smeets Signatures[C].Proceedings of the 1st international workshop on Arithmetic of Finite Fields.Springer-Verlag，2007.
　　[7] Dallot，Léonard，Damien Vergnaud.Provably Secure Code-Based Threshold Ring Signatures[J].Cryptography and Coding.Springer Berlin Heidelberg，2009（5）：222-235.
　　[8] 李澤慧，李子臣.基于Niederreiter公钥密码体制的盲签名方案[J].北京电子科技学院学报，2013，21（2）：50-55.
　　[9] 赵程程.基于McEliece公钥密码体制的盲签名算法研究[J].北京电子科技学院学报，2012，20（2）：32-38.
　　[10] 王倩，郑东，任方.基于编码的盲签名方案[J].计算机应用，2015，35（10）：2867-2871.
转载注明来源:https://www.xzbu.com/8/view-15348489.htm