Public Key Cryptosystem Based On Lucas Sequences

Modern cryptography is the basic of information security, and one significant section of it is the public key cryptosystem. The classical RSA and Elgamal cryptosystems have some drawback in security, while most of other newly proposed cryptosystems have disdvantages in efficiency. In this thesis, a public key cryptosystem based on Lucas sequences is studied. It is more secure than the old cryptosystems, and more efficient than many other new ones.When parameter Q constantly equals to1, the Lucas sequence becomes Chebyshev polynomial sequence, which has one-way property and semi-group property, and can be used to design Chebyshev-Elgamal and Chebyshev-RSA cryptosystems. The security of Chebyshev-Elgamal cryptosystem is enfluenced by the sequence composed of Chebyshev polynomials on finite field Fp, but with the previous research methodology, it is hard to deeply investigate that sequence, and furtherly discuss about the parameter selection issue for the cryptosystem. In this thesis a new expression of Chebyshev polynomial sequence is introduced, based on which some important properties of the sequence are proved. Then the security of Chebyshev-Elgamal is discussed in detail, and some principles for parameter selection of the cryptosystem are proposed. Besides, the security of Chebyshev-RSA is also discussed, and it is found the cryptosystem is resistant to some known attacks against RSA-like cryptosystem, while vulnerable to some others. Because the general Lucas sequence (parameter Q takes arbitary value) has no obvious semi-group property, there are few public key cryptosystems based on it. In this thesis, the prorerties of the Lucas sequence are deeply investigated. Some special peoperties of the second Lucas sequence are found, by which a public key cryptosystem is constructed. The new designed cryptosystem is more secure than RSA cryptosysem, and more efficient than LUC-RSA cryptosysem. Based on it, a new secret key transport protocol and a new digital signature scheme is designed, whose security is also discussed, respectively.There are two most significant issues for a cryptosystem:the security and the efficiency. The latter is also studied, and some improvement schemes and a new algorithm are proposed. By converting the computation of Lucas sequence to the calculation of Chebyshev polynomial sequence and the operation of modular exponentiation, the running time of Yen-Laih algorithm is reduced by25%; Through the introduction of pre-computation in characteristic polynomial algorithm, a new computation scheme called "windowing algorithm" is proposed, which is very efficient when the computation of Lucas sequence is performed for many times; The Mogomery modular multiplication is used in modified Yen-Laih algorithm and characteristic polynomial algorithm, with the Mogomery modular square algorithm in CIOS mode being improved, to reduce the running time of single modular multiplication; finally, a new algorithm is presented and discussed, which computes Lucas sequence by only a few of modular exponentiations, when certain conditions are satisfied.