236 Hardware Components for Post-Quantum Elliptic Curves Cryptography Rodrigue Elias1, Valerii Hlukhov2, Mohammed Rahma2, Ivan Zholubak2 1. School of Engineering at Lebanese International University, LEBANON, Beirut, 2nd floor - Block F- Beirut Campus, P.O. Box: 146404, Mazraa, e-mail: rodrigue.elias@liu.edu.lb 2. Computers Dept., Lviv Polytechnic National University, UKRAINE, Lviv, 12 Bandera Str., e-mail: glukhov@polynet.lviv.ua Abstract: Investigations in the sphere of quantum 2 Galois Field GF ( p ) . An isogeny of an elliptic curve E is calculations form up new challenges in the public key a rational map from E to another elliptic curve E' which is cryptography. Currently known public key crypto also a group homomorphism. Provided the isogenies algorithms may be compromised with the implementation are separable, they are determined by the points inside of quantum computers. The workgroups of ETSI and their kernel up to isomorphisms of E'. NIST determined the promising trends, within the The SIDH method works with a prime of the form framework of which there could be obtained acceptable solutions and one of the trends is the use of algorithms p = ( w A )e A ( wB )eB ( f ) ± 1 where w A and w B are small that process points of supersingular elliptic curves. primes and an elliptic curve E defined by the equation: Hardware implementations of components for processing y 2 = x 3 + ax + b . SIDH builds an isogeny map from a points of elliptic curves are well known. The purpose of this publication is to investigate how they can be used to single elliptic curve point which is taken as the generator for process points of supersingular elliptic curves. the isogeny's kernel. This point is chosen to be a random Keywords: hardware components, post-quantum, linear combination to two fixed points chosen to be in the elliptic curves, cryptography. kernel of the isogeny. The j-invariant of an elliptic curve E is a fixed function of I. INTRODUCTION a set of isomorphic curves. It is computed from the The advent of large-scale quantum computing offers great parameters that define the curve. For an elliptic curve E promise to science and society, but brings with it a defined by the equation: y 2 = x 3 + ax + b the j-invariant significant threat to global information infrastructure. Public- 4a 3 key cryptography - widely used on the internet today – relies of the curve E is j( E ) = 1728 . upon mathematical problems that are believed to be difficult 4 a 3 + 27 b 2 to solve given the computational power available now and in The security of SIDH is closely related to the problem of the medium term. finding the isogeny mapping between two supersingular However, popular cryptographic schemes based on these elliptic curves with the same number of points. In [3] it was hard problems – including Elliptic Curve Cryptography – will shown that the security of SIDH will be O(p1/4) for classical be easily broken by a quantum computer. This will rapidly computers and O(p1/6) for quantum computers. This suggests accelerate the obsolescence of currently deployed security that SIDH with a 768-bit prime (p) will have a 128-bit systems and will have dramatic impacts on any industry security level. where information needs to be kept secure. In 2014, researchers at the University of Waterloo Quantum-safe cryptography refers to efforts to identify developed a software implementation of SIDH. They ran algorithms that are resistant to attacks by both classical and their partially optimized code on an x86-64 processor running quantum computers, to keep information assets secure even at 2.4 GHz. For a 768-bit modulus they were able to complete after a large-scale quantum computer has been built [1]. the key exchange computations in 200 milliseconds thus Supersingular isogeny Diffie–Hellman key demonstrating that the SIDH is computationally practical [4]. exchange (SIDH) is a post-quantum cryptographic algorithm In 2016, researchers from Microsoft posted software for used to establish a secret key between two parties over an the SIDH which runs in constant time (thus protecting against otherwise insecure communications channel. It is analogous timing attacks) and is the most efficient implementation to to the Diffie–Hellman key exchange, but is designed to date [5]. resist cryptanalytic attack by an adversary in possession of In 2017, researchers from Florida Atlantic University a quantum computer. developed the first FPGA implementations of SIDH for 83- bit and 124-bit quantum security levels [6]. II. THE SUPERSINGULAR ISOGENY DIFFIE- HELLMAN BACKGROUND III. DEFINITION OF ISOGENY The supersingular isogeny Diffie-Hellman (SIDH) method For supersingular elliptic curves there is well known Vélu works with the set of supersingular elliptic curves E over algorithm [7] for isogeny [8]: Let E1 and E2 be elliptic curves over the field F. The isogeny E1 E2 over F is a non- ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic 237 constant rational mapping over F, which is also a group hardest was the purpose of the study. It was assumed that homomorphism hackers use software methods. f1( x, y ) g1( x, y ) One of the computer system hacking methods is the brute- ( x, y )  →( , ) , where f 1 , g 1 , f 2 , force method [8], in which the general-purpose computer f 2 ( x, y ) g 2 ( x, y ) selects all sorts of keys or passwords until one of them fits. g 2 are polynomials. For example, F = GF(19) , The same operations over Galois fields elements are elliptic curve E1: y2 = x3 + x + 1; performed both during the execution of the hack program and elliptic curve E2: y2 = x3 + 4x + 13 in the hardware crypto processors. For general purpose #E1 = #E2 = 21; computers, it is possible to estimate the time of execution of x 3 − 4 x 2 − 8 x − 8 x 3 y − 6 x 2 y − 5 xy − 6 y . the main operation, multiplication of the Galois fields ( x, y )  →( , ) elements, for extended fields with different characteristics, x2 − 4x − 4 x3 − 6 x2 −7 x − 8 but with approximately the same order. The basis for such a So, to determine the isogeny, it is necessary to perform the check you can take the field GF(2999). The calculations you operations of addition, multiplication and inverse element can make using the Maple 2017 package [9]. The relative calculation in the Galois field GF(p2). times of execution of such number of multiplications with IV. ESTIMATION OF THE SOFTWARE TIME respect to the time of execution of the same number of COMPLEXITY OF OPERATIONS IN THE GALOIS operations in the binary field GF(2999) are shown Table 1 and in the Fig. 1 where prime p≈2999 is characteristic of prime FIELDS GF(p). In works [11] and [12], the evaluation of the ability of data protection means to counteract attacks by hackers was carried out. The definition of Galois field in which hackers work Relative Multiplication Time 1,60 1,40 1,20 1,00 0,80 0,60 0,40 0,20 Field Characteristic 0,00 2 3 5 7 11 13 17 19 23 29 768 p Fig. 1. Relative time complexity of software multiplying in a different fields. third after multiplication complexities in fields with The relative time complexity was determined by the ratio characteristics 3 and 5. Therefore, the following study will of the multiplication time in the field GF(dm) to the focus on binary fields. multiplication time in the field GF(2999). Software multiplication in fields with characteristic 768 As can be seen from the Table 1, software multiplication of which is used in [3] is performed for 10 times faster than in triple extended field elements has the longest execution time. binary fields. Therefore, this system can be hacked using It provides hardware cryptoprocessors based on such fields classic computers faster than the system that uses binary additional protection against hacking. Software-implemented fields. operations on simple field elements are executed in the fastest way, that indicates the inappropriateness of cryptographic processors based on such fields. Multiplication in binary fields has one of the highest time complexity, it is ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic 238 V. ESTIMATION OF THE HARDWARE TIME TABLE 1. THE RELATIVE TIME COMPLEXITY OF COMPLEXITY OF OPERATIONS IN THE GALOIS MULTIPLICATION IN EXTENDED FIELD OF DIFFERENT FIELDS CHARACTERISTICS Implemented in modern FPGA hardware multipliers for Field Characteristic Relative Time extended Galois field GF (dm) with approximately the same 2 1,00 number of elements dm ≈ 2n were estimated in [13] in terms 3 of their time complexity to determine the fields in which the 1,46 multiplier will have the least time complexity. Relative to 5 1,18 GF(2n) results of estimation is shown in Fig. 2. 7 0,84 11 0,59 VI. ESTIMATION OF THE SOFTWARE- 13 HARDWARE TIME COMPLEXITY OF 0,53 17 OPERATIONS IN THE GALOIS FIELDS 0,45 We will assume that the hardware implementation is used 19 0,42 by users of data protection tools, and software is used by 23 hackers. Then we can introduce a generalized time 0,38 complexity index. We will calculate this indicator as the ratio 29 0,33 of software time complexity to hardware time complexity for … the same fields. When the value of this indicator is greater, … 768 then hackers will have more problems, so data protection will 0,11 be better. p 0,03 Relative time complexity 3 Relative time complexit 2,5 2 1,5 1 0,5 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 GF characteristic d Fig. 2. Relative time complexity of hardware multipliers in different fields. Results of hardware-software complexity estimation is hardware tools to work in the field with the characteristic 768 shown in Fig. 3. [3] also has less effect than for working in binary and ternary As can be seen from Fig. 3, the trial and binary Galois fields. fields provide the best data protection. Fields with large The use of isogenies of supersingular elliptic curves is characteristics provide weaker protection. The use of oriented toward usage of Galois field with big characteristics, hardware tools for working in such fields has less effect than so they are focused on software implementation. for working in binary and trial fields. As result the use of ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic 239 Relative HS-Comlexity 2,5 2 1,5 1 0,5 Field Characteristic 0 2 3 5 7 11 13 17 19 Fig. 3. Relative hardware-software time complexity of multipliers in different fields. Supersingular Isogeny Diffie-Hellman Key Exchange V. CONCLUSION on FPGA" The use of isogenies of supersingular elliptic curves is [7] Jean Vélu. Isogénies entre courbes elliptiques. Comptes oriented toward software implementation of the method. Rendus de l’Académie des Sciences de Paris, 273:238– Hardware implementation of this method will not provide 241, 1971. such a reduction in time complexity and increase the degree [8] SIKE protocol and its stability to classical and quantum of data protection as it provides in methods oriented on attacks. binary fields. https://www.ruscrypto.ru/resource/archive/rc2018/files/ 02_Taraskin.pdf REFERENCES [9] Password cracking. [1] Quantum-safe cryptography. https://en.wikipedia.org/wiki/Password_cracking. http://www.etsi.org/technologies- [10] Maple User Manual. Copyright © Maplesoft, a division clusters/technologies/quantum-safe-cryptography of Waterloo Maple Inc. 2017. [2] Supersingular isogeny key exchange. http: [11] Hlukhov, V., Zholubak, I., Kostyk, A., Rahma https://en.wikipedia.org/wiki/Supersingular_isogeny_ke M. (2017), Galois Fields Elements Processing Units for y_exchange Cryptographic Data Protection in Cyber-Physical [3] De Feo, Luca; Jao, Plut. "Towards quantum-resistant Systems. Advances in Cyber-Physical Systems. Volume cryptosystems from supersingular elliptic curve II, Number 2, 2017. © Lviv Polytechnic National isogenies" (PDF). PQCrypto 2011. Springer. Retrieved4 University, pp. 9-18, in press. May 2014. [12] Rodrigue Elias, Valerii Hlukhov, Mohammed Rahma, [4] Fishbein, Dieter (30 April 2014). "Machine-Level Ivan Zholubak. FPGA cores for fast multiplicative Software Optimization of Cryptographic inverse calculation in Galois Fields. 9th International Protocols". University of Waterloo Library - Electronic IEEE Conference Dependable Systems, Services and Theses. University of Waterloo. Retrieved 21 Technologies DESSERT’2018 UKRAINE, KYIV, MAY June 2014. 24-27, 2018, in press. [5] Costello, Craig; Longa, Patrick; Naehrig, Michael [13] R. Elias, M. Rahma, V. Hlukhov. Multipliers for Galois (2016-01-01). "Efficient algorithms for supersingular fields Time Complexity. ELECTROTECHNIC AND isogeny Diffie-Hellman" COMPUTER SYSTEMS. Science and Technical. [6] Koziel, Brian; Kermani, Mehran; Azarderakhsh, Reza Odessa, No. 22 (98) 2016. Pp. 323-327 (In Ukrainian) (2016-11-07). "Fast Hardware Architectures for ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic