Open access peer-reviewed chapter

A Public Key Cryptosystem Using Cyclotomic Matrices

Written By

Md. Helal Ahmed, Jagmohan Tanti and Sumant Pushp

Reviewed: 07 October 2021 Published: 23 November 2021

DOI: 10.5772/intechopen.101105

From the Edited Volume

Coding Theory - Recent Advances, New Perspectives and Applications

Edited by Sudhakar Radhakrishnan and Sudev Naduvath

Chapter metrics overview

206 Chapter Downloads

View Full Metrics

Abstract

Confidentiality and Integrity are two paramount objectives in the evaluation of information and communication technology. In this chapter, we propose an arithmetic approach for designing asymmetric key cryptography. Our method is based on the formulation of cyclotomic matrices correspond to a diophantine system. The strategy uses in cyclotomic matrices to design a one-way function. The result of a one-way function that is efficient to compute, however, is hard to process its inverse except if privileged information about the hidden entry is known. Also, we demonstrate that encryption and decryption can be efficiently performed with the asymptotic complexity of Oe2.373. Finally, we study the computational complexity of the cryptosystem.

Keywords

  • finite fields
  • discrete logarithm problem
  • cyclotomic numbers
  • cyclotomic matrix
  • public key
  • secret key

1. Introduction

Apart from a rich history of Message encryption, the cryptosystem became more popular in the twentieth century upon the evolution of information technology. Until the last part of the 1970s, all cryptographic message was sent by the symmetric key. This implies somebody who has sufficient data to encode messages likewise has enough data to decode messages. Consequently, the clients of the framework must have to impart the secret key furtively. As a result of an issue stealthily key sharing, Diffie and Hellman [1] developed a totally new sort of cryptosystem called public key cryptosystem.

In a Public key cryptosystem, both parties (in a two-party system) have a pair of public enciphering and secret deciphering keys [2, 3]. Any party can send encrypted messages to an assigned party using a public enciphering key. However, only the assigned party can decrypt the message utilizing their corresponding secret deciphering key [4]. After that various public key cryptosystems were introduced based on tricky mathematical problems. Among these, RSA is the longest reasonable use of cryptography. Since its design, in spite of all effort, it has not been broken yet. The security of the RSA is acknowledged to be established on the issue of the factorization of an enormous composite number. Be that as it may, there are some practical issues in RSA execution. The fundamental issue is the key arrangement time that is absurdly long for computationally restricted processors used in certain applications. Another issue is the size of the key. It was demonstrated that the time required to factor an n-bit integer by index calculus factorization technique is of order 2n1/2+δ,δ>0 [5]. In 1990’s, J. Pollard [6] demonstrated that it was possible in time bounded by 2n1/3+δ,δ>0. The reduction of the exponent of n has significant outcomes over the long run. It should likewise be expanded each year as a result of upgrades in the factorization calculations and computational power. Until 2015, it was prescribed the base size of the RSA key should be 1024 bits and subsequently increases to 4096 & 8192 bits by 2015 & 2025 respectively [7]. While trying to remedy these issues, Discrete logarithm problem (DLP) has been utilized (to reduce key setup time and size of the key).

Discrete logarithm problem (DLP) is a mathematical problem that occurs in many settings and it is hard to compute exponent in a known multiplicative group [8]. Diffie-Hellman [1], ElGamal [9], Digital Signature Algorithm [10], Elliptic curve cryptosystems [11, 12] are the schemes evolved under the Discrete logarithm algorithm. The security of Diffie-Hellman relied upon the complexity of solving the discrete logarithm problem. However, the scheme has some disadvantages. It has not been demonstrated that breaking the Diffie-Hellman key exchange has relied upon DLP and also the scheme is vulnerable to a man-in-the-middle attack. For the security aspect, cryptosystem [9] was proposed, to introduce a digital signature algorithm (DSA) that’s primarily based on Diffie-Hellman DLP and key distribution scheme. It was demonstrated that DSA is around multiple times littler than the RSA signature and later DSA has been supplanted by the elliptic curves digital signature algorithm (ECDSA). Nonetheless, it has some practical implementation problems [13, 14, 15]. The length of the smallest signature is of 320 bits, which is still being too long for computationally restricted processors. Another issue emerged is as a correlation with RSA in a field with prime characteristics, which is forty times slower than RSA [16].

There are some other designs for public-key cryptosystems based on some extensive features of matrices. However, there were some practical implementation problems. Thus it had never achieved wide popularity in the cryptographic community. McElice [17] come up with a public key cryptosystem rooted on the Goppa codes Hamming metric. The scheme has the advantage that it has two to three orders of magnitude faster than RSA. Despite its advantage, it has some drawbacks. It was demonstrated that the length of the public key is 219 bits and the data expansion is too large. Some other extensions of the scheme can also be found in [18, 19, 20]. Unfortunately, the scheme & its variants has been broken in [21, 22, 23]. Later, Gabidulin [24] come up with the rank metric & the Gabidulin codes over a finite field with q elements, where q=pr i.e. Fq, as an alternative for the Hamming metric. The efficiency of the scheme relied on same set of parameters and the complexity of the decoding algorithm for random codes in rank metric is tons higher than the Hamming metric [17, 25, 26, 27]. Numerous fruitful attacks were utilized on the structure of the public code [28, 29, 30]. To prevent these attacks, numerous alterations of the cryptosystems were made, consequently drastically increases the size of the key [31, 32, 33]. Lau and Tan [34] proposed new encryption with a public key matrix by considering the addition of a random distortion matrix over Fq of full column rank n. There are also many other design on matrices, which are not cited here, but none of them gain wide popularity in the cryptographic community due to lack of efficient implementation problems in one and another way.

Thinking about these inadequacies, it would be desirable to have a cryptosystem dependent on other than the presumptions as of now being used. Thus, we propose a cyclotomy asymmetric cryptosystem (CAC) based on strong assumptions of DLP that have to reduce the key size and faster the computational process.

1.1 Outline of our scheme

In this chapter, we consider two significant problems in the theory of cyclotomic numbers over Fp. The first one deals with an efficient algorithm for fast computation of all the cyclotomic numbers of order 2l2, where l is prime. The subsequent one deals with designing public key cryptosystem based on cyclotomic matrices of order 2l2. The strategy employs for designing public-key cryptosystem utilizing cyclotomic matrices of order 2l2, whose entries are cyclotomic numbers of order 2l2, l be prime, where cyclotomic numbers are certain pairs of solutions ab2l2 of order 2l2 over a finite field Fp with p elements.

In our approach, to designing cyclotomy asymmetric cryptosystem (CAC) based on trapdoor one-way function (OWF). The public key is obtained by choosing a non-trivial generator γFp. The chosen value of the generator constructs a cyclotomic matrix of order 2l2. It is believed that cyclotomic matrices of order 2l2 is always non-singular if the value of k>1. Since there are efficient algorithms for the construction of cyclotomic matrices. Consequently, the key setup time in our proposed cryptosystem is much shorter than previously designed cryptosystems.

In the scheme, the secret key is given by choosing a different non-trivial generator, which is accomplished by discrete logarithm problem (DLP) over a finite field Fp. A key-expansion algorithm is employed to expand the secret keys, which form a non-singular matrix of order 2l2. Here it is important to note that, if one can change the generators of Fp, then entries of cyclotomic matrices get interchanged among themselves, however, the nature of the cyclotomic matrices remain as same. The decryption algorithm involves efficient algebraic operations of matrices. Hence the decryption in our proposed CAC is very efficient. In view of the perspective on the efficient encryption and decryption features, the polynomial time algorithm ensures that the proposed CAC makes it attractive in computationally restricted processors.

The chapter is organized as follows: Section 2 presents the definition and notations, including some well-known properties of cyclotomic numbers of order 2l2. Section 3 presents the construction of cyclotomic matrices of order 2l2. Section 4 contains encryption and decryption algorithms of CAC along with a numerical example. In addition, the computational complexity of the proposed CAC is discussed and in Section 5 presents the encryption & decryption can be efficiently perform with asymptotic complexity of Oe2.373. Finally, a brief conclusion is reflected in Section 6.

Advertisement

2. Cyclotomic numbers

Cyclotomic numbers are one of the most vital objects in Number Theory. These numbers had been substantially utilized in Cryptography, Coding Theory and other branches of Information Theory. Thus, calculation of cyclotomic numbers, so called to as cyclotomic number problems, of various orders is one of the primary problems in Number Theory. Complete answers for cyclotomic number problem for e = 26, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 22, l, 2l, l2, 2l2 with l an odd prime had been investigated by many authors see ([35, 36, 37, 38, 39, 40] and the references there in). The section contains the generalized definition of cyclotomic numbers of order e, useful notations followed by properties of cyclotomic numbers of order 2l2. These properties play a vital role in determining which cyclotomic numbers of order 2l2 are sufficient for the determination of all 4l4 cyclotomic numbers of order 2l2. The section also examines the cyclotomic matrices of order 2l2.

2.1 Definition and notations

Let e2 be an integer, and p1mode an odd prime. One writes p=ek+1 for some positive integer k. Let Fp be the finite field of p elements and let γ be a generator of the cyclic group Fp. For 0a,be1, the cyclotomic number abe of order e is defined as the number of solutions st of the following:

γes+a+γet+b+10modp;0s,tk1.E1

2.2 Properties of cyclotomic numbers of order 2l2

In this subsection, we recalled some elementary properties of cyclotomic numbers of order 2l2 [38]. Let p1mod2l2 be a prime for an odd prime l and we write p=2l2k+1 for some positive integer k. It is clear that ab2l2=ab2l2 whenever aamod2l2 and bbmod2l2 as well as ab2l2=2l2aba2l2. These imply the following:

ab2l2=ba2l2ifkiseven,b+l2a+l22l2ifkisodd.E2

Applying these facts, one can check that

a=02l21b=02l21ab2l2=q2E3

and

b=02l21ab2l2=kna,E4

where na is given by

na=1ifa=0,2korifa=l2,2k,0otherwise.
Advertisement

3. Cyclotomic matrices

This section presents the procedure to determine cyclotomic matrices of order 2l2 for prime l. We determine the equality relation of cyclotomic numbers and discuss how few of the cyclotomic numbers are enough for the construction of whole cyclotomic matrix. Further generators for a chosen value of p will be determined followed by the generation of a cyclotomic matrix. At every step, we have included a numerical example for the convenience to understand the procedure easily.

Definition:- Cyclotomic matrix of order 2l2, l be a prime, is a square matrix of order 2l2, whose entries are pair of solutions ab2l2; 0a,b2l21, of the Eq. (1).

For instance Table 1 depicts a typical cyclotomic matrix of order 8 (assuming l=2). Whose construction steps have been given in the next subsection.

3.1 Construction of cyclotomic matrix

Typically construction of a cyclotomic matrix has been subdivided into four subsequent steps. Below are those ordered steps for the construction of a cyclotomic matrix;

  1. For given l, choose a prime p such that p satisfies p=2l2k+1, kZ+. The initial entries of the cyclotomic matrix are the arrangement of pair of numbers ab2l2 where a and b usually vary from 0 to 2l21.

  2. Determine the equality relation of pair of ab2l2, which reduces the complexity of pair of solution ab2l2 of Eq. (1), that is discuss in next sub-section.

  3. Determine the generators of chosen p (i.e. generators of Fp). Let γ1, γ2, γ3,…, γn be generators of Fp.

  4. Choose a generator (say γ1) of Fp and put in Eq. (1). This will give cyclotomic matrix of order 2l2 w.r.t. chosen generator γ1.

The first step initializes the entries of cyclotomic matrix of order 2l2. Value of p will be determined for given l. Assuming l=2, an example of such initialization of matrix of order 8 has been shown in Table 1.

For the construction of cyclotomic matrix, it does not require to determine all the cyclotomic numbers of a cyclotomic matrix which is shown in Table 1 [36]. By well-known properties of cyclotomic numbers of order 2l2, cyclotomic numbers are divided into various classes, therefore there are a pair of the relation between the entries of initial table (Table 1) of a cyclotomic matrix. Thus to avoid calculating the same solutions in multiple times, we determine the equality relation of cyclotomic numbers (i.e. equality of solutions of ab2l2). In the next subsection, we will discuss which cyclotomic numbers are enough for the construction of the cyclotomic matrix. Thus it helps us to the faster computation of cyclotomic matrix.

3.2 Determination of equality relation of cyclotomic numbers

This subsection presents the procedure to determine the equality relation of cyclotomic numbers (i.e. the relation of pair of ab2l2), which reduces the complexity of solutions of pair of ab2l2 (see also [36]). For the determination of cyclotomic matrices, it is not necessary to obtain all 4l4 cyclotomic numbers of order 2l2. The minimum number of cyclotomic numbers required to determine all the cyclotomic numbers (i.e. required for construction of cyclotomic matrix) depends on the value of positive integer k on expressing prime p=2l2k+1. By (2), if k is even, then

ab2l2=ba2l2=abb2l2=baa2l2=aba2l2=bab2l2E5

otherwise

ab2l2=b+l2a+l22l2=l2+abb2l2=l2+bal2a2l2=aba2l2=l2bab2l2.E6

Thus by (5) and (6), cyclotomic numbers ab2l2 of order 2l2 can be divided into various classes.

  • 2k and l3: In this case, (5) gives classes of singleton, three and six elements. 002l2 form singleton class, a02l2, aa2l2, 0a2l2 form classes of three elements where 1a2l21mod2l2 and rest 4l43×2l2+2 of the cyclotomic numbers form classes of six elements.

  • 2k and l=3: In this case, (5) divide cyclotomic numbers ab18 of order 18 into classes of singleton, second, three and six elements. 0018 form singleton class, a018, aa18, 0a18 form classes of three elements, where 1a17mod18, 61218=12618 which is grouped into classes of two elements and rest 4l43×2l2 of the cyclotomic numbers form classes of six elements.

  • 2k and l3: Using (6), once again we get classes of singleton, three and six elements. 0l22l2 forms singleton class, 0a2l2, a+l2l22l2, l2aa2l2 form classes of three elements, where 0al22l21mod2l2 and rest 4l43×2l2+2 of the cyclotomic numbers form classes of six elements.

  • 2k and l=3: In this situation, (6) partitions cyclotomic numbers ab18 of order 18 into classes of singleton, two, three and six elements. Here 0918 form singleton class, 0a18, a+9918, 9aa18 form classes of three elements, where 0a917mod18, 6318=121518 which is grouped into classes of two elements and rest 4l43×2l2 of the cyclotomic numbers form classes of six elements.

Algorithm 1 Equality relation of cyclotomic numbers.

 1: START

 2: Declare integer variable e,l,p,k,flag.

 3: INPUT l, an odd prime and e=2l2

 4: Declare an array of size e×e, where each element of array is 2 tuple structure (i.e. ordered pair of ab2l2, where a and b are integers).

 5: INPUT p, prime number greater than 2

 6: ifp1%e==0then

 7:  k=p1/e

 8:  ifk even then

 9:    Update table (E)

10:  else

11:   Update table (O)

12:  end if

13: end if

Here Update table (E) means each entry ab2l2 of the table will be updated by applying the relations ab2l2=ba2l2=abb2l2=baa2l2=aba2l2=bab2l2, and Update table (O) means each entry ab2l2 of the table will be updated by applying the relations ab2l2=b+l2a+l22l2=l2+abb2l2=l2+bal2a2l2=aba2l2=l2bab2l2.

Further, if entries of the updated table are non-negative, then each entry should be replace by mod2l2, otherwise add 2l2. It is clear from above exploration, cyclotomic numbers of order 2l2 are divided into different classes depending on the values of k and l. For l=2 and let k be even, then 008 give unique solution, cyclotomic numbers of the form a08, aa8, 0a8 where 1a7mod8 gives the same solutions and rest of cyclotomic numbers (i.e. 42) which forms classes of six elements has maximum 7 distinct numbers of solutions. Therefore the initial table (i.e. Table 1) of cyclotomic matrix reduces to Table 2. Similarly, for l=2 and let k be odd, then 048 give unique solution, cyclotomic numbers of the form 0a8, a+448, 4aa8 where 0a47mod8 gives the same solutions and rest of cyclotomic numbers (i.e. 42) which forms classes of six elements has maximum 7 distinct numbers of solutions. Therefore the initial table (i.e. Table 1) of cyclotomic matrix reduces to Table 3. One can observe that 64 pairs of two parameter numbers ab8 reduced to 15 distinct pairs (see Tables 2 and 3).

(a,b)b
a01234567
0(0,0)(0,1)(0,2)(0,3)(0,4)(0,5)(0,6)(0,7)
1(1,0)(1,1)(1,2)(1,3)(1,4)(1,5)(1,6)(1,7)
2(2,0)(2,1)(2,2)(2,3)(2,4)(2,5)(2,6)(2,7)
3(3,0)(3,1)(3,2)(3,3)(3,4)(3,5)(3,6)(3,7)
4(4,0)(4,1)(4,2)(4,3)(4,4)(4,5)(4,6)(4,7)
5(5,0)(5,1)(5,2)(5,3)(5,4)(5,5)(5,6)(5,7)
6(6,0)(6,1)(6,2)(6,3)(6,4)(6,5)(6,6)(6,7)
7(7,0)(7,1)(7,2)(7,3)(7,4)(7,5)(7,6)(7,7)

Table 1.

Cyclotomic matrix of order 8.

(a,b)b
a01234567
0(0,0)(0,1)(0,2)(0,3)(0,4)(0,5)(0,6)(0,7)
1(0,1)(0,7)(1,2)(1,3)(1,4)(1,5)(1,6)(1,2)
2(0,2)(1,2)(0,6)(1,6)(2,4)(2,5)(2,4)(1,3)
3(0,3)(1,3)(1,6)(0,5)(1,5)(2,5)(2,5)(1,4)
4(0,4)(1,4)(2,4)(1,5)(0,4)(1,4)(2,4)(1,5)
5(0,5)(1,5)(2,5)(2,5)(1,4)(0,3)(1,3)(1,6)
6(0,6)(1,6)(2,4)(2,5)(2,4)(1,3)(0,2)(1,2)
7(0,7)(1,2)(1,3)(1,4)(1,5)(1,6)(1,2)(0,1)

Table 2.

Cyclotomic matrix of order 8 for even k.

(a,b)b
a01234567
0(0,0)(0,1)(0,2)(0,3)(0,4)(0,5)(0,6)(0,7)
1(1,0)(1,1)(1,2)(1,3)(0,5)(0,3)(1,3)(1,7)
2(2,0)(2,1)(2,0)(1,7)(0,6)(1,3)(0,2)(1,2)
3(1,1)(2,1)(2,1)(1,0)(0,7)(1,7)(1,2)(0,1)
4(0,0)(1,0)(2,0)(1,1)(0,0)(1,0)(2,0)(1,1)
5(1,0)(0,7)(1,7)(1,2)(0,1)(1,1)(2,1)(2,1)
6(2,0)(1,7)(0,6)(1,3)(0,2)(1,2)(2,0)(2,1)
7(1,1)(1,2)(1,3)(0,5)(0,3)(1,3)(1,7)(1,0)

Table 3.

Cyclotomic matrix of order 8 for odd k.

Remark 3.0 By Algorithm 1, to compute 2l2 cyclotomic numbers, it is enough to compute 2l2+2l212l22/6, if 2l212l226, otherwise 2l2+2l212l22/6+1. Further, when l is the least odd prime i.e. l=3, then 2l212l226. Therefore l=3, it is enough to calculate 64 distinct cyclotomic numbers of order 2l2 and for l3, it is sufficient to calculate 2l2+2l212l22/6 distinct cyclotomic numbers of order 2l2.

3.3 Determination of generators of Fp

To determine the solutions of (1), we need the generator of the cyclic group Fp. Let us choose finite field of order p that satisfy p=2l2k+1;kZ+. Let γ1, γ2, γ3,…, γn be generators of Fp. We consider finite field of order 17 (i.e. F17), since the chosen value of p=17 with respect to the value of l take previously. Now to determine the generators of cyclic group F17. The detail procedure to obtain the generator of F17 has been depicted in Algorithm 2. If G17 is a set that contain all the generator of F17, we could get elements of G17 as {3, 5, 6, 7, 10, 11, 12, 14}.

Algorithm 2 Determination of generators of Fp.

 1: Declare integer variable p, count

 2: Declare integer array arrFpp,arrFpflagp

 3: fori=1 to p1do

 4:   arrFpi=i, arrFpflagi=0

 5: end for

 6: Declare integer array arrGpmax

 7: Declare integer variable flag=0,r,γ

 8: fori=1 to p1do

 9:   count = 0

10:   forf=1 to p1do

11:    arrFpflagf=0

12:   end for

13:   γ=arrFpi

14:   fora=1 to p1do

15:    r=powerγamodp

16:    forj=1 to p1do

17:      ifr is equal to arrFpjthen

18:       arrFpflagj=1

19:      end if

20:    end for

21:   end for

22:   fork=1 to p1do

23:    ifarrFpflagk is equal to 1then

24:      count++

25:    end if

26:   end for

27:   if count is equal to p1then

28:    γ is generator

29:   end if

30: end for

3.4 Generation of cyclotomic matrices

This subsection, present an algorithm for the generation of cyclotomic matrices of order 2l2. Note that entries of cyclotomic matrices are solutions of (1). Thus we need the generator of the cyclic group Fp, which is discussed in the previous subsection. On substituting the generators of Fp in Algorithm 3, we obtain the cyclotomic matrices of order 2l2 corresponding to different generators of Fp. The chosen value of p=17 implies k=2 w.r.t. assume value of l=2. Therefore the cyclotomic matrix will be obtain from Table 2. Let us choose a generator (say γ1=3) from set G17. On substituting γ1=3 in Algorithm 3, it will generate cyclotomic matrix of order 8 over F17 w.r.t. chosen generator γ1=3. Matrix B0 show the corresponding cyclotomic matrix of order 8 w.r.t. chosen generator 3F17.

B0=0000001000001010001100000010000101000100000010011100000000010100.

Algorithm 3 Generation of cyclotomic matrix.

 1: INPUT: The value of p,l,γ

 2: Declare an array arrROWCOL (where elements are two tuple structure)

 3: Declare integer variable p,l,k,γ,x,y,A,s,t,a,b,count=0,p1,p2

 4: for a equal to 0 to number of rows do

 5:  for b equal to 0 to number of columns do

 6:   forx is equal to 0 to kdo

 7:    fory is equal to 0 to kdo

 8:     p1=2l2s+arrab.l

 9:     p2=2l2t+arrab.m

10:     A=powerγp1+powerγp2+1

11:     ifAmodp is equal to 0then

12:      count++

13:     end if

14:    end for

15:   end for

16:   arrab.n=count

17:   count=0

18:  end for

19: end for

Remark 3.1 It is noted that if we change the generator of Fp, then entries of cyclotomic matrices get interchanged among themselves but their nature remains the same.

Remark 3.2 It is obvious that (by (4)) cyclotomic matrices of order 2l2 is always singular if the value of k=1.

Advertisement

4. The public-key cryptosystem

In this section, we present the approach for designing a public key cryptosystem using cyclotomic matrices discussed in Section 3. The scheme employ matrices of order 2l2, whose entries are cyclotomic numbers of order 2l2. The public key is a non-trivial generator, say γ of a set of generator in Fp along with p and l. The set of generator is obtain by Algorithm 2. The chosen public keys generate a cyclotomic matrix as of required order (i.e. order of 2l2) make use of Algorithm 3. Here, we define a trapdoor one-way function ϕ:FpFp as ϕr0=logγ'γ''; r0N, γ,γ are non-trivial generators of Fp. Thus, the secret key are the values of p, l, γ & r0. To encrypt a message, define composition of matrix as M2l2ABM2l2C, where A is a message block matrix, B is a cyclotomic matrix w.r.t. γFp and C is the ciphertext matrix. Other way one can define M2l2BAM2l2C. Therefore, the length of the ciphertext in CAC is equal to 2l2.

To decrypt a message, an algorithm is required to expand the secret keys provided by the secret values. Therefore, the Algorithm 4 is utilized for this purpose.

Algorithm 4 Secrete key expansion.

1: SECRET INPUT: The values of p, l, r0 and γ

2: Algorithm 1

3: Algorithm 2

The main purpose, to utilize the above algorithm is to construct a non-singular cyclotomic matrix of order 2l2 w.r.t. non-trivial generator γ (γγ) in Fp. Now to decrypt the message, we define inverse composition relation of matrices, which is M2l2CZM2l2A, where matrix Z is obtain by some efficient algebraic computation of matrix. Other way one can define M2l2ZCM2l2A respectively.

4.1 Determination of matrix Z

The following steps have been taken for the determination of matrix Z.

  1. Determine the equality of cyclotomic matrix of order 2l2 corresponding to the secret values of p & l, which is perform by Algorithm 1.

  2. Each entry of equality of cyclotomic matrix is multiplied by r0.

  3. Compute the inverse of equality of cyclotomic matrix generated in step 2.

  4. Finally, on substitution the values of the generated cyclotomic matrix corresponding to γ to an inverse matrix in step 3.

The following two algorithms (i.e. Algorithm 5 & 6) are utilized to encrypt and decrypt a message in the proposed CAC, respectively.

Algorithm 5 Encryption.

1: Transfer the plain text (message) into its numerical value and store in matrix of order 2l2

2: PUBLIC INPUT: The values of p,l and γ

3: Execute Algorithm 3

4: Check: Generated cyclotomic matrix in step 3 is non-singular

5: Cipher matrix: Multiply cyclotomic matrix and the matrix generated in step 1

6: Ciphertext: The corresponding text values of matrix generated in step 5

Algorithm 6 Decryption.

1: Input: The cipher matrix/ciphertext

2: Execute Algorithm 4

3: Each entries of equality of cyclotomic matrix (i.e. output matrix of Algorithm 1) is multiply by r0. The entries of the generated matrix are pair of cyclotomic number

4: Compute the inverse of generated matrix in step 3 and substitute the value of each pair of cyclotomic number from generated matrix in step 2

5: Now multiply the cipher text matrix to generated matrix in step 4, we get back to the original plain text message.

4.2 Computational complexity of the CAC

In this section, we would validate the computational complexity of the proposed CAC. The computational complexity measures the amount of computational effort required, by the best as of now known techniques, to break a system [2]. However, it is exceptionally hard to demonstrate the computational complexity of public-key cryptosystems [2, 3]. For instance, if the public modulus of RSA is factored into its prime components, at that point the RSA is broken. Be that as it may, it is not demonstrated that breaking RSA is identical to factoring its modulus [41]. Here, we study the computational complexity of the CAC by providing arguments related to the inversion of the one-way function in CAC to a best known computational algorithm. The complexity of anonymous decryption could be understood as; if we assume that an attacker wants to recover the secret key by using all the information’s available to them. Then they need to solve the discrete logarithm problem (DLP) to find the secret key followed by a number of steps described in Algorithm 6. Since, the one-way function is define analogous to discrete logarithm problem (DLP). However, although most mathematicians and computer scientists believe that the DLP is unsolvable [42]. The complexity of the DLP depends on the cyclic group. It is believed to be a hard problem for the multiplicative group of a finite field of large cardinality. Therefore even determining the very first step is nearly unsolvable.

If it is the case that somehow attacker manages to solve the DLP, then they have to determine Eq. (1) and calculate all the solutions corresponding to different pairs ab2l2. Further, it is required to determine the relation matrix based on equality relation among the solutions of Eq. (1). Where entries of the relation matrix are the two-tuple structure of ab2l2. Finally, entries of inverse of the relation matrix are required to replace through the implication of DLP.

Here we could observe the computational complexity as it increases with the value of p and 2l2. Therefore it is nearly impossible to determine the secret key for a large value of p and 2l2; hence uphold the secure formulation claim of the proposed work.

4.3 An example of the CAC

In this section, we provide an example for the proposed CAC. The example is designed according to guidelines described in Section 4. The main purpose of this example is to show the reliability of our cryptosystem. It is important to note that this example is non-viable for the proposed CAC, since the values of the parameters are too small.

Example 1 Let us consider 2l2=8 (i.e. l=2) and p=17. Suppose we want to send a message X whose numerical value store in matrix A of order 8.

A=2359802115929305213256875307873142319873092356891029679891324456

We choose two distinct non-trivial generators of a set of generator in F17 (the set of generator is obtain by employing Algorithm 2), say γ=11 and γ''=3. Now, we evaluate the complex relation between these chosen generators, which can perform by DLP. One can write 37=11mod17. Consider that r0=7. The public key is the public values l=2,p=17 & γ=11 and the private key is the secret values l=2,p=17, r0=7 & γ=3. The public values generated cyclotomic matrix of order 8 as required, which is

B3=0010000000010100100000010100100000010001010000100000011000101000

Determinant of B3 is equal to 1, implies non-singular. Now we encrypt the message A by multiplying matrix B3 and A, which is as follows:

C=B3×A=213256875122101313111011481112477571231811781443912118725111115109131941211131717636314141510

The matrix C is a ciphertext matrix. To transmit the message, entries of the matrix converted into text. To decrypt the message, first, we expand the secret keys which are performed by Algorithm 4. It generates a non-singular cyclotomic matrix of order 8, which is shown by matrix B0. Now each entry of equality of cyclotomic matrix (i.e. output matrix of Algorithm 1) is multiplied by r0=7. We get matrix D whose entries are pair of cyclotomic numbers.

D=00070605040302010701121615141312061202132425241605161303142525150415241404152414031425251505161302132425241606120112161514131207

Now compute the inverse of D and substitute the value from B0 to each pair of cyclotomic numbers. The matrix becomes

D=1111111110010001100000001101011110000001100101111001010111011111

Finally, we obtain D* × C = A.

Advertisement

5. The complexity of CAC

Time and space are usually prominent factors to establish the effectiveness of security solutions. In the before seen sections, we have established the computational difficulty to break the proposed work. Further, we would demonstrate the complexity of the solution in terms of worst-case running time.

The time complexity of Algorithm 1 in worst case is Oe2. Since formation of matrix of order e and Update_Table() individually will take Oe2. In algorithm 2, for loop in line number 9, 15, and 17 contributes Oe3 in worst case. Since,

e=p1ke3=p1k3p3k3

Since k is a positive integer, therefore when k attains its minimum value i.e. 1,

p3k3p3e3.

For any higher value of k, there is guarantee that

p3k3<e3.

Hence, we conclude that Algorithm 2 can take Oe3 in worst case.

Similarly, in Algorithm 3, for loop in line number 4, 5, 6, 7 contributes e.e.k.k or say Oe2k2 running time in worst case. Using similar analogy as in case of Algorithm 2, worst case complexity will be Oe2.

5.1 Encryption

Encryption as expressed in Algorithm 5 constitutes of three logical divisions and the complexity of encryption would be the sum of the complexity of its part. The state divisions within are as follows;

  1. Generating cyclotomic matrix

  2. Checking the singularity of the cyclotomic matrix.

  3. Multiplication of generated cyclotomic matrix and matrix corresponds to plain text.

Starting from the generation of the cyclotomic matrix, comprises the total complexity Oe2 as stated earlier. Further, checking singularity involves the computation of determinants of the matrix of order e. In worst case computing determinant of a matrix of order n by fast algorithm [43] takes On2.373. Hence, singularity of the cyclotomic matrix of order e could be computed in Oe2.373 time. Finally, multiplication of cyclotomic matrix of order e and matrix corresponds to plain text of order e will take Oe2.3728639 time. Therefore, Complexity of Encryption would become Oe2+Oe2.373+Oe2.3728639Oe2.373. Thus a polynomial time complexity seems to be quite worthwhile.

5.2 Decryption

Decryption as expressed in Algorithm 6 that include Algorithm 4 which sums the complexity of Algorithm 1 and 3, therefore takes Oe2 + Oe2Oe2 time. Further, multiplication of cyclotomic matrix of order e by a constant value r0, therefore yield Oe2 complexity. Likewise, inverse of a matrix of order n can be computed by a fast algorithm [43] in On2.373, therefore, inverse of generated matrix of order e could be computed in Oe2.373 time. Finally multiplication of two matrix of order e could be computed in Oe2.3728639 by best known algorithm [44] till date. Therefore, Complexity of decryption would be Oe2 + Oe2 + Oe2.373 + Oe2.3728639, which becomes Oe2.373.

Advertisement

6. Conclusion

In this chapter, we have introduced a secured asymmetric key cryptography model applying the principle of cyclotomic numbers over a finite field. Procedure to generate cyclotomic matrix along with public & private key have been presented, where the relation between the public & private key has acquired by discrete logarithm problem (DLP). Finally, a convincing argument to strengthen the claim has been presented followed by the method of encryption, decryption & a numerical example.

Advertisement

Acknowledgments

The authors are thankful and acknowledge the Central University of Jharkhand, Ranchi, Jharkhand for providing the necessary facilities to carry out this research.

Advertisement

Mathematics Subject Classification (2010)

11T22; 11T71; 94A60; 11T24

References

  1. 1. Diffie, W., Hellman, M.: New directions in cryptography. IEEE transactions on Information Theory 22(6), 644–654 (1976)
  2. 2. Miller, V.S.: Use of elliptic curves in cryptography. In: Conference on the theory and application of cryptographic techniques, pp. 417–426. Springer (1985)
  3. 3. Wiener, M.J., Zuccherato, R.J.: Faster attacks on elliptic curve cryptosystems. In: International workshop on selected areas in cryptography, pp. 190–200. Springer (1998)
  4. 4. Ahmad, J.I., Din, R., Ahmad, M. Analysis review on public key cryptography algorithms. International Journal of Electrical and Computer Engineering (IJECE) 12(2), 447–454 (2018)
  5. 5. Korzhik, V.I., Turkin, A.I.: Cryptanalysis of mcelieces public-key cryptosystem. In: Workshop on the Theory and Application of of Cryptographic Techniques, pp. 68–70. Springer (1991)
  6. 6. Razborov, A.A., Rudich, S.: Natural proofs. Journal of Computer and System Sciences 55(1), 24–35 (1997)
  7. 7. Shirolkar, D., Katre, S.: Jacobi sums and cyclotomic numbers of order l2. Acta Arithmetica 1(147), 33–49 (2011)
  8. 8. Menezes, A.J., Katz, J., Van Oorschot, P.C., Vanstone, S.A.: Handbook of applied cryptography. CRC press (1996)
  9. 9. ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE transactions on information theory 31(4), 469–472 (1985)
  10. 10. Bruce, S. Applied cryptography. 2nd John Wiley and Sons, Inc (1996)
  11. 11. Koblitz, N., Menezes, A.J.: A survey of public-key cryptosystems. SIAM review 46(4), 599–634 (2004)
  12. 12. Ourivski, A.V., Johansson, T.: New technique for decoding codes in the rank metric and its cryptography applications. Problems of Information Transmission 38(3), 237–246 (2002)
  13. 13. Johnson, D., Menezes, A.: The elliptic curve digital signature algorithm (ecdsa) (1999) 21. Johnson, D., Menezes, A., Vanstone, S.: The elliptic curve digital signature algorithm (ecdsa). International journal of information security 1(1), 36–63 (2001)
  14. 14. Katre, S., Rajwade, A.: Complete solution of the cyclotomic problem in Fq for any prime modulus l,q=pa,p1mod1. Acta Arithmetica 45(3), 183–199 (1985)
  15. 15. Zuccherato, R.: Using a pki based upon elliptic curve cryptography: Examining the benefits and difficulties. Entrust-Securing Digital Identities and Information (2003).
  16. 16. De Win, E., Mister, S., Preneel, B., Wiener, M.: On the performance of signature schemes based on elliptic curves. In: International Algorithmic Number Theory Symposium, pp. 252–266. Springer (1998)
  17. 17. Meier, A.V.: The elgamal cryptosystem (2005)
  18. 18. Davida, G.I., Walter, G.G.: A public key analog gyptosystem. In: Advances in CryptologyEUROCRYPT87
  19. 19. Loidreau, P.: Designing a rank metric based mceliece cryptosystem. In: International Workshop on Post-Quantum Cryptography, pp. 142–152. Springer (2010)
  20. 20. Pollard, J.M.: Factoring with cubic integers. In: The development of the number field sieve, pp. 4–10. Springer (1993)
  21. 21. Lau, T.S.C., Tan, C.H.: A new technique in rank metric code-based encryption. Cryptography 2(4), 32 (2018)
  22. 22. Sidelnikov, V.M., Shestakov, S.O.: On insecurity of cryptosystems based on generalized reed-solomon codes. Discrete Mathematics and Applications 2(4), 439–444 (1992)
  23. 23. Stinson, D.R., Paterson, M.: Cryptography: theory and practice. CRC press (2018)
  24. 24. Gabidulin, E.M.: Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21(1), 3–16 (1985)
  25. 25. Canteaut, A., Chabaud, F.: A new algorithm for finding minimum-weight words in a linear code: application to mceliece’s cryptosystem and to narrow-sense bch codes of length 511. IEEE Transactions on Information Theory 44(1), 367–378 (1998)
  26. 26. Chabaud, F., Stern, J.: The cryptographic security of the syndrome decoding problem for rank distance codes. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 368–381. Springer (1996)
  27. 27. Overbeck, R.: Structural attacks for public key cryptosystems based on gabidulin codes. Journal of Cryptology 21(2), 280–301 (2008)
  28. 28. Gibson, J.K.: Severely denting the gabidulin version of the mceliece public key cryptosystem. Designs, Codes and Cryptography 6(1), 37–45 (1995)
  29. 29. Gibson, K.: The security of the gabidulin public key cryptosystem. In: International Conference on the Theory and Applications of Cryptographic Techniques, pp. 212–223. Springer (1996)
  30. 30. Park, C.S.: Improving code rate of mceliece’s public-key cryptosystem. Electronics Letters 25(21), 1466–1467 (1989)
  31. 31. Gabidulin, E., Ourivski, A.: Modified gpt pkc with right scrambler. In: International workshop on coding and cryptography (Paris, 8-12 January 2001), pp. 233–242 (2001)
  32. 32. Gabidulin, E.M., Ourivski, A.V., Honary, B., Ammar, B.: Reducible rank codes and their applications to cryptography. IEEE Transactions on Information Theory 49(12), 3289–3293 (2003)
  33. 33. McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. Coding Thv 4244, 114–116 (1978)
  34. 34. Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th international symposium on symbolic and algebraic computation, pp. 296–303 (2014)
  35. 35. Acharya, V.V., Katre, S. Cyclotomic numbers of order 2l, l an odd prime. Acta Arithmetica 69(1), 51–74 (1995)
  36. 36. Ahmed, M.H., Tanti, J. Computation of jacobi sums and cyclotomic numbers with reduced complexity. Bulletin of Pure & Applied Sciences-Mathematics and Statistics 38(1), 466–470 (2019)
  37. 37. Ahmed, M.H., Tanti, J. Cyclotomic numbers and jacobi sums: A survey. In: Class Groups of Number Fields and Related Topics, pp. 119–140. Springer (2020)
  38. 38. Ahmed, M.H., Tanti, J., Hoque, A. Complete solution to cyclotomy of order 2l2 with prime l. The Ramanujan Journal 53(3), 529–550 (2020)
  39. 39. Koblitz, N.: Elliptic curve cryptosystems. Mathematics of computation 48(177), 203 209 (1987)
  40. 40. Sidelnikov, V.M., Shestakov, S.O.: On encryption based on generalized reedsolomon codes. Diskretnaya Math 4, 57–63 (1992)
  41. 41. Goldwasser, S., Bellare, M.: Lecture notes on cryptography. Available: http://www.cs.ucsd.edu/users/mihir/papers/gb.html (2008)
  42. 42. Schneier, B.: Applied cryptography: protocols, algorithms, and source code in C. john wiley & sons (2007)
  43. 43. Aho, A.V., Hopcroft, J.E. The design and analysis of computer algorithms. Pearson Education India (1974).
  44. 44. Lin, M.C., Chang, T.C., Fu, H.L.: Information rate of mceliece’s public-key cryptosystem. Electronics Letters 26(1), 16–18 (1990)

Written By

Md. Helal Ahmed, Jagmohan Tanti and Sumant Pushp

Reviewed: 07 October 2021 Published: 23 November 2021