Analysis And Design Of Cryptographic Algorithms Based On XTR Public Key System

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.