论文摘要
本文主要分两部分.第一部分对二次剩余求解问题进行系统性的研究,并分析其计算复杂度.二次剩余求解问题在计算机代数中是一个经典问题,它是基于椭圆曲线密码体制的基石.现在已有许多关于有限域上二次剩余问题的计算方法,我们对这些算法进行了重新整理归纳,并作出适当改进.经我们改进的Mctwani-Raghavan算法,其运行时间由原来的O(len(p)4)降到了O(len(p)3).另外我们从新的角度阐述了Adleman-Manders-Miller算法,并首次给出该算法的伪代码.我们对文中列举的算法都给出了正式的复杂度分析,这一工作将使得二次剩余计算的理论体系更加完善.第二部分对GMY强数字签名方案进行密码分析,提出了一种存在性伪造攻击方法.GMY强数字签名基于大数分解的难度,在GMY强数字签名方案中,签名者将对明文的每一比特进行签名,设计者称对手在获得大量真实签名的情况下也无法伪造一个新的签名.在本文中,我们提出了对GMY强数字签名的一种存在性伪造攻击,能够从已有的真实签名得到一个新的签名.我们将在不知道私钥p,q的情况下伪造一个新签名(Mˉ, xˉk),为了进行伪造我们构造了xˉk,Mˉ, x0,利用这三个量可以顺利完成验证过程,确保此签名的有效性.