key: cord-0654046-7yot7ocr
authors: Kumari, Munesh; Tanti, Jagmohan
title: On the role of the Fibonacci matrix as key in modified ECC
date: 2021-12-21
journal: nan
DOI: nan
sha: a16ff479d4abb0c701f9af517f150ed1b774458e
doc_id: 654046
cord_uid: 7yot7ocr

In this paper, we have proposed a modified cryptographic scheme based on the application of recursive matrices as key in ECC and ElGamal. For encryption, we consider mapping analogous to affine Hill cipher in which a plaintext matrix has been constructed by points corresponding to letters on elliptic curves. In the formation of key-space, the generalized Fibonacci matrices have been taken into account, which is the sequence of matrices. The beauty of considering Fibonacci matrices is their construction where we need only two parameters(integers) in place of $n^2$ elements. The use of a recursive matrix makes a large keyspace for our proposed scheme and increases its efficiency. Thus, it reduces time as well space complexity, and its security &strength is based on EC-DLP which is a hard problem in number theory.

In discrete mathematics, recursive matrices are rich in many senses like properties, construction, the existence of inverse...etc. One of the popular recursive matrices is generalized Fibonacci matrix [9] , it can be constructed with only two parameters (n,k) and its element is taken from a generalized Fibonacci sequence. Kalika et.al. [11] proposed a public key cryptography based on generalized Fibonacci matrices where they also discussed properties of Fibonacci matrices. Nowadays dependency of the people across the world on the internet has been increased. After arising of COVID-19 situation, most of the meetings, academic activities, business, etc. are taking place in online mode where we used to share a huge number of data (e.g. personal information, video, audio, images, etc.). Now the question arises, is our data received by the authenticated recipient with integrity and confidentiality? So, here comes the Cryptography with the solution to these problems. Cryptography is the science of study about the security, privacy, and confidentiality of information transmitted over a secured channel. Elliptic curve cryptography(ECC) has recently attracted the industry sectors and academia very much. The reason behind this attraction is that for the equivalent security it uses a significantly smaller key size as compared to other schemes like RSA and ElGmal. Use of ECC reduces processing power, computations, and storage space. Hence it is ideal for implementation. A public-key cryptosystem based on discrete logarithm problem(DLP) was proposed by T. El-Gamal [3] in 1984 which is known as ElGamal Cryptosystem. A new approach to public key cryptography(PKC) using Elliptic curves was taken by N.Koblitz [8] named as Elliptic Curve Cryptography(ECC). The most fascinating thing about ECC was that it uses a smaller key size for the same level of security as the RSA cryptosystem provides. The basics of elliptic curves, algebra on it, and the benefits of using elliptic curve cryptography over RSA can be found in [6, 10, 15, 17] . Balamurugan et.al [1] proposed a new approach to the ECC based on the application of matrices and ElGamal technique, further they claimed to provide high security for the encrypted messages. Singh et.al [14] have proposed an alternative to the problem of a large key size that requires high computing power devices. A fast mapping method based on the matrix approach is presented by Geetha et.al [4] for ECC, where they offer high security for the encrypted message. Priyatharsan et.al. in [12] proposed a new cryptographic system using the elliptic curve cryptography based on square matrices. In [1, 4, 12] , they have worked with matrix approach and in this one has to check the invertibility of a matrix and then find the inverse of that matrix which takes much time as well as space. In most of the cryptographic schemes, authors have considered matrix for encryption and key generation. Here comes the requirement of fast computation and key generation, so for that purpose, we are using generalized Fibonacci matrices which help us in fast computation. This paper is organized as follows. In section 2, the basic concepts of Elliptic Curve Cryptography and properties of multinacci matrices are outlined. In section 3, we have proposed an encryption scheme analogous to affine Hill cipher in which a plaintext matrix has been constructed by points corresponding to letters followed by an example. And lastly, in section 4, we have done analysis on key-space and probability of retrieving the key matrix in the context of GL n (F p ).

2.1 Elliptic Curve over a finite field [5, 13, 16] Definition 2.1 (Elliptic Curve). For p ∈ Z + a prime and F p = Z/pZ, an elliptic curve E over F p is the set of points (x, y) with x,y ∈ F p which satisfy the equation

where a, b ∈ F p such that 4a 3 + 27b 2 = 0 (mod p) together with a single element denoted by O and called the "point at infinity".

The elliptic curve over F p is denoted by E Fp (a, b) .

The points on E Fp (a, b) forms an additive abelian group with 'O' as the identity element.

Definition 2.2. The generalized Fibonacci sequence of order n is defined by the recurrence relation,

with t 0 = t 1 = ... = t n−2 = 0 and t n−1 = 1.

The generalized Fibonacci sequence is also known as multinacci sequence and it's corresponding matrix is generalized Fibonacci matrix (sometime it is also called multinacci matrix). Multinacci sequence can be also defined in negative direction by rearranging eqn.(2.2), which is given as,

where initial values are same as of eqn.(2.2).

In particular for n = 2, eqn.(2.2) is Fibonacci sequence [A000045] while for n = 3, eqn.(2.2) gives tribonacci sequence [7, 9] .

The generalized Fibonacci matrix(GFM) [11] F k n of order n is given by,

with initial matrix,

where F 0 n = I n gives identity matrix of order n and t k represents the k th term of multinacci sequence.

And inverse of GFM is given by,

i.e. to calculate inverse of GFM, one doesn't need to follow usual method, simply replace k by −k in (2.4).

This is the main motivation to consider generalized Fibonacci matrices for encryption-decryption which help us in reducing time complexity and able to perform recursively.

Multinacci matrices are rich in many sense like multiplication and finding inverse. As we know that for fast and secure communication, we need an efficient algorithm which can generate and verify key quickly. So to make more efficient and fast encryption in ECC, we are taking in account multinacci matrices for key generation, for exchange of parameters ElGamal technique [3] and an encryption scheme analogous to affine hill cipher. Our proposed method is defined in three part,

• Construction of a public key • An algorithm for key generation

• An encryption scheme and decryption scheme which are discussed below step by step.

Let y 2 ≡ x 3 + ax + b (mod p) such that 4a 3 + 27b 2 (mod p) = 0 be an Elliptic Curve over the finite field F p denoted by E Fp(a,b) and G be a cyclic subgroup of F p with a generator point E . For better understanding, let two entities Alice and Bob want to communicate with each other. So, to construct public Key Alice have to do following steps. Let us consider S={F k n |F n is a generalized Fibonacci matrix of order n and k ∈ N} over finite field F p .

1. First Alice chooses a primitive element (say β) of p and a secret number r such that 1 < r < p − 1.

2. Calculate, E 1 ≡ β r (mod p).

3. Now, (β, E 1 ) is Alice's public key and (r) is her secret key.

Now, to send message P to Alice, Bob first compute encryption key using Alice's public key (β, E 1 ) and encrypts his message P as follows:

1. Bob chooses a secret number e such that 1 < e < p − 1.

a ≡ β e (mod p),

k ≡ E e 1 (mod p).

Compute key matrix 1 (sayK) as K ≡ F k n (mod p).

Convert plain text P in the points of E Fp (a, b), say the points are P 1 , P 2 , P 3 , ..., P m . Now construct a matrix of order n × n as

Encryption: Now encryption of plain text takes place as follow,

1 F k n is a multinacci matrix of order n which can be directly calculated using multinacci sequence not as usual multiplication.

6. Now, Bob will send (a, C) to Alice.

After receiving (a, C) from Bob, Alice perform following operations to recover plaintext:

1. Alice with her secret key(r), first calculate k as, k ≡ a r (mod p).

Where 

where J is given by (5).

Let E be a generator point of a cyclic subgroup of E Fp(a,b) and S={F k n |F n is a generalized Fibonacci matrix of order n and k ∈ N} over finite field F p .

1. β ← a primitive element of p .

Secret Key(r) ← r such that 1 < r < p − 1.

Public Key: E 1 ← β r (mod p).

4. Publish (β, E 1 ) publicly.

Private Key(e) ← e such that 1 < e < p − 1.

2. a ← β e (mod p) and k ← E e 1 (mod p).

3. Key Matrix: K ← F k n (mod p).

Encryption: C ← [K n×n (P n×n + k × EJ n×n )] (mod p), ,where J is given by (5).

5. Transfer (a, C).

After receiving (a, C),

1. k ← a r (mod p).

Decryption Key: D ← F −k n (mod p).

3. Decryption: P ← (D n×n C n×n − k × EJ n×n ) (mod p).

Example 1. Encrypt the plaintext COVID-19 with above proposed scheme. Here, Alice publish (β, E 1 )=(31, 37) publicly and r = 14 is her secret key.

Using Alice's public key (β, E 1 )=(31, 37), Bob will generate encryption key and then encrypts his plaintext as follows: 

Here, Plaintext(P ) = COV ID − 19 → KMNE!N6L = Ciphertext(C).

6. Now, Bob can share (a, C) = (38, 15, KMNE!N6L) with Alice.

After receiving (a, C) = (38, KMNE!N6L) from Bob, Alice perform following operations to recover plaintext:

1. Alice calculates, k ≡ a r (mod p) ≡ 38 14 (mod 47) ≡ 8 (mod 47). 

So, KMNE!N6L → COVID-19.

In group theory, general linear group GL n (F p ) denotes the group of invertible matrices of order n over the finite field F p where p is prime and it's order [2] is given by

In our work, we consider the set of generalized Fibonacci matrices over finite field F p and these matrices are invertible. Here we have presented a table of possible key-spaces for our proposed scheme based on general linear group over a finite field F p in particular for n = 3 and n = 4. From table we conclude that increase in value of p results a large key space. Simultaneously, increase in size of matrix also corresponds to a large key space which can be easily observed in above table. Thus, it is impractical to recover the key by an intruder by brute force attack. In such case, intruder may try some other attacks.

An intruder can not uncover plaintext until and except if, he has not private key for the beneficiary. Also in case of large prime number, the keyspace will be quite large which makes a brute force for finding private key impossible for a intruder. In the following From the table, we observe that if we take parameters n and p sufficiently large, the probability of getting the key matrix is negligible which makes this cryptographic scheme secure against brute force attack.

Some times intruder performs chosen-plaintext attack, where he used to choose a plain text and try to get corresponding ciphertext. With the help of that information intruder try to get encryption key and other relevant information regarding encryption. In our proposed method, ciphertext C is given by C ≡ K(P + kEJ) (mod p).

(4.2)

In equation (4.2) it is almost impossible to calculate K even though C and P is known because of the elliptic curve discrete logarithm problem (ECDLP)(see [5] ). So in this context again our proposed methodology is secure against CPA.

In this paper, we have proposed a modified public key cryptography along with Elliptic curve cryptography and Elgamal using multinacci matrices over a finite field F p . With the help of multinacci matrices, we reduce time as well as space complexity of computation. We have used recursive nature of direct calculation of inverse matrix and n th power of a matrix for fast computation. Also, we have observed that if we increase the prime number, keyspace increases as well and size of key matrix do not follow primes which results randomness in size. The security of our proposed cryptography depends upon the discrete logarithm problem of ECC which is a hard problem in number theory. In our analysis, we found that our proposed method has large key space, quite robust, and can be implemented easily.

Enhancing security in text messages using matrix based mapping and elgamal method in elliptic curve cryptography

A public key cryptosystem and a signature scheme based on discrete logarithms

Implementation of matrix based mapping method using elliptic curve cryptography

Guide to Elliptic Curve Cryptography

An introduction to mathematical cryptography

Fibonacci numbers and matrices

Elliptic curve cryptosystems

Understanding cryptography: a textbook for students and practitioners

Cryptography using generalized fibonacci matrices with affine-hill cipher

A new elliptic curve cryptographic system over the finite fields

A new approach to elliptic curve cryptography

A critical review on elliptic curve cryptography

Cryptography and network security: principles and practice. Pearson Upper Saddle River

Cryptography: theory and practice

The authors are thankful to anonymous reviewer for their care and advice. The first author acknowledge the University Grant Commission(UGC), India for providing fellowship for this research work.