下载文档原格式
几种数字签名方案简介1、RSA数字签名方案RSA是最早公钥密码算法之一，由Ron Rivest、Adi Shamir和Leonard Adleman于1978年发明。
RSA数字签名方案基于大数分解难题，其安全性与RSA问题紧密相关。
在RSA数字签名方案中，发送方使用私钥对消息进行签名，接收方使用公钥验证签名。
2、DSA数字签名方案DSA数字签名算法由美国国家标准与技术研究院(NIST)提出，并被采纳为联邦数据处理标准(FIPS)。
DSA数字签名方案基于离散对数难题，其安全性主要依赖于有限域上的离散对数问题。
DSA算法相较于RSA 算法，具有签名长度短、速度快以及抗量子攻击等优点。
3、ECDSA数字签名方案ECDSA是椭圆曲线数字签名算法，其基于椭圆曲线密码学，是在有限域上的椭圆曲线离散对数问题的基础上构建的。
ECDSA数字签名方案相较于RSA和DSA算法，具有更高的安全性和更低的计算开销。
因为椭圆曲线密码学具有较高的安全性和较低的计算复杂性，所以ECDSA 被广泛应用于比特币等加密货币中。
4、EdDSA数字签名方案EdDSA数字签名算法是对标DSA的抗量子攻击算法，由欧洲电信标准化协会(ETSI)提出。
EdDSA使用的是Schnorr签名算法的一种变体，具有较高的安全性和抗量子攻击能力。
此外，EdDSA算法还具有速度快、签名长度短等优点。
以上几种数字签名方案都是目前广泛应用的算法，每种方案都有其特定的应用场景和优缺点。
在实际应用中，我们需要根据具体需求选择合适的数字签名算法以保证信息的安全性和完整性。
随着互联网的快速发展，数字签名方案在信息安全领域变得越来越重要。
数字签名方案用于验证信息的完整性、真实性和不可抵赖性，广泛应用于电子政务、电子商务和网络安全等领域。
无证书数字签名方案作为一种新兴的数字签名技术，因无需证书颁发机构颁发证书，具有降低成本、提高效率等优点，逐渐受到广泛。
本文将对几种无证书数字签名方案进行介绍，并对其安全性进行分析及改进。
第３１卷第２期北京电子科技学院学报２０２３年６月Ｖｏｌ．３１Ｎｏ．２ＪｏｕｒｎａｌｏｆＢｅｉｊｉｎｇＥｌｅｃｔｒｏｎｉｃＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＩｎｓｔｉｔｕｔｅＪｕｎ．２０２３隐私集合求交算法的对比分析∗田文亮㊀王志强㊀张艳硕北京电子科技学院，北京市㊀１０００７０摘㊀要：隐私集合求交（ＰｒｉｖａｔｅＳｅｔＩｎｔｅｒｓｅｃｔｉｏｎ，ＰＳＩ）属于隐私计算领域的特定应用问题，包括秘密共享㊁同态加密㊁不经意传输㊁混淆电路和Ｈａｓｈ技术等基础知识，其兼具重要的理论意义与极强的现实应用价值㊂随着用户数据的隐私保护需求的日益提升，ＰＳＩ可以在满足依赖个人信息的业务的便利性的同时最大程度保护个人信息私密性需求㊂本文首先介绍了隐私集合求交的研究现状，其次按照底层密码技术对ＰＳＩ进行分类并对比分析了它们的复杂度，对其优缺点进行对比分析，同时对比分析了基于不同密码技术的ＰＳＩ的使用场景，最后指出其发展方向并得出结论㊂关键词：隐私集合求交；秘密共享；同态加密；不经意传输；混淆电路；Ｈａｓｈ技术中图分类号：ＴＰ３１２㊀㊀㊀文献标识码：Ａ文章编号：１６７２－４６４Ｘ（２０２３）２－９８－１１２∗㊀基金项目：２０２２年基本科研业务费优硕培养项目 ＨＴＴＰ协议的流量拟态技术研究 （项目编号：３２８２０２２８０）； 信息安全 国家级一流本科专业建设点和２０２０年教育部新工科项目 新工科背景下数学课程群的教学改革与实践∗∗㊀作者简介：田文亮（１９９６－），男，研究生在读，计算机技术专业㊂Ｅ⁃ｍａｉｌ：１０７０２７４２８７＠ｑｑ．ｃｏｍ王志强（１９８５－），男，副教授，博士，硕导㊂Ｅ⁃ｍａｉｌ：ｗａｎｇｚｑ＠ｂｅｓｔｉ．ｅｄｕ．ｃｎ张艳硕（１９７９－），男，通信作者，副教授，博士，硕导，从事密码理论及其应用研究㊂Ｅ⁃ｍａｉｌ：ｚｈａｎｇ＿ｙａｎｓｈｕｏ＠１６３．ｃｏｍ１㊀引言㊀㊀隐私数据保护最早源于安全多方计算（ｓｅｃｕｒｅｍｕｌｔｉｐａｒｔｙｃｏｍｐｕｔａｔｉｏｎ，ＭＰＣ），由姚期智［１］借百万富翁问题提出，指各计算参与方无法得到除计算结果外的任何其他信息，解决互不信任的数据持有者如何对隐私数据进行计算的问题㊂隐私集合交集是安全多方计算中的热点问题，允许在分布式场景下各自持有隐私集合的参与方联合计算出集合交集而不泄露除交集以外的任何隐私信息㊂在隐私保护的场景中，ＰＳＩ协议具有重要意义，如新冠接触者追踪［２］㊁隐私通讯录查找［３］㊁在线广告实际效果计算［４］㊁基因序列匹配检测［５］等㊂传统的ＰＳＩ协议针对２个参与方设计，Ｍｅａｄｏｗｓ［６］基于公钥加密和利用Ｄｉｆｆｉｅ⁃Ｈｅｌｌｍａｎ密钥交换的乘法同态性质提出了第１个ＰＳＩ协议㊂随后，由Ｈｕｂｅｒｍａｎ等人［７］对Ｍｅａｄｏｗｓ［６］的方案做出了完整描述㊂２００４年由Ｆｒｅｅｄｍａｎ等人［８］借助不经意多项式求值和同态加密构造了第１个安全ＰＳＩ协议㊂２０１７年申立艳等人［９］对安全多方计算框架下的ＰＳＩ协议进行了简要总结㊂之后涌现了大量ＰＳＩ的研究成果，一大批新技术手段和构造框架被提出㊂除了传统的安全多方计算理论中的混淆电路（ｇａｒｂｌｅｄｃｉｒｃｕｉｔ，ＧＣ）㊁不经意传输（ｏｂｌｉｖｉｏｕｓｔｒａｎｓｆｅｒ，ＯＴ）㊁秘密共享（ｓｅｃｒｅｔｓｈａｒｉｎｇ，ＳＳ）㊁同态加密（ｈｏｍｏ⁃第３１卷隐私集合求交算法的对比分析㊀ｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎ，ＨＥ）等技术外，不经意伪随机函数（ｏｂｌｉｖｉｏｕｓｐｓｅｕｄｏ⁃ｒａｎｄｏｍｆｕｎｃｔｉｏｎ，ＯＰＲＦ）㊁经意多项式求值（ｏｂｌｉｖｉｏｕｓｐｏｌｙｎｏｍｉａｌｅｖａｌｕａｔｉｏｎ，ＯＰＥ）㊁布隆过滤器（Ｂｌｏｏｍｆｉｌｔｅｒ，ＢＦ）等集合元素比较技术的应用，使得ＰＳＩ的效率得到了很大的提高㊂现有ＰＳＩ已经非常高效，但现有很多实际应用中仍然以使用高效但存在安全隐患的解决方案为主，了解现有基于不同密码原语构建的ＰＳＩ及其特定适用场景，对促进实际场景中使用安全的方案替换存在隐患的方案有很大帮助㊂在敌手模型方面，研究人员从诚实且好奇的安全模型出发，开始考虑在恶意模型下安全的ＰＳＩ协议㊂随着研究人员对隐私集合交集协议的深入研究，除了传统两方ＰＳＩ协议之外，已衍生出了云辅助ＰＳＩ㊁阈值ＰＳＩ（ｔｈｒｅｓｈｏｌｄＰＳＩ，ＴＰＳＩ）㊁不平衡ＰＳＩ（ｕｎｂａｌａｎｃｅｄＰＳＩ，ＵＰＳＩ）和多方ＰＳＩ新型应用场景㊂本文全面的介绍了ＰＳＩ研究现状，对基于不同底层密码技术的ＰＳＩ算法进行了较为详尽的描述，对不同的ＰＳＩ协议原理进行对比分析，同时对ＰＳＩ协议的复杂度以及ＰＳＩ协议的优缺点进行了对比分析，得出了基于不经意传输的ＰＳＩ协议目前具有更高效率的结果㊂最后针对当前存在的问题，指出ＰＳＩ协议的发展方向以及结论㊂２㊀隐私集合求交的研究现状㊀㊀隐私集合求交（ＰＳＩ）协议有很多分类方法，按照底层依赖的密码技术分类主要包括：基于公钥密码的ＰＳＩ方案，包括：基于密钥交换（ＤＨ：Ｄｉｆｆｉｅ⁃Ｈｅｌｌｍａｎ）的ＰＳＩ方案和ＲＳＡ盲签名的ＰＳＩ方案；基于不经意传输的ＰＳＩ方案；基于通用ＭＰＣ的ＰＳＩ方案，例如基于混淆电路的ＰＳＩ方案；基于同态加密的ＰＳＩ方案；基于以上密码技术同时对多方ＰＳＩ进行描述㊂２ １㊀基于公钥密码的ＰＳＩ方案１９８６年，Ｍｅａｄｏｗｓ［６］提出了基于Ｄｉｆｆｉｅ⁃Ｈｅｌｌｍａｎ问题的ＰＳＩ协议，该协议类似于Ｄｉｆｆｉｅ⁃Ｈｅｌｌｍａｎ密钥协商协议㊂双方以各自的输入集合中的元素作为Ｄｉｆｆｉｅ⁃Ｈｅｌｌｍａｎ密钥协商中选择出的 随机数 角色，将集合元素映射到随机 会话密钥 空间，接收方在 会话密钥 空间中进行匹配，并获取到最终的交集元素；可以看出，该方案需要双方执行多次的模指数运算（这种代价很高的计算），因此所得的ＰＳＩ方案效率并不高㊂与基于杂凑函数的算法类似，同样可以在签名空间进行比对㊂例如基于盲签名，发起方盲化本方输入的每个元素，向响应方的请求盲签名，获得结果并去盲后得到响应方私钥的签名㊂同时，响应方签名本方的每个元素，并将结果发送给发起方；发起方比对双方的签名结果，获得交集结果㊂ＤｅＣｒｉｓｔｏｆａｒｏ与Ｔｓｕｄｉｋ［１７］在２０１０年提出了基于ＲＳＡ盲签名的ＰＳＩ协议㊂在该协议中，响应方随机产生ＲＳＡ密钥；发起方对本方的每一个输入元素进行随机盲化，将结果发送给响应方；响应方使用ＲＳＡ私钥对盲化结果进行签名并发送给发起方，同时将本方的输入元素用本方私钥进行签名，将结果发送给发起方；发起方对盲化的签名进行去盲，与响应方的签名进行比对，得出交集结果㊂基于公钥体制的方案除了转换匹配空间之外，将参与方输入的集合元素看作是多项式的根，多项式可以与输入集合建立映射关系，对于多项式的某些操作可以转换为集合的某些操作㊂２０２２年ＡｒａｎｈａＤＦ［３５］提出了一种新的两方简洁ＰＳＩ协议，该协议从理论和实践两个方面都以最小化发送方的开销为目标㊂该协议在概念上非常简单，这使得在实践中实现它不易出错：在协议执行期间，只发送两条消息，一条消息从接收方发送到发送方，另一条消息返回㊂接收者的消息的大小是单个组元素（独立于接收者的㊃９９㊃北京电子科技学院学报２０２３年输入集合的大小），而发送者的消息大小与发送者的输入集合大小成线性关系㊂发送方的计算复杂度与接收方输入集的大小无关㊂该协议为了证明新假设的合理性，证明了它在一般群体模型中是成立的㊂还讨论了在主动攻击存在的情况下保证隐私的简单对策，并提出了一个协议，该协议提供了完全基于模拟的安全性来对抗主动攻击㊂２ ２㊀基于不经意多项式计算的ＰＳＩ方案不经意多项式计算的ＰＳＩ协议主要是将参与方集合元素表示为多项式的根，利用多项式的数学性质来计算交集，并采用同态加密算法加密交互过程中的信息来保证协议的隐私㊂最早由Ｆｒｅｅｄｍａｎ等人在２００４年提出的ＰＳＩ协议［８］就是不经意多项式计算的ＰＳＩ协议㊂其协议的主要过程为：客户端生成同态加密密钥对（ｐｋ，ｓｋ）并发送公钥给服务器端，将输入集Ｘ＝｛ｘ１，ｘ２， ，ｘｖ｝表示为多项式Ｐ的根Ｐ（ｚ）＝（ｘ１－ｚ）（ｘ２－ｚ） （ｘｖ－ｚ）＝ðｖｕ＝０ａｕｚｕ，利用插值法求得多项式系数｛ａ１，ａ， ，ａｖ｝，将多项式系数用Ｐａｉｌｌｉｅｒ［１３］或ＥＩＧａｍａｌ［１５］同态加密算法加密发送给服务器端；服务器端输入集合为Ｙ＝｛ｙ１，ｙ２， ，ｙｗ｝对集合中的每一个元素ｙ，利用同态加密性质计算Ｅｎｃ（ｒ．Ｐ（ｙ）＋ｙ），并将计算的密文混淆发送给客户端；客户端解密所有的密文，依次判断解密的结果是否和输入集合Ｘ中的某一元素ｘ相等，相等则说明ｘ属于集合交集㊂该协议中，多项式的次数过高，会导致同态加密运算中指数的计算代价太大㊂因此作者又采用Ｈａｓｈ函数将集合中元素映射到Ｂ个桶中，每个桶最多Ｍ个元素，在客户端生成Ｍ个低次多项式，服务器端采用同样的Ｈａｓｈ函数将元素进行映射，客户端将相对应的桶里的元素和多项式进行集合交集判断；为了减小Ｍ的值，作者采用了负载均衡Ｈａｓｈ［２１］方法㊂２０１４年Ｆｒｅｅｄｍａｎ等人进一步在文献［８］的基础上改进ＰＳＩ协议［３１］，客户端和服务器端分别采用不同的Ｈａｓｈ函数将集合元素进行映射来减少协议的计算复杂度，并将随机Ｈａｓｈ㊁负载均衡Ｈａｓｈ㊁布谷鸟散列［２２］进行实验对比，其中应用负载均衡Ｈａｓｈ㊁布谷鸟散列进行集合元素计算的复杂度较低㊂以上协议被证明在标准模型下对半诚实敌手是安全的㊂２ ３㊀基于不经意传输的ＰＳＩ方案不经意传输是密码协议体系中的一个基础协议，由Ｒａｂｉｎ于１９８１年提出［２３］㊂与最原始的概念相比，在更标准化的定义中，发送方拥有若干个输入，接收方输入一个索引下标，该索引下标表示接收方想要得到的结果，在协议过程中这一指标并不会泄露给发送方㊂最基础的ＯＴ协议是２选１ＯＴ㊂基于ＯＴ的ＰＳＩ协议需要使用的ＯＴ运行实例的数量与ＰＳＩ双方输入的集合大小有关系，因此ＯＴ协议成为大集合ＰＳＩ方案的主要瓶颈㊂ＯＴ扩展协议的出现［１３］，使得大集合ＰＳＩ方案的落地成为现实㊂所谓ＯＴ扩展协议是指，ＯＴ协议在并行数量方面的扩展㊂具体来说，是用少量的ＯＴ协议实例来构造较为大数量的ＯＴ协议实例㊂文献［１４－１６］给出了ＯＴ扩展的相关理论结果与实现改进㊂２０１３年，Ｄｏｎｇ等人在文献［２４］中第一次将布隆过滤器引入到ＰＳＩ中，并与ＯＴ扩展结合，使得ＰＳＩ协议能处理的集合数量首次突破了亿级别㊂此后，对于布隆过滤器的改进也成为优化ＰＳＩ协议的一个重要方向㊂通过改进布隆过滤器，Ｒｉｎｄａｌ和Ｒｏｓｕｌｅｋ给出了第一个恶意模型下的ＰＳＩ协议［２５］，这一方案也在２００ｓ时间内完成了两方百万数据量的安全求交㊂２０１６年，在文献［２６］中，Ｋｏｌｅｓｎｉｋｏｖ等人使用ＯＴ扩展来实现不经意伪随机函数，并且将此概念运用到ＰＳＩ中，这也成为后续基于不经意传输的ＰＳＩ协议的主要方向㊂以上所有ＰＳＩ协议的实现几乎都是在两个参与方的场景㊂对于多个参与方的场景，文献［２７］中Ｋｏｌｅｓｎｉｋｏｖ等人引入㊃００１㊃第３１卷隐私集合求交算法的对比分析㊀了不经意的可编程伪随机函数的概念（Ｐｒｏｇｒａｍ⁃ｍａｂｌｅＯｂｌｉｖｉｏｕｓＰｓｅｕｄｏｒａｎｄｏｍＦｕｎｃｔｉｏｎｓ，ＯＰ⁃ＰＲＦ），并且基于插值多项式㊁布隆过滤器等技术实现ＯＰＰＲＦ㊂ＯＰＰＲＦ要求只对发送者编程进去的集合元素，接收者才可以进行不经意地函数取值，未编程进去的元素，接收者返回随机值㊂各个参与方之间顺次循环扮演发送方和接收方角色，最终完成交集的结果㊂２０２２年，李顺［４８］提出了一种基于并行化ＯＰＰＲＦ的隐私集合交集协议㊂２０２２年，魏立斐等人［４９］提出了基一种于云服务器的公平多方隐私集合交集协议，该协议基于该不经意伪随机函数构建了半可信云服务器辅助的隐私集合交集计算协议，将主要计算量外包给云服务器，允许半可信的云服务器参与相等性测试，又不泄露参与方任何集合信息㊂２ ４㊀基于同态加密的ＰＳＩ方案ＰＳＩ根据参与者的数量可分为两方和多方，下面均以两方为例㊂假设参与ＰＳＩ的两方为发送方Ｓ（Ｓｅｎｄｅｒ）和接受方Ｒ（Ｒｅｃｅｉｖｅｒ），分别持有数据集Ｘ和Ｙ㊂根据两方数据集大小的不同，分为平衡场景和非平衡场景㊂在平衡场景下，双方样本数量相差不大，适用于双方客群有较多重叠的场景，如集团子部门之间的安全求交场景；在非平衡场景下，双方样本数量相差非常大，如营销场景中筛选本机构种子用户与外部数据方海量用户群中的共有用户群，实现目标客群筛选㊂在平衡场景中，ＰＳＩ的实现方式目前较为成熟的有基于ＲＳＡ㊁基于Ｄｉｆｆｉｅ⁃Ｈｅｌｌｍａｎ（ＤＨ）和基于不经意传输等㊂综合安全性㊁效率和通信量考虑，基于ＯＴ以及ＯＴＥｘｔｅｎｓｉｏｎ［４１］系列的对齐方案被广泛使用㊂在非平衡场景中，可在基于ＯＴ的ＰＳＩ方案基础上，将同态加密技术结合特定的优化方法，实现高效的ＰＳＩ㊂下面介绍两种高效的基于同态加密的非平衡ＰＳＩ方案㊂２０１７年，Ｃｈｅｎ等［４６］在ＣＣＳ２０１７中将同态加密应用到非平衡ＰＳＩ中，综合使用了Ｃｕｃｋｏｏｈａｓｈ㊁Ｐａｒｔｉｔｉｏｎ㊁Ｗｉｎｄｏｗ和ＭｏｄｕｌｕｓＳｗｉｔｃｈ技术㊂实验表明，在数据量为ＮＸ＝５０００，ＮＹ＝１６００万时，Ｃｈｅｎ在ＣＣＳ２０１７［２８］中提出的方案的通信量为１２ ５ＭＢ，求交时间为３６ｓ㊂２０１８年，Ｃｈｅｎ等［４６］改进了ＣＣＳ２０１７方案，提出了一个能抵抗恶意攻击的非平衡ＰＳＩ方案（ＣＣＳ２０１８［２９］）㊂与ＣＣＳ２０１７［２８］方案相比，该方案支持更高位（５１２位和１０２４位）的Ｉｔｅｍ（ＣＣＳ２０１７方案支持３２位），改进了ＳＩＭＤ编码，在不增加加密参数的前提下，提升了效率和安全性㊂该方案较ＣＣＳ２０１７方案在性能上做出很大改进，在数据量为ＮＸ＝２２４和ＮＹ＝５５３５时，ＣＣＳ２０１７方案需要２０ＭＢ的通信量和４０ｓ的在线计算时间，ＣＣＳ２０１８通信量为１６ＭＢ，在线计算时间为２２ｓ（单线程），运行时间几乎缩短２倍和通信量节约２７％㊂此外，当接受方Ｒ的数据集更小时，ＣＣＳ２０１８方案的同态加密的参数会更小，能进行更少的密文计算，当接受方Ｒ的数据量为５１２或１０２４时，该方案运行时间分别只需９ １ｓ和１７ ７ｓ，以及８ ２ＭＢ的通信量，较ＣＣＳ２０１７方案快２ ４倍，发送的数据量降低一半，同时支持任意长度的Ｉｔｅｍ㊂２ ５㊀其他根据底层密码学技术对传统多方ＰＳＩ进行梳理，主要分为基于公钥的多方ＰＳＩ和基于ＯＴ的多方ＰＳＩ，由于混淆电路在预计算阶段构造复杂，且内存占用较高，并没有基于混淆电路的传统多方ＰＳＩ协议的研究，但又鉴于混淆电路可以方便地计算任何功能函数的特性，其更适用于构造门限等特殊场景下的多方ＰＳＩ协议㊂基于公钥的多方ＰＳＩ方案主要采用同态加密技术㊂第１个基于同态加密技术的多方ＰＳＩ协议方案由Ｆｒｅｅｄｍａｎ等人［８］提出，首先使用加法同态加密实现的ＯＰＥ技术，将集合元素表示为多项式的根从而代替集合进行运算，实现了在半诚实敌手模型下的两方ＰＳＩ，其次提出了针对恶意的客户端㊁恶意的服务端㊁恶意的两方以及多方的情况下的ＰＳＩ协议的构造思路㊂在半诚㊃１０１㊃北京电子科技学院学报２０２３年实敌手模型中，Ｋｉｓｓｎｅｒ等人［１９］在２００５年对加法同态加密的私钥进行秘密共享，协议的计算复杂度和通信复杂度是集合大小和参与方数目的２次方㊂２０１７年，Ｈａｚａｙ等人［４４］使用星型通信模型将多方ＰＳＩ协议的通信轮数从Ｏ（ｎ）降低为Ｏ（１），且加解密的操作数与参与方集合大小呈线性关系㊂其中，星型通信结构是最直观的多方通信结构，多个参与方与同一个中心参与方进行交互，此结构对中心参与方的带宽和计算能力要求较高㊂基于ＯＴ协议的多方ＰＳＩ协议主要分为两种，一是使用ＯＴ协议构造ＯＰＲＦ㊁ＯＰＰＲＦ㊁多点ＯＰＲＦ等一系列协议，而后基于ＯＰＲＦ系列协议构造多方ＰＳＩ协议；二是多方直接使用ＯＴ协议进行数据传输㊂基于ＯＰＲＦ的多方ＰＳＩ协议中最经典的同时也是首篇将多方ＰＳＩ进行代码实现的协议为Ｋｏｌｅｓｎｉｋｏｖ等人［４２］在２０１７年提出的方案㊂该文献首次提出了使用ＯＰＲＦ构造ＯＰＰＲＦ的概念，旨在使用发送方的输入来对ＯＰＲＦ的密钥进行编程，其与单点ＯＰＲＦ的区别在于ＯＰＰＲＦ中密钥与发送方的私有集合元素相关㊂在直接使用ＯＴ协议作为数据传输协议方面，２０１８年，Ｉｎｂａｒ等人［４５］在半诚实敌手模型和增强的半诚实敌手模型中分别提出了两种多方ＰＳＩ协议，是对Ｄｏｎｇ等人［２４］两方ＰＳＩ协议的扩展㊂Ｉｎｂａｒ等人的协议［４５］与Ｋｏｌｅｓｎｉｋｏｖ等人的协议［４２］相比的优势在于随着参与方数目的增多，协议消耗时间增长缓慢，与参与方数目呈次线性关系；而Ｋｏｌｅｓｎｉｋｏｖ等人的协议［４２］的最后一个步骤中需要多次计算和比较，计算开销较大㊂由于混淆电路具有计算任何功能函数的特性，可以方便地设计多功能的安全计算协议，因此基于混淆电路的门限多方ＰＳＩ也是研究方向之一㊂２０２１年，Ｃｈａｎｄｒａｎ等人［４６］提出了半诚实敌手模型下的多方ＰＳＩ协议，并设计了两种变体协议，门限多方ＰＳＩ便在其研究范围中㊂协议主要分两部分，首先选择一个特定参与方与其他所有参与方两两交互进行元素相等性判断，此后所有参与方交互通过电路计算结果㊂近年来涌现了很多基于云辅助器的ＰＳＩ协议［４９－５２］，由于在日常生活中数据量庞大，因此借助云辅助器的方案可能是我们以后研究的重点㊂本文对以上基于不同密码技术的ＰＳＩ协议现状进行了总结，不仅对每一种ＰＳＩ协议的历史发展进行描述，而且说明其特点及基本使用场景㊂３㊀ＰＳＩ算法原理的对比分析㊀㊀ＰＳＩ算法既可以有两方参与，又可以有多方参与，以下分别对两方㊁多方以及不经意伪随机函数等ＰＳＩ原理进行对比分析㊂３ １㊀两方ＰＳＩ基本原理算法参与方包括Ｓｅｒｖｅｒ和Ｃｌｉｅｎｔ，假设ｓｅｖｅｒ和ｃｌｉｅｎｔ输入元素个数分别为ｋｓ和ｋｃ，ｓｅｒｖｅｒ方输入元素记为ｙｉ，ｉɪ［１，ｋｓ］，ｃｌｉｅｎｔ方输入元素记为ｘｉ，ｉɪ［１，ｋｃ］；２）基于公钥加密技术的加法同态加密算法Ｅｎｃ（ｘ）㊁Ｄｅｃ（ｃ）满足Ｅｎｃ（ｍ１＋ｍ２）＝Ｅｎｃ（ｍ１）＋Ｅｎｃ（ｍ２）（ｋｍ）＝ｋ（ｍ）１）ｃｌｉｅｎｔ方针对全部输入元素利用插值法构造如下多项式Ｐ（ｙ）＝ðｋｃｉ＝１（ｙ－ｘｉ），显然该多项式的最高次数为ｋｃ，用系数表示为Ｐ（ｙ）＝ðｋｃｉ＝０（ａｉｙｉ）㊂然后将全部系数进行加密后发送给ｓｅｒｖｅｒ；２）ｓｅｒｖｅｒ针对每一个ｙｉ进行如下计算：选择随机数ｒｉ计算Ｃｉ＝Ｅｎｃ（ｒｉＰ（ｙｉ）＋ｙｉ，并将Ｃｉ发送给ｃｌｉｅｎｔ；３）ｃｌｉｅｎｔ进行如下验证：对Ｃｉ进行解密得到ｍｉ＝ｒｉＰ（ｙｉ）＋ｙｉ㊂如果ｙｉ和某个ｘｉ相等，则ｒｉＰ（ｙｉ）为０，解密结果ｍｉ必定等于该ｘｉ，即为ＰＳＩ结果之一，如果ｙｉ不等于任一ｘｉ，则解密结果ｍｉ是一个随机数㊂３ ２㊀多方ＰＳＩ基本原理在２方ＰＳＩ算法基础上可以扩展到多方㊃２０１㊃第３１卷隐私集合求交算法的对比分析㊀ＰＳＩ㊂具体原理如下：１）假定ｎ＋１个参与方，记为Ｌｌ，ｌɪ［１，ｎ＋１］，第Ｌｎ＋１为ｌｅａｄｅｒ；２）对前面ｎ个参与方Ｌｌ，ｌɪ［１，ｎ］，生成各自的同态加密算法公私钥公钥ｐｋｌ和私钥ｓｋｌ，公开公钥ｐｋｌ；３）对前面ｎ个参与方Ｌｌ，ｌɪ［１，ｎ］，针对已方全部元素ｘｌｉ生成自己的多项式Ｐｌ（ｙ），并将多项式参数进行加密（使用公钥ｐｋｌ）后发送给ｌｅａｄｅｒ；４）Ｌｅａｄｅｒ针对己方每个元素ｙｉ进行如下操作：生成ｎ个随机数ｓｌｊ，ｌɪ［１，ｎ］，确保 ｎｉ＝１ｓｌｊ＝ｙｊ，然后针对ｎ个参与方Ｌｌ的每一方计算密文Ｃｌｊ＝Ｅｎｃ（ｒｌｊＰ（ｙｊ）＋ｙｊ），然后将全部Ｃｌｊ发送给Ｌｌ；５）对前面ｎ个参与方ＬＬ，ｌɪ［１，ｎ］，解密Ｃｌｊ得到ｍｌｊ，并将已方解密出来的ｍｌｊ全部公开：６）对前面ｎ个参与方Ｌｌ，针对收到的全部ｍｌｊ进行计算ｙｊ＝ ｎｌ＝１ｍｌｊ，如果ｙｊ等于已方的某个元素ｘｌｊ相等则表明该元素是多方交集元素㊂３ ３㊀基于不经意伪随机函数的ＰＳＩＰＳＩ算法参与方包括ｓｅｒｖｅｒ和ｃｌｉｅｎｔ，假设ｓｅｖｅｒ和ｃｌｉｅｎｔ输入元素个数都为ｎ㊂ＯＰＲＦＰＳＩ算法的基本思想是利用ＰＲＧ函数对双方明文元素进行加密，然后ｓｅｒｖｅｒ方和ｃｌｉｅｎｔ方对加密后元素进行逐一比对找出共同交集元素，ＰＲＧ函数设置加密密钥时通过ＯＴ协议交互使得该密钥能够确保相同交集元素的密文相同且不泄露明文元素的信息㊂ＯＰＲＦＰＳＩ算法相对其他ＰＳＩ算法的优势是计算量和通信量都比较小，而且对于ｃｌｉｅｎｔ方来说安全性很高，能够确保ｓｅｒｖｅｒ方无论是半诚实还是恶意模型下的ｃｌｉｅｎｔ方安全性，这样通过ＯＰＲＦＰＳＩ算法构建隐查询ＰＩＲ时能够保证查询方的绝对安全性㊂（１）基本原理１）ＯＰＲＦ函数记为ＯＰＲＦｋ（ｘ）＝Ｈ（ｑ ［Ｆ（ｘ）㊃ｓ］），㊃表示位与操作，⊕表示位异或操作，Ｆ（ｘ）表示ｘ作为种子的随机数生成器，Ｈ表示Ｈａｓｈ摘要函数（具有ｒａｎｄｏｍｏｒａｃｌｅ特性）㊂ｑ，ｓɪ｛０，１｝λ，λ表示安全参数；２）ｃｌｉｅｎｔ对己方输入元素ｘ：先采样随机字符串ｒ０ѳƔ｛０，１｝ｎ，计算ｒ１＝ｒ０ Ｆ（ｘ）；３）ｓｅｒｖｅｒ端先采样随机字符串ｓѳƔ｛０，１｝ｎ；４）ｃｌｉｅｎｔ和ｓｅｒｖｅｒ运行λ次ＯＴ协议：ｃｌｉｅｎｔ发送方输入ｒ０［ｉ］和ｒ１［ｉ］，ｓｅｒｖｅｒ端输入选择比特ｓ［ｉ］㊂ｓｅｒｖｅｒ通过λ次ＯＴ协议获取到的λ比特随机字符串ｑ＝ｒｓ［１］［１］ ｒｓ［２］［２］．．． ｒｓ［λ］［λ］；５）ｓｅｒｖｅｒ端设置ＯＰＲＦｋｅｙｋ＝（ｑ，ｓ），对己方输入元素ｙ计算ＯＰＲＦ值ＯＰＲＦｋ（ｙ）＝Ｈ（ｑ ［Ｆ（ｙ）㊃ｓ］），并将改值发送给ｃｌｉｅｎｔ；６）ｃｌｉｅｎｔ检验：当ＯＰＲＦｋ（ｙ）＝Ｈ（ｒ０）时表明ｙ＝ｘ㊂（２）ＯＰＲＦ算法协议公共函数及参数约定如下：λ表示计算安全参数，统计安全参数σ，协议参数ｍ，ｗ，ｌ１，ｌ２，Ｈａｓｈ函数Ｈ１：｛０，１｝∗ң｛０，１｝ｌ１和Ｈ２：｛０，１｝ｗң｛０，１｝ｌ２，伪随机函数Ｆ：｛０，１｝Ａˑ｛０，１｝ｌң［ｍ］ｗ；具体协议过程如下：１）阶段１：预处理ｓｅｒｖｅｒ端采样随机字符串ｓѳƔ｛０，１｝ｗ；ｃｌｉｅｎｔ端执行：初始化个ｍˑω二进制矩阵Ｄ为全１，Ｄｊ表示Ｄ第ｊ列，Ｄ１＝Ｄ２＝ ＝Ｄｓ＝１ｍ；采样随机字符串ｋѳƔ｛０，１｝λ作为ＰＲＦ函数Ｆ密钥；对于ｃｌｉｅｎｔ端的每个元素ｙ：计算ｖ＝Ｆｋ（Ｈ１（ｙ）），ｖɪ［ｍ］ｗ，对矩阵Ｄ的每一列设置Ｄｉ［ｖ［ｉ］］＝０，ｉɪ［ｗ］㊂２）阶段２ʒ０Ｔ传输㊃３０１㊃北京电子科技学院学报２０２３年ｃｌｉｅｎｔ端随机产生一个ｍˑω二进制矩阵Ａѳ＄｛０，１｝ｍˑｗ，计算Ｂ＝Ａ⊕Ｄ；ｃｌｉｅｎｔ和ｓｅｒｖｅｒ运行ｗ次ＯＴ协议，ｃｌｉｅｎｔ作为发送方，ｓｅｒｖｅｒ作为接收方，每次ＯＴ，ｃｌｉｅｎｔ输入消息｛Ａｉ，Ｂｉ｝，ｉɪ［ｗ］，ｓｅｒｖｅｒ输入ｓｉ进行选择㊂ＯＴ协议结束后ｓｅｒｖｅｒ获得ｗ㊀个ｍ比特字符串，然后作为ω列得到一个ｍˑω二进制矩阵Ｃ㊂３）阶段３：ＯＰＲＦ值验证ｃｌｉｅｎｔ端将ＰＲＦ函数Ｆ密钥发送给ｓｅｒｖｅｒ；ｓｅｒｖｅｒ端针对每个元素ｘｉ：计算ｖｊ＝Ｆｋ（Ｈ１（ｙｊ）），计算ＯＰＲＦ值Ｖｉ＝Ｈ２（Ｃ１［ｖｉ［１］］） Ｃｗ［ｖｉ［ｗ］）；ｓｅｒｖｅｒ将所有：发送给ｃｌｉｅｎｔｃｌｉｅｎｔ端针对己方每个元素ｙｉ：计算ｖｊ＝Ｆｋ（Ｈ１（ｙｊ）），计算ＯＰＦ值中，㊀ϕｊ＝Ｈ２（Ａ１［ｖｊ［１］］ Ａｗ［ｖｉ［ｗ］］），然后逐个比较中ϕｊ和ψｉ，当且仅当ϕｊ＝ψｉ时，㊀ｙｊ＝ｘｉ㊂３ ４㊀不经意的可编程伪随机函数的ＰＳＩＰＲＦ函数Ｆ跟ＯＰＲＦ中的定义一致㊂ＯＰＰＲＦ协议的参与方包括Ｓｅｎｄｅｒ（记为Ｓ）和Ｒｅｃｅｉｖｅｒ（记为Ｒ）两方㊂协议运行过程如下：１）约定安全参数Κ，公开参数ＰＲＦ函数Ｆ：２）Ｓ方输入｛（ｘ１，ｙ１），（ｘ２，ｙ２） （ｘｎ，ｙｎ）｝，ｘｉ不相等，协议生成Ｆ加密密钥ｋ和公共参数ｈｉｎｔ；３）Ｒ方进行公ｑ次查询，每次查询输入ｘ，协议返回ｙ＝Ｆ（ｘ，ｋ，ｈｉｎｔ）㊂Ｓ方的输入可以理解为一些点坐标，协议对Ｓ方输入进行加密计算得到公共参数ｈｉｎｔ，ＰＲＦ函数Ｆ加密密钥ｋ㊂Ｒ方的输入为ｘ，协议返回一个随机值ｙ，当ｘ与Ｓ方某个输入ｘ相等时，Ｒ方获得输出即为ｙ＝ｙｉ㊂协议的安全性要求Ｓ方无法获知Ｒ方输入的查询信息，Ｒ方无法获知查询输出是否匹配到了Ｓ方的某个输入㊂也就是说Ｒ方每次查询中无论输入值是否匹配到Ｓ方的某个输入ｘｉ，输出ｙ相对Ｒ方都是一个随机均匀分布㊂ＯＰＰＲＦ基于多项式的实现：假设Ｓ方输入｛（ｘ１，ｙ１），（ｘ２，ｙ２） （ｘｎ，ｙｎ）｝，令ｙᶄｉ＝ｙｉ Ｆ（ｋ，ｘｉ），Ｓ方通过对｛（ｘ１，ｙᶄ１），（ｘ２，ｙᶄ２） （ｘｎ，ｙᶄｎ）｝进行拉格朗日插值得到多项式如下：Ｐ（ｘ）＝ðｎｉ＝１ｙᶄｉ（ᵑ１ɤｊɤｎｊʂｉｘ－ｘｊｘｉ－ｘｊ）记上述多项式系数为ｈｉｎｔ，记Ｒ方查询输入为ｑ，则查询输出为：Ｆ（ｑ，ｋ，ｈｉｎｔ）＝Ｆ（ｋ，ｑ） Ｐ（ｑ）正确性验证：当Ｒ查询输入ｑ＝ｘ时，查询输出为ｙｉＦ（ｋ，ｘｉ） Ｐ（ｘｉ）＝Ｆ（ｋ，ｘｉ） ｙᶄｉ＝Ｆ（ｋ，ｘｉ） ｙｉ Ｆ（ｋ，ｘｉ）＝ｙｉ当输入ｑ不等于任一ｘｉ时，查询输出是随机均匀分布的㊂因为ｙｉ随机均匀分布，因此Ｐ（ｘ）系数也是随机均匀分布的㊂３ ５㊀ＭｕｌｔｉＰＳＩ算法原理：算法关键是利用秘密分享技术，通过２次ＯＰＰＲＦ找出共同元素㊂１）第一次ＯＰＰＲＦ：ｓｔｅｐ１中各参与方对本方的每个元素和其他各参与方生成多份秘密分享值ｓｉ，ｊｋ，然后ｓｔｅｐ２中各参与方运行ＯＰＰＲＦ，此时如果有相同元素进行查询则会获取到对方相同元素的某一份秘密分享值㊂如果是不相同元素的查询则是获得一个随机值；２）第二次ＯＰＰＲＦ：ｓｔｅｐ３中各参与方通过本方所有秘密分享值计算一个映射Ｓｉ（ｘｉｋ），然后ｓｔｅｐ４中Ｐ１作为协议中ｌｅａｄｅｒ（负责最终交集元素的输出），和各参与方运行第二次ＯＰＰＲＦ．每个参与方的Ｓｉ（ｘｉｋ）值包含了单个元素在各个参与方对应的秘密分享值㊂Ｓｔｅｐ５中Ｐ１对各个参与方Ｓ（ｘ）进行ＸＯＲ计算，此时如果是该元素在㊃４０１㊃第３１卷隐私集合求交算法的对比分析㊀各个参与方都有，则 ｉɪ［ｎ］ｙｉｋ包含了所有参与方关于ｘｉｋ元素的全部秘密分享值，因此 ｉɪ［ｎ］ｙｉｋ＝０意味着元素ｘｉｋ在各个参与方输入中都存在㊂４㊀ＰＳＩ算法复杂度的对比分析㊀㊀不同ＰＳＩ协议的计算复杂度和通信复杂度在表２中有所示㊂表１为符号说明，表２中的计算复杂度是通过非对称或是对称密码原语的使用次数衡量的，通信复杂度是通过在信道上传输的比特数衡量的㊂这里的假设是每完成一次ＯＴ协议花费３次对称密码操作（对于使用布隆过滤器的花费２ ５次对称密码操作）㊂计算姚氏电路中的与门使用４次对称密码操作，计算ＧＭＷ电路中的与门使用６次对称加密操作㊂在同一类别中的ＰＳＩ方案大多数拥有类似的复杂度㊂朴素哈希方法与服务器辅助的方法需要对每一个元素执行一次对称加密操作（哈希），基于公钥的协议需要对每一个元素执行两次公钥操作，并且需要发送两个密文和一个哈希值㊂基于电路的方法的计算复杂度与电路中与门的数量成正比，在基于布隆过滤器的协议中，计算复杂度与布隆过滤器的大小成正比㊂在基于ＯＴ的协议中，基于布隆过滤器的协议［２４］，通信复杂度是与安全参数κ的平方成正比的，但是在［３４］中的协议，通信复杂度是与κ呈线性关系㊂表１㊀符号说明符号说明Ｓ服务端或是发送端Ｒ客户端或是接收端Ｘ，Ｙ发送端和接收端的集合ＮＸ，ＮＹ发送端和接收端集合的大小ｍ哈希表的大小ｖ消息编码的长度σ集合元素的长度κ，λ计算意义的安全参数和统计意义的安全参数ρ，ϕ非对称安全参数与椭圆曲线的规模表２㊀不同ＰＳＩ协议复杂度比较分类协议计算复杂度（对称或非对称密码原语的次数）通信复杂度（比特）基于公钥体系的基于有限域ＤＨ的［６］２ｔｐｋｔρ＋ＮＸｖ基于椭圆曲线上ＤＨ的［６］２ｔｐｋｔϕ＋ＮＸｖ基于ＲＳＡ的［３０］２ｔｐｋｔρ＋ＮＸｖ基于电路的姚氏电路使用ＳＣＳ１２ｍσｌｏｇｍ＋３ｍσｓｙｍ６ｍΚσｌｏｇｍ＋３ｍσＧＭＷ使用ＳＣＳ１８ｍσｌｏｇｍｓｙｍ６ｍ（Κ＋２）σｌｏｇｍ姚氏电路使用ＰＷＣσ（４ ＮＹｍａｘｂ＋４ｓＮＸ＋３ ＮＹ）ｓｙｍ２ ＮＹΚｍａｘｂσ＋３ｓＮＸΚσ＋２ ＮＹσＧＭＷ使用ＰＷＣ６σ（ ＮＹｍａｘｂ＋ｓＮＸ）ｓｙｍ２（Κ＋２）σ（ ＮＹｍａｘｂ＋ｓＮＸ）姚氏电路使用ＯＰＲＦ２１７６０ＮＹ＋３σＮＹｓｙｍ１０８８０ＮＹΚ＋２ＮＹΚσ＋ＮＸｖＧＭＷ使用ＯＰＲＦ３２６４０ＮＹｓｙｍ１０８８０ＮＹ（Κ＋２）＋ＮＸｖＣｉａｍｐｉ等人的方案Ｍ（４σｌｏｇｍ＋３σ）ｓｙｍｍ（２σ＋１）ｍΚ基于ＯＴ协议的使用布隆过滤器［２４］３ ６ｍΚｓｙｍ１ ４４ｍΚ（Κ＋λ）使用哈希表［２０］３ ＮＹ＋（ｋ＋ｓ）ＮＸｓｙｍ５１２ ＮＹ＋（ｋ＋ｓ）ＮＸｖ使用哈希表［２６］（ｓ＋３）ｍ＋（ ｍ＋ｓ）ｓｙｍ４（ ｍ＋ｓ）ｋ＋（ｓ＋３）ｍｖ使用哈希表［３１］∗－６Κｎ＋βｎｌｏｇｍ基于ＦＨＥ的［４６］－－１ ５ＣσＮＹｌｏｇ２Ｎｘ㊀㊀注：其中ｓｙｍ和ｐｋ分别表示对称与非对称操作的统计，ｔ＝ＮＸ＋ＮＹ，ｍ＝ｍａｘ（ＮＸ，ＮＹ），βʈλ＋２ｌｏｇｎ－１， ，ｋ，ｓ，ｍａｘｂ是哈希函数用到的参数，ｖ是在ＯＴ扩展协议中，使用的哈希函数的输出长度，Ｃ是一个常数，表示［２６］的同态操作产生的密文扩展㊂标有∗的是在恶意模型下安全的协议㊂５㊀ＰＳＩ性能的对比分析㊀㊀基于公钥密码的ＰＳＩ方案中，一些协议公钥加解密操作的次数与集合大小成线性关系㊂因此虽然通信复杂度是最小的，但是计算开销远不及后面叙述的基于不经意传输扩展协议的ＰＳＩ㊂使用公钥加密体系的ＰＳＩ有另一个优点，就是在双方集合大小相差很大的情况下，花销很大的公钥加密操作可以集中在一方进行㊂结合这种方案通信复杂度低的优点，Ｃｈｅｎ等人在文献［２８］㊁㊃５０１㊃。
RSA加密算法原理及RES签名算法简介第⼀部分：RSA原理与加密解密⼀、RSA加密过程简述A和B进⾏加密通信时,B⾸先要⽣成⼀对密钥。
⼀个是公钥，给A，B⾃⼰持有私钥。
A使⽤B的公钥加密要加密发送的内容，然后B在通过⾃⼰的私钥解密内容。
⼆、RSA加密算法基础整个RSA加密算法的安全性基于⼤数不能分解质因数。
三、数学原理(⼀) 互质关系：两个数a和b没有除1外的其他公约数，则a与b互质1. 任意两个质数构成互质关系2. 两个数中，如果⼤数为质数，则两数必定互质3. 1和任意整数互质4. 当p>1时，p与p-1互质(相邻两数互质)5. 当p=2n+1(n>0且n为整数)时，p与p+2互质(相连的两个奇数互质)(⼆) 求欧拉函数：定义：与正整数n互质且⼩于正整数n的正整数的个数。
通常使⽤ψ(n)表⽰。
求取与正整数n互质的正整数的个数ψ(n),且ψ(n)满⾜ψ(n)∈(2,n)1. 如果n=1,则ψ(n)=12. 如果n是质数,则ψ(n)=n-13. 如果n是质数p的次⽅,则：ψ(p^k)=p^k-p^(k-1) = p^k*(1-1/p)4. 若p1和p2互质,n=p1*p2,则ψ(n)= ψ(p1*p2)= ψ(p1) ψ(p2)5. 任意⼀个⼤于1的正整数都可以写成⼀系列质数的积6. 根据定理5，推导欧拉定理：因为n = (p1^k1)* (p2^k2)*……(pr^kr) (p1~pr都是质数)所以ψ(n)= ψ((p1^k1)) ψ(p2^k2) ……ψ(pr^kr) 定理4ψ(n)= (p1^k1)*(1-1/p1) * (p2^k2)(1-1/p2)……(pr^kr)*(1-1/pr) 定理3ψ(n)= (p1^k1)* (p2^k2)*……(pr^kr) * (1-1/p1) (1-1/p2)…… (1-1/pr)ψ(n)=n (1-1/p1) (1-1/p2)…… (1-1/pr)(三) 欧拉定理：正整数a与n互质，则下式恒成⽴a^ψ(n) ≡1(mod n)即：a的ψ(n)次幂除以n,余数恒为1(四) 模反元素如果两个正整数a和n互质,则必定存在整数b使得a*b-1被n除余数为1ab ≡1(mod n)其中b被称为a的模反元素四、RSA算法详解：假设A和B要通信(⼀) ⽣成密钥1. 公钥1) 随机⽣成两个不相等的质数p和q(质数越⼤越安全)2) 计算n,n=p*q 则n的⼆进制位数就是密钥的长度。
rsa 签名和验签的原理RSA签名和验签的原理基于RSA算法的数学特性。
1. RSA签名原理：（1）假设Alice想要对一条消息进行签名，她首先选择一对RSA公钥和私钥。
公钥包括两个参数：RSA模数n和公钥指数e；私钥包括两个参数：RSA模数n和私钥指数d。
公钥（n,e）会公开给其他人，而私钥（n,d）会保密。
（2）Alice使用私钥（n,d）对消息进行加密，得到签名s。
加密过程为s = m^d mod n，其中m是消息的表示，^表示乘方，mod表示取模运算。
（3）Alice将消息m和签名s一起发送给Bob。
（4）Bob使用Alice的公钥（n,e）对签名s进行解密，得到消息m'。
解密过程为m' = s^e mod n。
（5）Bob计算收到的消息m'的表示，与实际收到的消息m进行比较。
如果相等，则说明签名是有效的，否则签名是无效的。
2. RSA验签原理：（1）Alice生成一对RSA公钥和私钥，公钥（n,e）公开给Bob，私钥（n,d）保密。
（2）Bob收到Alice发送的消息m和签名s。
（3）Bob使用公钥（n,e）对签名s进行解密，得到消息m'。
解密过程为m' = s^e mod n。
（4）Bob计算收到的消息m'的表示，与实际收到的消息m进行比较。
如果相等，则说明签名是有效的，否则签名是无效的。
通过RSA的数学特性，只有私钥的持有者才能对消息进行加密，从而生成唯一有效的签名。
而公钥的持有者只能使用公钥进行验证签名的有效性，无法生成有效的签名。
这样就能确保签名的有效性和身份认证。
密钥交换（密钥协商）算法及其原理密钥交换（密钥协商）算法是指双方在不安全的通信信道中协商出一个共享密钥的过程。
这个共享密钥被用于加密和解密通信中的数据，以确保通信的机密性和完整性。
在密码学中，有许多经典的密钥交换算法，如Diffie-Hellman密钥交换算法、RSA算法和ECC算法等。
Diffie-Hellman是一种最早的密钥交换算法，它利用了离散对数的难题。
该算法的原理如下：1.首先，双方共享一个公开的素数p和一个基数g。
这些参数可以在双方事先约定好，也可以通过其他安全的通信方式传递。
这些参数可以在不同的会话中重复使用。
2.然后，每个参与者选择一个私密的数值作为私钥。
这个私钥只有自己知道。
3.接下来，参与者通过计算公式计算出一个公钥，并将其发送给对方。
公钥的计算公式为：公钥=g的私钥次方对p取模。
4.接收方也进行相同的操作，计算出自己的公钥。
5.双方互相交换公钥信息。
6.然后，双方使用对方的公钥和自己的私钥进行计算，得到一个相同的共享密钥。
计算公式为：共享密钥=公钥的私钥次方对p取模。
7.最后，双方得到的共享密钥可以用于对后续的通信进行加密和解密。
RSA算法是一种公钥密码体制，也可以用于密钥交换。
其原理如下：1.首先，每个参与者生成一对密钥，即一个公钥和一个私钥。
私钥只有自己知道，公钥可以公开。
2.接着，参与者将自己的公钥发送给对方。
3.对方使用收到的公钥对数据进行加密，并将加密后的数据发送给发送方。
4.发送方使用自己的私钥对收到的数据进行解密。
5.最后，双方可以使用解密后的数据进行通信。
ECC（椭圆曲线密码学）算法是基于椭圆曲线离散对数问题的一种密钥协商算法。
其原理如下：1.首先，双方事先约定一个椭圆曲线和一个基点，这些参数可以公开。
2.每个参与者选择一个私密的数值作为私钥。
这个私钥只有自己知道。
3.接下来，每个参与者使用私钥和基点进行一系列的点乘运算，得到一个公钥。
4.然后，双方互相交换公钥信息。
混合离散对数及安全认证摘要：近二十年来，电子认证成为一个重要的研究领域。
其第一个应用就是对数字文档进行数字签名，其后Chaum希望利用银行认证和用户的匿名性这一性质产生电子货币，于是他提出盲签名的概念。
对于所有的这些问题以及其他的在线认证，零知识证明理论成为一个非常强有力的工具。
虽然其具有很高的安全性，却导致高负荷运算。
最近发现信息不可分辨性是一个可以兼顾安全和效率的性质。
本文研究混合系数的离散对数问题，也即信息不可识别性。
我们提供一种新的认证，这种认证比因式分解有更好的安全性，而且从证明者角度看来有更高的效率。
我们也降低了对Schnorr方案变形的实际安全参数的Girault的证明的花销。
最后，基于信息不可识别性，我们得到一个安全性与因式分解相同的盲签名。
1．概述在密码学中，可证明为安全的方案是一直以来都在追求的一个重要目标。
然而，效率一直就是一个难以实现的属性。
即使在现在对于认证已经进行了广泛的研究，还是很少有方案能兼顾效率和安全性。
其原因就是零知识协议的广泛应用。
身份识别：关于识别方案的第一篇理论性的论文就是关于零知识的，零知识理论使得不用泄漏关于消息的任何信息，就可以证明自己知道这个消息。
然而这样一种能够抵抗主动攻击的属性，通常需要许多次迭代来得到较高的安全性，从而使得协议或者在计算方面，或者在通信量方面或者在两个方面效率都十分低下。
最近，poupard和stern提出了一个比较高效的方案，其安全性等价于离散对数问题。
然而，其约减的代价太高，使得其不适用于现实中的问题。
几年以前，fiege和shamir就定义了比零知识更弱的属性，即“信息隐藏”和“信息不可分辨”属性，它们对于安全的识别协议来说已经够用了。
说它们比零知识更弱是指它们可能会泄漏秘密消息的某些信息，但是还不足以找到消息。
具体一点来说，对于“信息隐藏”属性，如果一个攻击者能够通过一个一次主动攻击发现秘密消息，她不是通过与证明者的交互来发现它的。
rsa密钥交换算法RSA密钥交换算法RSA（Rivest-Shamir-Adleman）密钥交换算法是一种非对称加密算法，可用于在不安全的网络环境中进行安全的数据传输。
该算法是由Ron Rivest、Adi Shamir和Leonard Adleman于1977年共同提出的，是目前应用最广泛的公钥加密算法之一。
RSA算法的基本原理是利用大素数的因子分解问题的困难性来保证数据传输的安全性。
在RSA算法中，每个参与者（通常是客户端和服务器）都拥有一对密钥，分别为公钥和私钥。
公钥可以公开给其他参与者，而私钥则必须严格保密。
公钥用于加密数据，私钥用于解密数据。
RSA密钥交换算法的过程如下：1. 生成密钥对：首先，参与者需要生成一对密钥，这对密钥是通过选择两个大素数p和q，并计算出相应的公钥和私钥得到的。
其中，p和q是保密的，而公钥和私钥可以公开和保密。
2. 加密数据：发送方使用接收方的公钥对数据进行加密。
具体而言，发送方将明文数据转换为一个数值，并使用接收方的公钥对该数值进行幂模运算，得到密文数据。
这样，即使敌方截获了密文数据，也无法解密得到原始数据。
3. 解密数据：接收方使用自己的私钥对密文数据进行解密。
具体而言，接收方使用私钥对密文数据进行幂模运算，得到原始数据的数值表示。
然后，接收方将该数值转换为原始数据。
4. 完成数据传输：接收方成功解密密文数据后，即可获得原始数据。
这样，通过RSA密钥交换算法，参与者可以在不安全的网络环境中安全地进行数据传输。
RSA算法的安全性基于两个数的大数分解问题的困难性。
即使在现代计算机中，对于大素数的因子分解问题也是非常耗时的。
因此，通过选择足够大的素数，RSA算法可以提供足够强的安全性。
然而，RSA算法也存在一些安全性问题。
首先，如果生成密钥对的过程中选择的素数不够随机或不够大，可能会导致密钥的安全性降低。
其次，如果私钥泄露，攻击者可以使用私钥对密文数据进行解密，从而获取原始数据。
rsa 验签原理RSA（Rivest-Shamir-Adleman）是一种常用的公钥密码体系，广泛应用于数字签名和加密通信等领域。
在RSA中，验证签名的过程被称为验签，它是一种用来验证数字签名的方法。
验签的原理基于RSA的公钥和私钥之间的数学关系，通过对签名和原始数据进行一系列的计算和比较，来判断签名的有效性。
RSA的验签原理主要包括公钥生成、签名生成、签名验证三个步骤。
公钥生成是验签的前提。
在RSA中，公钥由两个参数组成：模数n 和指数e。
这两个参数可以通过选择两个大素数p和q，然后计算n=p*q和e的方式得到。
公钥是公开的，可以被任何人使用。
签名生成是由消息的发送者完成的。
发送者首先使用自己的私钥进行计算，得到一个数字签名。
具体的计算过程是将原始数据进行哈希处理，然后使用私钥对哈希值进行加密。
生成的数字签名包含了发送者的身份信息和原始数据的摘要信息。
签名验证是由接收者完成的。
接收者首先使用发送者的公钥对数字签名进行解密，得到一个哈希值。
然后，接收者使用相同的哈希算法对原始数据进行处理，得到一个新的哈希值。
接着，接收者将解密得到的哈希值与新计算得到的哈希值进行比较。
如果两者相等，则说明数字签名是有效的，原始数据没有被篡改过；如果不相等，则说明数字签名无效，原始数据可能被篡改过。
通过RSA的验签原理，可以保证数据的完整性和真实性。
因为私钥只有发送者拥有，其他人无法伪造有效的数字签名；而公钥可以被任何人使用，用来验证签名的有效性。
这样，接收者可以通过验证签名来确认数据的来源和完整性，从而确保通信的安全性。
需要注意的是，RSA的验签过程是计算密集型的，需要进行大量的数学计算。
为了提高效率，通常会使用哈希算法来对原始数据进行摘要，减少计算量。
同时，为了保证安全性，RSA的密钥长度需要足够长，通常要求使用2048位或更长的密钥。
总结而言，RSA的验签原理是通过公钥和私钥之间的数学关系，对签名和原始数据进行计算和比较，来验证签名的有效性。
RSA实现数字签名数字签名，就是只有信息的发送者才能产生的别人无法伪造的一段数字串，这段数字串同时也是对信息的发送者发送信息真实性的一个有效证明。
主要功能保证信息传输的完整性、发送者的身份认证、防止交易中的抵赖发生。
数字签名技术是将摘要信息用发送者的私钥加密，与原文一起传送给接收者。
接收者只有用发送者的公钥才能解密被加密的摘要信息，然后用HASH函数对收到的原文产生一个摘要信息，与解密的摘要信息对比。
如果相同，则说明收到的信息是完整的，在传输过程中没有被修改，否则说明信息被修改过，因此数字签名能够验证信息的完整性。
数字签名是个加密的过程，数字签名验证是个解密的过程。
数字签名签名过程“发送报文时，发送方用一个哈希函数从报文文本中生成报文摘要,然后用自己的私人密钥对这个摘要进行加密，这个加密后的摘要将作为报文的数字签名和报文一起发送给接收方，接收方首先用与发送方一样的哈希函数从接收到的原始报文中计算出报文摘要，接着再用发送方的公用密钥来对报文附加的数字签名进行解密，如果这两个摘要相同、那么接收方就能确认该数字签名是发送方的。
数字签名有两种功效：一是能确定消息确实是由发送方签名并发出来的，因为别人假冒不了发送方的签名。
二是数字签名能确定消息的完整性。
因为数字签名的特点是它代表了文件的特征，文件如果发生改变，数字摘要的值也将发生变化。
不同的文件将得到不同的数字摘要。
一次数字签名涉及到一个哈希函数、发送者的公钥、发送者的私钥。
”数字签名：发送方用自己的密钥对报文X进行Encrypt(编码)运算，生成不可读取的密文Dsk，然后将Dsk传送给接收方，接收方为了核实签名，用发送方的公用密钥进行Decrypt(解码)运算，还原报文。
我自己看了crypto++的文档，利用文档给的rsa签名的示例代码自己做了一个小程序，代码示例如下：#define CRYPTOPP_ENABLE_NAMESPACE_WEAK 1#include"md5.h"#include<iostream>#include"pssr.h"#include<hex.h>#include"rsa.h"#include"osrng.h"using namespace CryptoPP;#pragma comment(lib, "cryptlib.lib")using namespace std;bool md5(const string &src, string &digest){Weak::MD5 md5;StringSource(src, true,new HashFilter(md5,new HexEncoder(new StringSink(digest))));return true;}int main(){try{////////////////////////////////////////////////// Generate keysAutoSeededRandomPool rng;InvertibleRSAFunction parameters;parameters.GenerateRandomWithKeySize(rng, 1024);RSA::PrivateKey privateKey(parameters);RSA::PublicKey publicKey(parameters);// Messagestring message;// = "Yoda said, Do or Do Not. There is not try.";string signature,md5_message;cout << "请输入要签名的内容：";cin >> message;cout << endl;md5(message, md5_message);cout <<"将信息哈希为摘要："<<endl<<endl<< md5_message << endl << endl;////////////////////////////////////////////////// Sign and EncodeRSASS<PSS, SHA1>::Signer signer(privateKey);StringSource(md5_message, true,new SignerFilter(rng, signer,new StringSink(signature)) // SignerFilter); // StringSourcecout << signature << endl<<endl<<endl;////////////////////////////////////////////////// Verify and RecoverRSASS<PSS, SHA1>::Verifier verifier(publicKey);StringSource(md5_message + signature, true,new SignatureVerificationFilter(verifier, NULL,SignatureVerificationFilter::THROW_EXCEPTION) // SignatureVerificationFilter); // StringSourcecout << "Verified signature on message" << endl;} // trycatch (CryptoPP::Exception& e) {std::cerr << "Error: " << e.what() << std::endl;}return 0;}。
基于RSA的数字签名实现实验2基于RSA的数字签名实现一、实验目的掌握RSA算法的基本原理，通过用RSA算法对实际数据进行加密和解密来深刻了解RSA的运行原理。
对数字签名有所了解，理解和掌握SHA–512算法，以及如何利用RSA和SHA–512算法来实现数字签名。
二、实验原理1.RSA算法简介公钥密码体制中,解密和加密密钥不同,解密和加密可分离,通信双方无须事先交换密钥就可建立起保密通信,较好地解决了传统密码体制在网络通信中出现的问题.另外,随着电子商务的发展,网络上资金的电子交换日益频繁,如何防止信息的伪造和欺骗也成为非常重要的问题.数字签名可以起到身份认证,核准数据完整性的作用.目前关于数字签名的研究主要集中基于公钥密码体制的数字签名.公钥密码体制的特点是:为每个用户产生一对密钥(PK和SK);PK公开,SK保密;从PK推出SK是很困难的;A,B双方通信时,A通过任何途径取得B的公钥,用B的公钥加密信息.加密后的信息可通过任何不安全信道发送.B收到密文信息后,用自己私钥解密恢复出明文.RSA公钥密码体制到目前为止还是一种认可为安全的体制.RSA算法和用RSA算法实现数字签名的理论,以及它们在实际应用中的实现.1、RSA算法RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。
RSA的算法涉及三个参数，n、e1、e2。
其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。
e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)*(q-1)互质；再选择e2，要求(e2*e1)mod((p-1)*(q-1))=1。
(n及e1),(n及e2)就是密钥对。
RSA加解密的算法完全相同,设A为明文，B为密文，则：A=B^e1mod n；B=A^e2mod n；e1和e2可以互换使用，即：A=B^e2mod n；B=A^e1mod n；2.RSA数字签名算法的理论描述RSA数字签名算法的过程为:A对明文m用解密变换作:s Dk(m)=md mod n,其中d,n为A的私人密钥,只有A才知道它;B收到A的签名后,用A的公钥和加密变换得到明文,因:Ek(s)=Ek(Dk(m))=(md)e mod n,又de1mod(n)即de=l(n)+1,根据欧拉定理m(n)=1mod n,所以Ek(s)=ml(n)+1=[m(n)]em=m mod n.若明文m和签名s一起送给用户B,B可以确信信息确实是A发送的.同时A也不能否认送给这个信息,因为除了A本人外,其他任何人都无法由明文m产生s.因此RSA数字签名方案是可行的.但是RSA数字签名算法存在着因计算方法本身同构造成签名易被伪造和计算时间长的弱点,因此实际对文件签名前,需要对消息做SHA–512变换. SHA–512函数是一种单向散列函数,它将任意长度的消息压缩成512位的消息摘要.应用SHA–512的单向性(即给定散列值,计算消息很难)和抗碰撞性(即给定消息M,要找到另一消息M'并满足两者的散列值很难),可以实现信息的完整性检验.另外该函数的设计不基于任何假设和密码体制而直接构造,执行的速度快,是一种被广泛认可的单向散列算法.3.RSA数字签名算法的实现RSA数字签名算法,包括签名算法和验证签名算法.首先用SHA–512算法对信息作散列计算.签名的过程需用户的私钥,验证过程需用户的公钥.A用签名算法将字符串形式的消息处理成签名;B用验证签名算法验证签名是否是A对消息的签名,确认是A发送的消息;消息没有被攥改过;A一定发送过消息.1签名算法签名算法包括三步:消息摘要、计算、RSA加密.消息摘要计算.消息在签名前首先通过SHA–512计算,生成512位的消息摘要，对摘要作RSA计算.用加密算法,采用签名者的私钥加密消息摘要,得到加密后的字符串.加密算法中使用的加密块为01类型.2验证签名算法验证签名算法包括两步:RSA解密得签名者的消息摘要,验证者对原消息计算摘要,比较两个消息摘要.验证签名的过程输入为消息,签名者的公钥,签名;输出为验证的结果,即是否是正确的签名.RSA解密.签名实际是加密的字符串.采用签名者的公钥对这个加密的字符串解密.解密的结果应为5128位的消息摘要.在解密过程中,若出现得到的加密块的类型不是01,则解密失败.签名不正确.消息摘要计算和比较.验证者对消息用SHA–512算法重新计算,得到验证者自己的消息摘要.验证者比较解密得到的消息摘要和自己的消息摘要,如果两者相同,则验证成功,可以确认消息的完整性及签名确实为签名者的;否则,验证失败.三、实验环境运行Windows操作系统的PC机，具有C#(Windows)或Java语言编译环境。
rsa 签名方法RSA签名方法是一种使用RSA算法进行数字签名的技术。
数字签名是一种确保数据完整性和身份验证的方法。
RSA签名方法可以用于保护数据的机密性和防止篡改。
在RSA签名过程中，使用者首先生成一对RSA密钥，包括一个私钥和一个公钥。
私钥用于签名数据，公钥用于验证签名的真实性。
私钥是保密的，而公钥可以公开。
签名者使用私钥对要签名的数据进行加密，生成签名。
然后，签名者将原始数据和签名一起发送给接收者。
接收者使用签名者的公钥对签名进行解密，并验证签名的有效性。
如果签名是有效的，接收者可以确认发送者的身份，并确保数据未经篡改。
RSA签名方法具有以下优点：1. 安全性高：RSA算法基于大数因子分解的数学难题，即使在计算资源非常强大的情况下，攻击者也很难破解签名。
2. 不可伪造性：由于私钥只有签名者拥有，其他人无法伪造签名。
3. 数据完整性：通过验证签名，接收者可以确保接收到的数据未经篡改。
4. 灵活性：RSA签名方法可以应用于各种类型的数据，包括文本、文件和数字等。
然而，RSA签名方法也有一些限制和注意事项：1. 性能开销：RSA签名方法的计算开销较大，特别是处理大型数据时。
因此，在大规模应用中，需要权衡性能和安全性。
2. 密钥管理：RSA签名方法需要对私钥进行保护和管理，以防止私钥泄漏或被盗用。
3. 可扩展性：RSA签名方法适用于小规模应用，但对于大规模分布式系统，需要使用更高效的签名方法。
总之，RSA签名方法是一种有效的数字签名技术，可以确保数据的完整性和身份验证。
它在安全通信、数字证书、电子商务等领域中得到广泛应用。
基于RSA算法的数字签名的实现毕业设计（论文）原创性声明本人郑重声明：所提交的毕业设计（论文），是本人在导师指导下，独立进行研究工作所取得的成果。
除文中已注明引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写过的作品成果。
对本研究做出过重要贡献的个人和集体，均已在文中以明确方式标明并表示了谢意。
论文作者签名：日期：年月日摘要随着Internet的发展，电子商务已经逐渐成为人们进行商务活动的新模式，越来越多的人通过Internet进行商务活动。
电子商务的发展前景十分诱人，而其安全问题也变得越来越突出，如何建立一个安全、便捷的电子商务应用环境，对信息提供足够的保护，已经成为商家和用户都十分关心的话题。
系统综合运用了RSA算法原理，散列函数以及C#和.NET编程技术，实现了基于RSA 算法的数字签名系统。
经过测试表明，系统运行可靠稳定，实现了保证信息完整性、鉴别发送者的身份真实性与不可否认性目标。
本文基于数字签名技术在电子商务中的应用，对公钥密码体制中的广泛流行的RSA算法做了深入的研究并主要阐述了利用C#语言实现基于RSA算法的数字签名方法。
从两大基本模块——签名系统和认证系统着手，对数字签名进行了详细的说明和分析。
关键词：数字签名；公钥密码体制；RSA；电子商务；加解密ABSTRACTWith the development of Internet，E-commerce has gradually become a new model of business activities，more and more people take up business affairs through the Internet. Prospects for the development of e-commerce is very tempting，and the security issues are becoming increasingly prominent.Many technologies have been adopted in the system, such as algorithm RSA, hash function, C# and .NET programming technology. And the Digital Signature system is based on algorithm RSA. The tests of application show that this system is reliable and achieves the design object of the integrity of information, identification of the sender's identity and the authenticity of the undeniable..Based on digital signature technology in the application of e-commerce，we conduct a study about the algorithm RSA which is very popular in the public-key cryptosystem，and we mainly explain the implementation of the Digital Signature based on algorithm RSA in C#. From the two basic systems -- the signature system and the authentication system, we did the detailed description and analysis of digital signature.Key words: digital signature; public-key cryptosystem; RSA; Eletronic Commerce; encryption and decryption目录第一章概述 (1)1.1课题背景 (1)1.2数字签名及其应用 (1)1.2.1数字签名概述 (1)1.2.2数字签名的应用 (2)1.3 课题内容 (3)第二章数字签名软件的技术支撑 (4)2.1 RSA加密算法 (4)2.1.1 公钥和私钥的产生 (4)2.1.2 加密消息 (5)2.1.3 解密消息 (5)2.1.4 安全 (5)2.1.5 实现细节 (6)2.2 数字签名原理 (7)2.3 散列函数 (7)2.3.1散列函数的性质 (8)2.3.2 散列函数的应用 (8)2.3.3 MD5算法 (10)2.3.4 SHA-1算法 (11)2.4 C#和.NET (11)第三章系统的分析与设计 (13)3.1需求分析 (13)3.2 总体设计 (13)3.3 功能模块的划分 (15)3.4 各功能模块的介绍 (16)第四章系统的实现 (18)4.1 RSA加密算法的实现 (18)4.1.1 公私密钥的生成 (19)4.1.2 使用私钥加密 (20)4.1.3 使用公钥解密 (21)4.1.4 其他 (21)4.2 散列函数 (21)4.3 数字签名的实现 (22)4.3.1 设计思想 (22)4.3.2 系统实现 (24)4.4 本章小结 (33)结束语 (34)致谢 (35)第一章概述1.1课题背景随着Internet和计算机网络技术的蓬勃发展，连通全世界的电子信息通道已经形成，应用Internet网开展电子商务业务也开始具备实用的条件，电子商务获得长足发展的时机已经成熟。
盲签名blindsignature简介盲签名(Blind Signature)定义是⼀种数字签名的⽅式,在消息内容被签名之前,对于签名者来说消息内容是不可见的.类⽐例⼦:对⽂件签名就是通过在信封⾥放⼀张复写纸，签名者在信封上签名时，他的签名便透过复写纸签到⽂件上。
盲签名(Blind Signature)性质它除了满⾜⼀般的数字签名条件外，还必须满⾜下⾯的两条性质：1. 签名者对其所签署的消息是不可见的，即签名者不知道他所签署消息的具体内容。
2. 签名消息不可追踪，即当签名消息被公布后，签名者⽆法知道这是他哪次的签署的。
盲签名(Blind Signature)模型1. 接收者⾸先将待签数据进⾏盲变换，把变换后的盲数据发给签名者。
2. 经签名者签名后再发给接收者。
3. 接收者对签名再作去盲变换，得出的便是签名者对原数据的盲签名。
4. 这样便满⾜了条件①。
要满⾜条件②，必须使签名者事后看到盲签名时不能与盲数据联系起来，这通常是依靠某种协议来实现的。
⼤致的图⽰如下:盲签名(Blind Signature)--RSA⽅案传统的 RSA ⽅案⼤致过程如下(前提条件就没有列出):加密:解密:签名者⼀般是基于消息的哈希值签名的,对于盲签名的要求,唯⼀不能满⾜的就是"签名者"事先会知道消息.所以RSA盲签名⽅案做了巧妙的转变.就是⾸先将消息 m 转化为 m`, 在此需要⼀个参数 r , gcd(r, N)=1. 然后就进⼊传统的 RSA 过程了.1. 盲化消息:2. 签名消息:3. 除盲消息:这个⽅案有效的原因是:盲签名(Blind Signature)--RSA⽅案的致命缺点(待续)本⽂译⾃:/wiki/Blind_Signatures,部分参考的百度百科.。
具有消息恢复功能的盲签名方案刘媛;张秉儒【摘要】通过对签名者不可抵赖性缺陷的分析和研究,将公钥密码体制和对称密码体制相结合,提出了一个基于冗余函数、收发双发都不能否认的具有消息恢复功能的盲签名方案,并对该方案的正确性、可靠性和安全性进行了分析.该方案保证了通信的公平公正性,保密性好,特别适合于商业领域的信息交互.【期刊名称】《华北水利水电学院学报》【年(卷),期】2011(032)006【总页数】3页(P125-127)【关键词】消息恢复;冗余函数;盲签名;不可否认性【作者】刘媛;张秉儒【作者单位】青海师范大学,青海西宁810000;青海师范大学,青海西宁810000【正文语种】中文盲签名已经发展成为一类特殊的数字签名，签名者不知道所签消息的具体内容，接收者将盲签名进行脱盲变换转化为普通的签名，签名人即使记录每次签名的记录也不能将盲签名和脱盲后的签名相关联［1］.在那些要求用户匿名性的场所，如匿名证券交易，口令认证，匿名电子现金和匿名电子投票等领域，盲签名技术发挥着重要作用.在保证安全的前提下，密码学家们致力于尽量减少通信量研究，Nyberg-Rueppel提出了消息恢复签名方案［2］，只需传递签名，接收方可以由签名和密钥恢复消息，直接缩短了传递的信息量，节省通信带宽，提高效率.当前的签名方案多数是由一个安全的杂凑函数将消息m对应到h(m)，以此保证消息的完整性、认证性和安全性.且h(m)的长度远小于m的长度.这样一来恢复的是h(m)而不是m;若在签名方案中用m，消息的保密性势必会受到威胁.冗余函数可以兼顾保密性和消息恢复特性，不过冗余函数的运算效率要低于 hash函数，因此其更适用于短消息传递.签名技术发展到现在，对签名者的不可否认性进行了较为深入的研究，提出了各种签名者不可否认的方案.基于当前的网络技术，信息传送过程中的延迟或者丢失是客观存在的，如果接收方恢复了消息却予以否认，这样的纠纷必须通过监管和技术两方双管齐下予以解决.为了满足当今社会的需求，对收发双发不可否认的签名技术的研究至关重要.笔者在已有研究基础上做了进一步尝试，结合公钥/私钥密码体制，提出一个收发双方都不能否认的具有消息恢复特性的盲签名方案，有效地解决了上述问题，具有很好的实用价值和应用前景.1 冗余函数M是消息集，单射R:M→M'，远远小于，M'为M的冗余消息集，R为冗余函数.R－1:R(M)→M是M'到M的映射，即R的逆映射，R和R－1都是公开的［3］.2 具有消息恢复功能的双方不可否认盲签名协议2.1 系统初始化设p，q为2个大素数，其中q(p－1)，g为的q阶元，签名私钥x∈Zn，公钥y=gxmod p，待签消息m∈Zn.2.2 生成可恢复消息的盲签名生成可恢复消息的盲签名步骤:步骤 1 签名人随机选择k∈Zq，计算 r=gkmod p.步骤2 将r发给消息拥有者;消息拥有者将消息进行冗余变换m→R(m)，随机选取l1，l2，l3∈Zn，盲化R(m):步骤3 将r'发送给签名人，签名人不知道R(m)，计算s=r'x+k mod q，然后将s 发给消息拥有者.消息拥有者验证gs=yr'r mod p是否成立.若成立，计算S=sl1+l2mod q，(R，S)为常规的具有消息恢复性能的的盲签名;否则输出“false”.任何人都可以验证签名的正确性:R(m)=g－SyRR mod p.再由公开的冗余函数恢复原消息.通常只希望指定的接收者能够恢复消息，将(R，S)处理得到一个指定接收者的签名［4］.2.3 (R，S)变换为指定接收者的盲签名(R，S)变换为指定接收者的盲签名步骤:步骤1 签名拥有者(以下称为A)随机选取对称密钥k，计算 M=Ek(R，S)，与关键字ξ结合后签名并加密，发送m1给指定的接收人(以下称为B):式中:ξ为关键字，包含报头，消息摘要等;ωn为实时时间戳，n=1，2，3，…，N;D 和 E 为 RSA 的加密/解密算法;PA，SA分别为A的公钥和私钥;PB，SB分别为B的公钥和私钥.步骤2 B收到m1后，计算得到ξ和M，根据ξ中的内容判断是否继续通信过程.若不需要该报文，单方面终止通信，否则计算步骤3 发送m2给A，A保留m2作为B收到m1的证据，将k签名加密得到的－k发送给B:步骤4B解密－k得到T″，判断时间戳ω3是否合理且没有使用过，保存ω3，计算:这样就可以验证签名的正确性，计算得到R(m)，再利用R－1得到m.3 对上述方案的进一步改进上述方案中，B仍然可以通过否认最后一步曾经收到－k，来达到对自己有利但违背公平公正原则的目的.为此引入可信第三方CA来制衡.A选取a∈，传送λ =(，IDB，IDA)给B.B 选择随机数b∈，传送μ =，gb，IDA，IDB)给 A，H 是收到λ的反馈承诺.A收到μ以后，计算选择c∈，计算传送υ给CA，并通知B从CA处获得新数据.B通过与CA的身份认证得到υ，计算B用消息密钥k解密恢复R(m)，检验如果R(m)∈R(M)，则m=R－1(R(m));如果这个消息m有意义，并且和关键字ξ中的信息吻合，就认为这个消息是安全、可靠、有效的［5－6］.4 安全性分析1)收方不能否认其收到签名.B首先收到的是加密后的签名，没有得到 ga之前，既不能对签名进行验证，也不能得到冗余消息R(m)，他必须向A发送已经接收到签名的证据H，A才会将ga传送给B，而有关ga的数据A必须经由CA得到.这样，由于可信第三方的存在，B不能否认他收到－k，若出现了上述问题中的纠纷，只能由他自己承担责任.从而维护了信息交互过程的公平公正性，有利于进一步促进该类协议的发展，增强人们对密码学协议的信心，更好地服务人们的生活.2)原始签名的不可伪造性.任何人要伪造一对有效的盲签名，使得成立，有以下3种途径:①任取R，S，带入上式中，R(m)=g－SyRR mod p，这样得到的 R(m)冗余度非常高，逆函数得到的消息没有错误且有意义的概率小之又小，也就是说冗余函数的引进有效防止了恶意的伪造攻击;②任取消息m和R，从中解出S，等价于求解离散对数问题;③任取消息m和S，从中解出R，比求解离散对数问题还要困难.3)签名者的不可否认性.签名中含有A的私钥，B在验证时用到A的公钥，A不能否认自己的签名.4)CA不能冒充A，也不能验证签名.RSA算法保证了B可以确信消息来源和恢复消息，其他人要想求得A的私钥，面临求解离散对数难题.由于A将gα以加密的形式传送给TTP，在没有B的私钥的情况下，很难获得gα;即便是不幸CA知道了gα，但没有B的私钥，还是不能验证签名并恢复消息.这就有了双重的安全保障。
rsa验签原理RSA验签原理RSA算法是一种非对称加密算法，其加密和解密的过程中使用了两个密钥：公钥和私钥。
公钥可以被任何人使用用于加密数据，但只有持有私钥的人才能够解密并读取数据。
RSA算法也可以用于数字签名，即发送者可以使用自己的私钥对消息进行签名，接收者可以使用发送者的公钥对签名进行验证，从而确认消息的真实性。
RSA数字签名用于在非对称加密系统中验证数据的真实性。
在数字签名中，发送方使用自己的私钥对数据进行哈希计算并签名，而接收方可以使用发送方的公钥来验证数字签名并确保数据的完整性和真实性。
数字签名可分为基于哈希函数的数字签名和基于公钥密码体制的数字签名两种。
在RSA数字签名中，接收者使用发送者的公钥来解密数字签名。
在进行数字签名时，发送者使用自己的私钥将要发送的数据进行哈希计算，然后将哈希值和签名一起发送给接收者。
接收者使用发送者的公钥对签名进行解密，并得到与发送者使用相同哈希函数对数据进行哈希计算时的哈希值。
接收者也会对要接收的数据进行哈希计算，如果接收到的哈希值与发送者发送的哈希值相同，则可以确认数据的完整性和真实性。
当进行RSA数字签名验证时，接收者使用发送者的公钥对接收到的签名进行解密，并得到哈希值。
如果接收者将接收到的数据进行哈希计算，并与解密后的哈希值进行比较，如果一致，则可以确认数据的完整性和真实性。
如果哈希值不一致，则可以确定数据已被篡改。
总的来说，RSA数字签名算法可以保证数据的完整性和真实性，防止数据被篡改。
在实际应用中，RSA数字签名算法可以被广泛应用于各种信息安全领域，如电子邮件、电子商务和移动支付等。
