Hybrid - Key agreement protocol based on chebyshev polynomials

𝐴 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝 = >> 1; 
 = 𝑛𝑛 (  ) (10) 8: = ( ) ; 
 𝑒𝑒 2 2 2 𝑒𝑒𝑖𝑖 9: end while𝑒𝑒 𝑒𝑒 
 From Eq.(𝐴𝐴 10),� an�𝐴𝐴 ��𝐴𝐴efficient���𝐴𝐴� algorithm for 10: Return𝐴𝐴 ; 𝐴𝐴 ∗ 𝐴𝐴 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝
 𝑖𝑖=0 𝑖𝑖 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡
computing is described in Algorithm 1. By 11: end procedure 
this way, we 𝑒𝑒proposed the top-level implementation of 𝑅𝑅
the ( ) 𝐴𝐴 𝑚𝑚𝑚𝑚𝑚𝑚 , this𝑝𝑝 architecture represents in Fig.1. 
 𝑇𝑇𝑔𝑔 𝑥𝑥 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝
 Fig. 1. Hardware Architecture of 
 𝑇𝑇𝑔𝑔
 52 
 Journal of Science & Technology 139 (2019) 050-056 
 A shift register _ with = 1, is a LSB 
of . Let us consider that = [ ] 
and = [ 𝐸𝐸 𝑟𝑟] 𝑟𝑟𝑟𝑟are the𝐸𝐸 coeffic𝑔𝑔 − ient𝑒𝑒 vectors 
 𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣 1 0
corresponding𝐸𝐸 with respectively. 𝐴𝐴 According𝑎𝑎 𝑎𝑎to 
 𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣 1 0
Algorithm𝑅𝑅 1, 𝑟𝑟the𝑟𝑟 equation the polynomial =
 + I and = + , = in step𝑒𝑒 5 
is equivalent to ( + ) ( + 𝐴𝐴) =
 1 0 1 0
 𝑎𝑎 𝐴𝐴 𝑎𝑎 + ( 𝑅𝑅 +𝑟𝑟 𝐴𝐴 𝑟𝑟 𝐼𝐼) +𝑅𝑅 𝑅𝑅 ,∗ since𝐴𝐴 A2 = 
 1 0 1 0
2 2 1 = 2 ( 𝑎𝑎 𝐴𝐴+ 𝑎𝑎),𝐼𝐼 we∗ have𝑟𝑟 𝐴𝐴 R = 𝑟𝑟R𝐼𝐼 A = 
 1 1 1 0 0 1 0 0 
(𝑎𝑎 𝑟𝑟 𝐴𝐴 + 𝐴𝐴 𝑎𝑎 𝑟𝑟+ 2 𝑎𝑎 ∗ 𝑟𝑟 ) 𝑎𝑎+ 𝑟𝑟( 𝐼𝐼
 1 0
 𝑥𝑥)𝑥𝑥. −The expression𝑥𝑥 𝑎𝑎 𝐴𝐴 is executed𝑎𝑎 𝐼𝐼 as following steps:∗ Fig. 2. Area of ASIC implementation Tg(x) mod p 
 𝑟𝑟0 ∗ 𝑎𝑎1 𝑟𝑟1 ∗ 𝑎𝑎0 𝑥𝑥 ∗ 𝑟𝑟1 ∗ 𝑎𝑎1 𝐴𝐴 𝑟𝑟0 ∗ 𝑎𝑎0 − 𝑟𝑟1 ∗
 As can be seen in Fig.3, the mod-exp block 
𝑎𝑎1 𝐼𝐼1) = >> 1, check the = [0, 1] 
 undertakes calculating mod , the finite state 
 2) 𝐸𝐸 = 𝐸𝐸 , = 𝐿𝐿𝐿𝐿𝐿𝐿 𝑒𝑒 machine (FSM) block is used𝛼𝛼 to control′ the operation 
 𝑔𝑔 𝑝𝑝
 3) 1 = 1 1+ 2 0+ 2 0 , 1 = of others. All benchmarks were executed on a kit 
 𝑡𝑡 𝑟𝑟 ∗ 𝑎𝑎 𝑡𝑡 𝑎𝑎 ∗ 𝑟𝑟 − 𝑡𝑡 FPGA Kintex KC705. Table 2 showed the 
 4) 𝑟𝑟Update1 𝑟𝑟0 ∗R 𝑎𝑎=1 R 𝑟𝑟A1 ∗and𝑎𝑎0 A = A𝑥𝑥 ∗ A𝑡𝑡1 𝑟𝑟0 𝑡𝑡2 performance of mod with several values of , , 
 and . It is clear 𝛼𝛼that the more the bit length of and 
 5) E = 0, we obtain∗ ( ) = (2∗ + ) 𝑔𝑔
 is, the slower𝑇𝑇 processing𝑝𝑝 speed and the more𝑥𝑥 𝑝𝑝 
where registers , contain𝑇𝑇𝑔𝑔 𝑥𝑥 temporary𝑥𝑥 𝑥𝑥𝑟𝑟1 values𝑟𝑟0 − 𝑟𝑟of1 hardware𝑔𝑔 𝛼𝛼 resources are required. 𝑥𝑥
multiplication and addition. 𝑝𝑝
 𝑡𝑡1 𝑡𝑡2 3. Hybrid-key Agreement Protocol 
 In order to maximum security, and should be 
a large prime and a large integer, respectively [6]. In In this section, we proposed a Hybrid-Key 
this design, registers have the length𝑝𝑝 from𝑥𝑥 64 to 256 Agreement Protocol using the Chebyshev-based 
bits which storage the values of and , thus both public-key encryption, called HKAChev. A hybrid 
and are chosen in ranges [0, 264 − 1] and [0, 2256 − approach is both the use of a the chebyshev-based 
1]. Authors in [12] indicated 𝑝𝑝that the𝑥𝑥 larger the𝑝𝑝 public-key encryption and the key distribution center 
iterative𝑥𝑥 coefficient is, the more the storage space of (KDC) to distribute the secret session keys between 
 users. The proposed scheme is illustrated in Fig.4. 
 ( ) is. Using the hardware platform on ASIC, Fig.2 
 Two elements including a security service and a 
shows the area of ASIC𝑔𝑔 implemention ( ) with the 
𝑇𝑇𝑔𝑔 𝑥𝑥 Chebyshev-based key generation are embedded on 
bit length of is corresponding with 64,𝑔𝑔 80, 128, 192 each user’s devices. The first element, a security 
 𝑇𝑇 𝑥𝑥
and 256 bits. service buffers packets and transmits a connection-
 𝑝𝑝
 Assumed that = , we referred to the request packet. The second one, a Chebyshev based 
calculation problem ′ ( 𝛼𝛼) . However, the key generation is created by the Chebyshev 
 𝑔𝑔 ′ 𝑔𝑔 module mentioned in Section 2. In the hybrid-key 
value of increases 𝑔𝑔 rapidly according to α, so 
Algorithm 1′ will be ineffective,𝑇𝑇 𝑥𝑥 𝑚𝑚𝑚𝑚𝑚𝑚 it 𝑝𝑝should take more protocol,𝛼𝛼 the session key is considered as a temporary 
 𝑇𝑇𝑔𝑔
C.P.U time.𝑔𝑔 We proposed the hardware architecture of key and used for the communication between end-
 in Fig.3, this is an efficient way to calculate the user’s devices in a certain duration, and then 
 discarded. Each session key is transmitted in 
Chebyshev𝛼𝛼 polynomials ( ) mod accurately. 
𝑇𝑇𝑔𝑔 encryption form by Chebyshev-based public key 
This design is based on properties𝛼𝛼 of the permutation 
 𝑔𝑔 scheme, using a master key shared by the KDC. 
polynomial over the finite 𝑇𝑇field𝑥𝑥. 𝑝𝑝
 3.1. Key Agreement Protocol based on Chebyshev 
 The period of ( ) is 1 or + 1 
 map 
depending on the ′roots of the characteristic 
 𝑔𝑔 𝜶𝜶
 𝑇𝑇 𝑥𝑥 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝 𝑝𝑝 − 𝑝𝑝 𝒈𝒈
polynomial ( ) = 2 + 1, the period is Figure𝑻𝑻 4 shows our proposed protocol that retains 
 1 if the roots are 2are in GF(p), otherwise, +′ 1 KDC to share the stream of parameters containing a 
when the roots𝑓𝑓 λ are inλ GF(− 𝑥𝑥λ) [15]. By this way,𝑝𝑝 if master key. A Chebyshev-based public key scheme is 
𝑝𝑝 − ( ) = ( ) = 1 then 2 = 1, else 𝑝𝑝= + applied to distribute the session key. 
1. On the other hand, 𝑝𝑝 ′mod is equivalent′ to 
𝑇𝑇𝑝𝑝−1 𝑥𝑥 𝑇𝑇0 𝑥𝑥 𝑝𝑝 𝑝𝑝 − 𝑝𝑝 𝑝𝑝
 ( ) , instead′ of calculating , we 
 𝑇𝑇𝑔𝑔 𝑝𝑝
 𝛼𝛼 ′ = 𝛼𝛼
determine𝑔𝑔 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝 . 
𝑇𝑇 ′𝑚𝑚𝑚𝑚𝑚𝑚 𝛼𝛼𝑝𝑝 ′ 𝑔𝑔
 𝑔𝑔 𝑔𝑔 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝
 53 
 Journal of Science & Technology 139 (2019) 050-056 
 time session key and send that to User B by the 
 steps below 
 • Generating = ( ) mod , 
 hence = 𝛼𝛼𝐴𝐴−(𝐾𝐾𝑀𝑀) mod . 
 𝐾𝐾𝑆𝑆𝑆𝑆 𝑇𝑇𝑔𝑔 𝑃𝑃𝑃𝑃𝐵𝐵 𝑝𝑝
 𝛼𝛼𝐴𝐴+𝛼𝛼𝐵𝐵−𝐾𝐾𝑀𝑀
 • Calculating𝐾𝐾𝑆𝑆𝑆𝑆 𝑇𝑇𝑔𝑔 = ( ,𝑥𝑥 ) and𝑝𝑝 =
 ( ) mod . 
 𝐶𝐶 𝐸𝐸 𝐾𝐾𝑆𝑆𝑆𝑆 𝐾𝐾𝑀𝑀 𝑆𝑆
 𝛼𝛼𝐴𝐴−𝐾𝐾𝑀𝑀−𝐶𝐶
 3) User𝑇𝑇 B𝑔𝑔 obtains (𝑥𝑥, ), the𝑝𝑝 following steps occur 
 • Recovering = ( ) mod , hence 
Fig. 4. Hybrid-Key Agreement Protocol based on 𝑆𝑆 𝐶𝐶
 = ( )𝛼𝛼 𝐵𝐵mod+𝐶𝐶 
Chebyshev polynomials 𝐾𝐾′𝑆𝑆𝑆𝑆 𝑇𝑇𝑔𝑔 𝑆𝑆 𝑝𝑝
 𝛼𝛼𝐴𝐴+𝛼𝛼𝐵𝐵−𝐾𝐾𝑀𝑀
 Let us suppose that User A wishes to establish a • 𝐾𝐾Recovering′𝑆𝑆𝑆𝑆 𝑇𝑇𝑔𝑔 = 𝑥𝑥( , 𝑝𝑝) and if =
connection with User B and encrypt messages by a then indicating′ ′ = as the ′one-
 𝑀𝑀 𝑆𝑆𝑆𝑆 𝑀𝑀
one-time session key on that connection. User A can time session𝐾𝐾 key. 𝐷𝐷 𝐾𝐾 𝐶𝐶 𝐾𝐾
 𝑀𝑀 𝑆𝑆𝑆𝑆 𝑆𝑆𝑆𝑆
issues a request with its identifier and a nonce 𝐾𝐾 𝐾𝐾′ 𝐾𝐾
 4) The result is that both A and B know , 
which is given as a time stamp to identify this 
 𝐴𝐴 𝑖𝑖 therefore the session key can be used for 
transaction uniquely. User B sets 𝐼𝐼up𝐼𝐼 a transaction 𝑁𝑁to 𝑆𝑆𝑆𝑆
 securely communicating between A and B. 𝐾𝐾Our 
KDC and sends the identifier of User B and 𝑆𝑆𝑆𝑆
 proposed scheme provides 𝐾𝐾either confidentiality 
 || . The KDC responds with the values of , , 
 𝐵𝐵 or authentication for exchanging the secret key. 
 and = { || || } to both A𝐼𝐼 𝐼𝐼and B. 
 𝐴𝐴 𝐼𝐼 At the next session, both A and B discard and 
𝐼𝐼Then𝐼𝐼 𝑁𝑁the following procedures are employed. 𝑥𝑥 𝑝𝑝
 𝑀𝑀 𝐵𝐵 𝐴𝐴 𝑖𝑖 make deal with each other to exchange a new 
𝑔𝑔 𝐾𝐾 ℎ𝑎𝑎𝑎𝑎ℎ 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝑁𝑁 𝑆𝑆𝑆𝑆
1) User B gets ( , , , ), calculating = session key. 𝐾𝐾
 { || || } and checking that if ′= then 
 𝑀𝑀 𝑀𝑀 In Table 3, time required for the generation of a 
 choosing a secret𝑥𝑥 𝑝𝑝 𝑔𝑔 key𝐾𝐾 and calculating′𝐾𝐾 ℎ 𝑎𝑎𝑎𝑎theℎ 
 𝐵𝐵 𝐴𝐴 𝑖𝑖 𝑀𝑀 𝑀𝑀 single key pair 128-bit symmetric with different 
 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝑁𝑁 ( ) 𝐾𝐾 𝐾𝐾
 public key = mod . User B algorithms such as RSA, Diffie-Hellman (DH) and 
 𝛼𝛼𝐵𝐵
 transmits to A. 𝛼𝛼𝐵𝐵 Elliptic curve Diffie-Hellman (EC) is shown in [1]. 
 𝑃𝑃𝑃𝑃𝐵𝐵 𝑇𝑇𝑔𝑔 𝑥𝑥 𝑝𝑝
 The keys generated in HKAChev protocol are 64, 80, 
2) User A selects𝑃𝑃𝑃𝑃𝐵𝐵 a random number as a secret 
 key and receives . User A can generate a one- 128, 192 and 256 bit width. 
 𝛼𝛼𝐴𝐴
 𝑃𝑃𝑃𝑃𝐵𝐵
 α 
 Fig. 3. Hardware Architecture of Tg
Table 2. Hardware Resource 
 Max Latency Max delay time 
 Bit length of , , Bit length of Fmax(MHz) Flip-flops 
 (cycle count) (ms) 
 64 𝑥𝑥 𝑝𝑝 𝑔𝑔 256 𝛼𝛼 217 79236 0.365 1488 
 80 256 193 122084 0.563 1792 
 128 256 150 305924 1.409 2704 
 192 256 141 680068 3.134 3920 
 256 256 136 1201668 5.538 5136 
 54 
 Journal of Science & Technology 139 (2019) 050-056 
3.2. Security analysis combinations is 2 . It implies that the HKAChev 
 protocol also withstands256 the replay attack. 
 The Hybrid-Key Agreement protocol 𝛼𝛼𝐴𝐴
(HKAChev) depicted in Figure 4 ensures against an 4. Conclusion 
attacker who can control the intervening 
 This paper has presented a Hybrid-Key 
communication between User A and B. In this case, an 
 Agreement protocol (HKAChev) which possessed 
adversary, E, wants to compromise the 
 both security attributes of public key based on the 
communication channel without being detected and 
 Chebyshev polynomial and efficient exchanging key 
desires the session key. By eavesdropping, E can 
 scheme of KDC. The proposed protocol achieved 
acquire a set of parameters involved ( || ) and knows 
 desirable security levels resisting man-in-the middle, 
( , , ). E has seen = ( ) 
 replay and brute-force attacks. 
 𝛼𝛼 −𝑆𝑆𝐾𝐾 𝐶𝐶−𝐶𝐶
without known . One way to 𝑔𝑔break𝐴𝐴 𝑀𝑀 our proposed 
protocol,𝑥𝑥 𝑔𝑔 𝑝𝑝 E should be first𝑆𝑆 to exploit𝑇𝑇 and𝑥𝑥 𝑚𝑚𝑚𝑚𝑚𝑚 by𝑝𝑝 A model-based hardware design of the discrete 
 𝐴𝐴
solving both of 𝛼𝛼the equations = ( ) and Chebyshev polynomial in the prime field is illustrated. 
 𝐴𝐴 𝐵𝐵
 = . If = ( ) 𝛼𝛼 then 𝛼𝛼 = These results show that the proposed structure 
 𝛼𝛼
 𝛾𝛾 ( + 1) satisfied𝛽𝛽 𝑇𝑇 that𝑥𝑥 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝1 and hardware requires a small resource and has more 
𝛼𝛼 𝑔𝑔 𝛽𝛽 𝑇𝑇𝛼𝛼 𝑥𝑥 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝 𝛼𝛼 effective performance. Thus, it is potential for 
 2 2
 12 ( ) ( )
𝑙𝑙𝑙𝑙𝑙𝑙𝑥𝑥+�𝑥𝑥 +must1 𝛽𝛽 be� in𝛽𝛽 the− field or √𝑥𝑥 − . To embedding in encryption applications. As an 
solve2 a square root in ( ) or ( ), it takes2 an exemplar, this hardware structure is applied to create a 
�𝛽𝛽 − 𝐺𝐺𝐺𝐺 𝑝𝑝 2 𝐺𝐺𝐺𝐺 𝑝𝑝 Chebyshev-based key generation in HKAChev 
expected running 𝐺𝐺𝐺𝐺time𝑝𝑝 of𝐺𝐺𝐺𝐺 𝑝𝑝 exp + protocol. Both the theoretical analysis and 
 experimental results show that the proposed key 
 (1) (ln( )) (ln(ln( ))) 𝑂𝑂 � 1.�92�𝜍𝜍
 1 2 where in agreement protocol has a good security and potential 
 3 3 for implementing on limited hardware resources. 
𝑂𝑂[6]. Besides,� 𝑛𝑛 the assumption𝑛𝑛 � that� E can get𝜍𝜍 the≅ value of 
 , the discrete logarithm = ( ) has no Acknowledgments 
efficient solution. It means that it is infeasible to find This research is funded by Ministry of Science 
𝛼𝛼 𝛾𝛾 𝑙𝑙𝑙𝑙𝑙𝑙𝑔𝑔 𝛼𝛼
 from . Consequently, it is impossible to recover the and Technology (MOST) under grant number 
value of from ; In other words, no efficient 10/2018/TCT-KC.01/16-20. 
method𝛼𝛼 𝛽𝛽 for recovering the value of . The shared 
 𝐴𝐴
session key𝛼𝛼 is against𝑆𝑆 the man-in-middle attack. For References 
 𝑆𝑆𝑆𝑆
connection-oriented protocols, session𝐾𝐾 keys are [1]. W. Stallings, Cryptography and Network Security: 
exchanged frequently. Each nonce , we have only Principles and Practice, Upper Saddle River, NJ, USA: 
one , assumed that A wants to change and B is Prentice Hall Press, 6th ed., 2013. 
 𝑖𝑖
unaware of changes. A new session𝑁𝑁 key is created by 
 𝑀𝑀 𝑆𝑆𝑆𝑆 [2]. Dong Hwi Seo and P. Sweeney, Simple authenticated 
randomly𝐾𝐾 generating the value of . User𝐾𝐾 B received key agreement algorithm, Electronics Letters, vol. 35, 
and authenticated the new session key by itself without pp. 1073–1074, June 1999. 
 𝐴𝐴
going through KDC. As a result,𝛼𝛼 an efficient key 
 [3]. P. E. Abi-Char, A. Mhamed, and B. El-Hassan, A 
exchange protocol is established by the HKAChev 
 secure authenticated key agreement protocol based on 
one. elliptic curve cryptography, in Third International 
Table 3. Time required for the generation of a single Symposium on Information Assurance and Security, 
key pair 128-bit symmetric pp. 89–94, Aug 2007. 
 [4]. C. Boyd and A. Mathuria, Key Agreement Protocols, 
 RSA DH EC HKAChev pp. 137–199. Berlin, Heidelberg: Springer Berlin 
 900(ms) 51(ms) 0.53(ms) 0.7045(ms) Heidelberg, 2003. 
 [5]. C. Adams, Kerberos Authentication Protocol, pp. 674–
 As a replay attack, the attacker E may intercept 675. Boston, MA: Springer US, 2011. 
 when it is sent by User B in Step 1 and then will [6]. G. Maze, Algebraic methods for constructing one-way 
masquerade as User B next time. Since the attacker 
 𝐵𝐵 trapdoor functions. PhD thesis, University of Notre 
does𝑃𝑃𝑃𝑃 not know the secret key of each user neither Dame Notre Dame, 2003. 
or , E can not compute a correct || , E must try all 
 𝐴𝐴 [7]. L. Kocarev and S. Lian, Chaos-based Cryptography. 
possible values of . In this case, the or can 𝛼𝛼be 
 𝐵𝐵 Springer, 2011. 
run𝛼𝛼 with maximum 256 bits 𝑆𝑆long.𝐶𝐶 Thus, the 
 𝐴𝐴 𝐴𝐴 𝐵𝐵
computational complexity𝛼𝛼 to brute-force𝛼𝛼 all𝛼𝛼 possible [8]. S. Vairachilai, M. K. Kavithadevi, and R. 
 Gnanajeyaraman, Public key cryptosystems using 
 chebyshev polynomials based on edge information, in 
 55 
 Journal of Science & Technology 139 (2019) 050-056 
 2014 World Congress on Computing and [12]. G. J. Fee and M. B. Monagan, Cryptography using 
 Communication Technologies, pp. 243–245, Feb chebyshev polynomials, in Laurier University, 
 2014. Waterloo, pp. 1–15, 2004. 
[9]. P. Bergamo, P. D’Arco, A. De Santis, and L. Kocarev, [13]. J. Liu, D. Yang, H. Zhou, and S. Chen, A digital image 
 Security of public-key cryptosystems based on encryption algorithm based on bit-planes and an 
 chebyshev polynomials, IEEE Transactions on improved logistic map, Multimedia Tools and 
 Circuits and Systems I: Regular Papers, vol. 52, pp. Applications, p. 1, Nov. 2017. 
 1382–1393, July 2005. 
 [14]. R. Bronson and G. B. Costa, 7 - matrix calculus, in 
[10]. T. T. K. Hue, T. M. Hoang, and A. Braeken, Matrix Methods (Third Edition) (R. Bronson and G. B. 
 Lightweight signcryption scheme based on discrete Costa, eds.), pp. 213 – 255, Boston: Academic Press, 
 chebyshev maps, in 2017 12th International third edition ed., 2009. 
 Conference for Internet Technology and Secured 
 Transactions (ICITST), pp. 43–47, Dec 2017. [15]. D. Yoshioka, Properties of chebyshev polynomials 
 modulo p^k, IEEE Transactions on Circuits and 
[11]. A. Braeken, P. Kumar, M. Liyanage, and T. T. K. Hue, Systems II: Express Briefs, vol. 65, pp. 386–390, 
 An efficient anonymous authentication protocol in March 2018. 
 multiple server communication networks (eaam), The 
 Journal of Supercomputing, vol. 74, pp. 1695– 1714, 
 Apr 2018. 
 56