The Fourth Order Linear Recurrence Sequence For RSA Type Cryptosystem

Wong, Tze Jin (2006) The Fourth Order Linear Recurrence Sequence For RSA Type Cryptosystem. Masters thesis, Universiti Putra Malaysia.

 123Kb

Abstract

A cryptosystem is derived from the fourth order linear recurrence relations analogous to the RSA cryptosystem which is based on Lucas sequences. The fourth order linear recurrence sequence is a sequence of integers −1 −2 −3 −4 = − + − n n n n n V PV QV RV SV , where P, Q, R and S are coefficients in quartic polynomial, 0 4 3 2 x − Px + Qx − Rx + S = .The factorization of the quartic polynomial modulo p can be classified into five major types. We define the cyclic structure for every types. Then, we can generate the Euler totient function from the cyclic structure of every types of the quartic polynomial.We have some properties of the sequence which are straightforward consequences of the definition. Then, we are able to define the composition and inverse of fourth order linear recurrence sequence. From cycles and totient, we know the quartic polynomial can be factorized into five major types, that is t[4], t[3,1], t[2,1], t[2] and t[1]. We sketch an algorithm to compute the type of a quartic polynomial in Fp[x], where p is any prime number. In this quartic cryptosystem, we have two large secret primes p and q, the product N of which is part of the encryption key. The encryption key is (e, N) where e is relatively prime toΦ(N) , which are analogous to Euler-φ function, to cover all possible cases. The decoding key, d is inverse e modulo Φ(N).For quartic cryptosystem, (P,Q,R) constitutes the message, and ( , , ) 1 2 3 C C C constitutes the ciphertext. In decoding, we are given the function ( ) g x = x −C x +C x −C x + but not ( ) 1 4 3 2 f x = x − Px + Qx − Rx + , and so we have to deduce the type of f in order to apply the algorithm correctly

Item Type: Thesis (Masters) Cryptography Associate Professor Mohamad Rushdan Bin Mohd Said, PhD IPM 2006 1 Institute for Mathematical Research 268 INVALID USER 23 May 2008 13:28 27 May 2013 06:47

Repository Staff Only: Edit item detail

View statistics for "The Fourth Order Linear Recurrence Sequence For RSA Type Cryptosystem "

Universiti Putra Malaysia Institutional Repository

Universiti Putra Malaysia Institutional Repository is an on-line digital archive that serves as a central collection and storage of scientific information and research at the Universiti Putra Malaysia.

Currently, the collections deposited in the IR consists of Master and PhD theses, Master and PhD Project Report, Journal Articles, Journal Bulletins, Conference Papers, UPM News, Newspaper Cuttings, Patents and Inaugural Lectures.

As the policy of the university does not permit users to view thesis in full text, access is only given to the first 24 pages only.