This paper presents a new sequence called the \(k-\)division sequence. The Pell and Lehmer sequences are then used to define new sequences called the \(k-\)division \(L-\)Lehmer-Pell sequences and some properties of these sequences are determined. Then the \(k-\)division \(L-\)Lehmer-Pell sequences and corresponding self-invertible matrices are used in a new Affine-Hill cipher algorithm. The security of this cipher is examined.
Definition 1.1.For integers \(L, M\), and \(LM\neq 0\), \(L-4M\neq 0\), the Lehmer sequence \(\lbrace U_n(L,M)\}_{n=0}^\infty\) is \[U_n(L,M)=\left \{ \begin{array}{ll} LU_{n-1}(L,M)-MU_{n-2}(L,M)& n \mbox{ odd},\\ UF_{n-1}(L,M)-MU_{n-2}(L,M)& n \mbox{ even}, \end{array}\right.\] where \(U_0(L,M)=0\) and \(U_1(L,M)=1\) [13].
The Lehmer sequence in finite groups was introduced in [3] and the period was studied. In [2], perfect powers in sequences were derived by shifting non-degenerate quadratic Lucas-Lehmer binary sequences by a fixed integer. The Lehmer sequences and Lehmer orbits of groups were considered in [17] to obtain a new RSA algorithm.
The Pell sequence \(\lbrace P_n\}_{n=0}^\infty\) is defined as \[P_n=2P_{n-1}+P_{n-2}, n\geq 0,\] with initial conditions \(P_0=0\) and \(P_1=1\). The Pell sequence and its generalizations have been investigated extensively [12,6,15,4,11]. In [9], the \(k-\)nacci sequences were introduced and the generalized order \(k-\)Pell sequences in the semi-direct product of finite cyclic groups were given. The generalized order 2-Pell sequences of some classes of groups were also presented. In [16], new sequences were obtained from the generalized Pell \(p-\)numbers and Mersenne numbers. They were used in algorithms for Diffie-Hellman key exchange.
The characteristic polynomials of the Pell and Lehmer sequences are \(x^2-2x-1\) and \[\left \{ \begin{array}{ll} x^2-Lx+M& n \mbox{ odd},\\ x^2-x+M& n \mbox{ even}, \end{array}\right.\] respectively.
Definition 1.2. A matrix \(M\) is called self-invertible matrix if \(M = M^{-1}\) [1].
The Hill cipher was introduced in [10] and the Affine cipher was defined in [21]. Public key cryptography using the Hill cipher was considered in [22]. In [19], a key matrix of order 3 that reflects a line \(y = ax+b\) was used to overcome the noninvertible matrix problem in the Affine-Hill cipher modulo a prime number. The following encryption and decryption algorithms were also given. Encryption is \[C_i\equiv P_iK+B \ (\mathrm{mod}\ p),\] and decryption is \[P_i\equiv (C_i-B)K^{-1} \ (\mathrm{mod}\ p),\] where \(K\) is an \(n\times n\) key matrix, and \(P_i\), \(C_i\), and \(B\) are \(1\times n\) matrices over \(Z_p\), \(p\) a prime [18].
Here, the Pell and Lehmer sequences are used to define new sequences called the \(k-\)division \(L-\)Lehmer-Pell sequences. Some properties of these sequences are obtained. Then the \(k-\)division \(L-\)Lehmer-Pell sequences and corresponding self-invertible matrices are employed to propose a new Affine-Hill cipher algorithm. The security of this algorithm is also discussed.
The remainder of this paper is organized as follows. Section 2 introduces a new method for constructing sequences called \(k-\)division. Then the \(k-\)division \(L-\)Lehmer-Pell sequences are defined and some results are given. Section 3 presents a new Affine-Hill cipher algorithm and its security is examined. Finally, some concluding remarks are given in Section 4.
In this section, we present a new method for constructing sequences called \(k-\)division. Then the \(k-\)division \(L-\)Lehmer-Pell sequences are defined.
Definition 2.1. Let \(f(x)\) and \(g(x)\) be the characteristic polynomials of two sequences of degree \(u\) and \(m\), respectively, where \(m\geq u\). For \(k \in \mathbb{N}\), the \(k-\)division sequence, \(\{ h_n(k)\} _{n=0}^\infty\), is \[h_n(k)=x^{k}(g(x))+t(x), n\geq k+m. \tag{1}\] where \(t(x)\) is the remainder of \({\dfrac{x^{k}(g(x))}{f(x)}}\), and the initial conditions are \(h_0(k)=h_1(k)=\cdots=h_{m+k-2}(k)=0, h_{m+k-1}(k)=1\).
Let \[g(x)=\left \{ \begin{array}{ll} x^2-Lx+M& n \mbox{ odd},\\ x^2-x+M& n \mbox{ even}, \end{array}\right.\] and \(f(x)=x^2-2x-1\), and consider \(M=-1\) in the remainder of the paper. By Definition 2.1, the following new sequences are obtained.
Definition 2.2. For \(M=-1\), the \(1-\)division \(3-\)Lehmer-Pell sequences, denoted by \(\{ hL_n(k,L)\} _{n=0}^\infty\), are \[hL_n(1,3)=\left \{ \begin{array}{ll} 3hL_{n-1}(1,3)+3hL_{n-2}(1,3)+hL_{n-3}(1,3)& n \mbox{ odd},\\ hL_{n-1}(1,3)+hL_{n-2}(1,3)+hL_{n-3}(1,3)& n \mbox{ even}, \end{array}\right.\] where \(hL_{0}(1,3)=hL_{1}(1,3)=0\) and \(hL_{2}(1,3)=1\).
Thus, we have \(\{ hL_n(1,3)\} _{n=0}^\infty=\{ 0,0,1,3,2,16,11,83,56,428,2289,\cdots, \}\).
We have the following \(k-\)division \(3-\)Lehmer-Pell sequences.
(i) The \(2-\)division \(3-\)Lehmer-Pell sequence, denoted by \(\{ hL_n(2,3) \}_{n=0}^\infty\), is \[hL_n(2,3)=\left \{ \begin{array}{ll} 3hL_{n-1}(2,3)+hL_{n-2}(2,3)+5hL_{n-3}(2,3)+2hL_{n-4}(2,3)& n \mbox{ odd},\\ hL_{n-1}(2,3)+hL_{n-2}(2,3)-5hL_{n-3}(2,3)-2hL_{n-3}(2,3)& n \mbox{ even}, \end{array}\right.\] with initial conditions \(hL_{0}(2,3)=hL_1(2,3)= hL_{2}(2,3)=0, hL_{2}(2,3)=1\), so \[\{ hL_n(2,3)\} _{n=0}^\infty=\{ 0,0,0,1,1,4,0,11,-11,-14,-80,-287,\cdots \}.\]
(ii) The \(3-\)division \(3-\)Lehmer-Pell sequence, denoted by \(\{ hL_n(3,3) \}_{n=0}^\infty\), is \[hL_n(3,3)=\left \{ \begin{array}{ll} 3hL_{n-1}(3,3)+hL_{n-2}(3,3)+12hL_{n-4}(3,3)+5hL_{n-5}(3,3)& n \mbox{ odd},\\ hL_{n-1}(3,3)+hL_{n-2}(3,3)-12hL_{n-4}(3,3)-5hL_{n-5}(3,3)& n \mbox{ even}, \end{array}\right.\] with initial conditions \(hL_0(3,3)=hL_1(3,3)= hL_{2}(3,3)= hL_{3}(3,3)=0,~hL_{4}(3,3)=1\), so \[\{ hL_n(3,3)\} _{n=0}^\infty=\{ 0,0,0,0,1,3,4,15,7,77,21,340,202,1905,1407,\cdots \}.\]
(iii) The \(4-\)division \(3-\)Lehmer-Pell sequence, denoted by \(\{ hL_n(4,3) \}_{n=0}^\infty\), is \[hL_n(4,3)=\left \{ \begin{array}{ll} 3hL_{n-1}(4,3)+hL_{n-2}(4,3)+29hL_{n-5}(4,3)+12hL_{n-6}(4,3)& n \mbox{ odd},\\ hL_{n-1}(4,3)+hL_{n-2}(4,3)-29hL_{n-5}(4,3)-12hL_{n-6}(4,3)& n \mbox{ even}, \end{array}\right.\] with initial conditions \(hL_0(4,3)=hL_1(4,3)= hL_{2}(4,3)= hL_{3}(4,3)=hL_{4}(4,3)=0, hL_{5}(4,3)=1\), so \[\{ hL_n(4,3)\} _{n=0}^\infty=\{ 0,0,0,0,0,1,1,4,5,19,-5,45,-88,-26,-725,\cdots \}.\]
(iv) The \(k-\)division \(3-\)Lehmer-Pell sequences, denoted by \(\{ hL_n(k,3) \}_{n=0}^\infty\), are \[hL_n(k,3)=\left \{ \begin{array}{ll} 3hL_{n-1}(k,3)+hL_{n-2}(k,3)+P_{k+1}hL_{n-k-1}(k,3) +P_{k}hL_{n-k-2}(k,3)& n \mbox{ odd},\\ hL_{n-1}(k,3)+hL_{n-2}(k,3)-P_{k+1}hL_{n-k-1}(k,3) -P_{k}hL_{n-k-2}(k,3)& n \mbox{ even}, \end{array}\right.\] with initial conditions \(hL_0(k,3)=hL_1(k,3)= \cdots = hL_{k}(k,3)=0, hL_{k+1}(k,3)=1\).
Lemma 2.3. For \(k\geq 2\), let \(g_{hL_n(k,3)}\) be the generating function of the \(k-\)division \(3-\)Lehmer-Pell sequences. Then \[g_{hL_n(k,3)}=\left \{ \begin{array}{ll} \dfrac{x^{k+1}}{1-3x-x^2-P_{k+1}x^{k+1} -P_{k}x^{k+2}} & n \mbox{ odd},\\ \dfrac{x^{k+1}}{1-x-x^2+P_{k+1}x^{k+1} +P_{k}x^{k+2}} & n \mbox{ even}, \end{array}\right. \tag{2}\]
Proof. For \(k\geq 2\), let \(g_{hL_n(k,3)}\) be the generating function of the \(k-\)division \(3-\)Lehmer-Pell sequences. If \(n\) is odd, then \[\begin{aligned} g_{hL_n(k,3)} &=\sum_{n=1}^\infty hL_n(k,3)x^n\\ &=hL_1(k,3) x+hL_2(k,3) x^2+\cdots+hL_{k+1}(k,3) x^{k+1}+\sum_{n=k+2}^\infty hL_n(k,3) x^n\\ &=x^{k+1}+\sum_{n=k+2}^\infty(3hL_{n-1}(k,3)+hL_{n-2}(k,3)+P_{k+1}hL_{n-k-1}(k,3) +P_{k}hL_{n-k-2}(k,3)) x^n\\ &=x^{k+1}+3\sum_{n=k+2}^\infty hL_{n-1}(k,3)x^n+\sum_{n=k+2}^\infty hL_{n-2}(k,3)x^n+P_{k+1}\sum_{n=k+2}^\infty hL_{n-k-1}(k,3)x^n\\ &~~~+P_{k}\sum_{n=k+2}^\infty h_{n-k-2}(k,3)x^n\\ &=x^{k+1}+3x\sum_{n=1}^\infty hL_{n}(k,3)x^n+ x^2\sum_{n=1}^\infty hL_{n}(k,3)x^n+P_{k+1}x^{k+1}\sum_{n=1}^\infty hL_{n}(k,3)x^n \\ &~~~+P_{k}x^{k+2}\sum_{n=1}^\infty hL_{n}(k,3)x^n\\ &=x^{k+1}+3xg_{hL_n(k,3)}+x^2g_{hL_n(k,3)} + P_{k+1}x^{k+1} g_{hL_n(k,3)}+P_{k}x^{k+2}g_{hL_n(k,3)}, \end{aligned}\] so \[g_{hL_n(k,3)}=\dfrac{x^{k+1}}{1-3x-x^2-P_{k+1}x^{k+1} -P_{k}x^{k+2}}.\]
If \(n\) is even, then
\[\begin{aligned} g_{hL_n(k,3)} &=\sum_{n=1}^\infty hL_n(k,3)x^n\\ &=hL_1(k,3) x+hL_2(k,3) x^2+\cdots+hL_{k+1}(k,3) x^{k+1}+\sum_{n=k+2}^\infty hL_n(k,3) x^n\\ &=x^{k+1}+\sum_{n=k+2}^\infty(hL_{n-1}(k,3)+hL_{n-2}(k,3)-P_{k+1}hL_{n-k-1}(k,3) -P_{k}hL_{n-k-2}(k,3)) x^n\\ &=x^{k+1}+\sum_{n=k+2}^\infty hL_{n-1}(k,3)x^n+\sum_{n=k+2}^\infty hL_{n-2}(k,3)x^n-P_{k+1}\sum_{n=k+2}^\infty hL_{n-k-1}(k,3)x^n\\ &~~~-P_{k}\sum_{n=k+2}^\infty h_{n-k-2}(k,3)x^n\\ &=x^{k+1}+x\sum_{n=1}^\infty hL_{n}(k,3)x^n+ x^2\sum_{n=1}^\infty hL_{n}(k,3)x^n-P_{k+1}x^{k+1}\sum_{n=1}^\infty hL_{n}(k,3)x^n \\ &~~~-P_{k}x^{k+2}\sum_{n=1}^\infty hL_{n}(k,3)x^n\\ &=x^{k+1}+xg_{hL_n(k,3)}+x^2g_{hL_n(k,3)} – P_{k+1}x^{k+1} g_{hL_n(k,3)}-P_{k}x^{k+2}g_{hL_n(k,3)}, \end{aligned}\] so \[g_{hL_n(k,3)}=\dfrac{x^{k+1}}{1-x-x^2+P_{k+1}x^{k+1} +P_{k}x^{k+2}}.\] ◻
Lemma 2.4. For \(k\geq 2\), the generating function of the \(k-\)division \(3-\)Lehmer-Pell sequences has exponential representation \[g_{hL_n(k,3)}=\left \{ \begin{array}{ll} x^{k+1}exp \sum_{i=1}^\infty\dfrac{x^i}{i}(3+x+P_{k+1}x^{k} +P_{k}x^{k+1})^i & n \mbox{ odd},\\ x^{k+1}exp \sum_{i=1}^\infty\dfrac{x^i}{i}(1+x-P_{k+1}x^{k} -P_{k}x^{k+1})^i & n \mbox{ even}, \end{array}\right.\]
Proof. From Lemma 2.3, for \(n\) odd we have \[\ln\dfrac{g_{hL_n(k,3)}}{x^{k+1}}=-\ln(1-3x-x^2-P_{k+1}x^{k+1} -P_{k}x^{k+2}),\] so then \[\begin{aligned} &-\ln(1-3x-x^2-P_{k+1}x^{k+1} -P_{k}x^{k+2}) =-[-x(3+x+P_{k+1}x^{k} +P_{k}x^{k+1})\\ &-\dfrac{1}{2}x^2(3+x+P_{k+1}x^{k} +P_{k}x^{k+1})^2-\cdots-\dfrac{1}{i}x^i(3+x+P_{k+1}x^{k} +P_{k}x^{k+1})^i-\cdots], \end{aligned}\] and for \(n\) even we have \[\ln\dfrac{g_{hL_n(k,3)}}{x^{k+1}}=-\ln(1-x-x^2+P_{k+1}x^{k+1} +P_{k}x^{k+2}),\] so then \[\begin{aligned} &-\ln(1-x-x^2+P_{k+1}x^{k+1} +P_{k}x^{k+2}) =-[-x(1+x-P_{k+1}x^{k} -P_{k}x^{k+1})\\ &~~~~-\dfrac{1}{2}x^2(1+x-P_{k+1}x^{k} -P_{k}x^{k+1})^2-\cdots-\dfrac{1}{i}x^i(1+x-P_{k+1}x^{k} -P_{k}x^{k+1})^i-\cdots]. \end{aligned}\] ◻
For \(k\geq 2\), define the \(k-\)division \(4-\)Lehmer-Pell sequences as follows.
(i) The \(2-\)division \(4-\)Lehmer-Pell sequence, denoted by \(\{ hL_n(2,4) \}_{n=0}^\infty\), is \[hL_n(2,4)=\left \{ \begin{array}{ll} 4hL_{n-1}(2,4)+hL_{n-2}(2,4)+10hL_{n-3}(2,4)+4hL_{n-4}(2,4)& n \mbox{ odd},\\ hL_{n-1}(2,4)+hL_{n-2}(2,4)-10hL_{n-3}(2,4)-4hL_{n-3}(2,4)& n \mbox{ even}, \end{array}\right.\] with initial conditions \(hL_{0}(2,4)=hL_1(2,4)= hL_{2}(2,4)=0, hL_{2}(2,4)=1\), so \[\{ hL_n(2,4)\} _{n=0}^\infty=\{ 0,0,0,1,1,5,-4,3,-55,-237,-306,-1999,285,\cdots \}.\]
(ii) The \(3-\)division \(4-\)Lehmer-Pell sequence, denoted by \(\{ hL_n(3,4) \}_{n=0}^\infty\), is \[hL_n(3,4)=\left \{ \begin{array}{ll} 4hL_{n-1}(3,4)+hL_{n-2}(3,4)+24hL_{n-4}(3,4)+10hL_{n-5}(3,4)& n \mbox{ odd},\\ hL_{n-1}(3,4)+hL_{n-2}(3,4)-24hL_{n-4}(3,4)-10hL_{n-5}(3,4)& n \mbox{ even}, \end{array}\right.\] with initial conditions \(hL_0(3,4)=hL_1(3,4)= hL_{2}(3,4)= hL_{3}(3,4)=0,~hL_{4}(3,4)=1\), so \[\{ hL_n(3,4)\} _{n=0}^\infty=\{ 0,0,0,0,1,4,5,24,5,150,-5,756,391,5970,4981,\cdots \}.\]
(iii) The \(4-\)division \(4-\)Lehmer-Pell sequence, denoted by \(\{ hL_n(4,4) \}_{n=0}^\infty\), is \[hL_n(4,4)=\left \{ \begin{array}{ll} 4hL_{n-1}(4,4)+hL_{n-2}(4,4)+58hL_{n-5}(4,4)+24hL_{n-6}(4,4)& n \mbox{ odd},\\ hL_{n-1}(4,4)+hL_{n-2}(4,4)-58hL_{n-5}(4,4)-24hL_{n-6}(4,4)& n \mbox{ even}, \end{array}\right.\] with initial conditions \(hL_0(4,4)=hL_1(4,4)= hL_{2}(4,4)= hL_{3}(4,4)=hL_{4}(4,4)=0, hL_{5}(4,4)=1\), so \[\{ hL_n(4,4)\} _{n=0}^\infty=\{ 0,0,0,0,0,1,1,5,6,29,-23,19,-318,\cdots \}.\]
(iv) The \(k-\)division \(4-\)Lehmer-Pell sequences, denoted by \(\{ hL_n(k,4) \}_{n=0}^\infty\), are \[hL_n(k,4)=\left \{ \begin{array}{ll} 4hL_{n-1}(k,4)+hL_{n-2}(k,4)+2P_{k+1}hL_{n-k-1}(k,4) +2P_{k}hL_{n-k-2}(k,4)& n \mbox{ odd},\\ hL_{n-1}(k,4)+hL_{n-2}(k,4)-2P_{k+1}hL_{n-k-1}(k,4) -2P_{k}hL_{n-k-2}(k,4)& n \mbox{ even}, \end{array}\right.\] with initial conditions \(hL_0(k,4)=hL_1(k,4)= \cdots= hL_{k}(k,4)=0, hL_{k+1}(k,4)=1\).
For \(k\geq 2\), define the \(k-\)division \(5-\)Lehmer-Pell sequence as follows.
(i) The \(2-\)division \(5-\)Lehmer-Pell sequence, denoted by \(\{ hL_n(2,5) \}_{n=0}^\infty\), is \[hL_n(2,5)=\left \{ \begin{array}{ll} 5hL_{n-1}(2,5)+hL_{n-2}(2,5)+15hL_{n-3}(2,5)+6hL_{n-4}(2,5)& n \mbox{ odd},\\ hL_{n-1}(2,5)+hL_{n-2}(2,5)-15hL_{n-3}(2,5)-6hL_{n-3}(2,5)& n \mbox{ even}, \end{array}\right.\] with initial conditions \(hL_{0}(2,5)=hL_1(2,5)= hL_{2}(2,5)=0, hL_{2}(2,5)=1\), so \[\{ hL_n(2,5)\} _{n=0}^\infty=\{ 0,0,0,1,1,6,-8,-13,-117,-682,-556,-5295,5018,\cdots \}.\]
(ii) The \(3-\)division \(5-\)Lehmer-Pell sequence, denoted by \(\{ hL_n(3,5) \}_{n=0}^\infty\), is \[hL_n(3,5)=\left \{ \begin{array}{ll} 5hL_{n-1}(3,5)+hL_{n-2}(3,5)+36hL_{n-4}(3,5)+15hL_{n-5}(3,5)& n \mbox{ odd},\\ hL_{n-1}(3,5)+hL_{n-2}(3,5)-36hL_{n-4}(3,5)-15hL_{n-5}(3,5)& n \mbox{ even}, \end{array}\right.\] with initial conditions \(hL_0(3,5)=hL_1(3,5)= hL_{2}(3,5)= hL_{3}(3,5)=0,~hL_{4}(3,5)=1\), so \[\{ hL_n(3,5)\} _{n=0}^\infty=\{ 0,0,0,0,1,5,6,35,5,255,-31,1450,714,\cdots \}.\]
(iii) The \(4-\)division \(5-\)Lehmer-Pell sequence, denoted by \(\{ hL_n(4,5) \}_{n=0}^\infty\), is \[hL_n(4,5)=\left \{ \begin{array}{ll} 5hL_{n-1}(4,5)+hL_{n-2}(4,5)+87hL_{n-5}(4,5)+36hL_{n-6}(4,5)& n \mbox{ odd},\\ hL_{n-1}(4,5)+hL_{n-2}(4,5)-87hL_{n-5}(4,5)-36hL_{n-6}(4,5)& n \mbox{ even}, \end{array}\right.\] with initial conditions \(hL_0(4,5)=hL_1(4,5)= hL_{2}(4,5)= hL_{3}(4,5)=hL_{4}(4,5)=0, hL_{5}(4,5)=1\), so \[\{ hL_n(4,5)\} _{n=0}^\infty=\{ 0,0,0,0,0,1,1,6,7,41,-39,-31,-628,-2346,-2346,\cdots \}.\]
(iv) The \(k-\)division \(5-\)Lehmer-Pell sequence, denoted by \(\{ hL_n(k,5) \}_{n=0}^\infty\), is \[hL_n(k,5)=\left \{ \begin{array}{ll} 5hL_{n-1}(k,5)+hL_{n-2}(k,5)+3P_{k+1}hL_{n-k-1}(k,5) +3P_{k}hL_{n-k-2}(k,5)& n \mbox{ odd},\\ hL_{n-1}(k,5)+hL_{n-2}(k,5)-3P_{k+1}hL_{n-k-1}(k,5) -3P_{k}hL_{n-k-2}(k,5)& n \mbox{ even}, \end{array}\right.\] with initial conditions \(hL_0(k,5)=hL_1(k,5)= \cdots= hL_{k}(k,5)=0, hL_{k+1}(k,5)=1\).
Thus, for \(k\geq 2\), the \(k-\)division \(L-\)Lehmer-Pell sequences, denoted by \(\{ hL_n(k,L) \}_{n=0}^\infty\), are \[hL_n(k,5)=\left \{ \begin{array}{ll} LhL_{n-1}(k,5)+hL_{n-2}(k,5)+(L-2)P_{k+1}hL_{n-k-1}(k,5)& \\~~~~+(L-2)P_{k}hL_{n-k-2}(k,5)& n \mbox{ odd},\\ hL_{n-1}(k,5)+hL_{n-2}(k,5)-(L-2)P_{k+1}hL_{n-k-1}(k,5)& \\~~~~-(L-2)P_{k}hL_{n-k-2}(k,5)& n \mbox{ even}, \end{array}\right.\] with initial conditions \(hL_0(k,L)=hL_1(k,L)= \cdots= hL_{k}(k,L)=0, hL_{k+1}(k,L)=1\).
Lemma 2.5. For \(k\geq 2\), let \(g_{hL_n(k,L)}\) be the generating function of the \(k-\)division \(L-\)Lehmer-Pell sequences. Then \[g_{hL_n(k,L)}=\left \{ \begin{array}{ll} \dfrac{x^{k+1}}{1-Lx-x^2-(L-2)P_{k+1}x^{k+1} -(L-2)P_{k}x^{k+2}} & n \mbox{ odd},\\ \dfrac{x^{k+1}}{1-x-x^2+(L-2)P_{k+1}x^{k+1} +(L-2)P_{k}x^{k+2}} & n \mbox{ even}, \end{array}\right. \tag{3}\]
Proof. The proof is similar to that for Lemma 2.3 and so is omitted. ◻
Similar to Lemma 2.4, the following lemma is obtained.
Lemma 2.6. For \(k\geq 2\), the generating function of the \(k-\)division \(L-\)Lehmer-Pell sequences has exponential representation \[g_{hL_n(k,L)}=\left \{ \begin{array}{ll} x^{k+1}exp \sum_{i=1}^\infty\dfrac{x^i}{i}(L+x+(L-2)P_{k+1}x^{k} +(L-2)P_{k}x^{k+1})^i & n \mbox{ odd},\\ x^{k+1}exp \sum_{i=1}^\infty\dfrac{x^i}{i}(1+x-(L-2)P_{k+1}x^{k} -(L-2)P_{k}x^{k+1})^i & n \mbox{ even}, \end{array}\right.\]
In this section, the \(k-\)division \(L-\)Lehmer-Pell sequences and corresponding self-invertible matrices are employed to obtain an Affine-Hill cipher algorithm. Let the public key be \((hL_n(k,L),p)\) where \(p\) is prime and \(i \in \mathbb{N}\) is the secret key. The message \(m\) is first divided into matrices of size \(1\times 4\) modulo \(p\) denoted \(P_j\), \(1\leq j\leq n\). The secret key is used to compute \[hL_{i}(k,L),~hL_{i+1}(k,L), hL_{i+2}(k,L),~hL_{i+3}(k,L).\]
Then, a self-invertible matrix \(K\) is obtained as follows \[K=\begin{bmatrix} hL_{i}(k,L)&hL_{i+1}(k,L)&1-hL_{i}(k,L)&-hL_{i+1}(k,L)\\ hL_{i+2}(k,L)&hL_{i+3}(k,L)&-hL_{i+2}(k,L)&1-hL_{i+3}(k,L)\\ 1+hL_{i}(k,L)&hL_{i+1}(k,L)&-hL_{i}(k,L)&-hL_{i+1}(k,L)\\ hL_{i+2}(k,L)&1+hL_{i+3}(k,L)&-hL_{i+2}(k,L)&-hL_{i+3}(k,L) \end{bmatrix} \ (\mathrm{mod}\ p),\] as well as \[B=\begin{bmatrix} hL_{p+i}(k,L)&hL_{p+i+1}(k,L)&hL_{p+i+2}(k,L)&hL_{p+i+3}(k,L) \end{bmatrix}.\]
The message is used to compute \(C_j\equiv P_jK+B \ (\mathrm{mod}\ p)\) and \(C=C_j, 1\leq j \leq n\) is sent. For decryption, the public key \((hL_n(k,L),p)\) and the secret key \(i\) are employed to compute \(K\) and \(B\). Then \(K\) and \(B\) are used to obtain \[P_j\equiv (C_j-B)K^{-1} \ (\mathrm{mod}\ p).\]
The proposed algorithm is given below.
Let \((hL_n(k,L),p)\) be the public key where \(p\) is prime and \(i \in \mathbb{N}\) be the secret key.
Encryption
1. Divide the message into matrices of size \(1\times 4\) modulo \(p\) denoted \(P_j\). Using the secret key, compute \(hL_{i}(k,L),hL_{i+1}(k,L), hL_{i+2}(k,L),hL_{i+3}(k,L)\).
2. Obtain a self-invertible matrix \(K\) as follows \[K=\begin{bmatrix} hL_{i}(k,L)&hL_{i+1}(k,L)&1-hL_{i}(k,L)&-hL_{i+1}(k,L)\\ hL_{i+2}(k,L)&hL_{i+3}(k,L)&-hL_{i+2}(k,L)&1-hL_{i+3}(k,L)\\ 1+hL_{i}(k,L)&hL_{i+1}(k,L)&-hL_{i}(k,L)&-hL_{i+1}(k,L)\\ hL_{i+2}(k,L)&1+hL_{i+3}(k,L)&-hL_{i+2}(k,L)&-hL_{i+3}(k,L) \end{bmatrix} \ (\mathrm{mod}\ p).\]
3. Compute \[B=\begin{bmatrix} hL_{p+i}(k,L)&hL_{p+i+1}(k,L)&hL_{p+i+2}(k,L)&hL_{p+i+3}(k,L) \end{bmatrix}.\]
4. Using the message, compute \(C_j\equiv P_jK+B \ (\mathrm{mod}\ p)\).
5. Send \(C\).
Decryption
1. Using the public key \((hL_n(k,L),p)\) and secret key \(i\), compute \(K\) and \(B\).
2. Using \(K\) and \(B\), obtain \(P_j\equiv (C_j-B)K^{-1} \ (\mathrm{mod}\ p).\)
The proposed algorithm is illustrated in the following example.
Examle 3.1. Let the public key be \((hL_n(1,3),5)\) and the secret key be \(i=4\). The message is \(12,13,2,3,3,7,9,2380,1,3\).
Encryption
1. Divide a message into matrix size \(1\times 4\) modulo \(p\) denoted \(P_j\), \(1\leq j\leq n\). We have \[P_1=\begin{bmatrix} 12&13&2&3 \end{bmatrix}=\begin{bmatrix} 2&3&2&3 \end{bmatrix} \ (\mathrm{mod}\ 5).\] \[P_2=\begin{bmatrix} 3&7&9&2380 \end{bmatrix}=\begin{bmatrix} 3&2&4&0 \end{bmatrix} \ (\mathrm{mod}\ 5).\] \[P_3=\begin{bmatrix} 1&3&0&0 \end{bmatrix}\ (\mathrm{mod}\ 5).\] Using secret key, compute \(hL_{4}(1,3)=2,hL_{5}(1,3)=16, hL_{6}(k,3)=11,hL_{7}(k,3)=83\).
2. Obtain a self-invertible matrix \(K\) as follows \[\begin{aligned} K&=\begin{bmatrix} hL_{4}(1,3)&hL_{5}(1,3)&1-hL_{4}(1,3)&-hL_{5}( 1,3)\\ hL_{6}(1,3)&hL_{7}(1,3)&-hL_{6}(1,3)&1-hL_{7}( 1,3)\\ 1+hL_{4}(1,3)&hL_{5}(1,3)&-hL_{4}(1,3)&-hL_{ 5}(1,3)\\ hL_{6}(1,3)&1+hL_{7}(1,3)&-hL_{6}(1,3)&-hL_{ 7}(1,3) \end{bmatrix}\\&=\begin{bmatrix} 2&16&-1&-16\\ 11&83&-11&-82\\ 3&16&-2&-16\\ 11&84&-11&-83\\ \end{bmatrix}\\ &=\begin{bmatrix} 2&1&4&4\\ 1&3&4&3\\ 3&1&3&4\\ 1&4&4&2 \end{bmatrix} ~\ (\mathrm{mod}\ 5). \end{aligned}\]
3. Compute \[\begin{aligned} B&=\begin{bmatrix} hL_{9}(1,3)&hL_{10}(1,3)&hL_{11}(1,3)&hL_{ 12}(1,3)\\ \end{bmatrix}\\&=\begin{bmatrix} 428&289&2207&1407 \end{bmatrix}\\ &\equiv\begin{bmatrix} 3&4&2&0 \end{bmatrix} ~\ (\mathrm{mod}\ 5). \end{aligned}\]
4. Using the message, compute \(C_j\equiv P_jK+B \ (\mathrm{mod}\ p)\) so then we have \[C_1\equiv P_1K+B=\begin{bmatrix} 2&3&2&3 \end{bmatrix}\begin{bmatrix} 2&1&4&4\\ 1&3&4&3\\ 3&1&3&4\\ 1&4&4&2 \end{bmatrix}+\begin{bmatrix} 3&4&2&0 \end{bmatrix}\equiv \begin{bmatrix} 4&4&0&1 \end{bmatrix} \ (\mathrm{mod}\ 5).\] \[C_2\equiv P_2K+B=\begin{bmatrix} 3&2&4&0 \end{bmatrix}\begin{bmatrix} 2&1&4&4\\ 1&3&4&3\\ 3&1&3&4\\ 1&4&4&2 \end{bmatrix}+\begin{bmatrix} 3&4&2&0 \end{bmatrix}\equiv \begin{bmatrix} 3&2&4&4 \end{bmatrix} \ (\mathrm{mod}\ 5).\] \[C_3\equiv P_3K+B=\begin{bmatrix} 1&3&0&0 \end{bmatrix}\begin{bmatrix} 2&1&4&4\\ 1&3&4&3\\ 3&1&3&4\\ 1&4&4&2 \end{bmatrix}+\begin{bmatrix} 3&4&2&0 \end{bmatrix}\equiv \begin{bmatrix} 3&4&3&3 \end{bmatrix} \ (\mathrm{mod}\ 5).\]
5. Send \(C=C_1C_2C_3=4,4,0,1,3,2,4,4,3,4,3,3\).
Decryption
1. Using the public key \((hL_n(1,3),5)\) and secert key \(4\), compute \(K\) and \(B\).
2. Using \(K\) and \(B\), obtain \(P_j\equiv (C_j-B)K^{-1} \ (\mathrm{mod}\ 5)\). \[\begin{aligned} P_1&\equiv (C_1-B)K^{-1} \\&=(\begin{bmatrix} 4&4&0&1 \end{bmatrix}-\begin{bmatrix} 3&4&0&1 \end{bmatrix})\times \begin{bmatrix} 2&1&4&4\\ 1&3&4&3\\ 3&1&3&4\\ 1&4&4&2 \end{bmatrix}^{-1} \\&\equiv \begin{bmatrix} 2&3&2&3 \end{bmatrix}\ (\mathrm{mod}\ 5), \end{aligned}\] \[\begin{aligned} P_2&\equiv (C_2-B)K^{-1}\\ &=(\begin{bmatrix} 3&2&4&4 \end{bmatrix}-\begin{bmatrix} 3&4&0&1 \end{bmatrix})\times \begin{bmatrix} 2&1&4&4\\ 1&3&4&3\\ 3&1&3&4\\ 1&4&4&2 \end{bmatrix}^{-1} \\&\equiv \begin{bmatrix} 3&2&4&0 \end{bmatrix}\ (\mathrm{mod}\ 5), \end{aligned}\] \[\begin{aligned} P_3&\equiv (C_3-B)K^{-1} \\&=(\begin{bmatrix} 3&4&3&3 \end{bmatrix}-\begin{bmatrix} 3&4&0&1 \end{bmatrix})\times \begin{bmatrix} 2&1&4&4\\ 1&3&4&3\\ 3&1&3&4\\ 1&4&4&2 \end{bmatrix}^{-1}\\& \equiv \begin{bmatrix} 1&3&0&0 \end{bmatrix} \ (\mathrm{mod}\ 5). \end{aligned}\]
For \(s \geq 5\), the proposed algorithm can be generalized so that \(K\) is an \(s\times s\) self-invertible matrix [1], \(B\) is an \(l \times s\) matrix, and the message matrix divides an \(l \times s\) matrix.
An important attack on the Affine-Hill cipher is the brute force attack [20]. In this method, all possible matrices must be tested. In the proposed algorithm, the keys are constructed using self-invertible matrices. Since these matrices are invertible, we must check the order of the group \(GL_{n}(F_p)\). \(GL_n(F_p)\), \(p\) prime, consists of all invertible matrices of order \(n\times n\) over \(F_p\) [8]. This group has order \[\mid GL_n(F_p)\mid=(p^n-p^{n-1})(p^n-p^{n-2})\cdots(p^ n-1).\]
Since \(K\) is an invertible matrix of order \(4\times 4\), we have \[\mid GL_{4}(F_p)\mid=(p^{4}-p^{3})(p^{4}-p^{2})(p^{4}-p^{1})(p^{4}-1).\]
For example \[\begin{aligned} &\mbox{if } p=2, \mbox{ we have } \mid GL_{4}(F_2)\mid=(2^{4}-2^{3})(2^{4}-2^{2})(2^{4}- 2^{1})(2^{4}-1)=20160,\\ &\mbox{if } p=3, \mbox{ we have } \mid GL_{4}(F_3)\mid=(3^{4}-3^{3})(3^{4}-3^{2})(3^{4}- 3^{1})(3^{4}-1)=24261120,\\ &\mbox{if } p=5, \mbox{ we have } \mid GL_{4}(F_5)\mid=(5^{4}-5^{3})(5^{4}-5^{2})(5^{4}- 5^{1})(5^{4}-1)=116064000000. \end{aligned}\] As \(p\) and \(n\) increase, \(\mid GL_{n}(F_p)\mid\rightarrow\infty\). Therefore, the key space is very large so the probability of a successful attack is negligible.
Another attack is a timing attack. This is a type of side channel attack in which the attacker tries to compromise the cryptographic system by analyzing the time taken to execute the algorithm. Because the keys in the proposed algorithm are matrices and multiplication is employed, accessing the system and obtaining the required information will be very time-consuming and prone to errors, so this is not a practical attack.
A new sequence called the \(k-\)division sequence was introduced. Then the Pell and Lehmer sequences were used to obtain new sequences called the \(k-\)division \(L-\)Lehmer-Pell sequences, and some properties of these sequences were determined. As an application, the \(k-\)division \(L-\)Lehmer-Pell sequences and corresponding self-invertible matrices were employed in a new Affine-Hill cipher algorithm, and the security was studied. Other sequences such as Mersenne, Fibonacci, and Jacobsthal sequences [5,7,14] can be used for this algorithm.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.