Open access peer-reviewed chapter - ONLINE FIRST

A Public Key Cryptosystem Using Cyclotomic Matrices

By Md. Helal Ahmed, Jagmohan Tanti and Sumant Pushp

Submitted: July 2nd 2021Reviewed: October 7th 2021Published: November 23rd 2021

DOI: 10.5772/intechopen.101105

Downloaded: 23

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 factorizationtechnique 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 nhas 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 219bits 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 qelements, where q=pri.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 Fqof 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 lis 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, lbe prime, where cyclotomic numbers are certain pairs of solutions ab2l2of order 2l2over a finite field Fpwith pelements.

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 2l2is 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, 2l2with lan 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 2l2are sufficient for the determination of all 4l4cyclotomic numbers of order 2l2. The section also examines the cyclotomic matrices of order 2l2.

2.1 Definition and notations

Let e2be an integer, and p1modean odd prime. One writes p=ek+1for some positive integer k. Let Fpbe the finite field of pelements and let γbe a generator of the cyclic group Fp. For 0a,be1, the cyclotomic number abeof order eis defined as the number of solutions stof 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 p1mod2l2be a prime for an odd prime land we write p=2l2k+1for some positive integer k. It is clear that ab2l2=ab2l2whenever aamod2l2and bbmod2l2as 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 nais given by

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

3. Cyclotomic matrices

This section presents the procedure to determine cyclotomic matrices of order 2l2for 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 pwill 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, lbe 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 psuch that psatisfies p=2l2k+1, kZ+. The initial entries of the cyclotomic matrix are the arrangement of pair of numbers ab2l2where aand busually vary from 0to 2l21.

  2. Determine the equality relation of pair of ab2l2, which reduces the complexity of pair of solution ab2l2of 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,…, γnbe generators of Fp.

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

The first step initializes the entries of cyclotomic matrix of order 2l2. Value of pwill 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 4l4cyclotomic 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 kon expressing prime p=2l2k+1. By (2), if kis 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 ab2l2of order 2l2can be divided into various classes.

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

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

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

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

Algorithm 1Equality 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 2tuple structure (i.e. ordered pair of ab2l2, where aand bare integers).

 5: INPUT p, prime number greater than 2

 6: ifp1%e==0then

 7:  k=p1/e

 8:  ifkeven then

 9:    Update table (E)

10:  else

11:   Update table (O)

12:  end if

13: end if

Here Update table (E)means each entry ab2l2of the table will be updated by applying the relations ab2l2=ba2l2=abb2l2=baa2l2=aba2l2=bab2l2, and Update table (O)means each entry ab2l2of 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 2l2are divided into different classes depending on the values of kand l. For l=2and let kbe even, then 008give unique solution, cyclotomic numbers of the form a08, aa8, 0a8where 1a7mod8gives the same solutions and rest of cyclotomic numbers (i.e. 42) which forms classes of six elements has maximum 7distinct numbers of solutions. Therefore the initial table (i.e. Table 1) of cyclotomic matrix reduces to Table 2. Similarly, for l=2and let kbe odd, then 048give unique solution, cyclotomic numbers of the form 0a8, a+448, 4aa8where 0a47mod8gives the same solutions and rest of cyclotomic numbers (i.e. 42) which forms classes of six elements has maximum 7distinct numbers of solutions. Therefore the initial table (i.e. Table 1) of cyclotomic matrix reduces to Table 3. One can observe that 64pairs of two parameter numbers ab8reduced to 15distinct pairs (see Table 2 and Table 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.0By Algorithm 1, to compute 2l2cyclotomic numbers, it is enough to compute 2l2+2l212l22/6, if 2l212l226, otherwise 2l2+2l212l22/6+1. Further, when lis the least odd prime i.e. l=3, then 2l212l226. Therefore l=3, it is enough to calculate 64distinct cyclotomic numbers of order 2l2and for l3, it is sufficient to calculate 2l2+2l212l22/6distinct 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 pthat satisfy p=2l2k+1;kZ+. Let γ1, γ2, γ3,…, γnbe generators of Fp. We consider finite field of order 17(i.e. F17), since the chosen value of p=17with respect to the value of ltake previously. Now to determine the generators of cyclic group F17. The detail procedure to obtain the generator of F17has been depicted in Algorithm 2. If G17is a set that contain all the generator of F17, we could get elements of G17as {3, 5, 6, 7, 10, 11, 12, 14}.

Algorithm 2Determination of generators of Fp.

 1: Declare integer variable p, count

 2: Declare integer array arrFpp,arrFpflagp

 3: fori=1to p1do

 4:   arrFpi=i, arrFpflagi=0

 5: end for

 6: Declare integer array arrGpmax

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

 8: fori=1to p1do

 9:   count = 0

10:   forf=1to p1do

11:    arrFpflagf=0

12:   end for

13:   γ=arrFpi

14:   fora=1to p1do

15:    r=powerγamodp

16:    forj=1to p1do

17:      ifris equal to arrFpjthen

18:       arrFpflagj=1

19:      end if

20:    end for

21:   end for

22:   fork=1to p1do

23:    ifarrFpflagkis equal to 1then

24:      count++

25:    end if

26:   end for

27:   ifcount 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 Fpin Algorithm 3, we obtain the cyclotomic matrices of order 2l2corresponding to different generators of Fp. The chosen value of p=17implies k=2w.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=3in Algorithm 3, it will generate cyclotomic matrix of order 8over F17w.r.t. chosen generator γ1=3. Matrix B0show the corresponding cyclotomic matrix of order 8w.r.t. chosen generator 3F17.

B0=0000001000001010001100000010000101000100000010011100000000010100.

Algorithm 3Generation 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: fora equal to 0to number of rows do

 5:  forb equal to 0to number of columns do

 6:   forxis equal to 0to kdo

 7:    foryis equal to 0to kdo

 8:     p1=2l2s+arrab.l

 9:     p2=2l2t+arrab.m

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

11:     ifAmodpis 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.1It 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.2It is obvious that (by (4)) cyclotomic matrices of order 2l2is 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 Fpalong with pand 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 ϕ:FpFpas ϕ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 Ais a message block matrix, Bis a cyclotomic matrix w.r.t. γFpand Cis 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 4Secrete key expansion.

1: SECRET INPUT: The values of p, l, r0and γ

2: Algorithm 1

3: Algorithm 2

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

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 2l2corresponding 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 5Encryption.

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

2: PUBLIC INPUT: The values of p,land γ

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 6Decryption.

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 3and 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 pand 2l2. Therefore it is nearly impossible to determine the secret key for a large value of pand 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 1Let us consider 2l2=8(i.e. l=2) and p=17. Suppose we want to send a message Xwhose numerical value store in matrix Aof 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 γ=11and γ''=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& γ=11and the private key is the secret values l=2,p=17, r0=7& γ=3. The public values generated cyclotomic matrix of order 8as required, which is

B3=0010000000010100100000010100100000010001010000100000011000101000

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

C=B3×A=213256875122101313111011481112477571231811781443912118725111115109131941211131717636314141510

The matrix Cis 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 Dwhose entries are pair of cyclotomic numbers.

D=00070605040302010701121615141312061202132425241605161303142525150415241404152414031425251505161302132425241606120112161514131207

Now compute the inverse of Dand 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 eand Update_Table() individually will take Oe2. In algorithm 2, forloop in line number 9, 15, and 17 contributes Oe3in worst case. Since,

e=p1ke3=p1k3p3k3

Since kis a positive integer, therefore when kattains 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 Oe3in worst case.

Similarly, in Algorithm 3, forloop in line number 4, 5, 6, 7 contributes e.e.k.kor say Oe2k2running 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 Oe2as 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 nby fast algorithm [43] takes On2.373. Hence, singularity of the cyclotomic matrix of order ecould be computed in Oe2.373time. Finally, multiplication of cyclotomic matrix of order eand matrix corresponds to plain text of order ewill take Oe2.3728639time. 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+ Oe2Oe2time. Further, multiplication of cyclotomic matrix of order eby a constant value r0, therefore yield Oe2complexity. Likewise, inverse of a matrix of order ncan be computed by a fast algorithm [43] in On2.373, therefore, inverse of generated matrix of order ecould be computed in Oe2.373time. Finally multiplication of two matrix of order ecould be computed in Oe2.3728639by 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

DOWNLOAD FOR FREE

chapter PDF

© 2021 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Md. Helal Ahmed, Jagmohan Tanti and Sumant Pushp (November 23rd 2021). A Public Key Cryptosystem Using Cyclotomic Matrices [Online First], IntechOpen, DOI: 10.5772/intechopen.101105. Available from:

chapter statistics

23total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us