论文部分内容阅读
数字签名作为密码学基本元语,广泛应用于认证,授权和抗抵赖,在密码学的理论与应用中占有重要地位.因为直接对长消息进行签名效率较低,为提高效率,数字签名总是和密码Hash函数结合使用.作为一种组合结构,分离Hash函数族与强分离Hash函数族的构造是组合设计理论在密码学中具体应用的一个重要研究课题.这是因为在密码学中,分离Hash函数族与强分离Hash函数族对构造无覆盖族, FP码,SFP码和IPP码起到重要作用156,85,89,94,96,97].
另一方面,群签名是数字签名的一个重要内容,是研究将签名用户的匿名性和签名的可追踪性有机结合起来的学术课题.群签名将密码学中两个看似矛盾的性质匿名性和追踪性统一在一起,充分体现了密码学的神奇作用,在数字合同,电子选举,电子投标和电子现金[17,18,23,24,45,53,62,84]等一系列实际生活中具有广泛并且重要的应用价值.对群签名方案的安全性进行分析,改进群签名方案以及设计出更加安全有效的群签名方案成为密码学研究的重要课题.
本文研究内容是应用有限域上的代数曲线构造Hash函数族,分析群签名方案的安全性以及应用Shor量子算法分解RSA模.
设n与m是整数且2≤m≤n,集合X和y的阶分别为n与m.设F={f|f:X→y},且|f|=N,则称F为(N,n,m).Hash函数族.Hash函数族F如果满足任意X<,1>,X<,2>∈,X<,1>∩X2=φ,|X|=ω1且|X<,2>|=ω2,至少存在一个函数f∈F满足f(X<,1>)∩f(X<,2>)=φ,称Hash函数族F为(N,n,m,{ω<,1>,<,ω>2})-分离Hash函数族,记为SHF(N;n,m,{ω<,1>,ω<,2>}).设N(n,m,{ω<,1>,ω<,2>})表示SHF(N;n,m,{ω<,1>,ω<,2>})存在的最小值N.应用概率与组合方法,我们得到:对给定的正整数m,ω<,1>和ω<,2>,N(n,m,{ω<,1>,ω<,2>})=θ(log n).然而,这个存在性定理的证明是非构造性的.构造出满足上面渐近性结果的分离Hash函数族是一个很有难度的研究课题.尽管许多学者在这方面做过工作[56,85,89,94,97,100],但他们都是应用组合设计的技巧进行递规构造,无法进一步提高函数的性能.
在第三章,应用有限域上的代数曲线,我们给出构造分离Hash函数族的方法.特别地,将我们基于Garcia-Stichtenoth曲线的构造方法与D.R.Stinson等人197I提出的乘积构造方法相结合,对任意给定的整数m,叫1和叫2,我们构造出满足Ⅳ=(=)(10g n)的一个无限类分离Hash函数族.对任意给定的整数m和w,我们得到满足码长N=O(logn)的无限类FP码和SFP码.进而本质地改进了应用组合方法得到的结果[85,97],并给出文章[89]中第五个公开问题的一个答案.
在第四章,应用有限域上的代数曲线,我们给出构造强分离Hash函数族的方法.应用Garcia-Stichtenoth曲线的构造方法与我们证明的强分离Hash函数族的乘积构造方法相结合,对任意给定的整数m,w<,1>和w<,2>,得到满足N=O(logn)的一个无限类强分离Hash函数族.对任意给定的整数m和w,我们得到满足码长N=O(logn)的无限类IPP码.对任意给定的整数m,w和t,我们得到满足码长N=O(logv)的无限类广义IPP码.本质地改进了关于强分离Hash函数族的渐近性结论[85]和IPP码的渐近性结果[85,100].
因为有限域上的代数曲线存在多项式时间的构造方法,本文对分离Hash函数族和强分离Hash函数族以及FP码,SFP码,IPP码和广义IPP码的构造达到了界N-O(logn),提供了最好的渐近行为,给出多项式时间的构造方法.
第五章分析了Kim-Park-Won群签名方案,Lee-Chang群签名方案,改进的Tseng-Jan群签名方案,Wang-Fu群签名方案,Zhang-Wu-Wang群签名方案和.Xia-Yuo群签名方案的安全性,证明这些方案是不安全的.我们从分析这些方案的安全性过程中总结出两个有用的技巧:随机扰动法,指数分析法.随机扰动法是指在保证签名验证方程成立的前提下,对某些签名数据作适当的随机变换使得追踪方程不成立.指数分析法是指在固定底数的情况下,为了消除指数位置上的挑战值,对相应的指数进行分析并逐步推出各个指数应具有的表达式.
第六章首先介绍群签名在电子商务中的应用,然后分析文献[24l中提出的一个基于群签名方案的电子货币系统Canard-Traore公平电子现金方案的安全性.文献[24]的作者声称Canard-Traore公平电子现金方案的安全性依赖于强RSA假设和Diffie-Hellman假设.我们证明该方案的安全性仅依赖于一个公开参数选取的区间长度.
应用量子计算机,Shor在文献[88]中证明了大整数因子分解问题存在多项式时间算法.对给定整数n,在模n乘法群中,Shor确定了寻找元素的阶的算法.应用随机算法[69],大整数因子分解问题可以约化为寻求元素阶的问题,所以该算法是可行的.但有一点值得强调:对随机选取的数,阶必须是偶数.事实上,这一限制在特定的情况下是可以去掉的.第七章,我们证明分解RSA模只需要求出2的阶,不论2的阶是奇数还是偶数.