【作者】 丁秀欢；

【导师】 张树功；

【作者基本信息】 吉林大学 ， 计算数学， 2009， 博士

【摘要】 计算机和互联网技术的飞速发展,将我们的社会带入了信息化时代,使得信息系统的建立逐渐成为社会各个领域不可或缺的基础设施.任何机构都有需要保密的信息,使得信息的安全成为各界所共同关注的热点。XTR是由Lenstra和Verheul在Crypto 2000提出的一种新型公钥密码体制。它使用了GF(p~2)上的迹来表示GF(p~6)~*中阶为p~2-p+1的子群的元素,从而使得数据量降低到原来的1/3,而且相应的运算速度也比传统表示方法快。从安全角度来看,XTR是一种传统的基于子群离散对数问题的密码体系,即其安全性依赖于求有限域乘法群中离散对数的困难性。XTR体制已经成为近年来研究的热点,并被逐渐推广到密码体制的各种应用环境中。本文采用增加附加的2位串的方法来解决XTR密钥恢复算法中的“最小者”问题,充分考虑此算法中的其他限制条件,并利用加速的XTR算法来具体给出XTR-Blind-Nyberg-Rueppel和XTR-Blind-Schnorr改进签名方案,XTR-Nyberg-Rueppel完整消息恢复签名方案,XTR-Kurosawa-Desmedt自适应选择密文安全的密码方案。使得在同等安全程度下,各应用协议的效率,包括数据的存储量和各阶段的计算量,都大大提高。本文还借鉴Lenstra和Verheul等人在XTR方面的工作,在XTR~+公钥体制中提出无矩阵的核心算法,使得核心算法的运算效率显著提高。由于研究和改进扩展欧几里得序列的选择项算法对于计算机代数、数论和密码学的研究和发展有着非常重要的理论意义,所以本文最后分别对多项式和整数的扩展欧几里得序列的选择项算法进行了研究,其中包括了对多项式扩展欧几里得序列的选择项算法的加速和对整数扩展欧几里得序列的选择项算法的修正。更多还原

【Abstract】 With the rapid development and extensive applications of computer and communication technologies,our society goes into an information time.The establishment of information system has gradually become an essential foundation for nearly all fields of our society.As there exists confidential information in any organizations,the security problem about this information has become the common focus of both academia and enterprises.Since the invention of the concept of public key cryptography(PKC),PKC has been developed for about thirty years.Many excellent public key cryptosystems have been proposed and improved.But,the most popular public key cryptosystems are still RSA scheme and EIGamal scheme.Moreover,elliptic public key scheme has always been focused just because of its high efficiency.However,the present public key cryptosystems have some defects in computation,storing,convenient practicability and so on,which results in more restrictive applications.In recent years people is concerned about the study of systems that have the algebraic structures which use the extension finite fields.These systems can provide high compression data transmission,compact implementation process and performance improvement.XTR stands for "ECSTR",which is an abbreviation for Efficient and Compact Subgroup Trace Representation.The XTR public key system is a new cryptosystem proposed by Lenstra and Verheul in Crypto 2000.It uses the trace over GF(p~2) to represent elements of the order p~2-p+1 subgroup of GF(p~6)~*,thereby achieving a factor 3 size reduction.Also,the resulting calculations are appreciably faster than using the standard representation.Under the same application systems and similar secure conditions,it can be known from theoretical analysis that XTR can greatly increase the speed,and reduce the key sizes,data storage,computation and communication overhead compared with EIGamal and RSA public key cryptosystems.The method which uses trace function to represent elements of multiplicative group can completely take the place of the traditional representation of elements of subgroup.It can be applied to any cryptosystems based on discrete logarithm problem and raise to more excellent qualities without compromising security.From a security point of view,XTR is a traditional discrete logarithm system:for its security it relies on the difficulty of solving discrete logarithm related problems in the multiplicative group of a finite field.Thus,XTR is not based on any new primitive or new allegedly hard problem,on the contrary,it is based on the primitive underlying the very first public key cryptosystem,the Diffie-Hellman key agreement protocol.By using the analysis of theoretical foundation and protocol,we can deduce that the advantages of XTR compared with the popular public key cryptosystems nowadays are:ⅰ.Its very fast parameters and keys selection.Key selection for XTR is very fast compared to RSA,and orders of magnitude easier and faster than for ECC.This performance makes it easily feasible for all users of XTR to have public keys that are not shared with others,unlike ECC where a large part of the public key is often shared between all users of the system.ⅱ.Small key sizes.XTR keys are much smaller than RSA keys of comparable security.ECC keys allow a smaller representation than XTR keys,but in many circumstances(e.g. storage) ECC and XTR key sizes are comparable.ⅲ.Fast calculation speed.Full exponentiation in XTR is faster than full scalar multiplication in ECC over a 170-bit prime field,and thus substantially faster than full exponentiation in either RSA or traditional subgroup discrete logarithm systems of equivalent security.ⅳ.Its very easy programmability.ⅴ.Also,compared to ECC,the mathematics underlying XTR is straightforward, thus avoiding two common ECC-pitfalls:ascertaining that unfortunate parameter choices are avoided that happen to render the system less secure,and keeping abreast of,and incorporating additional checks published in,newly obtained results. As a result,XTR may be regarded as the best of three worlds,RSA,EIGamal,and ECC.It is an excellent alternative to either RSA,EIGamal,or ECC in applications such as SSL/TLS(Secure Sockets Layer/Transport Layer Security),public key smart cards,WAP/WTLS(Wireless Application Protocol/Wireless Transport Layer Security), IPSEC/IKE(Internet Protocol Security/Internet Key Exchange),and SET(Secure Electronic Transaction).In 2000,Lenstra and Verheul further proposed XTR key recovery algorithm,which leads to a factor 3 data transmission.However,this key recovery algorithm is restricted by some conditions.The most important condition among them is the "smallest" restriction. These conditions are very critical in practice,but they are neglected in almost all application protocols.If there are not rigorous assumptions and fully consideration about the details of the implementation of algorithm,the parameter corresponding problem may arise in future.This problem may lead to difficulties in the XTR compliant protocols, such as blind signature schemes and message recovery signature schemes.XTR system can be used into many cryptoschemes and digital signatures,but so far it is still not considered in provable security cryptosystems.For these problems,this paper mainly studies:◆We introduce additional two-bit strings to resolve the "smallest" question in XTR key recovery algorithm,fully consider the other restrictive conditions in this algorithm and use the accelerate XTR algorithms to give the improved XTR-Blind-Nyberg-Rueppel and XTR-Blind-Schnorr signature schemes which are presented by Chen Xiao-feng,Gao Hu-ming and Wang Yu-ming,the full version of the XTR-Nyberg-Rueppel message recovery signature scheme proposed by Lenstra and Verheul.The improved schemes are more efficient than the original signature schemes both in communication and computation without compromising security.◆Nowadays the most efficient adaptive chosen-ciphertext secure cryptosystem in the standard model is the one due to Kurosawa and Desmedt.We proposes an XTR version of the Kurosawa-Desmedt scheme.Our scheme is secure against adaptive chosen-ciphertext attack under the XTR version of the Decisional Diffie-Hellman assumption in the standard model.Comparing the efficiency between the proposed XTR-Kurosawa-Desmedt cryptoscheme and the Kurosawa-Desmedt scheme,we find that the proposed scheme is more efficient than the Kurosawa-Desmedt scheme both in communication and computation without compromising security.In order to resolve the parameter corresponding problem in XTR system,as well as to improve the computation efficiency,Wang Zehui et al.proposed a new public key cryptosystem so called XTR~+ based on the effective and compact subgroup trace representation in 2007.The XTR~+ public key system achieves GF(p~8) security using GF(p~4) arithmetic,so that the data storage is a half reduced.It was based on 4-th order LFSR sequence.But the fast pivotal algorithms were done by a 2nd order iteration based on the fast computation of the nth power of a 2×2 matrix.In addition,XTR+ is constructed as a cryptosystem of provable IND-CCA2 security and can be used for the strongly provable secure digital signature schemes,blind signature protocols and zeroknowledge proof protocols.Due to its optimization over the parameters,the expansion rate of these complicated protocols in XTR~+ is largely decreased.For the XTR~+ public key system,this paper studies:◆Motivated by the work in XTR studied by Lenstra and Verheul et al.,we describe matrix-free pivotal algorithms in XTR~+ public key system.These new algorithms obviously improve the computation efficiency.The algorithm for selected term of the extended Euclidean sequence which is still used nowadays has played a very important role in the study of early algorithms and procedural process.It is of great significance for the research fields in computer algebra, number theory and cryptology.Therefore,the study of the algorithm for selected term of the extended Euclidean sequence is of great importance in research and development of these fields.For the algorithm for selected term of the extended Euclidean sequence,this paper respectively studies:◆The reduced sum of two divisors is one of the fundamental operations in many problems and applications related to hyperelliptic curves.M.J.Jacobson,Jr et al presented a new algorithm for this operation in terms of continued fraction expansions on the three different possible models of a hyperelliptic curve:imaginary, real,and unusual.This algorithm relies on the Algorithm for Selected Term of the Polynomial Extended Euclidean Sequence(ASTPEES),and requires O(g~2) field operations,where g denotes the genus of the curve.We accelerate the ASTPEES algorithm by applying Half-GCD algorithm.Consequently, the algorithm for computing the reduced sum of two divisors of an arbitrary hyperelliptic curve is accelerated from quadratic to nearly linear time. ◆The common approach to the solution of the problems of modular and numerical rational number reconstruction which are two customary approach in computer algebra is by applying the Algorithm for Selected Term of the Integer Extended Euclidean Sequence(ASTIEES).Wang and Pan proposed an ASTIEES algorithm. The algorithm only spent nearly linear time,matching the known complexity bound for the integer gcd.We analyze the ASTIEES algorithm,then point out the bugs which are not considered comprehensively,and finally modify the ASTIEES algorithm.更多还原